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