一 RS大致的工作流程
上一篇提到，我们要提高系统整体可靠性并且降低成本，只能用RS编码了。
那么RS是如何工作的？它是如何提高可靠性？如何降低成本的？我之前所说的范德蒙矩阵，柯西矩阵，有限域运算等等等是嘛玩意？那么，在本篇中，我会做一个简要的介绍。深入一点的数学内容我会另外开篇。
就坐这里随便想象的话。纠删码听上去实在是门可怕的技术——好好的一份数据，它可以是视频可以是图片等等等，我们居然可以根据自己的要求对其的“副本”进行”压缩“？照这个思路走下去，那简直是茫然不知所措。
我们先来确定一下我们想要的结果，然后看看有没有什么技术可以满足这样的需求：
1. 编码必须是systematic. 也就是说origin data不会因为编码而改变，至多被切割分布在不同的磁盘之上（肯定是分布在不同磁盘之上，因为如果在一块盘上，那这块盘死了，数据全没了）
2. parity的数目可以达到或者超过3
3. 计算负荷在可以承受的范围内
为什么照“刚才”的副本思路走是不对的呢？因为副本是相对独立的，它可以自行计算出完整的数据。但是erasure code是非独立的，它的计算依赖于其他symbol一起来得到结果。因此，overhead可以做到1以下。
我们假设剩余的内容为A，B , C , D丢失的内容为L，他们的运算结果是P，那么最简单的形式就是：
A + B + C +D + L = P
这种形式最简单的实现就是RAID5中的异或运算，但是其只能满足parity为1的要求。如果增加parity呢？
通过小学体育老师的数学教育，我们知道解一个未知数至少需要一个方程，解两个未知数需要两个方程。因此，我们在RAID5的基础之上，再引入事先规定好的系数（保存在运算规则里），则可以得到另一个parity：
c1A + c2B + c3C +c4D + c5L= Q
那么为了更多的parity我们继续引入一套系数，依次类推，我们将得到足够的parity.
我们同时发现，引入系数之后，2进制貌似不够用了啊。
那就升级位数呗。
RS的雏形其实就已经有了。
我们把待编码块表示出来，不就是一个矩阵吗？我们引入m套系数不就是另外一个矩阵吗？我们运算先要得到原始数据，这不就是单位矩阵的乘法运算吗？另外，我们要计算结果的word在一定范围之内这不就是有限域计算吗？只不过异或是个最简单的表现形式。
我们要在数据丢失的情况下，得到原始数据。只要保证结果的各行之间线性无关，不就可以利用两边各乘上运算矩阵（即与原始矩阵相乘的矩阵）的逆矩阵，得到原始数据了吗？
然后我们要提高计算速度。那么运算矩阵要想办法引入一个能保证结果线性无关，又能比较快的计算逆矩阵的矩阵。再就是利用一些数学技巧降低有限域计算的复杂度。
二 RS的图形化表达
刚才分析了得到这个算法在直觉上的思路，现在我们看看用直观的图形表达来认识这个算法的过程。
B*D=(D + C)
这里的B的下半部分即柯西矩阵（我这里直接介绍Cauchy Reed-Sololmon code，即CRS）。后面的Galois Field multiplications转换为XORs.至于柯西矩阵是什么样的形式，相较于范德蒙矩阵为什么有优势，以及有限域的运算如何转换为XORs我在这里就不多加阐述了。
那么，当有磁盘上西天的时候，我们怎么修复数据呢？假设坏了三块盘：
D1 D4 C2死掉了
我们计算B‘的逆矩阵，可得下面的式子：
也就是：
这样就把数据给解出来了。
但是，大家肯定也发现了一个问题，就是恢复数据的过程的repair traffic很高。
我们都知道，在一个大型分布式系统中。网络资源是非常宝贵的，如此浪费行为不仅仅是钱的问题，还会影响整个系统的生态平衡。
三 利用LRC减少修复时网络负载
LRC，即Locally Repairable Codes. 该方案已经在Azure和facebook上稳定运行多时。上面的RS举的例子我们可以简单的称之为5+3或（5，3）的方案，storage overhead是60%.但是Facebook的LRC方案则看上去有点奇怪(10,6,5),storage overhead也是是60%.
更有意思的是Facebook原先的方案是RS（10，4），然后他们仅小改一下就平滑过渡到了(10,6,5)的LRC
越说越糊涂，越描越黑了。
我们来看看，facebook自己给自己的方案画的图：
画了个图就非常清晰了。原先（10，4）的底子还在。只不将10块原始数据分成两组分别计算出一块冗余。
显然，坏两块盘的几率要远小于一块盘。这样一来，我们修复一块坏盘的时候，调用一下本地的其他盘就够了。在绝大部分情况下，我们的repair traffic减少了一半。
有些朋友反应很快，这本地组不就是RAID5吗？
然而，用RAID5固然是可以，但冗余就会比原来多3，而不是2了。（注意看上图的虚线部分）
也就是说，我们通过选取合适的系数，使得S3可以通过S1,S2算出来。facebook的方式是使得
S1+S2+S3=0. 这样的话，overhead=6/10=60%
每一组LRC可以容忍5-6块盘坏掉，其可靠性介于(10,5)到（10，6）之间。但减少了修复时的网络开销。实践证明，这样的取舍是值得的。
网友评论