【作者】 蒋海波；

【导师】 王晓京；

【作者基本信息】 电子科技大学 ， 计算机软件与理论， 2013， 博士

【摘要】 随着信息技术的不断发展，数据日益成为人们日常生活中重要资源。据统计，2010年全球创建、存储和复制的数字信息总量已达到1.2ZB，2011年的数据量达到里程碑式的1.8ZB，而且这种增长还在加速，预计2015年将达到近8ZB。爆炸式增长的数据必然带来存储设备的持续增加。目前，海量数据存储环境下的现代数据中心的存储节点规模少则几万多则几十万，但在规模巨大的存储环境系统中，磁盘损毁或者存储节点失效已成为一种常态行为；与此同时，因网络连接设备或者存储节点其它元器件造成的数据不可访问或者丢失现象也时有发生。为了满足日益扩展的数据存储需求，人们对数据存储的可靠性，可用性等相关特性提出了更高的要求，传统的常规技术手段根本无法应对当前的形式，如何实现海量数据的低冗余度高可靠性存储已经成为业界面临的一个巨大挑战。因而，本文针对构建低冗余度高可靠性海量数据存储系统的关键问题，在总结了当今数据可靠性增强理论和海量数据存储系统基本架构的基础上，对高性能数据容删数据布局算法以及高可靠性存储架构等方面进行了深入的研究，取得了一定的进展，具体如下：1．针对已在数据存储系统中有广泛应用的RAID技术，提出了一种新的基于异或运算的水平阵列纠删码：EX-ENOD码。该码能够容许任意三列的随机删除错，并具有极大距离可分性质。根据该码的几何构造特点，提出了一种具有低计算复杂度的译码方法，该方法的计算复杂度要低于目前已知的其它可纠三列随机删除错纠删码的译码方法。同时，该编码方法具有明显的通用性，可以扩展应用到STAR码、EEOD码的译码过程。2．针对海量存储系统规模不断扩大，可靠性要求不断提高的需求，本文将在{0,1}符号域上的范德蒙系统编码方法引入存储系统中来。该种编码方法继承了传统有限域上构建的范德蒙编码的参数不受存储节点规模、容错参数限制的优良特性，而且存储效率达到最高，同时该方法突破了传统有限域上构建的编码需要大量查询运算的弊端。基于该编码方法构建的存储系统，在保证其数据仍然可用的情况下，最多可容许系统内部一半的存储节点发生损毁，在该种情况下，系统仅需要与原数据相同的冗余数据量。3．针对{0,1}符号域上编码矩阵的特点，根据编码矩阵中各行向量中“1”元素的分布，提出了可降低编译码计算复杂度的优化算法。文章同时针对传统译码重构过程重构带宽较高的缺点，提出了基于校验矩阵的译码方法，并根据校验矩阵列向量的特点和存储系统所需要重构数据的数目，给出了一种低带宽重构算法。该种低带宽重构算法，可以推广到所有构建在{0,1}符号域上的编码存储系统。4．根据编码冗余策略数据布局的特点，设计了一种低冗余度高可靠性海量数据存储系统基础架构。系统将数据消冗和编码冗余可靠性增强技术纳入统一的基础架构，并针对编码冗余数据的分布特点，进行了存储节点的节能设计；针对数据使用特点提出了非均等存储及自适应读取策略；并提出了数据消冗与数据验证协同进行的运行策略。更多还原

【Abstract】 With the development of information technology, data is increasingly becomingan important resource in our daily lives. According to the statistics, the total amount ofdata which the world created in2010, stored and replicated has reached1.2ZB, and in2011the amount is1.8ZB. It is expected to reach nearly8ZB in2015. The primaryproblem brought by the explosive growth of data is the increasing costs of storageequipment and management. Now, the scale of storage nodes in the modern data centeris ranging from tens of thousands to hundreds of thousands. Disk and storage nodefailures have become a normal behavior in the huge storage systems. At the same time,the network connection device and other components of storage node often becomeinvalid. In order to meet the expanding demand of reliability, availability, and otherrelevant characteristics of data storage, there need new techniques to cope with thecurrent situation. How to implement the mass data storage technology with lowredundancy and high reliability has become a huge challenge.Thus, this dissertation focuses on the key technology of constructing the massdata storage system with low redundancy and high reliability. Basing on the longresearch of the theory of data reliability and the framework of the storage systems, wehave made some progress. The main contents of this dissertation are as follows:1. As the RAID technology has already been widely used in the data storagesystem, we propose a new level array code based on the exclusive-OR operation:EX-ENOD code. This code can tolerate any random three failures and it has the beststorage efficiency. According to the geometrical configuration of the code, we proposea decoding method with low computational complexity. Further more thecomputational complexity of this method is much lower than those of other erasurecodes. Meanwhile, this decoding method can be applied to the STAR code, the EEODcode and so on.2. In order to improve the reliability of the mass storage system, we design andimplement Vandermonde system encoding method that is based on {0,1} symboldomain in the mass storage system. This encoding method inherits the excellent features of Vandermonde code that is on the traditional finite field. There is no need toconsider the limits number of the storage nodes and fault-tolerant parameters. At thesame time, it can achieve the best storage efficiency. This method can avoid thedisadvantage of the traditional encoding on finite field which requires a lot of queryoperations. In particularly, this method is very suitable for the binary representation ofthe data in the computer system, so it is more suitable for the mass data storage thanothers.3. According to the distribution of the "1" element in each row vector of theencoding matrix in {0,1} symbol domain, we propose an optimization algorithm whichcan reduce the computational complexity of encoding and decoding. At the same time,In order to reduce the high bandwidth that is needed in the traditional decodingreconstruction process, we propose a decoding method which is based on the paritycheck matrix. We also give a low-bandwidth reconstruction method according to thecharacteristics of the parity check matrix column vector. This low-bandwidthreconstruction algorithm can be extended to all the encoding storage systems that arebuilt on {0,1} symbol domain.4. According to the characteristics of the data layout of erasure codes, we design amass storage system infrastructure with low redundancy and high reliability. Thissystem combine the data deduplication technology and encoding technology together.Basing on the structural characteristics of the erasure code, we extend an energy-savingand self-adaption access strategy to the storage system. At the same time, we alsointegrate the data redundant elimination and data validation together in the system.更多还原