logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 10: 100302(2018) https://doi.org/10.1007/s11432-018-9485-7

A class of binary MDS array codes with asymptotically weak-optimal repair$^\dagger$

More info
  • ReceivedMar 11, 2018
  • AcceptedJun 12, 2018
  • PublishedAug 15, 2018

Abstract

Binary maximum distance separable (MDS) array codes contain $k$ information columns and $r$ parity columns in which each entry is a bit that can tolerate $r$ arbitrary erasures. When a column in an MDS code fails, it has been proven that we must download at least half of the content from each helper column if $k+1$ columns are selected as the helper columns. If the lower bound is achieved such that the $k+1$ helper columns can be selected from any $k+r-1$ surviving columns, then the repair is an optimal repair. Otherwise, if the lower bound is achieved with $k+1$ specific helper columns, the repair is a weak-optimal repair. This paper proposes a class of binary MDS array codes with $k\geq~3$ and $r\geq~2$ that asymptotically achieve weak-optimal repair of an information column with $k+1$ helper columns. We show that there exist many encoding matrices such that the corresponding binary MDS array codes can asymptotically achieve weak-optimal repair for repairing any information column.


Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant Nos. 61701115, 61671007).


References

[1] Blaum M, Brady J, Bruck J. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures. IEEE Trans Comput, 1995, 44: 192-202 CrossRef Google Scholar

[2] Corbett P, English B, Goel A, et al. Row-diagonal parity for double disk failure correction. In: Proceedings of the 3rd USENIX Conference on File and Storage Technologies, San Jose, 2004. 1--14. Google Scholar

[3] Huang C, Xu L. STAR: an efficient coding scheme for correcting triple storage node failures. IEEE Trans Comput, 2008, 57: 889-901 CrossRef Google Scholar

[4] Blaum M. A family of MDS array codes with minimal number of encoding operations. In: Proceedings of IEEE International Symposium on Information Theory, Seattle, 2006. 2784--2788. Google Scholar

[5] Blaum M, Brady J, Bruck J, et al. The EVENODD code and its generalization. In: Proceedings of High Performance Mass Storage and Parallel I/O. Hoboken: John Wiley & Sons, Inc., 2001. 187--208. Google Scholar

[6] Blaum M, Bruck J, Vardy A. MDS array codes with independent parity symbols. IEEE Trans Inform Theor, 1996, 42: 529-542 CrossRef Google Scholar

[7] Feng G-L, Deng R-H, Bao F, et al. New efficient MDS array codes for RAID Part II Rabin-like codes for tolerating multiple (= 4) disk failures. IEEE Trans Comput, 2005, 54: 1473--1483. Google Scholar

[8] Hou H, Han Y S. A New Construction and an Efficient Decoding Method for Rabin-Like Codes. IEEE Trans Commun, 2018, 66: 521-533 CrossRef Google Scholar

[9] Dimakis A G, Godfrey P B, Wu Y. Network Coding for Distributed Storage Systems. IEEE Trans Inform Theor, 2010, 56: 4539-4551 CrossRef Google Scholar

[10] Hou H X, Han Y-S, Lee P-P-C, et al. A new design of binary MDS array codes with asymptotically weak-optimal repair. 2018,. arXiv Google Scholar

[11] Hou H, Shum K W, Chen M. BASIC Codes: Low-Complexity Regenerating Codes for Distributed Storage Systems. IEEE Trans Inform Theor, 2016, 62: 3053-3069 CrossRef Google Scholar

[12] Li J, Tang X H, Tian C. A generic transformation for optimal repair bandwidth and rebuilding access in MDS codes. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Aachen, 2017. 1623--1627. Google Scholar

[13] Rashmi K V, Shah N B, Kumar P V. Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction. IEEE Trans Inform Theor, 2011, 57: 5227-5239 CrossRef Google Scholar

[14] Tamo I, Wang Z, Bruck J. Zigzag Codes: MDS Array Codes With Optimal Rebuilding. IEEE Trans Inform Theor, 2013, 59: 1597-1616 CrossRef Google Scholar

[15] Ye M, Barg A. Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth. IEEE Trans Inform Theor, 2017, 63: 2001-2014 CrossRef Google Scholar

[16] Gad E-E, Mateescu R, Blagojevic F, et al. Repair-optimal MDS array codes over GF(2). In: Proceedings of IEEE International Symposium Information Theory, Istanbul, 2013. 887--891. Google Scholar

[17] Pamies J-L, Blagojevic F, Mateescu R, et al. Opening the chrysalis: on the real repair performance of MSR codes. In: Proceedings of 14th USENIX Conference on File and Storage Technologies, Santa Clara, 2016. 81--94. Google Scholar

[18] Hou H, Lee P-P-C, Han Y-S, et al. Triple-fault-tolerant binary MDS array codes with asymptotically optimal repair. In: Proceedings of IEEE International Symposium Information Theory, Aachen, 2017. 839--843. Google Scholar

[19] Wang Y, Yin X, Wang X. MDR Codes: A New Class of RAID-6 Codes with Optimal Rebuilding and Encoding. IEEE J Sel Areas Commun, 2014, 32: 1008-1018 CrossRef Google Scholar

[20] Wang Y, Yin X, Wang X. Two new classes of two-parity MDS array codes with optimal repair. IEEE Commun Lett, 2016, 20: 1293--1296. Google Scholar

[21] Xiang L, Xu Y, Lui J, et al. Optimal recovery of single disk failure in RDP code storage systems. In: Proceedings of ACM SIGMETRICS Performance Evaluation Rev, New York, 2010. 119--130. Google Scholar

[22] Xu S, Li R, Lee P P C. Single Disk Failure Recovery for X-Code-Based Parallel Storage Systems. IEEE Trans Comput, 2014, 63: 995-1007 CrossRef Google Scholar

[23] Wang Z Y, Dimakis A-G, Bruck J. Rebuilding for array codes in distributed storage systems. In: Proceedings of GLOBECOM Workshops, Miami, 2010. 1905--1909. Google Scholar

  • Table 1   An example of the code with $k=3,r=3,p=3$, and $\tau=4$, where ${\boldsymbol~a}_{8,j}=a_{0,j}+a_{4,j}$, ${\boldsymbol~a}_{9,j}=a_{1,j}+a_{5,j}$, ${\boldsymbol~a}_{10,j}=a_{2,j}+a_{6,j}$, and ${\boldsymbol~a}_{11,j}=a_{3,j}+a_{7,j}$ for $j=1,2,\ldots,6$
    Column 1 Column 2 Column 3 Column 4 Column 5 Column 6
    $a_{0,1}$ $a_{0,2}$ $a_{0,3}$ $a_{0,4}=a_{0,1}+a_{0,2}+a_{0,3}$ $a_{0,5}={\boldsymbol~a}_{11,1}+{\boldsymbol~a}_{10,2}+{\boldsymbol~a}_{8,3}$ $a_{0,6}={\boldsymbol~a}_{8,1}+{\boldsymbol~a}_{11,2}+{\boldsymbol~a}_{10,3}$
    $a_{1,1}$ $a_{1,2}$ $a_{1,3}$ $a_{1,4}=a_{1,1}+a_{1,2}+a_{1,3}$ $a_{1,5}=a_{0,1}+{\boldsymbol~a}_{11,2}+{\boldsymbol~a}_{9,3}$ $a_{1,6}={\boldsymbol~a}_{9,1}+a_{0,2}+{\boldsymbol~a}_{11,3}$
    $a_{2,1}$ $a_{2,2}$ $a_{2,3}$ $a_{2,4}=a_{2,1}+a_{2,2}+a_{2,3}$ $a_{2,5}=a_{1,1}+a_{0,2}+{\boldsymbol~a}_{10,3}$ $a_{2,6}={\boldsymbol~a}_{10,1}+a_{1,2}+a_{0,3}$
    $a_{3,1}$ $a_{3,2}$ $a_{3,3}$ $a_{3,4}=a_{3,1}+a_{3,2}+a_{3,3}$ $a_{3,5}=a_{2,1}+a_{1,2}+{\boldsymbol~a}_{11,3}$ $a_{3,6}={\boldsymbol~a}_{11,1}+a_{2,2}+a_{1,3}$
    $a_{4,1}$ $a_{4,2}$ $a_{4,3}$ $a_{4,4}=a_{4,1}+a_{4,2}+a_{4,3}$ $a_{4,5}=a_{3,1}+a_{2,2}+a_{0,3}$ $a_{4,6}=a_{0,1}+a_{3,2}+a_{2,3}$
    $a_{5,1}$ $a_{5,2}$ $a_{5,3}$ $a_{5,4}=a_{5,1}+a_{5,2}+a_{5,3}$ $a_{5,5}=a_{4,1}+a_{3,2}+a_{1,3}$ $a_{5,6}=a_{1,1}+a_{4,2}+a_{3,3}$
    $a_{6,1}$ $a_{6,2}$ $a_{6,3}$ $a_{6,4}=a_{6,1}+a_{6,2}+a_{6,3}$ $a_{6,5}=a_{5,1}+a_{4,2}+a_{2,3}$ $a_{6,6}=a_{2,1}+a_{5,2}+a_{4,3}$
    $a_{7,1}$ $a_{7,2}$ $a_{7,3}$ $a_{7,4}=a_{7,1}+a_{7,2}+a_{7,3}$ $a_{7,5}=a_{6,1}+a_{5,2}+a_{3,3}$ $a_{7,6}=a_{3,1}+a_{6,2}+a_{5,3}$
  •   

    Algorithm 1 Algorithm for repairing the failure of a single information column

    The information column $f$ fails.

    if $f\in\{1,~2,\ldots,~(r-2)\lfloor~\frac{k}{r-1}\rfloor\}$ then

    Repair the bit $a_{\ell,f}$ using the first encoding column, for $\ell~\mod~2e_{1+(f-1~\boldsymbolod~\lfloor~\frac{k}{r-1}\rfloor)~}~\in~\{0,1,\ldots,e_{1+(f-1~\boldsymbolod~\lfloor~\frac{k}{r-1}\rfloor)}-1\}$. Otherwise, repair the bit $a_{\ell,f}$ using the encoding column $1+\lceil\frac{f}~{\lfloor~\frac{k}{r-1}\rfloor}\rceil$, for $\ell~\mod~2e_{1+(f-1~\boldsymbolod~\lfloor~\frac{k}{r-1}\rfloor)}~\in~\{e_{1+(f-1~\boldsymbolod~\lfloor~\frac{k}{r-1}\rfloor)},\ldots,2e_{1+(f-1~\boldsymbolod~\lfloor~\frac{k}{r-1}\rfloor)}-1\}$.

    end if

    return

    if $f\in\{(r-2)\lfloor~\frac{k}{r-1}\rfloor+1,\ldots,k\}$ then

    Repair the bit $a_{\ell,f}$ using the first parity, for $\ell~\mod~2e_{f-(r-2)\lfloor~\frac{k}{r-1}\rfloor}~\in~\{0,1,\ldots,e_{f-(r-2)\lfloor~\frac{k}{r-1}\rfloor-1}\}$. Otherwise, repair the bit $a_{\ell,f}$ using the encoding column $r$, for $\ell~\mod~2e_{f-(r-2)\lfloor~\frac{k}{r-1}\rfloor}~\in~\{e_{f-(r-2)\lfloor~\frac{k}{r-1}\rfloor},\ldots,2e_{f-(r-2)\lfloor~\frac{k}{r-1}\rfloor}-1\}$.

    end if

    return

  • Table 2   Comparison of binary MDS array codes
    Code Repair bandwidth Number of helper columns $d$ Number of parity columns $r$
    ButterFly code [18,19] Optimal $k+1$ 2
    MDR code [16,17] Optimal $k+1$ 2
    Code in [20] Asymptotically weak-optimal $k+1$ 3
    Code-I in [10] Asymptotically weak-optimal $k+\frac{r-1}{2}$ $r\geq~3$ is odd
    Code-II in [10] Asymptotically weak-optimal $k+\frac{r}{2}$ $r\geq~4$ is even
    Proposed code Asymptotically weak-optimal $k+1$ $r\geq~2$

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1