# American Institute of Mathematical Sciences

August  2018, 12(3): 465-503. doi: 10.3934/amc.2018028

## Architecture-aware coding for distributed storage: Repairable block failure resilient codes

 1 Western Digital, San Jose, CA 95119, USA 2 UC Berkeley, Berkeley CA 94720, USA

* Corresponding author: Gokhan Calis

Received  February 2017 Revised  November 2017 Published  July 2018

Fund Project: G. Calis is with Western Digital Corporation, San Jose, CA 95119. O. Ozan Koyluoglu is with University of California, Berkeley, CA 94720. The paper was submitted when both authors were with Department of Electrical and Computer Engineering, University of Arizona, Tucson, AZ 85712. This paper was in part presented at 2014 IEEE International Symposium on Information Theory (ISIT 2014), Honolulu, HI, June 2014. This work is supported in part by the National Science Foundation under Grants No CCF-1563622 and CNS-1617335.

In large scale distributed storage systems (DSS) deployed in cloud computing, correlated failures resulting in simultaneous failure (or, unavailability) of blocks of nodes are common. In such scenarios, the stored data or a content of a failed node can only be reconstructed from the available live nodes belonging to the available blocks. To analyze the resilience of the system against such block failures, this work introduces the framework of Block Failure Resilient (BFR) codes, wherein the data (e.g., a file in DSS) can be decoded by reading out from a same number of codeword symbols (nodes) from a subset of available blocks of the underlying codeword. Further, repairable BFR codes are introduced, wherein any codeword symbol in a failed block can be repaired by contacting a subset of remaining blocks in the system. File size bounds for repairable BFR codes are derived, and the trade-off between per node storage and repair bandwidth is analyzed, and the corresponding minimum storage regenerating (BFR-MSR) and minimum bandwidth regenerating (BFR-MBR) points are derived. Explicit codes achieving the two operating points for a special case of parameters are constructed, wherein the underlying regenerating codewords are distributed to BFR codeword symbols according to combinatorial designs. Finally, BFR locally repairable codes (BFR-LRC) are introduced, an upper bound on the resilience is derived and optimal code construction are provided by a concatenation of Gabidulin and MDS codes. Repair efficiency of BFR-LRC is further studied via the use of BFR-MSR/MBR codes as local codes. Code constructions achieving optimal resilience for BFR-MSR/MBR-LRCs are provided for certain parameter regimes. Overall, this work introduces the framework of block failures along with optimal code constructions, and the study of architecture-aware coding for distributed storage systems.

Citation: Gokhan Calis, O. Ozan Koyluoglu. Architecture-aware coding for distributed storage: Repairable block failure resilient codes. Advances in Mathematics of Communications, 2018, 12 (3) : 465-503. doi: 10.3934/amc.2018028
##### References:

show all references

##### References:
A data-center architecture where top-of-rack (TOR) switch of the first rack fails
(a) Node repair in regenerating codes. (b) Node repair in relaxation of regenerating codes. (c) Trade-off curves in toy example.
Repair process for $b = 2$ (two blocks) case
(a) Ratio $\frac{\gamma^{\textrm{k-odd}}_{\textrm{BFR-MSR}}}{\gamma_{\textrm{MBR}}}$ vs. $d$. (b) Ratio $\frac{\gamma^{\textrm{k-even}}_{\textrm{BFR-MSR}}}{\gamma_{\textrm{MBR}}}$ vs. $d$
Transpose code is a two-block BFR-MBR code
(a) Matrix representation of block design. (b) Threeblock BFR-RC
Illustrating the construction of BFR codes using projective plane based placement of regenerating codes. ($n' = \tilde{n}-\frac{\tilde{n}}{r}+1.)$
Data center architecture. Each rack resembles a block and each cluster forms a local group for node repair operations in the BFR model
when zoomed in">Figure 9.  Repair delay vs. storage overhead comparisons for $b = 7$, $n = 21$ and $\sigma = 3$. (a) Data points for possible cases of each node. (b) Lower envelope of Fig. 9a when zoomed in
Repair delay vs. storage overhead comparisons for $b = 7$ and $\sigma = 3$, (a) when $n = 21$, (b) when $n = 35$
Construction of a set $\mathcal{B}^*$ with $H(\mathbf{c}(\mathcal{B}^*)) <\mathcal{M}$ for BFR-LRC
Summary of the contributions
 Characterization of BFR points $d_r \geq k_c$ and $\sigma <\rho$ Section 3.1.1 Characterization of BFR points $d_r \geq k_c$ and $\sigma \geq \rho$ Section 3.1.2 Characterization of BFR points $d_r < k_c$ and $\sigma < \rho$ Section 3.2 BFR codes $b=2$, $d_r \geq k_c$, $\sigma=1$ and $\rho=0$ Section 4.1 BFR codes $d_r \geq k_c$, $\sigma=1$ and $\rho=0$ Section 4.2 BFR codes $d_r \geq k_c$, $\sigma < b-1$ and $\rho = 0$ Section 4.3 BFR-LRC and code constructions resilience $\rho$ Section 5.1, 5.2 Local regeneration in BFR-LRC $d_r \geq k_c$, $\sigma < b-1$ and $\rho_L = 0$2 Section 5.3 Relaxed BFR any set of parameters Section 6.2
 Characterization of BFR points $d_r \geq k_c$ and $\sigma <\rho$ Section 3.1.1 Characterization of BFR points $d_r \geq k_c$ and $\sigma \geq \rho$ Section 3.1.2 Characterization of BFR points $d_r < k_c$ and $\sigma < \rho$ Section 3.2 BFR codes $b=2$, $d_r \geq k_c$, $\sigma=1$ and $\rho=0$ Section 4.1 BFR codes $d_r \geq k_c$, $\sigma=1$ and $\rho=0$ Section 4.2 BFR codes $d_r \geq k_c$, $\sigma < b-1$ and $\rho = 0$ Section 4.3 BFR-LRC and code constructions resilience $\rho$ Section 5.1, 5.2 Local regeneration in BFR-LRC $d_r \geq k_c$, $\sigma < b-1$ and $\rho_L = 0$2 Section 5.3 Relaxed BFR any set of parameters Section 6.2
 [1] Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024 [2] Shiqiu Liu, Frédérique Oggier. On applications of orbit codes to storage. Advances in Mathematics of Communications, 2016, 10 (1) : 113-130. doi: 10.3934/amc.2016.10.113 [3] Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87 [4] Horst R. Thieme. Distributed susceptibility: A challenge to persistence theory in infectious disease models. Discrete & Continuous Dynamical Systems - B, 2009, 12 (4) : 865-882. doi: 10.3934/dcdsb.2009.12.865 [5] Hans-Joachim Kroll, Sayed-Ghahreman Taherian, Rita Vincenti. Optimal antiblocking systems of information sets for the binary codes related to triangular graphs. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020107 [6] Finley Freibert. The classification of complementary information set codes of lengths $14$ and $16$. Advances in Mathematics of Communications, 2013, 7 (3) : 267-278. doi: 10.3934/amc.2013.7.267 [7] Leonid Faybusovich, Cunlu Zhou. Long-step path-following algorithm for quantum information theory: Some numerical aspects and applications. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021017 [8] W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 [9] David Grant, Mahesh K. Varanasi. Duality theory for space-time codes over finite fields. Advances in Mathematics of Communications, 2008, 2 (1) : 35-54. doi: 10.3934/amc.2008.2.35 [10] Tomáš Roubíček, Giuseppe Tomassetti. Thermomechanics of hydrogen storage in metallic hydrides: Modeling and analysis. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 2313-2333. doi: 10.3934/dcdsb.2014.19.2313 [11] Phil Howlett, Julia Piantadosi, Paraskevi Thomas. Management of water storage in two connected dams. Journal of Industrial & Management Optimization, 2007, 3 (2) : 279-292. doi: 10.3934/jimo.2007.3.279 [12] Sze-Bi Hsu, Junping Shi, Feng-Bin Wang. Further studies of a reaction-diffusion system for an unstirred chemostat with internal storage. Discrete & Continuous Dynamical Systems - B, 2014, 19 (10) : 3169-3189. doi: 10.3934/dcdsb.2014.19.3169 [13] Sze-Bi Hsu, Chiu-Ju Lin. Dynamics of two phytoplankton species competing for light and nutrient with internal storage. Discrete & Continuous Dynamical Systems - S, 2014, 7 (6) : 1259-1285. doi: 10.3934/dcdss.2014.7.1259 [14] Lisa C Flatley, Robert S MacKay, Michael Waterson. Optimal strategies for operating energy storage in an arbitrage or smoothing market. Journal of Dynamics & Games, 2016, 3 (4) : 371-398. doi: 10.3934/jdg.2016020 [15] Patrice Bertail, Stéphan Clémençon, Jessica Tressou. A storage model with random release rate for modeling exposure to food contaminants. Mathematical Biosciences & Engineering, 2008, 5 (1) : 35-60. doi: 10.3934/mbe.2008.5.35 [16] Linfeng Mei, Sze-Bi Hsu, Feng-Bin Wang. Growth of single phytoplankton species with internal storage in a water column. Discrete & Continuous Dynamical Systems - B, 2016, 21 (2) : 607-620. doi: 10.3934/dcdsb.2016.21.607 [17] Hua Nie, Sze-Bi Hsu, Feng-Bin Wang. Global dynamics of a reaction-diffusion system with intraguild predation and internal storage. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 877-901. doi: 10.3934/dcdsb.2019194 [18] Rui Wang, Denghua Zhong, Yuankun Zhang, Jia Yu, Mingchao Li. A multidimensional information model for managing construction information. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1285-1300. doi: 10.3934/jimo.2015.11.1285 [19] Vikram Krishnamurthy, William Hoiles. Information diffusion in social sensing. Numerical Algebra, Control & Optimization, 2016, 6 (3) : 365-411. doi: 10.3934/naco.2016017 [20] Subrata Dasgupta. Disentangling data, information and knowledge. Big Data & Information Analytics, 2016, 1 (4) : 377-389. doi: 10.3934/bdia.2016016

2020 Impact Factor: 0.935