文章目录
  1. 1. 纠删码(erasure coding)
    1. 1.1. 介绍
    2. 1.2. 相关概念介绍
      1. 1.2.1. stripe
      2. 1.2.2. stripe_head
    3. 1.3. 推荐论文

纠删码(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
文章目录
  1. 1. 纠删码(erasure coding)
    1. 1.1. 介绍
    2. 1.2. 相关概念介绍
      1. 1.2.1. stripe
      2. 1.2.2. stripe_head
    3. 1.3. 推荐论文