分布式系统下的纠删码（二） -- Locally Repairable Codes (LRC)
一、 名词解释
MDS： Maximun Distance Separable.
|
|
MDS 性质:是纠删码的一个重要性质，它保证n=k+m个磁盘中任意k个磁盘都可恢复出k个数据盘，或可表示为该编码容忍任意m=n-k个磁盘发生故障，而数据不发生丢失。传统的RS码、CRS码都具有MDS性质，最近提出来的一些编码往往牺牲MDS性质（Rotated RS，Local Repair Codes等），减少修复开销
这里所说的“LRC牺牲MDS性质”，本文后面会讨论LRC的容错能力，可以解释这句话。
二、LRC的原理
本文默认您已经读过本文的前一篇关于EC编码的介绍，以及理解了前一篇关于EC的编码和解码过程（有例子解释）。
EC编码的介绍：http://blog.csdn.net/u011026968/article/details/52295666
1、LRC与EC
LRC和EC的不同在于，EC只有两种类型的chunk，data chunk和code chunk， 其中每个code chunk都是其他所有的data chunk的线性组合，也就是每个code chunk和其他所有的data chunk都是有关系的，称之为global code chunk。LRC和EC不同的地方在于，LRC多了一种local code chunk，local code chunk和global code chunk的不同在于，local code chunk只与部分data chunk有关系，而global code chunk和所有的data chunk都有关系。比如：
（PS:这个LRC是新浪的LRC算法库的构造方法）
这个例子中，编码过程如上图，可以看出
| C0=D0+D1 C1=D2 上面两个code chunk只和部分Data chunk有关，也就是所谓的”local”的意思 C2= D0+2*D1+4* D2 这个code chunk和所有的Data chunk都有关系，称为global code chunk |
2、LRC的原理简述
本质上，其实，上面的Datachunk被分成了两组EC组，C0 D0 D1这三块是一个小的EC组，如果这个组里面坏掉任何一块chunk，那么可以通过其他两块恢复，C1和D2这一组也是一样的，坏掉任何一块都是可以通过本组里面的数据恢复的。这个时候，要恢复数据，需要的源数据块数< k， k是data chunk的总的个数。而EC中，坏掉一块数据，仍然需要拉去k块数据。可以看出LRC在某些情况下，做数据的恢复可以比EC效率高（尤其分布式环境下，少拉去源数据就能少很多通信的代价）。
但是也可以从上面的例子看出新浪的LRC的算法的一点不足，这个LRC的构造可以做到坏掉任何一个data chunk都可以拉取小于k块数据来恢复，但是如果global code坏掉呢，就是C2坏掉呢？必须拉去k块数据才能恢复。
我所做的工作，一是把新浪的LRC库用的范德蒙矩阵换成柯西矩阵（据说柯西矩阵更快），二就是解决上面的问题，最终目标是，坏掉任何一个chunk(无论是local code chunk , data chunk, global code chunk)，都可以拉取小于k块源数据块把丢失的数据恢复出来。
3、改进LRC的方法（我称为C_LRC， C是completely）
其实很简单，加一个数据块，让所有的global code chunk和这个数据块成为一个新的ec组即可。LRC所谓的分组，其实就是分成小的EC组，然后有全局的EC组来辅助。所以这个做法还是很简单的。具体实现看下面部分。（第三部分写的都是LRC，其实都是按照我修改后的LRC也就是C_LRC的例子）
三、LRC编码解码示例
LRC编码解码的例子：
图 1 编码矩阵的结构
1、符号的定义：
data_cnt： 指的是数据块的数目
local code for data: LRC分组的code块
local_data_group_cnt: data的分组的数目，如上图是2。
global code: 通过所有的数据块计算出来的code块
global_code_chunk_cnt：global code 块的个数
local code for global code: global code的local code，也就是这个localcode只和global code有直接的计算关系
2、编码
（1）编码矩阵的构造
可以结合图1和符号定义部分理解编码矩阵的构造.
定义
X:
Y:
Y就是新浪的LRC的编码矩阵，没有local code for global code。为了多一行作为local code for global code，我在新浪的LRC的encode矩阵左乘了一个矩阵X，X是(k + local_data_group_cnt + global_code_chunk_cnt + 1 ) * (k +local_data_group_cnt + global_code_chunk_cnt )的，其中上面的(k +local_data_group_cnt + global_code_chunk_cnt )*(k +local_data_group_cnt + global_code_chunk_cnt )是单位矩阵，下面多了一行，该行的构成是k +local_data_group_cnt 个0后面跟了global_code_chunk_cnt 个系数。我写的这些系数是范德蒙矩阵的第（1+global_code_chunk_cnt ）行（行数下标从0开始）的前global_code_chunk_cnt 个数。实际实现的时候因为我用的intel ec库的cauchy 矩阵，所以选的是cauchy 矩阵的第（1+global_code_chunk_cnt ）行（行数下标从0开始）的前global_code_chunk_cnt 个数。X*Y得到的矩阵就是C_LRC的编码矩阵。
（2）编码过程
换种表示方法，结果一样，过程稍微不一样，这样表示有好处，后面具体说
强调一点：
local code for data:
| C0=D0+D1 C1=D2+D3 |
M:
M=X*Y。
注意到矩阵M的最后一行是与global code对应的编码矩阵的几行是线性相关的。
(2) 解码过程
(a)LRC起作用的时候：一个块丢掉的时候，具体分以下几种情况，分别解释decode的方法：
(a1)丢掉一个data块，比如丢掉D2
此时一个注意点，C0=D0+D1，也就是在global code没参与decode计算的时候，C0对于恢复D2和D3起不到任何作用。
对于丢掉D2的情况，恢复数据只需要数据块：D1 C1，其他数据都不需要。记source[i] ==1为第i个数据块在decode的时候用到
Decode matrix的生成：
（i）选取没有损坏的数据对应的行
（ii）选取Source[i]== 1的code 以及丢掉的code。假设二者数目合起来为n_code。
顺序按照(i) (ii)操作，直到构造出k*k的矩阵，其中k为数据块的个数，此处k=4。
本例中的矩阵为：
记为Z1，
(iii)求Z1的逆矩阵Z1-1，进而求出decode矩阵
逆矩阵：
decode Matrix就是：
式子(a1-1)中的[0 0 -1 1]这个矩阵
这样就求出来了丢失的数据D2
这里其实也可以看出来，求D2虽然用到了D0和D1的行，但是其实完全没有用到相应的数据。我写成式子a1-1的形式，就是为了说明这一点。式子a1-2的形式是为了按照EC解码的原理理解。
(a2)丢失一个local code for data的情况，比如丢掉C0
具体原理同(a1)，所以此处简述推导过程：
恢复数据只需要数据块：D0 D1 ,
生成decodematrix的过程：
(i)选取数据没有损坏的k行生成k*k的矩阵Z
(ii)求Z的逆矩阵
（iii）生成逆矩阵解码：
decode matrix:
解码过程：
一样可以看出，虽然用到了D2D3的行，但是只是在求逆的时候用到，最后生成的decode matrix还是不会用到D2和D3的具体数据。
（a3）丢了一个global code
之前看的新浪的LRC库，这种情况下是按EC搞了，也就是必须拉去至少k个块来恢复。
改进的LRC，这种情况是要用num(globalcode)块数据来恢复。
式子2-2的表示的好处应该可以看出来了，decode相当于针对下面这个矩阵来说的
先说几点结论：
（a3.1）矩阵的行列做交换不影响矩阵是否可逆
（a3.2）如果globalcode对应的行或者local code for global code对应的行去掉，剩下的k*k的矩阵（对于上图而言k=8），是满秩的。这个还是很容易证明的，简单说说把，“如果global code对应的行”去掉，那么剩下的global code和local code for global code对应的行通过加减等操作肯定能把localcode for global code对应的行变成去掉的行，然后可以通过矩阵行列做交换，变成单位矩阵，也就是这个剩下的k*k的矩阵是满秩的，因此必然可逆。
上面其实证明了LRC decode的时候，选择的k*k的矩阵是为什么是可逆的。（我对新浪的LRC做的补充就是让global code和data都是LRC的，也就是all chunk can be repaired locally . 这才是LRC(LocallyRepairable Code)）。
由上面就可以知道globalcode和local code for global code这些块坏掉一块的时候如何恢复。恢复方法和Localcode for data中，一个数据块或者Local code for data块丢掉是完全一样的。不再赘述。
(PS:这种情况下其实我做得更加简单粗暴，我是直接用EC decode做了，也就是把global code 和local code for global code作为一个EC组，矩阵会更小点，EC会更快点吧，当然计算的代价差异很小的)
（a4）丢了local code for global code。跟a3差不多，此处不赘述
（b）丢失多块（>1块）数据，丢失的数据不包含local code for global code。
此时和新浪的LRC是一样的，需要拉取k块数据。（其实是有一些代价可以衡量下选择策略的，比如一种情况：…..）
如上文所述，“矩阵M的最后一行是与global code对应的编码矩阵的几行是线性相关的”，因此当某些情况下，如果globalcode对应的行都选取的话，local code for global code选上是没用的。
举个例子丢2块数据，分别为D0和D1吧。
（i）选取k*k矩阵
(ii)decode的过程
第一步解出所有的data，如下
第二步是解出丢失的数据，也就是上面的式子两边同时乘以丢失的chunk对应的Ecode matrix的行，也就是D0和D1对应的encode matrix的行，即可恢复出来数据，如下
（c）丢失多块（>1块）数据，丢失的数据包含local code for global code。
还是举个例子，假设丢了3块，分别为D1C2 C4，也就是一个data 一个global code，加上local code for global code丢了。
（i）选取k*k矩阵：
（ii）decode 的推导
第一步是解出所有的Data，如下
第二步是恢复出来数据，也就是上面的式子两边同时乘以丢失的chunk对应的Ecode matrix的行，也就是D1 C2 C4对应的encodematrix的行，即可恢复出来数据，过程如下，
你没看错，就是这么简单。
四、 C_LRC的效果分析
1、C_LRC与新浪的LRC
LRC增加一个local code for globalcode和新浪的LRC的对比：
本质上，其实我的LRC也就是对global code做了冗余为1的EC。（当然LRC每个组的本质也就是对某些块做了冗余为1的EC），每多一个分组，也都是冗余chunk的数目加一，提高了decode速度。
2、容错能力
还有一个值得细考虑的问题，增加localcode for global code对容错能力有没有提升？
先看新浪的LRC（没有local code for global code）, 新浪的LRC的容错能力，有可能是3块有可能是4块
比如丢了D1 D0 C0 C2
剩下
显然不可逆。也就没法恢复。
如果丢失
剩下D1 D2 C0 C2
显然是可逆的，而且能计算出来。从这里可以看出来关键在于是不是某一个组的chunk都丢了，这会影响是否能恢复。我们参考这个发现，考虑local code for global code的情况。
如果没有local code for global code， 那么容错能力至少是n-k-local_group_cnt+1，对于本例应该是3，也就是最多丢三块，那么我们此处讨论如果丢了4块是不是能恢复。仍然分两种情况：
（1）丢失的4块里面包含local code for global code和global code中的一块，有一个数据组完全丢失。
假设丢了D1D0 C0 C2，
不考虑local codefor global code的话，此时剩下的4行为：
逆矩阵
于是发现还是可以解码的。
（2）丢失的数据里面包含local code for global code和global code中的2块
此时C4是可以用的，而C4是C3和C2的线性组合，因此可以作为一个Global code用。也就是两个global code 和1个local code for global code这一个组，如果丢了两个，剩下的可以作为一个globalcode用。这样的话，其他的数据丢失任意2个都是可以恢复的。丢失3个有可能不能恢复。比如
丢失了
D1 D0 C0 C2C3
这种情况下留下的k*k矩阵为
显然秩为3，不可逆（此时丢了5块）。
也有丢了5块可以恢复的例子：
比如丢了
D1 D0 C1 C2C3
剩下的矩阵为
是可逆的。
总结来看，就上面的例子，所有的块分了三组，分别为
group_1: D0 D1 C0
group_2: D2 D3 C1
group_3:C2 C3 C4
每个组可以提供的秩的个数为num(group_i) – 1，因为每个组有一个code块，该code块其实是另两个块的线性组合。
Local code for global code这个组比较特殊，相当于万能的，可以提供任意列的秩。而data的group只能提供某num(group_i) – 1列的秩，比如group_1只能是第一行和第二行，而group_2只能是第三行和第四行，group_3可以随意补充group_1和group_2的秩。（我这样描述不知道会不会被搞数学的拿砖拍死 T_T）。
因此判断是不是能恢复，只需要看这几个组留下的数据中，对应的encode matrix的行能不能凑出来一个秩为4的矩阵。
记函数s(g)为g这个group能提供的秩，
函数left(g)为g这个group剩下的数据块的个数
函数num(g)为g这个group的总的数据块的数目
那么每个组的s(g)的计算方法是（这个方法我自己理解总结的，如果有问题可以探讨）：
| if (left(g) == num(g)) { //也就是这个组没有损失数据 s(g) = num(g) – 1; } else { s(g) = left(g); } |
然后对每个组s(g)求和，假设结果是sum, 如果sum >= k，那么是可逆的也就是可以恢复的。其中k为数据块的个数。所以对于LRC，用丢失了多少块来判断是不是能恢复是不合适的，还是要看具体丢了哪几块。另外也可以看出来，多了一块local code for global code块对所有数据的容错能力还是有提升的，而且是可以作为global code用的（当>=1个其他global code丢失的时候）。
对于C_LRC，可以容忍的丢失的数据块的数目的上限t的范围是： global_code_cnt +1 =< t <= m-k。 也就是如果<=global_code_cnt +1个数据块丢失，一定可以恢复出来，如果是丢失t块数据（ global_code_cnt +1 =< t <= m-k） 要根据具体丢了哪几块数据来确定是不是能恢复
其中m是C_LRC编码矩阵的行数，k是所有的data chunk的数目
五、下一步工作
（1）上面的一些说明都没有基于有限域，所以下一步可能还是要在有限域上简单证明下
（2）分布式环境下Local怎么分组？ 我目前想得是，同一个组在一台机器，同一个组的不同数据块在这台机器的不同的硬盘上。这样可以减小通信的代价。
（3）LRC在解码的时候，少于k块可以，但是矩阵构造的时候还是按照k*k来构造的。这个事情需要再确认下用的intel ec库在用于LRC的时候有没有冗余计算，以及用的k*k矩阵，为什么少于k就可以恢复，这个此处只是道理讲了以及举了一些例子，还没想到更好的说明方式。
（4）facebook ms都有自己的做法。论文看了一部分，可以考虑下有没有可以借鉴和继续优化LRC算法的地方。
目前这个C_LRC测试得还不够，还在继续，因为上学原因，最近时间很少，周末加班+晚上赶了赶搞的，博客可能有点乱，因为是边写代码边写博客理思路的
