纠删码理论介绍

1 什么是EC？

EC：纠删码-Erasure Code，是一种编码理论：

• EC是纠错码的一种，通过增加校验片，保证数据可靠性。
• 特性：将数据分成k个分片，生成m个校验片，假设n=k+m，在n个分片中任意选取k个分片，就可以将原始数据恢复回来。

EC不仅应用在存储领域，通信领域也是EC的主要应用场景。

2 EC(4+2)编解码简介

上图可以简单说明EC(4+2)的编码、解码以及故障恢复的主要流程，包括：

• chunk：将数据进行分片，如图分成4个片：d1、d2、d3、d4.
• encode：根据4个数据片，生成2个校验片（生成校验片的逻辑请看下一节），这样就形成4+2的EC数据片
• 故障：4+2的EC，允许这6个数据片任意损坏2个，假如损坏了d2和c1，如图
• decode：通过d1、d3、d4、c2，根据EC的计算，可以算出原始的数据块
• re-encode：将原始的数据块分成d1、d2、d3、d4，再次计算出c1、c2
• replace：将损坏的数据块d2、c1进行替换掉即可

可以发现EC的故障恢复比副本更复杂，副本直接再copy一份即可，但是EC比副本的优势是成本，相比于3副本，EC在保证同样可靠性的同时，并不需要保存3份数据。

3 EC的数学原理

其中：

• B是一个(5+3)行5列的矩阵，这个矩阵有这样的特点，任意5阶方阵都是一个可逆矩阵
• D是数据，分成了5等份，D1~D5

根据矩阵乘法，B * D 的结果是一个刚好是(5+3)行1列的矩阵，即：D1、D2、D3、D4、D5、C1、C2、C3，这种(5+3)的EC策略是允许任意3份的丢失。

假如D1、D4、C2损坏了，那么依然存在这样的等式：B’ * D = D2、D3、D5、C1、C3，如上图2.中的等式

由于B’存在可逆矩阵，那么两边同时乘以B’的可逆矩阵，得到上图4.等式，那么就到的原始数据D：D1、D2、D3、D4、D5。

最后，B * D就能把损坏的D1、D4、C2计算出来，进而达到故障恢复。

说明

符合B矩阵要求的，有：

• 范德蒙矩阵：就是高等数学里面我们学过的那个范德蒙矩阵
• 柯西矩阵：应该也学过
• 其他符合要求的矩阵

4 EC存储的优缺点

优势

• 磁盘利用率高，存储成本低，通常是3副本存储的一半，甚至更低
• 和3副本相比，有较低的网络开销，尤其在write的时候表现明显

劣势

• 在编、解码过程中通常有较大的CPU占用和网络开销，主要体现在write和故障read、故障恢复的情况下
• EC必须满条带的读写，不足条带的情况下会有padding
• 和3副本相比，EC存储系统更复杂，集群稳定性挑战更大

EC编码的缺点，使得EC最开始并没有应用在线数据，一般都是应用在低频存储中，何为低频存储，就是访问频次较低数据的存储系统中，不过目前已经有的在线存储也开始使用EC编码了。