CONSTRUCTION OF HIGH-RATE, ACCESS-OPTIMAL, MINIMUM STORAGE REGENERATING (MSR) ERASURE CODES

摘要

High-Rate MSR (n, k) erasure codes (HMSR) for application in distributed data storage systems are generated using m r-Ary trees where n=k x m and r = n - k. Nodes in the tree structures represent systematic and parity storage nodes. Each parity symbol for the HMSR erasure codes will be a linear combination of maximum k + klr systematic symbols. The tree structures show that when a systematic node fails, its original systematic symbols can be recovered by accessing beta symbols for each of its leaf nodes from each of the remaining nodes. Traversing the m r-Ary trees to design a codeword array will provide the linear equations needed to solve for and recover the lost systematic symbols. When forming the linear equations, random number or other coefficients can be added to the systematic symbols to construct the parity symbols. The parities of the HMSR erasure code will ensure access-optimal, help-by-transfer recovery of any systematic node failure by using only a minimum bandwith.