纠删码（Erasure Code）浅析

【摘要】：副本策略和纠删码是存储领域常见的两种数据冗余技术。相比于副本策略，纠删码具有更高的磁盘利用率。 Reed-Solomon码是一种常见的纠删码。

多副本策略即将数据存储多个副本（一般是三副本，比如HDFS），当某个副本丢失时，可以通过其他副本复制回来。三副本的磁盘利用率为1/3。

纠删码技术主要是通过纠删码算法将原始的数据进行编码得到冗余，并将数据和冗余一并存储起来，以达到容错的目的。其基本思想是将n块原始的数据元素通过一定的计算，得到m块冗余元素（校验块）。对于这n+m块的元素，当其中任意的m块元素出错（包括原始数据和冗余数据）时，均可以通过对应的重构算法恢复出原来的n块数据。生成校验的过程被成为编码（encoding），恢复丢失数据块的过程被称为解码（decoding）。磁盘利用率为n/(n+m)。基于纠删码的方法与多副本方法相比具有冗余度低、磁盘利用率高等优点。

两种冗余技术对比如下表：

两种技术	磁盘利用率	计算开销	网络消耗	恢复效率
多副本(3副本)	1/3	几乎没有	较低	较高
纠删码(n+m)	n/(n+m)	高	较高	较低

Reed-Solomon(RS)码

Reed-Solomon（RS）码是存储系统较为常用的一种纠删码，它有两个参数n和m，记为RS(n,m)。n代表原始数据块个数。m代表校验块个数。接下来介绍RS码的原理。

RS码原理

以n=5，m=3为例。即5个原始数据块，乘上一个(n+m)*n的矩阵，然后得出一个(n+m)*1的矩阵。根据矩阵特点可以得知结果矩阵中前面5个值与原来的5个数据块的值相等，而最后3个则是计算出来的校验块。

Paste_Image.png

以上过程为编码过程。D是原始数据块，得到的C为校验块。

假设丢失了m块数据。如下：

丢失m块

那我们如何从剩余的n个数据块（注意，这里剩余的n块可能包含几个原始数据块+几个校验块）恢复出来原始的n个数据块呢，就需要通过下面的decoding（解码）过程来实现。

第一步：从编码矩阵中删去丢失数据块和丢失编码块对应行。 将删掉m个块的(n+m)*1个矩阵变形为n*1矩阵，同时B矩阵也需要删掉对应的m个行得出一个B'的变形矩阵，这个B'就是n*n矩阵。如下：假设D1、D4、C2丢失，我们得到如下B’矩阵及等式。

vandermode矩阵

第二步：求出B’的逆矩阵。

B’逆矩阵

第三步：等式两边分别乘上B’的逆矩阵。

两边乘上B’逆矩阵

B’和它的逆矩阵相乘得到单位矩阵I，如下：

单位矩阵

左边只剩下原始数据矩阵D：

Paste_Image.png

至此完成解码过程。

注：图中黄色部分为范德蒙矩阵。至于如何生成B矩阵，以及如何求B’的逆矩阵，请查看其他相关文献，这里不再赘述。

小结

RS的特点：

• 低冗余度，高磁盘利用率。
• 数据恢复代价高。 丢失数据块或者编码块时， RS需要读取n个数据块和校验块才能恢复数据， 数据恢复效率也在一定程度上制约了RS的可靠性。
• 数据更新代价高。 数据更新相当于重新编码， 代价很高， 因此常常针对只读数据，或者冷数据。

工程实践中，一般对于热数据还是会使用多副本策略来冗余，冷数据使用纠删码。

值得期待的是，纠删码技术也即将在Hadoop 3.0中发布。

参考资料

• 论文《Erasure Codes for Storage Applications》
• 论文《存储系统中纠删码研究综述》

FullStackPlan

欢迎关注公众号: FullStackPlan 获取更多干货哦~