MDS array codes with low disk I/O and small repair bandwidth

Abstract

Erasure codes are being widely implemented in distributed storage systems to achieve fault tolerance with high storage efficiency. Reed-Solomon code is commonly deployed in data centers due to its optimal storage efficiency, but it requires massive bandwidth for node repair. Minimum Storage Regenerating code (MSR) and Locally Repairable (LR) code are proposed to reduce repair bandwidth, which is defined as the amount of data communicated during node repair. However, MSR code usually carries a heavy disk I/O burden and LR code is not optimal in storage efficiency. In this paper, we take disk I/O, storage efficiency, repair bandwidth and sub-packetization level into consideration together, and propose novel constructions of maximum distance separable array codes with low disk I/O, reduced repair bandwidth and very small sub-packetization level of l=\mathcal{O}(r). We focus on the repair of systematic nodes since they are more likely to fail than parity nodes. Specifically, the proposed codes achieve the cut-set bound on repair bandwidth for systematic nodes when the code rate \frac{k}{n}=\frac{1}{2}, and for \frac{k}{n}>\frac{1}{2}, the repair bandwidth is less than twice of the cut-set bound. Compared with new advanced piggybacking codes, the proposed codes obtain a significant reduction on repair bandwidth for systematic nodes while also consuming less disk I/Os. In terms of average repair bandwidth of all nodes, the proposed codes are intuitively better than the existing advanced piggybacking codes.

Graphical abstract

Keywords

distributed storage systems / low disk I/O / repair bandwidth / degraded read / small sub-packetization level

References

[1] Ghemawat S, Gobioff H, Leung S T. The Google file system. In: Proceedings of the 19th ACM Symposium on Operating Systems Principles. 2003, 29–43

[2] Shvachko K, Kuang H, Radia S, Chansler R. The Hadoop distributed file system. In: Proceedings of the 26th IEEE Symposium on Mass Storage Systems and Technologies. 2010, 1–10

[3] Huang C, Simitci H, Xu Y, Ogus A, Calder B, Gopalan P, Li J, Yekhanin S. Erasure coding in windows azure storage. In: Proceedings of 2012 USENIX conference on Annual Technical Conference. 2012, 15–26

[4] MacWilliams F J, Sloane N J A. The Theory of Error-Correcting Codes. Amsterdam: Elsevier, 1977

[5] Reed I S, Solomon G . Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 1960, 8( 2): 300–304

[6] Dimakis A G, Godfrey P B, Wu Y, Wainwright M J, Ramchandran K . Network coding for distributed storage systems. IEEE Transactions on Information Theory, 2010, 56( 9): 4539–4551

[7] Rashmi K V, Shah N B, Gu D, Kuang H, Borthakur D, Ramchandran K. A solution to the network challenges of data recovery in erasure-coded distributed storage systems: a study on the Facebook warehouse cluster. In: Proceedings of the 5th USENIX Conference on Hot Topics in Storage and File Systems. 2013

[8] Balaji S B, Krishnan M N, Vajha M, Ramkumar V, Sasidharan B, Kumar P V . Erasure coding for distributed storage: an overview. Science China Information Sciences, 2018, 61( 10): 100301

[9] Wu Y . Existence and construction of capacity-achieving network codes for distributed storage. IEEE Journal on Selected Areas in Communications, 2010, 28( 2): 277–288

[10] Wu Y, Dimakis A G. Reducing repair traffic for erasure coding-based storage via interference alignment. In: Proceedings of 2009 IEEE International Symposium on Information Theory. 2009, 2276–2280

[11] Rashmi K V, Shah N B, Kumar P V, Ramchandran K. Explicit construction of optimal exact regenerating codes for distributed storage. In: Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing. 2009, 1243–1249

[12] Suh C, Ramchandran K. Exact-repair MDS codes for distributed storage using interference alignment. In: Proceedings of 2010 IEEE International Symposium on Information Theory. 2010, 161–165

[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 Transactions on Information Theory, 2011, 57( 8): 5227–5239

[14] Cadambe V R, Jafar S A, Maleki H, Ramchandran K, Suh C . Asymptotic interference alignment for optimal repair of MDS codes in distributed storage. IEEE Transactions on Information Theory, 2013, 59( 5): 2974–2987

[15] Cadambe V R, Huang C, Li J. Permutation code: optimal exact-repair of a single failed node in MDS code based distributed storage systems. In: Proceedings of 2011 IEEE International Symposium on Information Theory Proceedings. 2011, 1225–1229

[16] Tamo I, Wang Z, Bruck J . Zigzag codes: MDS array codes with optimal rebuilding. IEEE Transactions on Information Theory, 2013, 59( 3): 1597–1616

[17] Tamo I, Wang Z, Bruck J . Access versus bandwidth in codes for storage. IEEE Transactions on Information Theory, 2014, 60( 4): 2028–2037

[18] Sasidharan B, Agarwal G K, Kumar P V. A high-rate MSR code with polynomial sub-packetization level. In: Proceedings of 2015 IEEE International Symposium on Information Theory. 2015, 2051–2055

[19] Rawat A S, Koyluoglu O O, Vishwanath S. Progress on high-rate MSR codes: enabling arbitrary number of helper nodes. In: Proceedings of 2016 Information Theory and Applications Workshop. 2016, 1–6

[20] Ye M, Barg A . Explicit constructions of high-rate MDS array codes with optimal repair bandwidth. IEEE Transactions on Information Theory, 2017, 63( 4): 2001–2014

[21] Ye M, Barg A . Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization. IEEE Transactions on Information Theory, 2017, 63( 10): 6307–6317

[22] Balaji S B, Vajha M, Kumar P V . Lower bounds on the sub-packetization level of MSR codes and characterizing optimal-access MSR codes achieving the bound. IEEE Transactions on Information Theory, 2022, 68( 10): 6452–6471

[23] Sasidharan B, Vajha M, Kumar P V. An explicit, coupled-layer construction of a high-rate MSR code with low sub-packetization level, small field size and d<(n-1). In: Proceedings of 2017 IEEE International Symposium on Information Theory. 2017, 2048–2052

[24] Li J, Tang X, Tian C . A generic transformation to enable optimal repair in MDS codes for distributed storage systems. IEEE Transactions on Information Theory, 2018, 64( 9): 6257–6267

[25] Vajha M, Balaji S, Kumar P V . Small-d MSR codes with optimal access, optimal sub-packetization, and linear field size. IEEE Transactions on Information Theory, 2023, 69( 7): 4303–4332

[26] Vajha M, Ramkumar V, Puranik B, Kini G, Lobo E, Sasidharan B, Kumar P V, Barg A, Ye M, Narayanamurthy S, Hussain S, Nandi S. Clay codes: moulding MDS codes to yield an MSR code. In: Proceedings of the 16th USENIX Conference on File and Storage Technologies. 2018, 139–154

[27] Li C, Feng D, Hua Y, Wang F . A high-performance and endurable SSD cache for parity-based RAID. Frontiers of Computer Science, 2019, 13( 1): 16–34

[28] Pamies-Juarez L, Blagojevic F, Mateescu R, Gyuot C, En Gad E, Bandic Z. Opening the chrysalis: on the real repair performance of MSR codes. In: Proceedings of the 14th USENIX Conference on File and Storage Technologies. 2016, 81–94

[29] Kralevska K, Gligoroski D, Jensen R E, Øverby H . Hashtag erasure codes: from theory to practice. IEEE Transactions on Big Data, 2018, 4( 4): 516–529

[30] Rashmi K V, Shah N B, Ramchandran K . A piggybacking design framework for read-and download-efficient distributed storage codes. IEEE Transactions on Information Theory, 2017, 63( 9): 5802–5820

[31] Sun R, Zhang L, Liu J . A new piggybacking design with low-repair bandwidth and complexity. IEEE Communications Letters, 2021, 25( 7): 2099–2103

[32] Shi H, Hou H, Han Y S, Lee P P C, Jiang Z, Huang Z, Bai B. New piggybacking codes with lower repair bandwidth for any single-node failure. In: Proceedings of 2022 IEEE International Symposium on Information Theory. 2022, 2601–2606

[33] Wu T Y, Han Y S, Li Z, Bai B, Zhang G, Zhang X, Wu X. Achievable lower bound on the optimal access bandwidth of (K + 2, K, 2)-MDS array code with degraded read friendly. In: Proceedings of 2021 IEEE Information Theory Workshop. 2021, 1–5

[34] Guruswami V, Wootters M. Repairing reed-Solomon codes. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing. 2016, 216–226

[35] Tamo I, Ye M, Barg A. Optimal repair of Reed-Solomon codes: achieving the cut-set bound. In: Proceedings of the 58th Annual Symposium on Foundations of Computer Science. 2017, 216–227

[36] Con R, Tamo I . Nonlinear repair of Reed-Solomon codes. IEEE Transactions on Information Theory, 2022, 68( 8): 5165–5177

[37] Li J, Liu Y, Tang X . A systematic construction of MDS codes with small sub-packetization level and near-optimal repair bandwidth. IEEE Transactions on Information Theory, 2021, 67( 4): 2162–2180

[38] Rawat A S, Tamo I, Guruswami V, Efremenko K. MDS code constructions with small sub-packetization and near-optimal repair bandwidth. IEEE Transactions on Information Theory, 2018, 64(10): 6506–6525

[39] Li L, Ying C, Yu X, Chen L, Dong Y, Luo Y. Constructing MDS array codes with small repair bandwidth under sub-packetization two. In: Proceedings of 2023 International Conference on Wireless Communications and Signal Processing. 2023, 293–298

[40] Tang K, Cheng K, Chan H H W, Li X, Lee P P C, Hu Y, Li J, Wu T Y. Balancing repair bandwidth and sub-packetization in erasure-coded storage via elastic transformation. In: Proceedings of the IEEE INFOCOM 2023-IEEE Conference on Computer Communications. 2023, 1–10

RIGHTS & PERMISSIONS

Higher Education Press