Reed Solomon Erasure Codes-xiong9937-ChinaUnix博客

storage&nbsp;architect

首页　| 　博文目录　| 　关于我

xiong9937

博客访问： 1939969
博文数量： 1000
博客积分： 0
博客等级：民兵
技术积分： 7921
用户组：普通用户
注册时间： 2013-08-20 09:23

个人简介

storage R&D guy.

文章分类

全部博文（1000）

hh（5）
python（1）
flashcache（2）
levelDB（12）
java（4）
mac（5）
zookeeper（73）
ceph（108）
investation（2）
raid（3）
USB（21）
raise（1）
others（2）
salary（2）
salary（0）
KVM（11）
3G（2）
SAS（3）
PMC（2）
cold（24）
algorithm（9）
HDFS（92）
HDFS（4）
gdb（5）
hp（1）
DDK（27）
C（25）
eclipse（3）
tools（52）
kernel（37）
iscsi（19）
HPC（1）
FS（35）
scst（15）
istributed （5）
cloud（19）
NAS（41）
intel（1）
algorithm（0）
command（2）
tcpip（18）
documents（2）
board（1）
memory（13）
management（1）
linux boot（34）
bios（3）
pcie（56）
memory（3）
ethnet（56）
driver（3）
fcoe（13）
FC（14）
english（4）
switch（2）
links（14）
private（0）
protocal（0）
office（2）
network（2）
vm（8）
database（1）
os（43）
storage（27）

fcoe（4）
server（3）
未分配的博文（1）

文章存档

2019年（5）

2017年（47）

2016年（38）

2015年（539）

2014年（193）

2013年（178）

我的朋友

基本思想

如上图所示，我们总共有块盘，其中块用来存放数据，m块用来存储erasure编码()，在上面的块盘中，任意坏块，都可以通过erasure编码将其余的恢复出来。也就是说，通常的erasure编码，能容块盘故障的场景，这时候的存储成本是, 通常 , 因此，通过erasure编码，我们能够把副本数降到1.x。假如我们用3+2的erasure编码，就能容2块盘坏的故障，同时把成本降到了1.67。可以通过增加进一步降低成本，但是随着的增加，故障恢复的开销会变大，具体的应用过程中要根据实际的业务场景来权衡。据说GFSv2用的是6+3的方案，成本是1.5。

Reed Solomon算法

Reed Solomon算法的核心思想包括三个部分:
1. 利用范德蒙德(Vandermonde)矩阵，通过数据块计算编码块
2. 利用高斯(Gaussian)消元法, 恢复损坏的数据块
3. 为了方便计算机处理，所有运算都是在伽罗华域Galios Field)的基础上进行的

下面是Reed Solomon算法的具体步骤(的Reed Solomon, 处理的字长为):
1. 选择一个合适的字长, 保证
2. 构造上的对数表和反对数表
3. 取的Vandermonde矩阵F, 其中 $F_{i,j}=j^{i-1}$ ,
4. 用F去按字(w)乘数据块就会得到对应的编码块
5. 如果()块数据损坏，可以通过下面的方式恢复:
$A=\begin{bmatrix}I\\F\end{bmatrix}$ , $E=\begin{bmatrix}D\\C\end{bmatrix}$
我们知道, 在和中消去坏块对应的行，得到, , 满足 $A^{'}D=E^'$
通过高斯消元法，便可以解出; 另外如果是编码块中有坏块，可以直接通过算出对应的坏块。

关于Gaussian消元法: 读者朋友可以回忆一下小时候学的n元一次的方程组的解法，它所用的方法其实就是高斯消元法。由n个独立的方程组成的n元一次方程组，有确定的唯一解。在erasure编码中，个数据块相当于是个元，我们有个独立的一次方程，这个方程中，取任意个方程组成方程组，我们都可以通过高斯消元法解出个元，这便是erasure编码中真正的秘密。

关于Vandermonde矩阵: 为了保证”n元一次方程组”有解，我们需要保证每个方程都是”独立的”, 而用Vandermonde矩阵用来做为方程组的系数，便可以保证这一点。这就是erasure编码中为什么用Vandermonde矩阵的原因。下面是Vandermonde矩阵的定义:

?? $V=\begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ x_0 & x_1 & x_2 & \cdots & x_{n-1} \\ x_{0}^2 & x_{1}^2 & x_{2}^2 & \cdots & x_{n-1}^2 \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ x_{0}^{n-1} & x_{1}^{n-1} & x_{2}^{n-1} & \cdots & x_{n-1}^{n-1} \end{bmatrix}$

在erasure编码的具体应用到分布式存储系统中时，上面的都是在中，所有的运算都是在上做的。

Cauchy Reed Solomon算法

Cauchy Reed Solomon跟普通的Reed Solomon的最大的区别就是把Vandermonde矩阵换成了Cauchy（柯西)矩阵。通过《Finite Field Arithmetic》我们知道，在中的运算需要查对数表和反对数表来进行，并且随着的增大，查表的开销也会增大。在Cauchy Reed Solomon中，通过使用Cauchy矩阵，可以将上的四则运算做如下转化: 加法->异或，乘法->与，我们知道上的减法都可以转化为加法，除法都可以转化为乘法。因此，通过Cauchy Reed Solomon，可以将上的四则运算都转化为“异或”或者“与”运算，这对于计算机来说，更为友好，速度更快。
Cauchy Reed Solomon算法的过程跟普通的Reed Solomon算法的过程基本是类似的，关于如何构造Cauchy矩阵，以及如何把四则运算转化为位运算，感兴趣的同学可以参考[2], 这里不再赘述。

Jerasure and Java-Erasure

再回到算法本身的具体实现上，[3]有各种实现的对比，感兴趣的同学可以参考。总体来说，目前用得比较广泛的是James Plank实现的Jerasure, Jerasure本身是由纯C语言实现了，为了应用到Java语言实现的系统中(HDFS)，前段时间封装了一个wrapper library Java-erasure, 该库的用法和接口都非常简单，具体参考github上的README。

参考资料

1. A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems
2. Optimizing Cauchy Reed-Solomon Codes for Fault-Tolerant Storage Applications
3. Tutorial: Erasure Coding for Storage Applications

阅读(1280) | 评论(0) | 转发(0) |

上一篇：比较Swift与HDFS话Ceph本质(by quqi99)

下一篇：zookeeper事件的触发条件和再触发

给主人留下些什么吧！~~

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6