MDS阵列码是一类比较特殊的线性分组码。阵列码相对于RS码避免了有限域计算,仅通过异或运算实现纠删码。在这类码中,符号均为m维的列向量,从而每个码字都是一个m*n的二维阵列。绝大部分的阵列码都是二元阵列码,阵列码的每一列可以全是数据位也可以既有数据位也有校验位。以下为一个m=2, n = 5, k = 3的阵列码的示意图:
其中,A,B是2^(k-2) * (k-1)的bit矩阵,a,b则是一个包含2^(k-2)个元素的列向量。如果把 butterfly编码后的码字记为:Ck = (Dk−1 k ,...,D0 k ,H,B),则不难看出,H,B分别带为butterfly后的一个水平校验列和butterfly校验列。H,B的生成遵循如下递归准则:
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
Plank J S, Ding Y. Note: Correction to the 1997 tutorial on Reed-Solomon coding.Software: Practice and Experience, 2005, 35(2):189-194
Shokrollahi A. LDPC codes: An Introduction. Technical report, 2003.
Blaum M, Brady J, Bruck J, et al. EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures. IEEE Transactions on computers (TOC), 1995, 44(2):192-202.
Corbett P, English B, Goel A, et al. Row-diagonal Parity for Double Disk Failure Correction. in: Proceedings of The 2nd USENIX Conference on File and Storage Technologies (FAST'04), Berkeley, CA, USA, March 31 - April 2, 2004, 1-14.
Huang C, Xu L. STAR: An Efficient Coding Scheme for Correcting Triple Storage Node Failures. IEEE Transactions on Computers (TOC), 2008, 57(7):889-901.
James S. Plank: The RAID-6 Liberation Codes. FAST 2008: 97-110
I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616,2013.
Blaum M, Roth R, New array codes for multiple phased burst correction. IEEE Trans on Inform Theory, 1993,39(1): 66 ~ 77.
A. Dimakis, P. Godfrey, Y. Wu, M. Wainwright, and K. Ramchandran, “Network coding for distributed storage systems,” IEEE Trans. Inf. Theory,vol. 56, no. 9, pp. 4539–4551, Sep. 2010.
M. N. Krishnan and P. V. Kumar, “On MBR codes with replication,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 71–75.
N. B. Shah, “On Minimizing Data-Read and Download for Storage-Node Recovery,” IEEE Communications Letters, vol. 17, no. 5, pp. 964–967, 2013.
K. Rashmi, N. Shah, P. Kumar, and K. Ramchandran, “Explicit construction of optimal exact regenerating codes for distributed storage,” in Proc. 47th Annu. Allerton Conf. Communication, Control, and Computing, Urbana-Champaign, IL, Sep. 2009, pp. 1243–1249.
K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, 2011.
Y. Hu, H. C. H. Chen, P. P. C. Lee, and Y. Tang, “NCCloud: applying network coding for the storage repair in a cloud-of-clouds,” in Proc. 10th USENIX conference on File and Storage Technologies, San Jose, CA, USA,2012, p. 21.
Huang C, Simitci H, Xu Y, et al. Erasure Coding in Windows Azure Storage. in: Proceedings of USENIX Annual Technical Conference (ATC), Boston, MA, USA, June, 2012, USENIX.
Hu Y, Li X, Zhang M, et al. Optimal repair layering for erasure-coded data centers: From therory ot practive. ACM Transactions on Storage (TOS), 2017, 13(4):33.
Rashmi K, Nakkiran P, Wang J, et al. Having Your Cake and Eating It Too: jonintly Optimal Erasure Codes for I/O, Storage, and Network-bandwidth. in: Proceedings of USENIX Conference on File and Storage Technologies (FAST), Santa Clara, CA, USA, February, 2015, USENIX, 81-94.
Hou H, Lee P, Shum K, et al. Rack-aware regenerating codes for data centers. IEEE Transactions Information Theory, 2019,65(8):4730-4745.
Sathiamoorthy M, Asteris M, Papailiopoulos D, et al. XORing Elephants: Novel Erasure Codes for Big Data. in: Proceedings of VLDB Endowment. VLDB, March, 2013, 325-336.
RASHMI K, SHAN N B, RAMCHANDRAN K. A Piggybacking Design Framework for Read and Download-Efficient Distributed Storage Codes[J]. IEEE Transactions on Information Therory, 2017,63(9):5802-5820.
N. B. Shah, K. V. Rashmi, P. V. Kumar, and K. Ramchandran, “Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions,” IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2134–2158, Apr. 2012.
Y.WuandA.G.Dimakis,“Reducingrepairtrafficforerasurecoding-basedstorageviainterferencealignment,”Proc.IEEEInternationalSymposium on Information Theory, Seoul, Korea, June 2009, pp. 2276–2280.
K. V. Rashmi, N. B. Shah, and P. V. Kumar, “Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction,” IEEE Trans. Inf. Theory, vol. 57, no. 8, pp. 5227–5239, Aug. 2011.
S. J. Lin, W. H. Chung, Y. S. Han, and T. Y. Al-Naffouri, “A Unified Form of Exact-MSR Codes via Product-Matrix Frameworks,” IEEE Trans Inf Theory, vol. 61, no. 2, pp. 873–886, Feb 2015.
D. Papailiopoulos, A. Dimakis, and V. Cadambe, “Repair Optimal Erasure Codes through Hadamard Designs,” IEEE Trans. Inf. Theory, vol. 59, no. 5,pp. 3021–3037, 2013.
I. Tamo, Z. Wang, and J. Bruck, “Zigzag codes: MDS array codes with optimal rebuilding,” IEEE Trans. Inf. Theory, vol. 59, no. 3, pp. 1597–1616,2013.
Z. Wang, I. Tamo, and J. Bruck, “On codes for optimal rebuilding access,” in Proc. 49th Annual Allerton Conference on Communication, Control, and Computing, Sept 2011, pp. 1374–1381.
V. R. Cadambe, C. Huang, J. Li, and S. Mehrotra, “Polynomial length MDS codes with optimal repair in distributed storage,” in Proc. Forty Fifth Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, USA*, 2011, pp. 1850–1854.
Z. Wang, I. Tamo, and J. Bruck, “Long MDS codes for optimal repair bandwidth,” in Proc. IEEE International Symposium on Information Theory,Cambridge, MA, USA, 2012, pp. 1182–1186.
I. Tamo, Z. Wang, and J. Bruck, “Access Versus Bandwidth in Codes for Storage,” IEEE Trans. Inf. Theory, vol. 60, no. 4, pp. 2028–2037, 2014.
S. Goparaju, I. Tamo, and A. R. Calderbank, “An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes,” IEEE Trans. on Inf.Theory, vol. 60, no. 5, pp. 2770–2779, 2014.
B. Sasidharan, G. K. Agarwal, and P. V. Kumar, “A high-rate MSR code with polynomial sub-packetization level,” in Proc. IEEE International Symposium on Information Theory, 2015, pp. 2051–2055.
A.S.Rawat,O.O.Koyluoglu,andS.Vishwanath,“Progressonhigh-rateMSRcodes:Enablingarbitrarynumberofhelpernodes,”in Proc.Information Theory and Applications Workshop, La Jolla, CA, USA, 2016, pp. 1–6.
S. Goparaju, A. Fazeli, and A. Vardy, “Minimum Storage Regenerating Codes for All Parameters,” IEEE Trans. Inf. Theory, vol. 63, no. 10, pp.6318–6328, 2017.
G. K. Agarwal, B. Sasidharan, and P. V. Kumar, “An alternate construction of an access-optimal regenerating code with optimal sub-packetization level,” in Proc. Twenty First National Conference on Communications, Mumbai, India, 2015, pp. 1–6.
N. Alon, “Combinatorial nullstellensatz,” Combinatorics, Probability and Computing, vol. 8, no. 1-2, pp. 7–29, 1999.
N. Raviv, N. Silberstein, and T. Etzion, “Constructions of High-Rate Minimum Storage Regenerating Codes Over Small Fields,” *IEEE Trans. Inf.Theory, vol. 63, no. 4, pp. 2015–2038, 2017.
M. Ye and A. Barg, “Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth,” IEEE Trans. Inf. Theory, vol. 63, no. 4,pp. 2001–2014, 2017.
B. Sasidharan, M. Vajha, and P. V. Kumar, “An Explicit, Coupled-Layer Construction of a High-Rate MSR Code with Low Sub-Packetization Level,Small Field Size and All-Node Repair,” CoRR, vol. abs/1607.07335, 2016.
J. Li, X. Tang, and C. Tian, “A generic transformation for optimal repair bandwidth and rebuilding access in MDS codes,” in Proc. IEEE International**Symposium on Information Theory, Aachen, Germany, June 2017, pp. 1623–1627.
S. B. Balaji and P. V. Kumar, “A tight lower bound on the sub-packetization level of optimal-access MSR and MDS codes,” CoRR, Accepted at ISIT**2018, vol. abs/1710.05876, 2017.
M. Vajha, S. B. Balaji, and P. V. Kumar, “Explicit MSR Codes with Optimal Access, Optimal Sub-Packetization and Small Field Size for d =k + 1, k + 2, k + 3,” CoRR, vol. abs/1804.00598, 2018.
E.E.Gad,R.Mateescu,F.Blagojevic,C.Guyot,andZ.Bandic,“Repair-optimalMDSarraycodesoverGF(2),”inProc.IEEEInternationalSymposium on Information Theory, Istanbul, Turkey, 2013, pp. 887–891.
P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the Locality of Codeword Symbols,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6925–6934,2012.
S. B. Balaji and P. V. Kumar, “On partial maximally-recoverable and maximally-recoverable codes,” in Proc. IEEE International Symposium on Information Theory, Hong Kong, 2015, pp. 1881–1885.
M. Chen, C. Huang, and J. Li, “On the maximally recoverable property for multi-protection group codes,” in IEEE International Symposium on Information Theory, June 2007, pp. 486–490.
M. Blaum, J. L. Hafner, and S. Hetzler, “Partial-MDS Codes and Their Application to RAID Type of Architectures,” IEEE Trans. Inf. Theory, vol. 59, no. 7, pp. 4510–4519, 2013.
G. Calis and O. O. Koyluoglu, “A General Construction for PMDS Codes,” IEEE Communications Letters, vol. 21, no. 3, pp. 452–455, 2017.
R. Gabrys, E. Yaakobi, M. Blaum, and P. H. Siegel, “Constructions of partial MDS codes over small fields,” in Proc. IEEE International Symposium on Information Theory, Aachen, Germany, 2017, pp. 1–5.
P. Gopalan, C. Huang, B. Jenkins, and S. Yekhanin, “Explicit Maximally Recoverable Codes With Locality,” IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5245–5256, 2014.
G. Hu and S. Yekhanin, “New constructions of SD and MR codes over small finite fields,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 1591–1595.
J. Chen, K. W. Shum, Q. Yu, and C. W. Sung, “Sector-disk codes and partial MDS codes with up to three global parities,” in Proc. IEEE International Symposium on Information Theory, Hong Kong, 2015, pp. 1876–1880.
M. Blaum, “Construction of PMDS and SD codes extending RAID 5,” CoRR, vol. abs/1305.0032, 2013.
M. Blaum, J. S. Plank, M. Schwartz, and E. Yaakobi, “Construction of Partial MDS and Sector-Disk Codes With Two Global Parity Symbols,” IEEE Trans. Inf. Theory, vol. 62, no. 5, pp. 2673–2681, 2016.
V.LalithaandS.V.Lokam,“Weightenumeratorsandhighersupportweightsofmaximallyrecoverablecodes,”inProc.53rdAnnualAllertonConference on Communication, Control, and Computing, Monticello, IL, USA, 2015, pp. 835–842.
G. M. Kamath, N. Prakash, V. Lalitha, and P. V. Kumar, “Codes With Local Regeneration and Erasure Correction,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4637–4660, 2014.
Cai H, Miao Y, Schwartz M, et al. On optimal locally repairable codes with super-linear length. IEEE Trans Inform Theroy, 2020, 66: 4853-4868.
Chen B, Fang W, Xia S, et al. Constructions of optimal (r,sigma) locally repairabl codes via constacyclic codes. IEEE Trans Commun, 2019, 67: 5253-5263.
Chen B, Xia S, Hao J, et al. Constructions of optimal cyclic (r,sigma) locally repairable codes. IEEE Trans Inform Theory, 2018, 64:2499-2511.
Fang W, Fu F. Optimal cyclic (r,sigma) locally repairable codes with unbounded length. Finite Fields Appl, 2020,63:101650.
A. Agarwal, A. Barg, S. Hu, A. Mazumdar, and I. Tamo, “Combinatorial alphabet-dependent bounds for locally recoverable codes,” IEEE Trans. Inf. Theory, vol. PP, no. 99, pp. 1–1, 2018.
I. Tamo, A. Barg, S. Goparaju, and A. R. Calderbank, “Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes,” CoRR, vol. abs/1603.08878, 2016.
S. Goparaju and A. R. Calderbank, “Binary cyclic codes that are locally repairable,” in Proc. IEEE International Symposium on Information Theory, Honolulu, HI, USA, 2014, pp. 676–680.
A. Zeh and E. Yaakobi, “Optimal linear and cyclic locally repairable codes over small fields,” in Proc. IEEE Information Theory Workshop, Jerusalem, Israel, 2015, pp. 1–5.
I. Tamo, A. Barg, and A. Frolov, “Bounds on the Parameters of Locally Recoverable Codes,” IEEE Trans. Inf. Theory, vol. 62, no. 6, pp. 3070–3083, 2016.
A. Barg, I. Tamo, and S. Vldu, “Locally Recoverable Codes on Algebraic Curves,” IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4928–4939, 2017.
X. Li, L. Ma, and C. Xing, “Construction of asymptotically good locally repairable codes via automorphism groups of function fields,” CoRR, vol. abs/1711.07703, 2017.
M.Y.NamandH.Y.Song,“BinaryLocallyRepairableCodesWithMinimumDistanceatLeastSixBasedonPartialt-Spreads,”IEEECommunications Letters, vol. 21, no. 8, pp. 1683–1686, Aug 2017.
N. Silberstein and A. Zeh, “Optimal binary locally repairable codes via anticodes,” in Proc. IEEE International Symposium on Information Theory, Hong Kong, 2015, pp. 1247–1251.
J. Hao, S. T. Xia, and B. Chen, “Some results on optimal locally repairable codes,” in Proc. IEEE International Symposium on Information Theory, Barcelona, Spain, 2016, pp. 440–444.
M. Shahabinejad, M. Khabbazian, and M. Ardakani, “A Class of Binary Locally Repairable Codes,” IEEE Transactions on Communications, vol. 64, no. 8, pp. 3182–3193, 2016.
J. Hao, S. T. Xia, and B. Chen, “On optimal ternary locally repairable codes,” in Proc. IEEE International Symposium on Information Theory, Aachen, Germany, 2017, pp. 171–175.
J. Hao and S. Xia, “Bounds and Constructions of Locally Repairable Codes: Parity-check Matrix Approach,” CoRR, vol. abs/1601.05595, 2016. X. Li, L. Ma, and C. Xing, “Optimal locally repairable codes via elliptic curves,” CoRR, vol. abs/1712.03744, 2017.
KMM,et,al:An Efficient Piggybacking Design Framework with Sub-packetization l r for All-Node Repair
Francisco Maturana and K. V. Rashmi, et, al:Bandwidth Cost of Code Conversions in the Split Regime
Hanxu Hou, et, al:New Piggybacking Codes with Lower Repair Bandwidth for Any Single-Node Failure
Han Cai,et,al: On Optimal Locally Repairable Codes and Generalized Sector-Disk Codes
A “Hitchhiker’s” Guide to Fast and Efficient Data Reconstruction in Erasure-coded Data Centers
Mean time to meaningless: MTTDL, Markov models, and storage system reliability