纠删码(ErasureCode)

简介

• 纠删码是通过利用纠删码算法将原始的数据进行编码得到校验，并将数据和校验一并存储起来，以达到容错的目的;

• 其基本思想：是对于任意n元1次方程，需要n个方程可以求解；

• 对于n块数据，为了保证其任意损坏m块，任意能恢复出来，则需要额外增加m个一次方程，则需要存储(n(数据块)+m(校验块))份数据；

• 则这n+m个n元1次方程系数将是一个[n, n+m]的矩阵；

• 为保证任意的m块丢失都能求解，则改矩阵需满足任意的[n,n]维矩阵都必须可逆，满足该性质的矩阵为范德蒙矩阵或柯西矩阵；

• 纠删码技术在分布式存储 系统中的应用主要有三类，阵列纠删码（Array Code: RAID5、RAID6等）、RS(Reed-Solomon)里德-所罗门类纠删码和LDPC(LowDensity Parity Check Code)低密度奇偶校验纠删码。

Reed-Solomon（RS）码是存储系统较为常用的一种纠删码，它有两个参数 k 和 m，记为 RS(k，m)。如图所示，k 个数据块组成一个向量被乘上一个生成矩阵（Generator Matrix）GT 从而得到一个码字（codeword）向量，该向量由 k 个数据块和 m 个校验块构成。如果一个数据块丢失，可以用(GT)-1 乘以码字向量来恢复出丢失的数据块。RS(k，m)最多可容忍 m 个块（包括数据块和校验块）丢失。

LRC

EC在存储中的实践

• HDFS 3.0 Ecode
• Ceph ECode

参考

1. https://www.iteblog.com/archives/1684.html
2. https://blog.csdn.net/Androidlushangderen/article/details/51923582
3. 详解Hadoop3.x新特性功能-HDFS纠删码 - 五分钟学大数据 - 博客园
4. 知乎-纠删码 Erasure Code
5. 网易数帆 Ceph EC 纠删码在线存储性能优化实践【图文】_mb5ffbc7cecbf87_51CTO博客
6. Apache Hadoop 3.3.1 – HDFS Erasure Coding
7. HDFS EC在滴滴的实践-InfoQ
8. Apache Hadoop3 EC 原理与实践 - 墨天轮
9. Ceph的正确玩法之Ceph纠删码理论与实践
10. https://blog.openacid.com/storage/ec-2/