根据范德蒙矩阵的Erasure code技能详解51CTO博客 - 牛牛娱乐

根据范德蒙矩阵的Erasure code技能详解51CTO博客

2019-01-03 13:17:13 | 作者: 谷芹 | 标签: 矩阵,数据,德蒙 | 浏览: 803

在传统存储范畴,跟着磁盘容量的不断增大,RAID数据重构时刻将会是一个非常严峻的问题。咱们知道,过长的数据重构时刻意味着数据可靠性下降。所以,在RAID规划的进程中,一定要考虑数据重构的时刻,并且尽可能的将“无数据维护状况”的时刻降到最小。在不改动传统RAID架构前提下,只能经过添加数据冗余度来缓解大容量磁盘引进的超长数据重构时刻的问题。这种思路就比如几年前,当RAID5无法满意过长数据重构时刻时,只能被逼选用RAID6算法,经过RAID6能够供给两块盘的冗余度来缓解长时刻数据重构的问题。跟着时刻的推移,现在,在许多使用中,RAID6也无法满意使用需求了。为了到达更高的数据冗余度,一个比较不错的挑选是选用冗余度更大的编解码办法:Erasure Code。许多公司将根据这种编码办法的RAID称之为RAID7。

在互联网范畴,一般选用Server SAN的存储架构办法。也便是将廉价的Server经过集群软件的办法组成一套分布式的存储体系。Google首要倡议了这种办法,架构了GFS体系,将许多非格局化的数据(例如网页)存储到这种分布式体系中。一般,这种廉价的Server是不具备RAID功用的,那么数据可靠性怎么确保呢?在这种Server SAN中,一般会将数据仿制多份存储到不同的节点上,一旦一个节点失效,数据能够从其它节点上获取。数据多节点仿制的办法能够很好的进步数据可靠性,并且能够将读写数据流很好的别离。可是,带来的问题是存储利用率大为下降。关于一般的数据,一般会存储三份,关于非常重要的数据,会存储六份。怎么平衡存储空间和数据可靠性成了分布式存储需求考虑的重要问题。Erasure Code能够平衡这两者联系,在进步存储空间利用率的前提下,不会影响数据可靠性。选用Erasure Code对数据进行编码冗余的办法和“网络RAID(RAIN)”的概念是很相像的。当互联网范畴引进Erasure Code之后,需求考虑的问题是怎么下降编解码的运算复杂度问题。

现完结已证明,Erasure Code作为一种数据编解码技能在大数据环境下有了非常火急的需求。不只传统的RAID需求这种技能,并且分布式存储也需求这种技能去提高存储资源利用率。

常用的Erasure code是根据范德蒙(Vandermonde)矩阵的RS算法。其基本思想很简单,选用范德蒙矩阵作为生成矩阵,得到校验数据。现假定输入数据为D1~Dn,生成的校验数据为C1~Cm,那么输入数据和校验数据之间的联系能够描绘为:

 

 

其间,

 

 

 

为范德蒙矩阵,该矩阵为编码矩阵。所以,为了得到校验数据,首要的使命是将输入数据和编码矩阵相乘,得到的输出成果便是编码值。为了能够更好的表明磁盘上存储的数据,一般将编码矩阵方程表明如下:

 

 

 

能够发现这个生成矩阵(A)便是单元矩阵和范德蒙矩阵的组合。输入数据(D)和生成矩阵(A)的乘积便是编码之后的存储数据(E)。选用传统RAID的思路去了解,编码之后的成果便是一个条带需求存储的一切数据。

编码进程咱们现已很清楚了,生成矩阵的格局很规整。那么,问题是怎么进行解码操作呢?当存储的数据d1~dn,c1~cm中有些数据无法读取时,怎么进行数据康复呢?从数学的原理来看,只要将读取的有用数据和生成矩阵的逆矩阵相乘就能够康复丢掉的数据。假定m个数据块丢掉,则能够将m个数据块对应的矩阵A和E中的行删掉,得到新的n*n阶生成矩阵A2和1*n阶成果矩阵E2。因为生成矩阵是有范德蒙矩阵和单元矩阵的组合,所以,矩阵A的恣意n行子集都能够确保线性无关。因而,需求康复的数据能够经过A2和E2 的逆矩阵乘积得到,即D=逆(A2)*逆(E2)。

从数学的视点来看,咱们现在常用的RAID5和RAID6算法仅仅范德蒙矩阵算法的一个子集罢了。当冗余数据只要一个的时分,就退化成了RAID5算法,在实数域只需求将输入数据累加就能够得到校验码了。为了简化核算复杂度,编解码运算放到了迦罗话域,加法运算变成了XOR逻辑运算。当冗余数据有两个的时分,范德蒙矩阵退化成了RAID6算法,也能够在迦罗华域经过查表、XOR的办法完结运算。详细能够参阅文章《一个IO的传奇一生(12)-- 磁盘阵列1》。

从这个视点来看,根据范德蒙矩阵的Erasure Code办法是传统RAID5/RAID6算法的扩展。在完结进程中,相同能够在迦罗华域中完结乘、除和加减法运算。为了完结快速算法,需求构建两张对数表和对立数表,然后经过查表和XOR运算快速完结编解码。

根据范德蒙矩阵的Erasure Code编解码原理比较简单,能够说是在RAID5/RAID6算法基础上的一种延伸。选用这种办法的算法复杂度仍是比较高的,编码复杂度为O(mn),其间m为校验数据个数,n为输入数据个数。解码复杂度为O(n^3),解码具有较高的核算复杂度。

 

 

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表牛牛娱乐立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章