Erasurecode（纠删码）

1.概述

在编码理论里&＃xff0c;有一种前向纠错(FEC)编码方式&＃xff0c;也称为纠删码。
这种技术可以将原始数据中丢失的k字节数据从n个含编码字节的信息中进行恢复。
在纠删码技术中&＃xff0c;Reed-Solomon&＃xff08;里所码&＃xff09;码是一种常见的纠删码。

2.纠删码的应用

对于在分布式环境下数据存储的可靠性保证&＃xff0c;有两种策略&＃xff1a;
1&＃xff09;引入副本冗余机制策略
2&＃xff09;利用纠删码技术&＃xff0c;相比于副本策略&＃xff0c;纠删码技术可以节省更多磁盘的空间。即有更高的磁盘利用率

拿Hadoop的HDFS来说&＃xff0c;策略一般是三副本&＃xff0c;当某个副本丢失时&＃xff0c;可以通过其他副本复制回来。所以在这种情况下&＃xff0c;Hadoop集群的磁盘利用率为1/3。而如果使用纠删码技术后&＃xff0c;可以提高磁盘的利用率。

3.纠删码的思想

上图的含义是&＃xff1a;有n个原始数据块&＃xff0c;再引入m个数据校验块&＃xff0c;然后通过编码&＃xff08;encode&＃xff09;是原始数据块和数据校验块产生关联。

纠删码技术是一种数据恢复技术&＃xff0c;最早用于通信行业中数据传输中的数据恢复&＃xff0c;是一种编码容错技术。它通过在原始数据中加入新的校验数据&＃xff0c;使得各个部分的数据产生关联性。在一定范围内的数据出错情况下&＃xff0c;通过纠删码技术都可以进行恢复。
比如&＃xff1a;有原始数据块n个&＃xff0c;然后加入m个校验数据块。
原始数据块和校验数据块在丢失时&＃xff0c;都可以通过现有的数据块进行恢复

举例&＃xff1a;
①x&＃61;1
②y&＃61;2
③z&＃61;3
④x&＃43;y&＃43;z&＃61;6
⑤2x&＃43;3y&＃43;z&＃61;11
⑥x&＃43;2y&＃43;3z&＃61;14

1&＃xff09;如果我们丢了3个原始数据块&＃xff0c;可以恢复
④x&＃43;y&＃43;z&＃61;6
⑤2x&＃43;3y&＃43;z&＃61;11
⑥x&＃43;2y&＃43;3z&＃61;14
2&＃xff09;如果我们丢失了3个数据校验块&＃xff0c;可以恢复
①x&＃61;1
②y&＃61;2
③z&＃61;3
3&＃xff09;可以
②y&＃61;2
③z&＃61;3
④x&＃43;y&＃43;z&＃61;6
⑤2x&＃43;3y&＃43;z&＃61;11
⑥x&＃43;2y&＃43;3z&＃61;14
4&＃xff09;可以
③z&＃61;3
④x&＃43;y&＃43;z&＃61;6
⑤2x&＃43;3y&＃43;z&＃61;11
⑥x&＃43;2y&＃43;3z&＃61;14
5&＃xff09;不可以
③z&＃61;3
⑥x&＃43;2y&＃43;3z&＃61;14

4.Reed-solomon codes

4.1.概述

Reed-Solomon里所码&＃xff08;RS&＃xff09;码是存储系统较为常用的一种纠删码&＃xff0c;也称为里所码。它有两个参数n和m&＃xff0c;记为RS(n,m)。n代表原始数据块个数。m代表校验块个数。接下来介绍RS码的原理。

4.2Reed-Solomon(RS)码的编码和解码过程

1&＃xff09;编码过程&＃xff08;encoding&＃xff09;

数据丢失&＃xff1a;

2&＃xff09;解码过程

4.3.RS的优缺点&＃xff1a;

优点&＃xff1a;低冗余度&＃xff0c;高磁盘利用率。
比如一个文件有5个文件块&＃xff0c;假设用3副本冗余机制&＃xff0c;最后总的文件块是15块&＃xff0c;则磁盘利用率是&＃xff1a;5/15&＃61;1/3&＃61;33%
而用RS码来实现&＃xff0c;5个文件块&＃43;3个数据校验块&＃xff0c;则磁盘利用率是&＃xff1a;5/8&＃61;62.5%

缺点&＃xff1a;
1&＃xff09;计算代价高。 丢失数据块或者编码块时&＃xff0c; RS需要读取n个数据块和剩余的校验块才能恢复数据。
2&＃xff09;数据更新代价高。 数据更新相当于重新编码&＃xff0c; 代价很高&＃xff0c; 因此常常针对只读数据&＃xff0c;或者冷数据。

工程实践中&＃xff0c;一般对于热数据还是会使用多副本策略来冗余&＃xff0c;冷数据使用纠删码。

4.4.两种冗余技术对比如下&＃xff1a;