纠删码（erasure coding）

介绍

纠删码（erasure coding，EC）是一种数据保护方法，它将数据分割成片段，把冗余数据块扩展、编码，并将其存储在不同的位置，比如磁盘、存储节点或者其它地理位置。

纠删码会创建一个数学函数来描述一组数字，这样就可以检查它们的准确性，而且一旦其中一个数字丢失，还可以恢复。多项式插值（polynomial interpolation）或过采样（oversampling）就是纠删码所使用的关键技术。

从数据函数角度来说，纠删码提供的保护可以用下面这个简单的公式来表示：n = k + m。变量“k”代表原始数据或符号的值。变量“m”代表故障后添加的提供保护的额外或冗余符号的值。变量“n”代表纠删码过程后创建的符号的总值。

举个例子来说，在一个EC 10/16的配置中，会有6个额外的符号（变量m）被添加到10个原始符号（变量k）中。这16个数据片段（变量n）会遍布16个驱动器、节点或地理位置中。而原始文件可以从10个验证片段中重建。

纠删码，也称为前向纠错（FEC）编码，早在50年前就已出现。随后产生了不同类型。其中一个最早也是最常见的类型就是RS（Reed-Solomon），这种类型的数据可以使用任何k符号的组合或数据块来重建，即使m符号丢失或不可用。比如，在EC 10/16中，即使有6个驱动器、节点或者地理位置丢失或不可用，而原始文件还是可以恢复。

纠删码可以用于有大量数据和任何需要容错的应用程序或系统中，比如磁盘阵列系统、数据网格、分布式存储应用程序、对象存储或归档存储。目前，纠删码的一个常见的使用案例是基于对象的云存储。

相关概念介绍

众所周知，早年的计算机存储数据现在磁带上，然后发展到了磁盘，然而仅仅是单个盘，速度和性能都不是很好，然是，要知道人类的聪明才智是连ET都想不到的，前辈们不断的猜想，实验来提高计算机的性能，于是磁盘阵列问世了。由于磁盘阵列(Redundant Arrays of Independent Disks，RAID)的出现，使磁盘的存储性能和安全性等诸多方面有了飞速的提升，随着科技的进步，存储材质也在不断的优化，早期的磁带到磁盘，以及现在的SSD,甚至未来的比SSD性能更好的PCM(phase-change memory)都在极力的提高存储性能。

以raid5为例，介绍下基本概念

stripe

RAID5的读写操作采用的是stripe的基本结构，即以stripe为读写的基本单位，假设一个3+1的RAID5，即3个数据盘+1个校验盘，那么一个stripe就包含3个数据块和一个校验块。我们结合图示来仔细看下RAID5的架构。

如图所示，这是一个3+1的RAID5，图中的每一个方块表示一个stripe的一个基本单元，又称为chunk；相同颜色的方块组成一个stripe，即每个stripe由3个数据chunk(A,B,C)+1个校验chunk(P)组成。关于校验块的生成方法以及数据恢复原理如下：

校验块P的生成方法为P=A⊕B⊕C 。(⊕表示异或运算)
加入1号盘坏了，此时有读请求读B0块的数据，那么可以通过B0=A0⊕C0⊕P0 的方法 来进行恢复。

可以观察到上图中的校验块不是单独的全部存在一个盘上，这是为了实现RAID中磁盘的磨损平衡，防止某个盘寿命太短而先损坏。 内核中有很多这种平衡校验块的算法，上图中用到的是ALGORITHM_LEFT_SYMMETRIC。

内核中默认的stripe大小

基本上所有的OS都认可的page大小是4KB，由于内核中是按sector为基本大小单位，1 sector = 512B，所以有如下公式：

1 page = 8*sector = 4KB
1 chunk = 128*page = 512KB
1 stripe = 4*chunk = 2048KB
1 stripe的data size =3*chunk =1536KB

stripe_head

虽然说直观上看RAID5的基本处理单元是stripe，但是一个chunk的大小是512KB，这与OS一次处理的page大小相差太多，所以为了处理的一致性，内核将一个chunk分成128个page，由一个stripe的每个chunk出一个对应的page组成内核中的RAID5处理的基本单元：stripe_head。

我们用图来详细了解下stripe_head与stripe的区别

这是第一幅图中的stripe 0 的细化，stripe 0 由A0、B0、C0和P0组成，这幅图中，将每个chunk细化，由于一个chunk的大小是128个page的大小，所以一个chunk中含有128个page，每个page的大小是4KB，所以在每一个chunk中具有相同偏移量的page组成一个stripe_head，即图中每个颜色相同的方块组成一个stripe_head。

1 stripe_head = 4*page = 16KB
1 stripe = 128 * stripe_head =2048KB

所以说：我们经常说的RAID5的处理单元stripe，实际上是内核中的处理单元stripe_head的结合体

推荐论文

  1. usenix
  2. Tutorial: Erasure Coding for Storage Applications
  3. FastScale: Accelerate RAID Scaling by Minimizing Data Migration
  4. Rethinking RAID-5 Data Layout for Better Scalability
  5. Accelerate RDP RAID-6 Scaling by Reducing Disk I/Os and XOR Operations
  6. I/O-Efficient Scaling Schemes for Distributed Storage Systems with CRS Codes

参考资料：

  1. searchstorage
  2. csdn chenyouxu