基于组合设计的高效分布式存储编码研究

Large-scale distributed storage systems need to introduce redundancy techniques to guarantee system fault-tolerance. There are two common strategies to achieve data redundancy: replication and erasure coding. Data replication is of simple deployment, implementation and management, yet it will lead to large storage overhead. In recent years, erasure codes have attracted tremendous attention from both industry and academia, which can reduce the storage overhead while ensuring data reliability..Various coding schemes have been proposed to improve the storage performance of erasure codes. For example, regenerating codes can reduce the repair bandwidth during node recovery; locally repairable codes can reduce the number of available nodes needed to contact for repair. The proposed project aims to utilize combinatorial designs, to study the theory and application of fractional repetition (FR) codes. The main research contents include: (1) Present new construction methods for FR codes, extend the current parameters; (2) Design a family of FR codes with small repair locality, analyze the relation among different parameters; (3) Study the minimum distance of FR codes, theoretically derive the exact expressions; (4) Deploy the constructed codes in practical storage systems, verify the storage performance and further make sufficient test to support the application of FR codes in commercial storage systems.

大规模分布式存储系统需要引入冗余技术来保证系统的容错性，数据冗余通常有两种实现方式：复制技术和纠删码技术。数据复制技术部署简单、易于实现和管理，但是会导致巨大的存储开销。近年来，工业界和学术界逐步将目光投向了纠删码技术，在保证数据可靠性的同时降低系统存储开销。.国际上提出了多种编码方案来提高纠删码的存储性能，如再生码可以降低节点失效时的修复带宽，局部修复码可以降低修复过程中所需连接的可用节点数。本项目致力于利用组合设计理论，研究部分重复码的理论和应用。主要研究内容为：(1) 提出新型部分重复码构造方法，拓展现有码字参数；(2) 设计修复局部度低的部分重复码，分析各参数之间的关系；(3) 研究部分重复码的最小距离，从理论上推导精确表达式；(4) 在实际存储系统中部署所构造的码字，对比验证其存储性能，为将基于部分重复码的分布式存储系统推向商业化作充分的测试。

在当前大规模分布式存储系统中，由于节点失效变得愈发频繁，系统需要引入冗余机制来保证数据的可靠性。在相同冗余信息的情况下，纠删码技术可以大幅提高系统的可靠性。然而，传统纠删码的节点修复过程需要消耗大量的资源，为此研究人员提出再生码以解决节点修复带宽问题，但是参与修复的节点需要进行大量的线性运算。作为再生码的一种推广，部分重复码的节点修复过程只涉及简单的数据传输，因此修复带宽和修复复杂度均是最优的。本项目围绕部分重复码，重点研究基于组合设计的码字构造方法及相关性质。主要包括：（1）提出基于可分组设计和t-设计的部分重复码构造方法，扩展现有的码字构造参数。在相同系统参数情况下，所构造的码字能够达到甚至超过基于再生码的系统存储容量。特别地，本项目考虑部分重复码在动态存储环境中的应用，提出支持节点扩容和部分失效的码字构造方法。结合对称设计的性质，构造节点修复局部度低的码字。（2）引入对偶码的概念，并且从对偶的角度研究部分重复码的支撑文件大小。揭示部分重复码与其对偶码支撑文件大小之间的关系，在此基础上推导出一个改进的支撑文件大小上界，证明一个文件重构度下界并进一步优化该理论下界，同时分别给出基于组合设计和正则图的最优部分重复码。此外，本项目提出基于张量积的部分重复码合并方法，并分析生成码字与初始码字支撑文件大小之间的关系。（3）实现基于部分重复码的存储系统，在Hadoop分布式文件系统进行实验测试。与传统编码方案相比，部分重复码可以显著提高节点修复效率。.本项目的主要成果包括：（1）在国内外期刊发表论文11篇，在国际会议发表论文18篇。（2）提交美国专利申请8项，授权3项；提交中国发明专利申请10项，授权5项。（3）获得深圳市科技进步二等奖1项。（4）培养博士研究生2名及硕士研究生14名。