收藏本站  |  English  |  联系我们  |  中国科学院
   
 
       
    科普首页
    微电子历史
    行业动态
    术语解释
    无微不至
    芯片制程
    科普创意
     
(A-26)浅析大数据时代的存储可靠性增强技术(刘海洋)
2017-07-28 | 编辑: | 【 【打印】【关闭】

汽车电子中心 刘海洋

  随着半导体和互联网等新兴技术的出现和发展,人们已经进入了大数据(Big Data)时代,数据存储量正在以惊人的速度增加。如果存储设备的某个存储单元发生故障,其中的存储数据就会丢失,从而造成损失。这一问题在大数据时代显得尤为突出。因此,目前业内主流存储公司(例如微软、谷歌、百度等)都采用了可靠性增强技术,对存储数据进行保护。

  可靠性增强技术的基本方法是对原始数据增加一定冗余(Redundancy)[1],使得用户在读取数据时,如果有存储单元出现故障,可以尽量利用冗余数据恢复出原始数据。本文浅析了当前业界存储系统中使用的两种可靠性增强技术——数据复制(Replication)和删除编码(Erasure Coding)对存储数据保护的原理。

  数据复制是一种最简单也是最常用的增加冗余的方法。图1给出了这种方法的示意图。

  

  1 采用数据复制的存储过程示意图

  在图1中,每个方框代表一个存储单元。蓝色存储单元中的数据为原始数据,粉色存储单元中的数据为原始数据的复制。每个数据复制成为三份相同的数据进行存储。用户在数据读取时,依次对三份数据进行读取。若三份数据均读取失败则原始数据读取失败;否则,将读取的任意一份数据作为相应的原始数据。可以看出,只要三份相同数据中有一份可以读出,就可以得到原始数据。

  但是,采用上述复制方法,存储利用率只有1/3。也就是说,仅有1/3的空间用来存储有效数据,另外2/3的空间存储的是冗余数据。因此,存储利用率相对较低。为了克服这一问题,一些新颖的增加冗余的方法应运而生。其中删除编码是一种常用的方法。

  删除编码的基本思想是将需要存储的数据分成每K个一组,通过特定的编码方式,增加个冗余数据,构成个数据进行存储。选择的编码方式具有如下特征:若在N个数据中可以读取任意不少于K个数据,就能恢复全部K个原始数据。删除编码的数据编码及其读取方法均基于多项式(Polynomial)求值进行的。下面以, 为例说明其基本原理。

  

  2 采用删除编码的存储过程示意图

  如图2所示,假定需要存储的两个数据为字符AB。下面求取增加的一个冗余数据。在ASCII[2]中查得ABASCII值分别为6566。假定它们在平面直角坐标系中对应两个点,坐标分别为A(1,65), B(2,66),如图3所示。

  

  3 删除编码求取冗余数据示意图

  由平面几何知识可知,这两个点唯一确定一条直线。利用点A和点B的坐标可以求得该直线的函数方程为。增加冗余数据的方法是计算该函数在其它某个给定点的函数值。假定冗余数据对应,经计算可知其对应函数值为67,查ASCII表可知对应的字符为C。数据存储过程见图2,其中蓝色存储单元中的数据为原始数据,粉色存储单元中的数据为冗余数据。需要指出的是,对于用户来说,原始数据和冗余数据对应点的纵坐标是需要读取或者计算得到的,但是横坐标是预先知道的。下面分为三种情况讨论数据读取过程。

  情况一:假定在数据读取中前两个存储单元都没有发生故障。根据数据的排列方式,依次取这两个存储单元中的字符,就得到了原始数据。需要说明的是,由于第三个存储单元中存储的是冗余数据(C),因此无论其是否故障都不影响原始数据(AB)的读取。

  情况二:假定在数据读取中第一个存储单元出现故障,后两个单元中的数据可以读取。此时可以得到点B和点C的坐标(2,66)(3,67)。利用这两个点的坐标,可以求得通过BC的直线方程。由于第一个存储单元中的数据的对应点也在这条直线上,且横坐标。因此,计算该点的函数值并查ASCII表可知对应的字符为A。此时,两个原始数据都可以成功读取。

  情况三:假定在数据读取中第二个存储单元出现故障。与情况二完全类似,这时也可以成功读取两个原始数据。

  综合上面的分析可知,只要可以读取任意不少于2个数据,就可以保证恢复出全部2个原始数据字符AB

  一般地,若删除编码的参数为NK,则原始数据对应平面的K个不同点。根据代数知识可知,这K个点可以确定一个次数不超过K的多项式函数。求取冗余数据的方法可归结为计算该函数在其它个给定点的函数值。在数据读取时,若原始数据有些不能读取,但能够读取的数据数目不少于K,就可以通过求解线性方程组得到(即求出系数),进而得到原始数据对应的K个点的函数值,恢复出原始数据。

  需要指出的是,在实际存储中,上述多项式不是定义在实数集上,而是定义在一种特殊的代数系统——有限域(Finite Field)上。由于篇幅所限,对于有限域的基本知识和相关运算就不加以介绍了,感兴趣的读者请参考文献[3]

  不难看出,上述删除编码的存储利用率为K/N。通过恰当选择参数NK(例如,NK典型的取值为1410),可以使得其存储利用率高于复制方法。但是,从数据读取来看,删除编码比复制方法要复杂。此外,删除编码对数据的保护能力比复制方法可能要差一些。

  在大数据时代,可靠性增强技术在数据存储系统中发挥着非常重要的作用。随着存储系统的不断发展,新颖的可靠性增强技术也在不断涌现。希望读者通过本文的介绍对这一技术有初步了解,并能产生兴趣,从而进一步探索,发现更多有意义的结论。

  参考文献:

  [1] 李挥,侯韩旭. 分布式存储编码与系统[M]. 北京:科学出版社,2016.

  [2] 谭浩强. C程序设计(第四版)[M]. 北京:清华大学出版社,2010.

  [3] 冯克勤,廖群英. 有限域及其应用[M]. 大连:大连理工大学出版社. 2011.



 
    中国科学院微电子研究所版权所有 邮编:100029
单位地址:北京市朝阳区北土城西路3号,电子邮件:webadmin@ime.ac.cn
京公网安备110402500036号