分布式网络中基于纠删编码的存储机制及其优化

With the development of networks and communication techniques, distributed storage systems, supported with the infrastructure of the Internet, have broad prospects and potential spaces, such as peer-to-peer storage, cloud storage, etc. Different from the traditional storage model, the decentralization, dynamics and heterogeneity of the networks bring a challenge to keep stored data in the ideal available state, which is an obstacle for these storage systems in practice. It needs to investigate the storage schemes of high reliability, high availability and high performance. Therefore, the erasure-coding based storage mechanism, as one of the research directions, has been drawn more attentions in academic. .To design reliable and efficient distributed storage systems, we plan to study and optimize the erasure-coding based storage mechanism based on the awareness of network characteristics. We will consider multiple practical constraints to examine the optimal erasure-coding storage problems in the whole storage process, such as the storage space costs, network bandwidth overheads, the data access model, the expected storage reliability and some others. The research work mainly includes the following aspects. First, The optimal erasure codes which are adative to network features and coincided with the storage demands by extending some merited erasure codes is one of the concerned aspects. Then, the optimal allocation of erasure coded fragments under multiple constraints will be studied. Third, the schedule algorithm of data recover and repair for high performance will be examined. Final, the prototype storage system will be designed to validate and evaluate our presented algorithms in erasure coding based stroage networks. Our research work will not only be expected to flavor the theory of easure codes, but also provide the innovative support to build reliable and efficent distributed storage networks with erasure codes.

随着网络和通信技术的发展，以互联网络为支撑的分布式存储系统具有广阔的前景和发展空间，例如对等存储、云存储等。这与传统的数据存储模式不同，网络的分布性、动态性和异构性导致数据存储难以处于理想可用的状态，这亟需高可靠、高可用和高性能的数据存储策略。为此，基于纠删编码的数据存储成为当前倍受关注的研究方向。.本项目在认识分布式网络特性的基础上，根据多种纠删编码的容错特性，综合考虑存储空间开销、网络带宽消耗、数据访问模式以及数据存储的可靠性等因素，研究可靠高效的数据编码存储机制及其优化。主要体现在以下几个方面：(1)通过对具有良好特性的编码扩展，研究适应网络特点和存储需求的编码构造；(2)研究在多种约束条件下的编码数据的优化布局；(3)研究高性能编码数据重构的调度算法；(4)设计原型系统进行验证和评价。本项目有望丰富多容错纠删编码的理论研究，而且有望为布式网络存储提供创新技术支持。

随着网络和通信技术的发展，以互联网络为支撑的分布式存储系统具有广阔的前景和发展空间，例如对等存储、云存储等。这与传统的数据存储模式不同，网络的分布性、动态性和异构性导致数据存储难以处于理想可用的状态，这亟需高可靠、高可用和高性能的数据存储策略。为此，基于纠删编码的数据存储在分布式网络存储中日益得到工业界和学术界的重视。.本项目在认识分布式网络特性的基础上，根据纠删编码的容错特性，综合考虑存储空间开销、网络带宽消耗以及数据存储的可靠性等因素，对可靠高效的数据编码存储机制及其优化进行了研究。我们按照项目既定的计划，圆满地完成了预期的研究任务。主要的研究工作体现在以下几个方面：.(1)提出了一种新的支持在线连续扩展的纠删编码方法。该编码在双容错的前提下，支持网络存储节点的连续扩展，具有优越的扩展开销；通过优化正则图中圈的长度，优化了编码容错能力，并给出了相应的算法。.(2)在对关联故障的内在连接特性分析的基础上，研究了二元纠删编码的存在性，给出了算法证明，并且提出了一种低密度的编码构造方法。.(3)利用交换图模型研究了优化复制编码，将存储开销优化问题形式化抽象为装箱问题，并利用二部图模型描述，提出了基于禁忌搜索的优化算法。.(4)针对网络节点的存储能力的异构性，利用整数拆分理论提出了一种优化数据布局算法，建立加权的k-out-of-n的可靠性模型，对MDS编码存储数据块优化分布，增强数据存储的可靠性，并进行了性能评价分析。.(5)研究分布式存储系统扩容过程中数据管理的核心问题及其算法，构建了扩容数据空间管理的框架，针对数据空间收集和分配的优化问题，进行了形式化描述，分别提出了相应的优化算法，并且进行大量的实验，结果表明这些算法相比已有的算法具有显著的优势。.(6)在OpenStack Swift基础上构建了存储集群原型，对上述的编码存储中涉及的算法提供了一套可编程访问接口，对上述的理论研究进行验证和存储性能评价分析。.综上，本项目按计划完成了规定的研究内容，达到了预期目标。本项目研究成果不仅在理论上研究了纠删存储编码构造机制，而且对分布式网网络存储提供了有效的技术方法支持。