纠删码(ErasureCode)

纠删码(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/
updatedupdated2024-08-252024-08-25