A New Design of Binary MDS Array Codes With Asymptotically Weak-Optimal Repair
Hanxu Hou, Yunghsiang Sam Han, Patrick P. C. Lee, Yuchong Hu, Hui Li · IEEE Transactions on Information Theory · 2019
Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provides fault tolerance with minimum storage redundancy but also achieves low computational complexity. They are constructed by encoding k information columns into r parity columns, in which each element in a column is a bit, such that any k out of the k + r columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance in practical applications. Specifically, if a single column fails, then our goal is to minimize the repair bandwidth by downloading the least amount of bits from d healthy columns, where k <; d <; k + r - 1. If one column of an MDS code is failed, it is known that we need to download at least 1/(d - k + 1) fraction of the data stored in each of the d healthy columns. If this lower bound is achieved for the repair of the failure column from accessing arbitrary d healthy columns, we say that the MDS code has optimal repair. However, if such lower bound is only achieved by d specific healthy columns, then we say the MDS code has weak-optimal repair. In this paper, we propose two explicit constructions of binary MDS array codes with more parity columns (i.e., r ≥ 3) that achieve asymptotically weak-optimal repair, where k + 1 <; d <; k + L(r - 1)/2J, and “asymptotic" means that the repair bandwidth achieves the minimum value asymptotically in d. Codes in the first construction have odd number of parity columns and asymptotically weak-optimal repair for anyone information failure, while codes in the second construction have even number of parity columns and asymptotically weak-optimal repair for any one column failure.