logo

Source
纠删码

  1. 什么是erasure code?
    erasure code可以认为是RAID的通式,任何RAID都可以转换为特定的erasure code。在传统的RAID中,仅支持少量的磁盘分布,当系统中存在多个分发点和多节点时,RAID将无法满足需求。比如RAID5只支持一个盘失效,即使是RAID6也仅支持两个盘失效,所以支持多个盘失效的算法也就是erasure code是解决这一问题的办法。

    定义:erasure code是一种技术,它可以将n份原始数据,增加m份数据,并能通过n+m份中的任意n份数据,还原为原始数据。定义中包含了encode和decode两个过程,将原始的n份数据变为n+m份是encode,之后这n+m份数据可存放在不同的device上,如果有任意小于m份的数据失效,仍然能通过剩下的数据还原出来。
    enter image description here

  2. 使用场景
    凡是需要通过冗余来进行高可用的场景。但总体来说,主要运用于存储和数字编码领域。
    1) 阵列
    如果磁盘阵列需要使用高级特性,比如需要能够容错两个磁盘失效(RAID6),那么可以用n+2的模式;如果想容错4个磁盘失效,则可使用n+4的模式。
    2) 云存储
    erasure code是云存储的核心技术,最初诸如hadoop, GFS,CEPH等都采用的是n-way replication来做冗余,但是这样会带来极大的成本开销,因此几乎各大公司都在用erasure code替代n-way replication,之后我还会简要介绍一下具体他们使用的模式。
    3) P2P领域
    erasure code 的理论起码也有20年的历史了,但真正实践可能也就最近几年的时间,在P2P领域,动态的分布和智能的容错,特别是对短暂失效是非常关键的。以往的算法或多或少都有点山寨的感觉,而借助erasure code之后,将会使P2P的算法更具有数学的严谨性。
    4) 数字编码
    erasure code本身就是出自编码理论,所以在这一块具有先天的优势。
  3. Reed-Solomon Codes
    erasure code是所有基于之前定义的统称,但具体下来有很多种,其中RS code是最基本的一种。RS codes是基于有限域的一种编码算法,有限域又称为Galois Field,是以法国著名数学家Galois命名的,在RS codes中使用GF(2^w),其中2^w >= n + m.
    RS codes定义了一个(n + m) n的分发矩阵(Distribution Matrix)
    enter image description here
    因此,对每一段的n份数据,我们都可以通过B
    D 得到:
    enter image description here

加入D1, D4, C2 失效,那么我们可以同时从矩阵B和BD中,去掉响应的行,得到下面的等式:
enter image description here
接下来就是算法的核心部分,如果想要从survivors 求得D,我们只需简单的做矩阵乘法:
enter image description here
因为(B’)^-1
B’ = I 单位矩阵,所以我们就秋得了原始矩阵D:
enter image description here
但是上面的推导并不严谨,存在一些问题:
1) B’是否一定存在可逆矩阵?
2) Distribution Matrix - B如何求得?
3) 每次都用乘法,CPU的开销会很大。
针对上面问题,有如下解决方案:
在线性代数中有一种矩阵称为Vandermonde矩阵,这种举证的特点是,任意的子方阵均为可逆方阵。其定义如下:
enter image description here
其中a(i) 均不相同,且不为0. 之后,再利用vandermonde矩阵特性,在GF(2^w)上进行矩阵变换,最终得到Distribution Matrix - B. 具体可参考[Plank,Ding:2005]
在GF域上的加法是异或操作,乘法可以采用乘法表来进行。

  1. 其他
    实际还有其他的code,在这儿就不累述了。关于erasure code,有一个开源的实现Jerasure,有兴趣可以自己去研究一下。本原理主要是参考James S. Plank教授的论文写成,且Jerasure也是由其开发,不足之处请指正。

参考文献:
Erasure Codes for Storage Application - James S. Plank


ccj 于 2 年前 修改
0 回复
需要 登录 后方可回复, 如果你还没有账号你可以 注册 一个帐号。