ceph ec 介绍

    EC(erasure code)纠删码, 是一种校验编码技术，它可以将n份原始数据，增加m份数据，并能通过n+m份中的任意n份数据，还原为原始数据。定义中包含了encode和decode两个过程，将原始的n份数据变为n+m份是encode，之后这n+m份数据可存放在不同的device上，如果有任意小于m份的数据失效，仍然能通过剩下的数据还原出来。 　　
    
    EC可以认为是RAID的通式，任何RAID都可以转换为特定的erasure code。在传统的RAID中，仅支持少量的磁盘分布，当系统中存在多个分发点和多节点时，RAID将无法满足需求。比如RAID5只支持一个盘失效，即使是RAID6也仅支持两个盘失效，所以支持多个盘失效的算法也就是erasure code是解决这一问题的办法。 　　

    EC有多种实现的算法,主要有RS-code(Reed-Solomon),CRS-code(Caucy Reed Solomon), LRC(local reconstruction code),等

EC原理

    写入时候,编码过程:
    1, 将obj按照stipe width条带化,  stripe_width 是编码前的数据块大小, chunk是编码后的数据块大小, 他们之间的关系是stripe_width = chunk * k, 冗余数据是chunk*m.
    2, 将stripe width数据根据(k,m)值进行ec编码, 生成k+m份数据(大小chunk), 
    3, 将k+m份数据写入osd

    读出时候解码过程:
    1, 根据要读取的数据大小进行条带化规划, 包括offset和size按stripe_width对齐
    2, 根据ec规则(k,m), 读取k个osd上的数据, 
    3, 将读取回来的数据进行解码(合并), 并返回数据.

EC算法之RS/CRS-code

    RS(Reed Solomon)算法是应用最广泛的EC算法,  核心思想包括三个部分:
        1. 利用范德蒙德(Vandermonde)矩阵，通过数据块计算编码块
        2. 利用高斯(Gaussian)消元法, 恢复损坏的数据块
        3. 为了方便计算机处理，所有运算都是在伽罗华域GF(2^w)的基础上进行的
    
     CRS(Cauchy Reed Solomon)和RS的最大的区别就是把Vandermonde矩阵换成了Cauchy（柯西)矩阵。在RS的GF(2^w)中的运算需要查对数表和反对数表来进行，并且随着w的增大，查表的开销也会增大。在CRS中，通过使用Cauchy矩阵，可以将GF(2^w)上的四则运算做如下转化: 加法->异或，乘法->与，我们知道GF(2^w)上的减法都可以转化为加法，除法都可以转化为乘法。因此，通过Cauchy Reed Solomon，可以将GF(2^w)上的四则运算都转化为“异或”或者“与”运算，这对于计算机来说，更为友好，速度更快。

        在存储领域中,如果是软EC编解码,应该用CRS代替RS算法 
         
EC算法之LRC
    
        LRC(local reconstruction code)是RS/CRS的改进算法,将RS全局组划分成多个局部组, 当有一个数据块丢失的时候,可以优先的通过局部校验数据来恢复数据, 有效减少数据修复时的系统负载, 但需要消耗额外的空间(空间利用率略低), 例如:  　　
        
        计算10:6:2的LRC码，首先按照10:6的比例计算出RS码，得到chunk分片X1、X2、......X10、Y1、Y2、......Y6，然后取Z1=X1+X2+......+X5, Z2=X6+......+X10,  这样X1、X2、......X10、Y1、Y2、......Y6、Z1、Z2就构成了（10:6:2）的LRC码。 如果X1、X2、......X10中有一个分片出现数据丢失，那么只需要读取（前5个分片中的4个+Z1）或（后5个分片中的4个+Z2），就可算出丢失的分片。而传统的RS码则需要读取10个chunk分片, 节省二分之一的磁盘i/o和节点间的网络通信带宽.

        适用于节点数比较多(如大于1000个), 单点故障比较频繁的场景, 同时一个EC组也必须有比较多的数据块,效果才会更好

EC算法之SHEC
    
    SHEC(Shingled Erasure Code)利用多个奇偶校组验实现EC算法, SHEC(k,m,c), 表示k个有效数据块, m个奇偶校验块, 可以容忍c个块错误. SHEC能快速的恢复数据,是因为每个坏块都可以做到局部数据恢复,而无需读取全局数据才能恢复.对于数据的读取速度没有影响. 但是一般c数值小于m, 所以SHEC的空间利用率相对低.  一般认为,SHEC(mSHEC)算法用于需要快速恢复数据的场合,  4.4, EC算法库之Jerasure jerasure是通用的RS/CRS算法库 4.5,  EC算法库之ISA ISA是针对因特尔芯片优化的RS/CRS算法库 同样运行在inter的芯片上, 同样用RS/CRS算法, 那么ISA库的性能比jerasure库的性能好.

EC IO特点:

    EC在保证数据可靠性相同(2副本)的情况下, 可以节省更多的存储空间 
    EC的(k,m,Stripe_width)三个值对于EC的效率,空间利用率等都有比较大的影响, 需要针对应用做比对测试,并综合考虑,选择合适的值.
    EC的(k,m)选择还应该综合考虑文件系统碎片问题   
    EC用于存储小文件时,  空间利用率和性能都会比较低,并不适合
    CEPH  EC在覆盖写的时候会保留多个副本, 这些副本会浪费额外的空间, 需要对保留的副本个数做限制
    EC在故障恢复区间,对读写性能有比较大的影响,
    EC对于cpu,内存,带宽等资源相对replica来说都有更高的要求.
    每个stripe_width都会进行写时EC编码, 读时EC解码, 这样会使用更多的CPU资源, 会对性能有影响
    EC的4K随机读写性能比较差
    适合使用在顺序读写,没有随机写, 有少量随机读的场景, 常用于对象存储, 冷数据存储等.

Ceph 已经实现了部分的EC编码的功能, 但是在使用的过程中仍会有些限制, 体现如下:

         1,目前写io操作只实现了append模式, 且起始位置一定要stripe_width对齐.
         2, 每次读写都必须以块(chunk)的整数倍为单位, 块号一样的数据组在一起才是有意义的数据.
         3, 不支持随机写, 修改写入, 但支持随机读
         4, xattr等的存储仍使用replica的方式, omap没有实现