温馨提示：如果使用电脑查看图片不清晰，可以使用手机打开文章单击文中的图片放大查看高清原图。
Fayson的github：
https://github.com/fayson/cdhproject
提示：代码块部分可以左右滑动查看噢
Fayson在前面的文章中介绍过CDH6，参考《
Cloudera Enterprise 6正式发布
》和《
如何在Redhat7.4安装CDH6.0
》。CDH6主要集成打包了Hadoop3，包括Hadoop3的一些新特性的官方支持，比如NameNode联邦，纠删码等。纠删码可以将HDFS的存储开销降低约50%，同时与三分本策略一样，还可以保证数据的可用性。本文Fayson主要介绍纠删码的工作原理。
默认情况下，HDFS的数据块都会保存三个副本。副本提供了一种简单而健壮的冗余方式来最大化保证数据的可用性。数据的多副本同时可以尽量保证计算任务的本地化。
但副本方式成本是较高的：默认情况下三副本方式会在存储空间或其他资源(比如写入数据时的网络带宽)中产生200%的开销。对于较少访问的数据集(对集群的I/O影响相对不大)，它们的第二个或者第三个副本会比较少访问，但是仍会消耗相同的存储空间。
因此可以使用纠删码(ErasureCoding)来代替多副本的方式，它使用更少的存储却可以保证相同级别的容错。在典型配置下，与三副本方式相比，EC可以将存储成本降低约50%。基于这个考虑，Cloudera与Intel的工程师在HDFS-7285(https://issues.apache.org/jira/browse/HDFS-7285)下启动并推动了HDFS-EC项目。目前HDFS-EC已经在CDH6和HDP3中发布。
本文主要会介绍HDFS纠删码的设计。该需求来源于Cloudera的大型客户对HDFS的要求，我们的设计主要是解决如何将HDFS改造以支持EC。后面将详细讨论如何将EC应用于HDFS，对NameNode，DataNode和客户端读写路径所做的更改，以及使用Intel ISA-L加速编码和解码计算的优化。最后，我们将讨论未来的一些开发工作，包括对不同数据布局和高级EC算法的支持。
1.背景
1.1.EC和RAID
在比较不同的存储方案时，有两个重要的考虑因素：数据持久性（通过能够容忍同时故障的数量来衡量）和存储效率（逻辑大小除以原始使用）。
副本方式(比如RAID1和HDFS)是一种容忍磁盘故障简单而有效的方法，但代价是额外的存储开销。N个副本可以容忍N-1个同时发生故障，存储效率1/n。比如HDFS默认的三副本最多可容忍两个副本故障，存储效率为三分之一(或者开销为200%)。
Erasurecoding纠删码技术简称EC，是一种数据保护技术。最早用于通信行业中数据传输中的数据恢复，是一种编码容错技术。他通过在原始数据中加入新的校验数据，使得各个部分的数据产生关联性。在一定范围的数据出错情况下，通过纠删码技术都可以进行恢复。
在存储系统中，纠删码技术主要是通过利用纠删码算法将原始的数据进行编码得到校验，并将数据和校验一并存储起来，以达到容错的目的。其基本思想是将ｋ块原始的数据元素通过一定的编码计算，得到ｍ块校验元素。对于这ｋ ｍ块元素，当其中任意的ｍ块元素出错（包括数据和校验出错），均可以通过对应的重构算法恢复出原来的ｋ块数据。生成校验的过程被成为编码（encoding），恢复丢失数据块的过程被称为解码（decoding）。
表1：XOR (exclusive-or，异或) 操作
如表1所示，最简单的EC实现可以基于异或操作(XOR)，XOR码的原理是：数据编码时按照位进行异或运算,数据恢复的时候也就是解码时则通过结果与其他数据位进行异或操作的逆运算。异或操作与我们常见的”与”操作和”或”操作略有不同,遵循”相同为0,不同则为1”的运算原则。如表1，⊕就是异或操作的意思。
现在假设最后一个式子中的第二位,就是数字第一个数字1丢失了,变成了下面这个式子:
0 ⊕ ? ⊕ 1 = 0;
我们可以通过异或操作的逆运算恢复数据,因为最后结果为0,所以0 ⊕ ?的结果应该为1,也就是0 ⊕ ? = 1,因为异或运算,不同才为1,所以这里丢失的数据就是1,数据成功恢复.但是这里暴露出了一个问题,如果丢失或损坏的数据位超过1位的时候,数据好像就不是那么好恢复了,比如丢失了头2位:
? ⊕ ? ⊕ 1 = 0;
这个时候头2位是0，1还是1，0呢？只能说都有可能。OK，从这里我们可以看出XOR编码算法存在可容忍错误过少的问题，那么有什么别的EC算法能帮我们解决这个问题呢？在很多场合下，是会存在多个数据丢失的情况的，并不能确保每次只有1个数据出错的情况。下面介绍的新的编码算法能解决这个棘手的问题。
Reed-SolomonCodes也是EC编码中的一种。Reed-Solomon Codes缩写为RS码，中文名称里德所罗门码。RS使用复杂的线性代数运算来生成多个奇偶校验块，因此可以容忍每组多个故障。这是一个生产存储系统的常见选择。RS需要配置2个参数，k和m。如图1所示，RS（k，m）通过将k个数据块的向量与生成矩阵（GT）相乘来实现，从而得到一个码字（codeword）向量，该向量由k个数据块和m个校验块构成。如果一个数据块丢失，可以用(GT)-1乘以码字向量来恢复出丢失的数据块。RS(k，m)最多可容忍m个块（包括数据块和校验块）丢失。
图1：有4个数据库和2个奇偶校验块的Reed-Solomon编码
参考：https://www.usenix.org/legacy/event/fast09/tech/full_papers/plank/plank.pdf
使用Reed-Solomon，你可以通过设置不同的k和m来灵活的调整数据持久性和存储成本。奇偶校验块的数量m确定可以容忍的同时存储故障的数量。数据块与奇偶校验块的比率决定了存储效率：
典型的RS配置如RS（6,3）和RS（10,4）与三副本方式相比，可提供不错的数据持久性与存储效率。因为它们可以分别容忍多达三个或四个故障，并且
