HDFS的纠删码工作原理

问题导读：

1.什么是纠删码？

2.HDFS中怎样实现的纠删码？

3.Erasure Coding技术有哪些优劣势？

最新经典文章，欢迎关注公众号

默认情况下，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丢失了,变成了下面这个式子:

[mw_shl_code=text,true]0 ⊕ ? ⊕ 1 = 0;[/mw_shl_code]

我们可以通过异或操作的逆运算恢复数据,因为最后结果为0,所以0 ⊕ ?的结果应该为1,也就是0 ⊕ ? = 1,因为异或运算,不同才为1,所以这里丢失的数据就是1,数据成功恢复.但是这里暴露出了一个问题,如果丢失或损坏的数据位超过1位的时候,数据好像就不是那么好恢复了,比如丢失了头2位:

[mw_shl_code=text,true]? ⊕ ? ⊕ 1 = 0;[/mw_shl_code]

这个时候头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/ev ... ers/plank/plank.pdf

使用Reed-Solomon，你可以通过设置不同的k和m来灵活的调整数据持久性和存储成本。奇偶校验块的数量m确定可以容忍的同时存储故障的数量。数据块与奇偶校验块的比率决定了存储效率：

典型的RS配置如RS（6,3）和RS（10,4）与三副本方式相比，可提供不错的数据持久性与存储效率。因为它们可以分别容忍多达三个或四个故障，并且<50 ％存储开销。表2比较了副本、XOR和RS的容错和存储效率。

表2：副本、XOR和RS容错和存储效率比较

本地存储系统也经常使用EC技术，特别是RAID5和RAID6(https://en.wikipedia.org/wiki/Standard_RAID_levels)。RAID5一般使用XOR编码，因为她只需要容忍单个磁盘故障，而RAID6使用Reed-Solomon和两个奇偶校验块来容忍最多两个磁盘故障。数据块与校验块的比例是可以配置的，一组纠删码数据由数据块和校验块组成，这些块与每块磁盘是对应的。如下图2所示：

图2：RAID5和RAID6示例

参考：https://en.wikipedia.org/wiki/Standard_RAID_levels

1.2.分布式系统中的纠删码

为了管理非常大的文件，分布式存储系统通常将文件划分为固定大小的逻辑块。然后将这些逻辑块映射到集群上的存储块，这反映了集群上数据的物理布局。

逻辑块和存储块之间最简单的映射是连续的块布局，它将每个逻辑块一对一映射到存储块。读取连续块布局的文件就像按顺序线性读取每个存储块一样简单。

相比之下，条带式块布局将逻辑块分成更小的存储单元（通常称为cells），并在一组存储块中以轮询的方式写入单元条带(stripes of cells)。读取带有条带布局的文件需要查询逻辑块的存储块集，然后从存储块集中读取单元条带。本节讨论如何在两种块布局上支持EC。

数据被依次写入一个块中，一个块写满之后再写入下一个块，数据的这种分布方式被称为连续布局。在一些分布式文件系统如QFS和Ceph中，广泛使用另外一种布局：条带式布局。条（stripe）是由若干个相同大小单元（cell）构成的序列。在条形布局下，数据被依次写入条的各个单元中，当条被写满之后就写入下一个条，一个条的不同单元位于不同的数据块中。如图3所示，在条带式示例图中，对应的EC编码类型是RS(6, 3)。前面从DataNode0~5总共6个节点存数据块，后面的DataNode6~8存的则是加密块。

图3：EC使用连续存储和条带式存储的示例

原则上，块布局（连续与条带）和冗余形式（副本复制与EC）是两个正交维度，产生四种可能的组合。如图4所示，主流的存储系统都会使用这几种方式。某些系统（包括Ceph和QFS）支持在每个目录或每个文件的基础上配置布局方式和/或冗余方式。

图4：现有分布式存储系统使用块布局和冗余方式的范围

如前所述，就存储效率而言，纠删码优于副本复制方式。然而，这是以额外的复杂性和更昂贵的故障恢复为代价的。

沿着块布局维度，条带化可以提供比连续布局更好的I/O吞吐量，因为它可以并行的更好的利用多个磁盘(multiple spindles)。然而这意味着大多数读取都是远程的，强调需要快速完全平分网络。这种方法与传统的MapReduce在处理数据时强调的数据本地性(data locality)相矛盾，但是如果应用程序在了解底层cell和条带大小的情况下读取和写入数据，则仍然还是可行的。

2.设计和实现

2.1.选择块布局

对于HDFS-EC，最重要的问题是确定哪种块布局最合适。连续布局更容易实现，因为读取和写入路径与采取副本复制方式的当前系统非常相似。但是它仅适用于文件非常大的情况，因为只有在写入完整的条带时，才能发挥成本节省的所有优势。例如对于RS（10,4），如果一个条带仅仅只有一个单独的128MB的数据块，但仍然需要写入4个128MB的奇偶校验块，存储开销为400%，比三副本方式开销还大。连续布局也仅适用于离线或后台EC，否则客户端需要缓存GB级的数据块以计算奇偶校验。

另一方面，条带式布局的EC可以同时实现小文件和大文件的存储空间节省，因为一个cell都比较小(通常为64KB-1MB)。cell较小同时也允许你在线做EC，客户端可以直接写入纠删码数据，因为仅仅只需要几MB的缓存来计算奇偶校验信息。缺点是对于位置敏感(locality-sensitive，就是上文提到的有些强依赖data-locality的MapReduce作业会消耗大量的网络资源的情况。)的工作负载性能不会太好，如果运行在条带块上。为了更好的运行此类工作负载，可以将条带文件转换为连续布局，但这几乎需要重写整个文件。

基于此分析，文件大小是最关键的决定因素。如果集群中存储的都是大文件 - 每个文件至少由6个128MB的block组成，可以满足RS（6,3）模式下的完整EC组 - 那么连续布局是合适的，因为我们可以不用去实现合并多个小文件到一个EC组。但是如果集群中保存的是大量小文件，从存储成本和管理上来说的话，条带化布局是更好的选择。

图5：来自生产集群的文件大小直方图

我们研究了Cloudera最大的三个客户的HDFS文件大小分布，详细报告可以参考：https://issues.apache.org/jira/s ... alysis-20150105.pdf，图5是对该报告的一个总结。我们有一个重要发现，小文件(少于一个EC组)的使用基本占比为36%-97%，表明小文件问题都比较严重。

基于这一发现，我们在HDFS-EC的第一阶段，开发主要专注于实现条带式布局的EC。

2.2.泛化NameNode中的Block概念

该项目的主要工作在于泛化HDFSblock的基本概念以支持数据条带化。连续块布局被广泛而深入地嵌入到HDFS内部逻辑中。为了支持条带布局，逻辑块的概念必须与存储块的概念分开。前者表示文件中的逻辑字节范围，而后者是存储在DataNode上的数据块的基本单位。图6是逻辑和存储块的概念的示例。在该示例中，文件/tmp/foo在逻辑上被划分为13个条带化单元（cell_0到cell_12）。逻辑块0(图中的logicalblock 0)表示cell_0~8的逻辑字节范围，逻辑块1(图中的logical block 1)表示cell_9~12。cell_0,3,6组成存储块，该存储块将作为单个数据块存储在DataNode上。为简明起见，该图不包括奇偶校验块/单元。

图6：逻辑和存储块

支持此泛化的一种简单的机制是HDFSNameNode监视其块映射中的每个存储块，该映射从块ID映射到相应的块，然后使用另一个映射从逻辑块转到其成员存储块(member storage block)。但是这意味着小文件会在NameNode上产生大量内存开销，因为条带化会导致比备份复制方式更多的存储块。

为了减少这种开销，我们引入了一种新的分层块命名协议。目前，HDFS根据块创建时间顺序分配块ID。该协议将每个块ID分成2~3个部分，如图7所示。每个块ID以一个标志(flag)开始，表示其布局（连续=0，条带= 1）。对于条带块，ID的其余部分由两部分组成：中间部分，ID为逻辑块，尾部表示逻辑块中存储块的索引。这允许NameNode管理逻辑块作为其存储块的摘要(summary)。可以通过屏蔽索引将存储块ID映射到其逻辑块，当DataNode向NameNode汇报block时必须这么做。

图7：分层块命名协议

基于图5中三个集群的HDFS image文件，我们模拟了启用了EC后NameNode的内存使用情况。结果表明，如果没有新的分层块命名协议，条带化将使NameNode块映射的大小增加250％~440％。使用该协议，条带化仅将NameNode块映射增加21％~76％。有关内存开销分析的更多详细信息，请参考：

https://issues.apache.org/jira/secure/attachment/12690129/fsimage-analysis-20150105.pdf

由于此设计，逻辑块在NameNode上显示为一组内部存储块。表3总结了与条带化和EC块相关的术语。默认的EC策略是使用6个数据块和3个奇偶校验块，以及64KB的条带化cell大小。我们是根据一些真实集群的典型的文件大小来选择的这个默认值。其他的EC模式，比如Facebook使用HDFS-RAID（http://wiki.apache.org/hadoop/HDFS-RAID）的（10,4）设置，具有更好的存储效率，但会导致恢复数据花费更高，并且对集群中的机架数量有更高的要求。

表3：EC块相关的术语

支持逻辑块抽象需要更新NameNode的许多部分。举一个例子，为了防止数据丢失，HDFS会自动尝试复制副本数不足的数据。以前该算法仅考虑剩余副本的数量，但现在被泛化为还包括EC schema的信息。其他主要变化包括updating quota，fsck，balancer等。

2.3.客户端扩展

HDFS客户端的主要I/O逻辑在DFSInputStream和DFSOutputStream中实现。为了支持数据条带化和EC，我们已经将它们扩展为DFSStripedInputStream和DFSStripedOutputStream。扩展背后的基本原理是允许客户端节点并行处理逻辑块中的多个存储块。当与HDFS加密一起使用时，这些扩展在加密数据上运行 - 即在加密层下面。

在输出/写入路径上，DFSStripedOutputStream管理一组数据流(data streamers)，每个DataNode用于在当前逻辑块中存储内部存储块。streamers大多是异步工作的。协调器负责整个逻辑块的操作，包括结束当前逻辑块，分配新的逻辑块，等等。

在输入/读取路径上，DFSStripedInputStream将请求的逻辑字节数据范围转换为存储在DataNode上的内部存储块。然后它并行发出读取请求。失败后，它会发出额外的解码读取请求。

2.4.DataNode扩展

为了避免在客户端进行数据重建，这个成本往往较高，后台能够识别和修复DataNode故障是非常重要的。与以前的复制备份方式一样，NameNode需要负责跟踪EC条带中的缺失块，并给DataNode分配恢复这些缺失块的任务。DataNode上的恢复工作由新的ErasureCodingWorker（ECWorker）组件处理，该组件执行以下操作以重建缺少的EC块：

1.从源节点读取数据：在ErasureCodingWorker启动时会初始化一个专用的线程池用于从不同的源节点读取数据块。基于EC schema，它调度对所有源目标的读取请求，并确保仅读取重建所需的最小输入块。

2.解码数据并生成输出数据：与EC客户端类似，ECWorker会在Erasure Codec Framework中引入的编解码器框架完成解码/编码工作。

3.将生成的数据块传输到目标节点：解码完成后，它会将输出数据封装到数据包并将它们发送到目标DataNode。

2.5.编解码器计算框架

数据编码/解码是CPU密集型的，所以在使用纠删码技术时也是资源的主要开销。为了缓解HDFS-EC，我们利用英特尔的开源智能存储加速库（英特尔ISA-L，Intelligent Storage Acceleration Library），通过利用SSE，AVX和AVX2等高级硬件指令集，加速与EC相关的线性代数计算。ISA-L支持所有主要操作系统，包括Linux和Windows。参考：
https://www.intel.com/content/www/us/en/storage/erasure-code-isa-l-solution-video.html

在HDFS-EC中，我们通过两种形式实现了Reed-Solomon算法：一种基于ISA-L，另一种基于纯Java（适用于没有所需CPU的系统）。我们比较了这两种实现的性能，同时比较了Facebook的HDFS-RAID实现的编码器。本节中的所有测试都使用RS（6,3）。

图8显示了基于内存的编码/解码基准测试的结果。 ISA-L实现比HDFS-ECJava实现快4倍以上，比Facebook HDFS-RAID编码器快约20倍。根据这个结果，我们强烈建议生产系统部署实施ISA-L加速。

图8：编码和解码性能比较

我们还比较了不同编码器的端到端的HDFS I/O性能，包括HDFS默认的三副本方式。测试环境是10Gb网络，11个节点（1个NameNode，9个DataNode，1个客户端节点）。图9主要包括：1）客户端将12GB文件写入HDFS的吞吐量结果; 2）客户端从HDFS读取12GB文件。在读取测试中，我们手动杀死了两个DataNode，因此结果包括解码开销。

图9：HDFS I/O性能比较

如图9所示，在顺序写入/读取及读取基准测试中，吞吐量受到纯Java编码器（HDFS-RAID和我们自己的实现）的极大限制。ISA-L实现比纯Java编码器快得多，因为它具有出色的CPU效率。同时它比三副本方式快2-3倍，因为条带化布局允许客户端并行执行多个DataNode的I/O，从而利用其磁盘驱动器的总吞吐。我们还测试了读取性能，没有任何DataNode故障：HDFS-EC比三副本方式快大约5倍。

请注意，应该可以进一步提高性能。使用RS（6,3）布局，条带布局应该能够实现I/O吞吐量大约6倍的提升，或大约1GB/s的吞吐量。当前性能部分不符合理论上的优化，因为条带布局将逻辑顺序I/O请求传播到多个DataNode，这可能会降低本地磁盘驱动器上的顺序I/O模式。我们计划在未来的优化中为客户端添加更高级的预取(prefetching)和写缓冲(writebuffering)。

ISA-L的另一个重要优化是支持增量编码。这意味着应用程序在开始编码过程之前不必等待所有源数据。这将有可能使HDFS-EC能够有效地处理慢速写入应用程序以及追加操作。

3.未来的工作

本文总结了HDFS-EC的第一个开发阶段。在HDFS-8031(https://issues.apache.org/jira/browse/HDFS-8031)下已经确定并记录了许多令人兴奋的扩展和优化。后续的一个主要任务是构建一个通用的EC策略框架，允许系统用户部署和配置多个编码模式，如传统的Reed-Solomon，HitchHiker(http://www.eecs.berkeley.edu/~ni ... hiker_SIGCOMM14.pdf)，LRC等。通过抽象和模块化通用编解码器逻辑，该框架还将使用户能够轻松开发新的EC算法。我们还计划进一步优化NameNode内存消耗并减少数据重建延迟。

为了节省位置敏感型（locality-sensitive，就是前文提到的有些强依赖data-locality的MapReduce作业会消耗大量的网络资源的情况。）工作负载的文件存储空间，我们建立了HDFS-EC第二阶段（HDFS-8030，https://issues.apache.org/jira/browse/HDFS-8030）以支持具有连续块布局的EC。

4.总结

与复制备份方式相比，纠删码可以将HDFS的存储开销减少大约50％，同时保证相同的数据可用性。这样可以节省大量在硬件的存储上的投入，因为用户现在可以在相同数量的原始存储上存储两倍的数据。

实现HDFS-EC需要在HDFS的许多部分进行改进，同时需要Cloudera，Intel和其他ApacheHadoop社区的开发人员的协作努力才能完成。HDFS-EC的设计通过使用新的分层块命名协议在NameNode上产生最小的额外开销(主要是对NameNode的内存)，并且还利用IntelISA-L中的优化Reed-Solomon事务(routines )来实现奇偶校验信息的高性能编码和解码。

5.Erasure Coding技术的优劣势

优势

纠删码技术作为一门数据保护技术,自然有许多的优势，首先可以解决的就是目前分布式系统，云计算中采用副本来防止数据的丢失。副本机制确实可以解决数据丢失的问题，但是翻倍的数据存储空间也必然要被消耗。这一点却是非常致命的。EC技术的运用就可以直接解决这个问题。

劣势

EC技术的优势确实明显，但是他的使用也是需要一些代价的，一旦数据需要恢复，它会造成2大资源的消耗：

1.网络带宽的消耗，因为数据恢复需要去读其他的数据块和校验块
2.进行编码，解码计算需要消耗CPU资源

概况来讲一句话，就是既耗网络又耗CPU，看来代价也不小。所以这么来看,将此技术用于线上服务可能会觉得不够稳定，所以最好的选择是用于冷数据集群，有下面2点原因可以支持这种选择：

1.冷数据集群往往有大量的长期没有被访问的数据,体量确实很大,采用EC技术,可以大大减少副本数
2.冷数据集群基本稳定,耗资源量少,所以一旦进行数据恢复,将不会对集群造成大的影响

出于上述2种原因，冷数据（集群）无疑是一个很好的选择。当然如果采购的硬件支持Intel CPU的ISA-L，使用其实也是不错的，毕竟比三副本的方式还优秀！

来源： weixin

作者： Fayson Hadoop实操

原文链接：什么是HDFS的纠删码

https://mp.weixin.qq.com/s/uNXpr35KamdwyJYDZr7Pbg