Erasure Code

EC （Erasure Coding）是一种编码容错技术，最早是在通信行业解决部分数据在传输中的损耗问题。其基本原理就是把传输的信号分段，加入一定的校验再让各段间发生相互关联，即使在传输过程中丢失部分信号，接收端仍然能通过算法将完整的信息计算出来。在数据存储中，纠删码将数据分割成片段，把冗余数据块扩展和编码，并将其存储在不同的位置，例如磁盘、存储节点或者其他地理位置。

从纠删码基本的形态看，它是k个数据块+m个校验块的结构，其中k和m值可以按照一定的规则设定，可以用公式：n=k+m来表示。变量k代表原始数据或符号的值。变量m代表故障后添加的提供保护的额外或冗余符号的值。变量n代表纠删码过程后创建的符号的总值。当小于或等于m个存储块（数据块或校验块）损坏的情况下，整体数据块可以通过计算剩余存储块上的数据得到，整体数据不会丢失。

下面以k=3，m=2为例，介绍一下如何以纠删码的形式将一个名称为NYAN的对象存放在Ceph中，假定该对象的内容为ABCDEFGHI。客户端在将NYAN上传到Ceph以后，会在主OSD中调用相应的纠删码算法对数据进行编码计算：将原来的ABCDEFGHI拆分成三个分片，之后再计算出另外两个校验条带分片（内容为YXY QGC）。按照crushmap所指定的规则，将这5个分片随机分布在5个不同的OSD上面，完成对这个对象的存储操作，如图1所示。

下面再看一下如何使用纠删码读取数据，同样还是以NYAN为例。客户端在发起读取NYAN请求以后，这个对象所在PG的主OSD会向其他关联的OSD发起读取请求，比如主OSD是图中的OSD1，当请求发送到了其他4个OSD，此时刚好OSD4出现故障无法回应请求，导致最终只能获取到OSD1(GHI)、OSD3(YXY)和OSD5（ABC）的条带分片，OSD2虽然也收到请求并发送数据，但OSD2是最慢被接收的，此时OSD1作为主OSD会对OSD1、OSD3和OSD5的数据分片做纠删码解码操作，OSD2上面的分片内容会被忽略，之后重新组合出新的NYAN内容(ABCDEFGHI)，最终将该结果返回给客户端。