EC存储原理初探

---

1.副本orEC？

把一个文件放进磁盘很难吗？不难，放进去就是了。

那么如果是特别重要的文件呢？也不难，多放几份就是了。

还记得怎么对待毕业论文的吗，电脑里存一份，U盘里存一份，网盘里再存一份，甚至好几个网盘里都存一份。内心战战兢兢，生怕几个月的努力（并没有。。。）付诸东流。这，就是副本存储。

假设我们的存储是以三副本方式进行的话，我们可以计算出实际利用率是一个很低很低的值，33.3%。那么有没有什么更好的办法呢，有，就是纠删码的方案。

利用纠删码储存文件，一共分三步:

• 把一个文件均分为K个数据块
• 将这K个数据块通过一定的方式联系起来生成M个校验块
• 当某几个数据块丢失时，利用校验块重新计算出丢失的数据块

以K，M取值为5、3为例，可以得出纠删码方案的利用率达到了5/8，62.5。在同样可以容忍丢失三个数据块的情况下，纠删码方案比副本方案容量利用率高出了近一倍！

可以看到重点就在于，如何计算出校验块以及如何利用其进行数据恢复，接下来就讲重点介绍这两部分，这，也就是EC的原理。

注意：这里的文件并不是指真实的文件，比如一首歌曲或者一部电影，而是由存储系统对真实文件进行条带化后生成的更小的文件。

2.EC原理

2.1 校验数据生成

• 可以丢失一个数据的EC算法

一部电影太大了，我们不妨以一个很简单的例子入手，比如存几个整数，

如果怕d1,d2,d3的某一个数据可能会丢失，那么我们就需要利用这三个数据通过计算来生成一个新的校验数据。说白了，一个最简单的方式就是，

直接保存一个三者相加的值，那么当其中一个数据丢失，就可以通过c1减去另外两个数据来进行恢复。
到此，一个最简单的可以允许一个数据丢失的EC算法就构造成功了。

• 可以丢失两个数据的EC算法

与丢失一个数据类似，我们会很容易想到，直接再构造一个校验块，比如，

但是这样真的可以吗，仔细想来，这是个非常蠢的做法，如果真的丢失了两个数据，这两个一模一样的方程根本无法解出两个未知数，因为有两个未知数但只有一个有效的方程。那么这两个方程的系数向量有什么关系呢，这里引入一个线性代数的定义，它们线性相关。也就是说其中一个可以被另外一个线性表示。

知识点：线性相关。还不懂的同学自己回炉~

于是，我们可以改变c2方程的系数，随便取一个，让它和另一个线性无关，比如：

显然，我们可以用初中一年级学到的解二元一次方程的方法轻易地将丢失的两份数据恢复（就是解出来了那俩值）。

• EC算法推广

如果，我们把上面的方程写成矩阵乘法的形式，如下，

通过上文的分析，我们可以用非常朴素（low）的数学思想总结，当生成矩阵（就是校验公式的系数矩阵）的行向量两两不相关时，生成的校验数据可以在丢失数据时将其恢复。此时，如果我们回忆下大一的线性代数的知识，其实这就是要求生成矩阵可逆。

知识点：逆矩阵。

两个矩阵相乘等于单位矩阵，就称它们互为逆矩阵。

刚才我随便取了c2的系数为7 6 3（其实是我的UM帐号后缀。。。），它恰巧是可行的，但是在有多个的情况下，需要有一个规律性的生成矩阵的取值，且保证这个矩阵可逆。比如，我们可以用下面这个规律，

这，就是传说中的范德蒙德矩阵。之所以用这个矩阵最重要的一点是它保证了矩阵的可逆性，也就是保证了求解的唯一性。

2.2 数据恢复

上文中，我们知识讨论了校验数据块的生成，那么，如果在丢失了某个或者某几个数据后，如何通过矩阵计算来进行数据恢复呢？

现在我们把上文的生成矩阵进行一下扩展，在其上面加一个单位矩阵，这样让数据块和校验块做一个统一，

不妨，我们举个具体的例子，还以我们最开始讲的KM比例5/3来算，

其中，5,2,8,7,0为数据块，22, 61, 197为范德蒙矩阵生成的校验块。现在我们来看下，22, 61, 197这三个校验块到底能不能在丢失数据块的时候将数据恢复出来。

如果非要纠结数据块数字的意义的话，它是我的分机号码。。

假设在一个极端情况下，五个数据块丢失了三个，也就是可以容忍的最大数量，比如，丢失了

5,2,8，此时把丢失的数据块和其对应的声称矩阵的行去掉，然后用生成矩阵的逆矩阵乘以校验块和剩余的数据块组成的矩阵。

F = [0,0,0,1,0;0,0,0,0,1;1,1,1,1,1;1,2,3,4,5;1,4,9,16,25];
F_INV = inv(F); %求F的逆矩阵
C = [7;0;22;61;197];
D = F_INV*C;
D = 
    5.0000
    2.0000
    8.0000
    7.0000
         0

可以看到，丢失的数据得到了完美的还原。