基于最小修复带宽的分布式存储系统编码机制构造的研究

发布时间：2018-04-25 08:29

本文选题：分布式存储 + 纠删码　；参考：《复旦大学》2014年硕士论文

【摘要】：随着大数据时代的到来,全球信息数据资源开始呈现出爆炸性增长。图灵奖获得者James Gray甚至提出了关于全球数据总量的摩尔定律：全球数据总量每18个月就将翻一番,也即未来每18个月就能产生出与人类有史以来全部数据总量相同规模的数据。为了满足大数据时代各种大规模存储应用的存储需求,人们开始越来越多地关注分布式存储技术。分布式存储系统(Distributed Storage System,DSS)就是利用一定的技术手段将原始数据分别存储在相互独立的若干台设备上,并能通过不同程度的数据冗余来提供对数据的可靠访问。然而分布式存储系统中相互独立的各个节点本身会因为各种原因发生失效。随着分布式存储系统规模的不断扩大,这种节点失效的情况出现得越来越普遍。因此,构建分布式存储系统需要面临的一个问题便是节点修复：为了使系统能够保持相同的可靠性,当一个存储了编码信息的节点发生失效后,必须在新的节点再生出丢失的编码信息。本文对采用纠删码的分布式存储系统进行研究发现,即使为了修复某一独立的失效节点,修复的过程也必需先恢复出完整的原始数据,再根据原始数据再生出有效的数据片段。为了更加有效地进行节点修复,降低修复带宽,提高存储效率,本文重点研究了基于最小修复带宽的分布式存储系统编码机制。Dimakis等人创造性地将网络编码技术与分布式存储结合起来,定义了针对节点修复问题的若干种再生码(Regenerating codes),并得到了存储容量与修复带宽之间的基本权衡关系。Wu等人在此基础上,利用最大距离可分离码(Maximum distance separable code)以及系统性(Systematic)码的特点设计了相应的系统性MDS编码(Systematic MDS codes)机制,当d=k+l时实现了理论上的最小修复带宽。本文分析比较了Wu的编码机制与其他实现最小修复带宽的编码机制,指出了Wu的构造客观上所存在的局限,然后对Wu提出的系统性MDS编码机制进行了拓展。拓展后的构造形式简洁,并且比Wu的构造更具一般性,在不提高有限域尺寸的前提下,使拓展后的构造在进行节点修复的过程中继续保持系统性属性与MDS属性,且使构造中系数的选择更加灵活,为节点修复提供更多的组合方式,进而可以满足更多应用场景和网络状况下的需求。
[Abstract]:With the arrival of big data era, global information data resources began to show explosive growth. Turing laureate James Gray has even proposed Moore's law on global data: global data will double every 18 months, that is, every 18 months in the next 18 months will produce data of the same size as all the data we have ever had. In order to meet the storage requirements of various large-scale storage applications in big data era, people began to pay more and more attention to distributed storage technology. Distributed Storage system DSS (distributed Storage system DSS) uses certain technical means to store raw data on several independent devices, and it can provide reliable access to data by varying degrees of data redundancy. However, the independent nodes in the distributed storage system will fail for various reasons. With the increasing scale of distributed storage system, this kind of node failure is becoming more and more common. Therefore, one of the problems in building a distributed storage system is node repair: in order to maintain the same reliability of the system, when a node that stores the encoded information fails, The missing encoding information must be reproduced at the new node. In this paper, the distributed storage system using erasure code is studied. It is found that even in order to repair an independent failure node, the complete original data must be restored first, and then the valid data fragments are regenerated according to the original data. In order to repair nodes more effectively, reduce repair bandwidth and improve storage efficiency, This paper focuses on the research of distributed storage system coding mechanism based on minimum repair bandwidth. Dimakis et al creatively combine network coding technology with distributed storage. In this paper, several kinds of regenerating codes for node repair are defined, and the basic trade-off between storage capacity and repair bandwidth is obtained. Wu et al. Based on the characteristics of maximum distance separable code and systematic system MDS code, the corresponding systematic MDS codes-mechanism is designed. The minimum repair bandwidth is realized when dl is used. In this paper, the coding mechanism of Wu is analyzed and compared with other coding mechanisms to realize the minimum repair bandwidth, and the limitations of Wu's construction are pointed out, and then the systematic MDS coding mechanism proposed by Wu is extended. The extended structure is simpler and more general than Wu's. Without increasing the size of the finite field, the extended structure keeps the systematic and MDS attributes in the process of node repair. It also makes the selection of coefficients in the structure more flexible, and provides more combination methods for node repair, which can meet the needs of more application scenarios and network conditions.
【学位授予单位】：复旦大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP333

【共引文献】