Modern large-scale distributed storage systems usually deploy erasure codes to provide high data reliability at a small storage overhead. Among them, maximum distance separable codes are the most common choice as they can achieve the optimal tradeoff between fault tolerance and storage overhead. In this paper, we focus on the repair problem of MDS codes and present constructions of binary MDS array codes which achieve the optimal repair bandwidth for multiple node failures. Specifically, by stacking multiple Blaum-Roth code instances whose “evaluation points” are judiciously designed, we obtain two families of binary MDS array codes with optimal cooperative repair bandwidth. The first family of codes of length n and dimension k can achieve the optimal cooperative repair bandwidth for \(2 \le h \le n-k\) and \(k+1 \le d \le n-h\) where h and d are the number of failed nodes and helper nodes, respectively. The second family of codes are optimal for multiple values of d simultaneously. Both of the codes are constructed on a special polynomial ring over binary field, thereby only XORs and cyclic shifts are involved during nodes repair and file reconstruction. Moreover, due to the inherent parallel structure of the codes, both the encoding and decoding procedures can be implemented in parallel, which can speed up the computing process.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Construction of Binary Cooperative MSR Codes with Multiple Repair Degrees

  • Lei Li,
  • Xinchun Yu,
  • Yaqian Zhang,
  • Liang Chen,
  • Yuanyuan Dong,
  • Chenhao Ying,
  • Yuan Luo

摘要

Modern large-scale distributed storage systems usually deploy erasure codes to provide high data reliability at a small storage overhead. Among them, maximum distance separable codes are the most common choice as they can achieve the optimal tradeoff between fault tolerance and storage overhead. In this paper, we focus on the repair problem of MDS codes and present constructions of binary MDS array codes which achieve the optimal repair bandwidth for multiple node failures. Specifically, by stacking multiple Blaum-Roth code instances whose “evaluation points” are judiciously designed, we obtain two families of binary MDS array codes with optimal cooperative repair bandwidth. The first family of codes of length n and dimension k can achieve the optimal cooperative repair bandwidth for \(2 \le h \le n-k\) and \(k+1 \le d \le n-h\) where h and d are the number of failed nodes and helper nodes, respectively. The second family of codes are optimal for multiple values of d simultaneously. Both of the codes are constructed on a special polynomial ring over binary field, thereby only XORs and cyclic shifts are involved during nodes repair and file reconstruction. Moreover, due to the inherent parallel structure of the codes, both the encoding and decoding procedures can be implemented in parallel, which can speed up the computing process.