高容错能力的阵列纠删码模型研究

How to improve the fault tolerance in a storage system, which is the key point to deal with ever-increasing faulty nodes risk caused by the sustained growth of storage scale. The research object of this project is the applicable array erasure code with high fault tolerant capability, and the project studies on scientific problems including reachable approach of high fault tolerance and optimal update penalty in the array code model, eliminating or reducing the limit strength of storage array size which most array codes must satisfy, storage efficiency improvement method which does not take fault tolerance capability for the price, and so on. Introducing the concept of code-chain-slope set into array codes with classic horizontal data layout, using all elements in the code-chain-slope set to establish a relationship between data and redundant elements, and through the above method, this project is to design and implement a class of array code model which achieve theoretical limitless fault tolerance capability, besides the innate advantage of computational efficiency, the model has a storage efficiency which can approach the theoretical optimum endlessly and optimalizing update penalty in theory, so it has a high practical value. The significance of this study is hopeful to reveal the relationship between slopes of code chains and fault tolerance in array codes, make a breakthrough the fault tolerance capability bottleneck which has restricted fault-tolerant model based on array codes, provide a new approach for reliability of large-scale storage systems.

如何提高存储系统的整体容错能力，是应对由于存储规模持续扩大而带来的同时失效节点数目增加风险的关键问题。本项目以可实用的高容错阵列纠删码为研究对象，对阵列码模型的高容错能力及最优更新代价的可达途径、消除或减弱阵列码构造时在存储阵列尺寸上的强约束条件、不以容错能力为代价的存储效率提升方法等科学问题展开研究。通过在典型水平式数据布局的阵列码中引入码链斜率集的概念，以及使用码链斜率集中所有元素共同建立数据与冗余之间关系的方法，拟设计并实现一类理论上容错能力不受限制的阵列码容错模型，除了天然的计算效率优势外，该容错模型还具备不断趋近理论最优值的存储效率和最优的更新代价，因而具有很高的实用价值。研究意义在于有望揭示阵列码中的码链斜率与容错能力之间的关系，突破长期以来限制以阵列码为核心构建存储系统容错模型的容错能力瓶颈，为大规模存储系统的可靠性保障提供一类新的方法途径。

在目前的信息社会，数据不仅呈现出持续爆炸式增加的趋势，而且已经成为了各行各业正常运转的基本资源，数据存储的可靠性显得日益重要。对于现在运行的存储系统，不仅单个存储节点的存储容量在扩大，其存储节点数也在不断增加，在这些大规模存储系统中如何有效保证存储数据的可靠性，当部分节点发生崩溃时如何保证系统中的数据能有效恢复，如何在相同容错能力前提下减少冗余节点数据从而节约能耗，如何能在节点崩溃后尽快时间恢复等，本项目正是基于上述关键问题而展开的研究。项目在执行期间，设计了一类能适用于大规模多节点存储系统的一类高容错的阵列纠删码，该编码具备理论上的任意容错能力且能根据实际运算环境而提前设置容错数量，该码的编码和数据恢复等操作所需的所有计算均为二进制的异或运算，具有极高的运算效率，简单的构造形式非常有利于软硬件的实现，而其存储效率可以通过加大存储条块尺寸而不断增加，从而接近香农限，此外，该编码具有理论可达的最小更新代价，该特征可以为整个存储系统并发存取操作的高效性提供保障。项目在单机和Hadoop上设计并实现了用于测试纠删码容错的演示系统，通过演示系统实验，证明了新提出的阵列纠删码在编码译码的时间效率上高于相同容错能力的柯西RS码2个数量级，与传统EVENODD、X、RDP等纠删码及LDPC码的编译码效率相当，单节点错误恢复时略低于更多考虑单节点重构效率的LRC码，考虑存储系统节点负载、带宽限制、存储效率等诸多约束条件后，使用新的阵列码可以构建出节点容错能力超过10的存储系统。通过此次项目的实施，项目研究组打通了根据实际应用环境进行多容错阵列纠删码模型构建的路径，在当前几乎所有大规模存储系统使用副本技术或RS码作为容错核心技术的背景下，探索了采用阵列纠删码进行存储系统数据容错的方法和技术路线，与副本技术相比提高了数据存储的空间利用率，与RS码技术相比大幅提升了编码译码的时间效率，是一类可以根据应用环境而在多个主要性能指标间做出平衡的容错技术。