分布式存储系统中的低计算复杂度再生码研究

Distributed storage systems are composed by many unreliable distributed storage nodes. A data file is stored in multiple storage nodes redundantly to provide high reliability. Erasure codes are being increasingly employed in distributed storage systems to combat the cost of reliably storing larger amounts of data, with optimal storage efficiency. Regenerating codes form a class of erasure codes which can achieve the optimal trade-off between storage capacity and the bandwidth needed to repair a failed node. However, one of the critical drawbacks of existing regenerating codes in general is the high coding and repair complexities. This project proposes a framework of linear codes with the binary parity-check code as the alphabet. A new family of regenerating codes is constructed based on the proposed coding framework. We show that the proposed functional repair regenerating codes in the project can achieve the optimal trade-off curve between the storage and repair bandwidth with less computational complexity. Furthermore, we will show that some exciting exact repair regenerating codes can be modified to the corresponding exact repair regenerating codes proposed in the project with much less encoding, repair and decoding complexity. Construction of minimum storage regenerating codes with high coding rate and lower computational complexity is also one main research content of the project.

分布式存储系统是由很多不可靠的存储节点组成。为了保证存储数据的高可靠性，需要把数据的冗余数据存储在多个节点。纠删码因其拥有最优的存储效率而被广泛的用于分布式存储系统以提高数据可靠性。再生码是一类可以达到存储容量和修复一个失效节点所需带宽的最优折中的纠删码。然而，现有再生码的编解码和修复计算复杂度高。本项目提出了以二进制奇偶校验码为字母表的线性码的编码框架。使用该编码框架构造了一类新的再生码。本项目提出的功能修复再生码可以达到存储容量与修复带宽的最优折中，而相比于现有的功能修复再生码，本项目提出的功能修复再生码的计算复杂度低。此外，本项目将研究把一些现有的精确修复再生码均修改为相应的本项目提出的精确修复再生码，而编解码计算复杂度和修复计算复杂度可以大幅度的降低。编码率高、计算机复杂度低的最小存储再生码构造亦是本项目的研究内容之一。

现有再生码的三个核心问题是：编解码计算复杂度高、分包数大和跨机架修复带宽大。为解决以上问题，本项目（i）提出了以二进制奇偶校验码为字母表的线性码的编码框架，使用该编码框架构造了一类新的再生码，并针对Vandermonde矩阵和Cauchy矩阵分别设计了高效的解码算法；（ii）提出了分包数小的再生码构造方法；（iii）研究存储与跨机架修复带宽的最优折中理论，设计了一系列达到跨机架修复带宽最优的构造方法。.首先，导致编解码计算复杂度高的主要原因在于有限域乘法运算的计算复杂度高。本项目设计了一类具有循环结构的多项式环并基于该多项式环提出了具有计算复杂度低的再生码编码框架和构造方法。此外，本项目分别为Vandermonde矩阵和Cauchy矩阵设计了LU分解的解码算法，比现有解码算法均具有更低的解码计算复杂度。其次，我们提出了高码率再生码的新型构造方法，具有更低的分包数。最后，本项目提出了具有最优跨机架修复带宽的再生码编码模型，推导出了存储与跨机架修复带宽的最优折中曲线，并给出了达到最优跨机架修复带宽的再生码编码框架和构造方法。