随机化数据冗余方法及其在存储系统中的应用

发布时间：2018-07-17 07:29

【摘要】：利用网络分布式存储系统存储大数据已成为数据存储技术的发展趋势。网络分布式存储系统通常由数量众多的存储节点构成，由于人为或自然灾难的不可避免性，或是存储节点本身的低可靠性，常常会发生部分存储节点损坏或是无法及时使用的情况。而这一旦发生，存储其中的重要数据就会丢失或是不可用，造成极大的损失。因此，为了保证存储数据的安全性和可靠性，将数据冗余方法引入网络分布式存储系统成为一种必然。已有的数据冗余方法，，如基于复制的数据冗余方法，基于阵列码的数据冗余方法等均存在种种不足，或者是存储冗余度过高，或者是容错能力有限，无法满足网络环境下分布式存储系统的需求。针对这一问题，本文首次以随机矩阵理论为基础，提出了一类新的数据冗余方法，称之为随机化数据冗余方法，并研究了其在两类具体的网络分布式存储环境——分布式数据容灾存储和传感器网络数据存储环境下的应用。本文的主要研究成果包括以下几个方面： 1．提出了性能优异的随机化数据冗余方法。容错能力高、存储冗余度低、运算速度快、修复带宽低是网络环境下的分布式存储系统对数据冗余方法的需求。现有的数据冗余方法往往无法同时满足这些需求。本文以二元域上的随机矩阵为基础，提出了一类新的能满足上述需求的随机化数据冗余方法，给出了详细的文件存储、读取、以及修复算法。在本文提出的随机化数据冗余方法中：由源文件得到冗余文件、由冗余文件恢复出源文件均基于构造好的随机矩阵完成；随机矩阵满秩的高概率性质保证了冗余方法的高容错能力和低存储冗余度；同时，源文件和冗余文件之间的转换只依靠异或运算进行，降低了计算复杂度，提高了文件的处理速度；另外，随机矩阵的稀疏性也使得修复丢失的部分冗余文件数据所需的修复带宽有效降低； 2．提出了基于随机化数据冗余方法的低冗余度数据容灾方案。数据容灾方案是网络分布式数据容灾存储系统抵御大规模存储节点损毁，保证数据生存能力的有效手段。传统的容灾方案通常以复制冗余方法为基础，以高存储空间代价换取一定的容灾能力。本文在随机化数据冗余方法的基础上，提出了一类具有低存储冗余度的数据容灾方案。与复制容灾方案相比，本文方案在提供相同容灾能力的前提下，可将系统的存储空间代价降到近似的理论最小值。本文方案的可行性和有效性在相关实验中得到了验证。 3．以随机化数据冗余方法为基础，提出了适用于无人值守传感器网络的具有低通信成本和低访问成本的分布式存储算法。无人值守传感器网络可以看作是一类没有路由表的特殊网络分布式存储系统，其目的在于感知数据并将感知到的数据可靠地存储在整个网络中。本文以随机化数据冗余方法为基础，并与定向随机游走机制相结合，提出了适用于无人值守传感器网络的分布式存储算法。采用本文算法：可以有效地将网络中k个数据节点感知到的k个源数据包存储到网络所有的n个节点中（n k），形成n个存储数据包。当存储过程完成之后，即使有部分节点损坏而导致存储其中的存储数据包丢失，用户也能通过从任意k+12个以上未损坏节点的存储数据包还原出原来的k个源数据包。与具有代表性的基于LT码的算法相比，本文算法将存储过程中每个源数据包在网络中的通信次数从约nlnn降到了约n；同时，本文算法也将存储完成之后，用户为获取源数据包而需要访问网络节点的个数从大于k+100降到了约k+12。本文算法的可行性和有效性在数值实验中得到了验证。
[Abstract]:In order to ensure the safety and reliability of the storage data , it is inevitable to introduce the data redundancy method into the network distributed storage system in order to ensure the safety and reliability of the data .

This paper presents a new method of data redundancy , which is based on random matrix theory , and studies its application in two types of network distributed storage environment _ distributed data disaster storage and sensor network data storage environment . The main research results include the following aspects :

1 . A randomized data redundancy method with excellent performance is proposed .

This paper presents a new kind of randomized data redundancy method which can meet the above requirements . In this paper , a new kind of randomized data redundancy method is proposed , which is based on the random matrix on the binary domain , and the detailed file storage , reading and repair algorithm are presented .
the high probability property of the full rank of the random matrix ensures the high fault tolerance capability and the low storage redundancy of the redundancy method ;
meanwhile , the conversion between the source file and the redundant file is carried out only by XOR operation , the calculation complexity is reduced , and the processing speed of the file is improved ;
In addition , the sparsity of the random matrix also effectively reduces the repair bandwidth required to repair the missing partial redundant file data ;

2 . A low redundancy data disaster recovery scheme based on a randomized data redundancy method is proposed .

This paper presents a kind of data disaster recovery scheme with low storage redundancy . This paper presents a kind of data disaster tolerance scheme with low storage redundancy on the basis of duplication redundancy method . In this paper , the cost of storage space of the system can be reduced to the approximate theoretical minimum value under the precondition of providing the same disaster tolerance . The feasibility and effectiveness of this paper are verified in the relevant experiments .

3 . Based on the data redundancy method , a distributed storage algorithm with low communication cost and low access cost for unattended sensor networks is proposed .

An unattended sensor network can be regarded as a kind of special network distributed storage system without routing table . The purpose of this paper is to sense the data and store the perceived data reliably in the whole network .
At the same time , the algorithm also reduces the number of access network nodes from more than k + 100 to about k + 12 for acquiring source data packets . The feasibility and effectiveness of the algorithm are verified in numerical experiments .
【学位授予单位】：电子科技大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：TP333

【相似文献】