随着半导体和互联网等新兴技术的出现和发展，人们已经进入了大数据(Big Data)时代，数据存储量正在以惊人的速度增加。如果存储设备的某个存储单元发生故障，其中的存储数据就会丢失，从而造成损失。这一问题在大数据时代显得尤为突出。因此，目前业内主流存储公司(例如微软、谷歌、百度等)都采用了可靠性增强技术，对存储数据进行保护。
可靠性增强技术的基本方法是对原始数据增加一定冗余(Redundancy)[1]，使得用户在读取数据时，如果有存储单元出现故障，可以尽量利用冗余数据恢复出原始数据。本文浅析了当前业界存储系统中使用的两种可靠性增强技术——数据复制(Replication)和删除编码(Erasure Coding)对存储数据保护的原理。
数据复制是一种最简单也是最常用的增加冗余的方法。图1给出了这种方法的示意图。
图1 采用数据复制的存储过程示意图
在图1中，每个方框代表一个存储单元。蓝色存储单元中的数据为原始数据，粉色存储单元中的数据为原始数据的复制。每个数据复制成为三份相同的数据进行存储。用户在数据读取时，依次对三份数据进行读取。若三份数据均读取失败则原始数据读取失败；否则，将读取的任意一份数据作为相应的原始数据。可以看出，只要三份相同数据中有一份可以读出，就可以得到原始数据。
但是，采用上述复制方法，存储利用率只有1/3。也就是说，仅有1/3的空间用来存储有效数据，另外2/3的空间存储的是冗余数据。因此，存储利用率相对较低。为了克服这一问题，一些新颖的增加冗余的方法应运而生。其中删除编码是一种常用的方法。
删除编码的基本思想是将需要存储的数据分成每K个一组，通过特定的编码方式，增加
个冗余数据，构成
个数据进行存储。选择的编码方式具有如下特征：若在N个数据中可以读取任意不少于K个数据，就能恢复全部K个原始数据。删除编码的数据编码及其读取方法均基于多项式(Polynomial)求值进行的。下面以
, 
为例说明其基本原理。
图2 采用删除编码的存储过程示意图
如图2所示，假定需要存储的两个数据为字符A和B。下面求取增加的一个冗余数据。在ASCII表[2]中查得A和B的ASCII值分别为65和66。假定它们在平面直角坐标系中对应两个点，坐标分别为A(1,65), B(2,66)，如图3所示。
图3 删除编码求取冗余数据示意图
由平面几何知识可知，这两个点唯一确定一条直线。利用点A和点B的坐标可以求得该直线的函数方程为
。增加冗余数据的方法是计算该函数在其它某个给定点的函数值。假定冗余数据对应
，经计算可知其对应函数值为67，查ASCII表可知对应的字符为C。数据存储过程见图2，其中蓝色存储单元中的数据为原始数据，粉色存储单元中的数据为冗余数据。需要指出的是，对于用户来说，原始数据和冗余数据对应点的纵坐标是需要读取或者计算得到的，但是横坐标是预先知道的。下面分为三种情况讨论数据读取过程。
情况一：假定在数据读取中前两个存储单元都没有发生故障。根据数据的排列方式，依次取这两个存储单元中的字符，就得到了原始数据。需要说明的是，由于第三个存储单元中存储的是冗余数据(C)，因此无论其是否故障都不影响原始数据(A和B)的读取。
情况二：假定在数据读取中第一个存储单元出现故障，后两个单元中的数据可以读取。此时可以得到点B和点C的坐标(2,66)和(3,67)。利用这两个点的坐标，可以求得通过BC的直线方程。由于第一个存储单元中的数据的对应点也在这条直线上，且横坐标
。因此，计算该点的函数值并查ASCII表可知对应的字符为A。此时，两个原始数据都可以成功读取。
情况三：假定在数据读取中第二个存储单元出现故障。与情况二完全类似，这时也可以成功读取两个原始数据。
综合上面的分析可知，只要可以读取任意不少于2个数据，就可以保证恢复出全部2个原始数据字符A和B。
一般地，若删除编码的参数为N和K，则原始数据对应平面的K个不同点。根据代数知识可知，这K个点可以确定一个次数不超过K的多项式函数
。求取冗余数据的方法可归结为计算该函数在其它个给定点的函数值。在数据读取时，若原始数据有些不能读取，但能够读取的数据数目不少于K，就可以通过求解线性方程组得到
(即求出系数
)，进而得到原始数据对应的K个点的函数值，恢复出原始数据。
需要指出的是，在实际存储中，上述多项式不是定义在实数集上，而是定义在一种特殊的代数系统——有限域(Finite Field)上。由于篇幅所限，对于有限域的基本知识和相关运算就不加以介绍了，感兴趣的读者请参考文献[3]。
不难看出，上述删除编码的存储利用率为K/N。通过恰当选择参数N和K(例如，N和K典型的取值为14和10)，可以使得其存储利用率高于复制方法。但是，从数据读取来看，删除编码比复制方法要复杂。此外，删除编码对数据的保护能力比复制方法可能要差一些。
在大数据时代，可靠性增强技术在数据存储系统中发挥着非常重要的作用。随着存储系统的不断发展，新颖的可靠性增强技术也在不断涌现。希望读者通过本文的介绍对这一技术有初步了解，并能产生兴趣，从而进一步探索，发现更多有意义的结论。
参考文献：
[1] 李挥，侯韩旭. 分布式存储编码与系统[M]. 北京：科学出版社，2016.
[2] 谭浩强. C程序设计(第四版)[M]. 北京：清华大学出版社，2010.
[3] 冯克勤，廖群英. 有限域及其应用[M]. 大连：大连理工大学出版社. 2011.
科学普及