1.问题陈述

当前HDFS每个块有3个副本是出于以下几个方面的考虑：

1）预防DataNode的故障

2）对MapReduce本地性任务提供更好的支持

3）通过在多个副本间选择读取的块，避免DataNodes节点的过载

    副本是昂贵的--在HDFS中默认的3副本机制有200%的存储空间和其它的资源（比如：网络带宽）开销。然而，相对于低 I/O 活动的暖数据集和冷数据集，在正常的操作期间对其额外的副本很少访问，但是其仍然消耗与第一副本相同数量的资源。因此，一个自然的改进是使用纠删码（Erasure Coding）替代副本机制，它使用更少的存储空间提供相同的容错级别，一个典型的纠删码设置，会使得存储空间的开销不超过50% .

    HDFS归档存储（HDFS�6584）也有类似的动机，它是为具有平衡性良好的主存储资源和归档存储资源设计的；EC还优化了同质存储体系结构，此外，可以在归档存储之上使用EC节省多级存储资源。

    Facebook的解决方案是在HDFS之上构建RAID层，这样可以使开发变得容易，但是限制了它与HDFS内核的交互，结果，它将奇偶校验数据存储为用户可见的文件，而不是块，这样很容易导致误操作，此外，它不是HDFS中自带的Feature，它依赖MySql保存元数据，使用MapReduce去创建校验文件，RAID节点会周期性的查询毁坏的文件，增加了NameNode的负载。

2.使用案例

2.1.使用案例：节省 sealed / warm 数据空间

    在谷歌文件系统（GFS）和微软的Azure存储系统（WAS），数据集最初是3份的，在一个文件或则块被确定为“sealed”(不在修改)后，后台任务对它编码，之后删除其余的副本，在HDFS 特定架构、特性和负载下，下面的场景需要被考虑支持：

2.1.1.倾斜数据热度

    HDFS承载多种的工作负载：从批量的MapReduce作业到交互式的、延迟敏感的Impala和HBase查询，因此我们应该允许用户和管理员去指定（或者说暗示）文件的热度。热数据即便是 sealed 的，也将保留副本，这样读客户端可以选择多个副本，避免负载过高的DataNode。

2.1.2.倾斜文件大小

    原始的GFS设计中一个很重要的假设是处理大文件，随着大数据负载能力的发展，这显得不那么重要了，像HBase和MapReduce这样的应用软件会生成很多小的和中等的文件，有些文件只有几个块，更有一些比单个块还小，HDFS-EC应该能通用的处理各种分布类型的文件大小。

2.2.使用案例：高可用性和耐久性

    在当前的副本机制下，HDFS在离线和在线的情况下都能发现和修复块错误，EC块应该有相同级别的保护。

2.2.1.被动恢复（在读路径上）

    当读取一个副本块，并且它的主副本不可用时，第二副本被用于服务请求，块也在后台被重新复制，每一个EC块只有一个副本，当那个仅有的副本在读取的时候不可用时，EC机制应该能够在延迟不高的情况下重构丢失的块从而继续提供读请求服务，恢复延迟对于像Impala这样的高性能的查询引擎是很至关重要的，在服务读请求之前去重构整个丢失的块是不能接受的。

2.2.2.主动恢复（在后台）

    HDFS NameNode从周期性的块汇报中主动发现丢失的块或者坏块，副本块的修复方式是通过拷贝健康的副本到一个新的DataNode，这使得块又恢复到之前的数量；在EC情况下，原始的块应该主动的判断确保他们已经准备好I/O，校验块应该被类似的对待去维持容错的能力。

2.3.使用案例：动态数据访问模式

    一个文件的访问模式可以被随时的改变，当冷数据集变成热数据时，HDFS应该重建它的其它副本用于快速的I/O访问。

2.4.使用案例：在写路径上节省I/O带宽

    当直接应用到写路径上时，EC会通过减少客户端到存储服务节点总的数据写入数量来节省网络和磁盘的带宽，QFS使用这种在线的方式，注意：EC会在块重构的情况下使用比副本机制更多的I/O带宽。

2.5.使用案例：利用多个磁盘主轴

    网络带宽的增长速度比磁盘的快很多，数据中心的存储正变得扁平化，当EC使用小的编解码单元（比如：在QFS中是64K），来自客户端的单个的读写请求可以跨越多个存储服务器，因此会利用它们的磁盘主轴的总带宽。

2.6.使用案例：地理分布式灾难恢复

    地理位置的副本帮助数据集在可能使整个数据中心不可用的故障中幸存下来（HDFS�5442），这种更大的容错会导致双倍的存储开销，在默认的副本因子下，同一个块需要存本储6个副，在这种情况下使用EC会节省大量的存储空间和WAN带宽，Facebook的 f4 BLOB存储系统使用跨3个站点的XOR来达到这一目标。

3.目标

3.1.节省大量的存储空间

    基于我们已经收集的用户请求，节省存储空间是用户最重要的需求，在WAS中，EC目标的存储开销是33%，而采用3副本方式的开销是200%，对大文件和单一策略编码 sealed 的数据，达到这个级别的空间的节省是很容易的，我们的设计应该能高效的处理热数据和小文件，因此，在大多数工作负载下，EC仍然可以显著的节省存储空间。

3.2.灵活性策略

    用户和管理员应能标记文件是热的或者冷的，并且这些提示应该反映在EC的操作中，这个应该与HDFS归档存储工作中的存储策略进行集成，当前的存储策略只能为块的副本定义所需的存储类型，EC需要扩展存储策略来定义和实施分配模式。

    此外，当存储使用接近配额时，某些EC任务应该被标记为高优先级/紧急优先级用于支持释放空间。

3.3.快速恢复/转换

    我们应该使用本地重构编码（LRC）或者它的等同物去减少恢复使用的网络传输，目前最先进的编解码技术应是可插拔的，比如：Jerasure,、Intel ISA库等。

3.4.在写路径上节省IO带宽

    在I/O密集型的工作负载下，EC可以通过减少写入系统的数据的数量来潜在的节省带宽。

3.5.低开销

    EC在NameNode上会不可避免的引入开销以追踪校验块，我们应该尝试去最小化开销。

3.6.透明性/兼容性

HDFS用户应该能够去使用纠删码数据上所有基础的或者高级的特性，包括缓存、快照、加密、追加、截断等等

4.非当前目标

以下特性是低优先级的用户需求，考虑到它们的开发消耗，它们不包含在当前阶段的范围。

4.1.Geo-distributed EC

    当完成geo-replication (HDFS-5442) 之后，我们应该重新关注这个话题。

6.技术途径

6.1.设计决策和体系架构

6.1.1.EC和块布局

图1: EC和块布局

    当前HDFS在单个DataNode上连续的存储每一个块副本，另外一个广泛使用的布局是跨多个DataNodes存储条带数据，其中包括QFS,Colossus, Ceph, 和Lustre。原则上，块布局（连续的VS条带）和冗余方式（副本 VS 纠删码）是2个正交维度，会导致4中可能的组合在图1中。

    本文前面已经讨论了EC的优缺点，另一方面，条带方式利用并行的多磁盘主轴可以很大的增强顺序I/O的性能，然而数据位置将作为代价丢失；在EC的背景下，条带布局有很多重要的优点。首先，它能在线EC，这将绕过转换阶段，直接节省了存储空间，这在高端网络的集群中非常的需要；其次，它自然的分发小文件到多个DataNodes，消除了将多个文件绑定到一个编码组的需要，这会很大的简化文件的操作，比如删除、配额汇报和在联邦集群中不同的Namespace之间数据迁移等。

    在权衡考虑之后，当前阶段的目标是支持条带的EC (Phase 1.1)，{EC+Striping} 和{Replication+Contiguous}表单之间的转换(Phase 1.2)，它导致了以下的设计决策：

        1）编码可以在线完成也可以离线完成。在离线编码中，块最初仍然采用复制的方式，当满足指定条件时，转换该块为EC块。

        2）编解码过程由客户端和DataNode共同完成，客户端为最初的在线编码计算校验码数据，并在读请求期间重构丢失的原始数据；DataNode采用主动/后台恢复方式构建和存储编码的块，并提供将副本模式转换为EC的模式。

        3）只有finalized状态的文件才有资格转换，在转换期间是不支持追加写的。

6.1.2.系统架构

图2: 总体架构

    图2阐明了提议设计的总体架构，添加的组件和逻辑被标记为蓝色的，ECClient指示了HDFS客户端的扩展，它将条带数据往返于多个DataNodes，ECManager被放到了NameNode中，用于管理EC块组，它的责任包括块组的分配、替换、健康检测、和协调恢复工作。

    在正常的I/O操作期间，DataNodes对于EC或者条带是无感知的，添加的ECWorker守护线程用于监听来之ECManager的恢复或者转换命令，它通过从对等的DataNodes中拉取数据、进行编解码计算、建立恢复或转换的块来完成这些请求，并且可能会推送到额外的ECWorker（如果有多个块被恢复或者转换）。在每个操作中，ECManager都会通知ECWorker要使用的块组和编解码约束的名称（例如：使用Reed�Solomon编码给原生的块 {A, B, C} 创建校验块），为了简化设计文档，ECWorker主要的功能聚焦在恢复上，它在转换中的作用将在后续的1.2阶段的工程设计中进行讨论。

6.2.用户接口

    HDFS用户和管理员可以使用几种样式控制存储给定路径时的策略和首选项，本节其余部分将在EC上下文中分析和比较不同的选项。

6.2.1.存储策略

    由于对异构和归档存储的支持，HDFS中引入了存储类型和策略，基于这个框架，新的存储策略（例如：EC）可以被定义，在这个存储策略下的块是EC块，在最初的阶段，原生数据和校验数据都被存储在磁盘存储类型上。

    然后，存在APIs可以用于获取和设置存储策略，例如，下面的命令告诉HDFS在目录/ec�dir下的所有的文件的块都使用纠删码存储。

        hdfs dfsadmin -setStoragePolicy /ec-dir EC

    存储策略被存储在inode的header中，就像在HDFS�6584中实现的那样，如图1中展示的，项目的1.1阶段主要聚焦于在以{EC+Striping}的方式创建的文件，因此，当目录为空时，该目录的EC存储策略需要被配置，一旦配置将会被修复 -- 类似加密区域。

    在1.2阶段，通过改变存储策略可以完成纠删码和副本方式之间的转换，通过Mover或则ECManager直接的触发一个新的策略被执行，详情将在接下来的1.2阶段设计中被讨论。

在这个框架下，用户应该有能力为目录配置编解码约束，特别是，接口应支持特殊的编解码算法（例如：Reed�Solomon vs. XOR）和块组布局（例如：3-of-6 vs. 4-of-10）。

6.2.2. DFS 命令

    和使用hdfs dfs -setrep的方式改变一个路径的副本因子类似，新的dfs命令被添加用于直接将一组文件在副本和纠删码方式之间转换。

    ● hdfs dfs -convertToEC -path <path> <EC schema>: 转换path下的所有的块为EC的格式（不在EC格式，并且可以被编码）

    ● hdfs dfs -convertToRep -path <path>: 转换path下的所有的块到副本格式。

6.3.协议和元数据扩展

6.3.1.块组

块组

    所有的纠删码操作中心是围绕在块组的概念中的，它在初始编码中形成，在恢复和转换中被查找，一个轻量级的类BlockGroup被创建用于在编码块组时记录原始块和校验块。EC存储策略，和编解码约束一样，可以在文件的inode（header 或则扩展属性）中找到，在条带布局下，HDFS客户端需要并行的操作块组中所有的块，因此我们建议去扩展文件的inode用于切换连续布局和条带布局的模式，条带布局的文件有一系列的BlockGroups，BlockGroup即没有ID也没有时间戳，在BlockGroup中的所有的块可能会使用连续的IDs并使用相同的时间戳，详见“减少NameNode内存使用”小节。这就允许使用第一个Block代表整个块组，重用存在的blockmanagement 代码去处理块组，只有第一个块的ID和共享的时间戳会被存储在BlockGroup中，为了提供清晰的概念的讨论，本文档后面的部分使用从真实的实现中抽象出来的BlockGroup去声明一个逻辑的EC块组。

6.3.2.ErasureCodec

    编解码算法应是可插拔的，由ErasureCodec接口支持，提供了连接到流行的库的一组接口的实现，比如英特尔的ISAL(Intelligent Storage Acceleration Library)，下面的2个关键的EC参数应该也被配置，纠删码编解码详细的设计可以在HDFS�7337中被找到，如下：

        M：在条带布局组中原始块的数量

        K：在条带布局组中校验块的数量

    接着，(M,K)-codec可以容忍K个并发的坏块，M也是访问原始数据和恢复不可用的块的最小需求的块的数量，K/M比率是相对的存储开销比率，(M,K)-codec的一个例子是(6,3)�Reed�Solomon，(6,3)�Reed�Solomon被选择作为默认的编解码器。

    可能需要添加其它的块状态，例如，当连续布局的EC在2阶段被启用时，每个块会有一个二进制的标志标识它是否是校验块（isParity），连续的校验块被创建、存储和汇报与原生的方式相同，他们有固定的块IDs与相同组中的原生块是不相关的，它们的副本（通常只有1个）被存储在DataNodes的RBW和finalized目录中，具体取决于阶段，它们也会包括在块汇报中，与连续奇偶校验块唯一的区别是缺少文件从属关系。

6.4. Client Extensions

图3: 客户端扩展 (图2的修订版)

6.4.1. ECClient

    HDFS客户端将被扩展成并行的从多个DataNodes读写，如图3所示，注意：当前的高层设计是基于QFS客户端，并将在实现阶段为HDFS定制，特别是，当在文件中定位一个位置时，ECClient从NameNode获取的是BlockGroup信息而不是块的信息，如下：

        C  --每个条带单元的大小，通常是 64kB

        B  --   I/O缓存区的大小，通常为 1MB

    更小的条带单元的尺寸C可以提高I/O并行度，但是增加开销，更大的缓存大小B可以提高I/O效率，但是会延迟数据保护。

    当在一个文件上操作时，HDFS客户端检测它的存储策略去决定是否去使用ECClient为I/O进行分段。

    对于EC文件，可以像使用普通文件类似的方式去使用hflush/hsync/append，在普通文件上的hflush/hsync/append的设计查看 [HDFS�265]。

6.4.2. EC Writer

    当向一个EC文件写入时，客户端会并行的向多个DataNodes写入条带（例如：64K）数据，EC策略采用(6,3)�Reed�Solomon时，客户端数据写入到前面的6个DataNodes，将校验数据写入剩下的3个DataNodes，注意：DataNodes和客户端都有缓存存在。因此，当客户端写一些数据到DataNode，这些数据会先被拷贝到一个缓存中（例如：1MB），然后刷出去；DataNodes的写缓存相对较小，通常4KB，在本文剩下的部分，我们会把缓存忽略掉。

    起初，客户端写第一个条带数据到第一个DataNode，写第二个条带数据到第二个DataNode等等，一旦它有了第6个条带数据，它会计算出3个校验数据条带，并把它们写入到剩下的3个DataNodes中，和写管道类似（例如：写管道用于多个副本），一旦一个DataNode已经接收到了来自客户端的包（数据包或则校验包），它会发送一个确认信息到客户端，客户端会不断的写，除了最后一个包外，其它的包客户端都不会等待来自DataNode的确认信息。

    除了最后一个条带组，客户端总是发送完整的条带数据到DataNode，在文件的末尾，数据长度可能不是数据条带组的大小（在这个例子中是 6 X 64K）的倍数，客户端一旦收到关闭文件的请求就会计算校验数据，当最后一个条带组不完整时，客户端还会在末尾写入最后一个条带组的长度。

    解码所需要的条带组的长度如下所述。

6.4.3. 在写期间处理Datanode故障

    在写数据的时候当一个或多个DataNode失败（例如：DataNode挂掉，网络问题）时，客户端会忽略失败的DataNodes，为块组中剩下的所有的块重新生成时间戳，之后往剩下的DataNodes上继续写数据，前提是剩余的DataNodes的数量大于等于最小需求的DataNodes的数量，注意：块组中的块共用相同的时间戳，直到客户端完成到块组的写入前，丢失的块不能恢复，恢复操作通常是由NameNode中EC重构计划调起的。如果剩余的DataNodes小于最小需求的DataNodes，客户端会抛出一个写失败的异常，EC策略采用(6,3)�Reed�Solomon时，最小需求的DataNodes是6，客户端可以容忍3个DataNodes失败。

    另外一种方式是关闭当前的BlockGroup，之后使用变长块组长度特性继续写一个新的BlockGroup [HDFS�3689]。

6.4.4. 慢速写入器，故障时更换Datanode

    对于HDFS写管道（多副本机制），有一个特性replace�datanode�on�failure用于当DataNode写管道失败时，可以使用新的DataNode来替换它，该特性的设计用于支持慢写者，因为慢写者不是EC文件（慢写者应该使用写管道）的使用案例，所以特性replace�datanode�on�failure不支持EC文件。

6.4.5. 读取已关闭文件

    因为文件已经被关闭了，它的长度是固定的，客户端可以读取9个DataNode中的任意6个，带有数据块的DataNode比带有校验块的DataNode更可取，因为这样可以减少EC块重构工作量。

    对于有完整数据的块组，客户端从选择的6个DataNodes中读数据块/校验块，如需要会重构数据块。

    对于部分块组（仅对文件中最后一个块组有效），如果没有校验块被调用，并且不需要EC重构，客户端会从选中的6个DataNodes中读数据块/校验块，否则，客户端还要从对等的DataNode上读取最后一个条带的长度；在重构EC数据块前，客户端需要校验来自校验块的最后的条带长度、数据真实的长度和从NameNode中获取的文件长度是否匹配。

6.4.6. 读正在被写入的文件

    当一个文件正在被写时，块组中的每一个块的大小可能不相同，客户端首先从带有数据块的DataNode获取数据长度，从带有校验块的DataNode获取校验长度和最后一个条带的长度，它使用长度信息来决定最大有效长度，并从中选择6个要读取的DataNode，之后，客户端可以从中读取数据，如果需要还可以像以前一样重构数据，它保证新的客户端可以像以前的客户端读取器一样读取相同的数据量。

6.4.7. Hflush

    当hflush被调用，客户端将所有存在的数据和校验码刷新到所有的DataNodes，之后客户端会阻塞等待所有的DataNodes返回的最新的确认信息，一旦接收到了所有的确认信息，它将返回成功，这个时候，新的读取器能够读取到hflush位置之前的所有的数据，当恢复写操作时，并且hflush的位置不在完整的条带组的边界时，客户端需要重写最后一个校验条带。

6.4.8. Hsync

    hsync 和hflush类似，只是DataNode在发送确认信息之前还会发送一个本地fsync调用。

6.4.9. Append

    追加数据到一个存在的BlockGroup，需要有效的DataNode的数量大于等于最小请求的DataNode数量，它从BlockGroup中的所有块中更新生成的时间戳开始，之后，客户端写数据到所有有效的DataNodes，类似于hflush，当最后一个条带组不完整时，客户端需要去重写最后一个校验条带。

    追加也可以支持使用变长块长度特性[HDFS�3689]，例如，追加数据到一个新的BlockGroup，但是不能重新打开上次存在的BlockGroup。

6.4.10. Truncate

    截断一个EC文件，除了最后一个条带的校验文件可能需要去重新计算，其它的类似于截断一个正常的文件；和append类似，它需要有效的DataNode的数量大于等于最小需求的DataNodes的数量，它更新BlockGroup中的所有块的生成时间戳开始，对于条带组边界的截断，客户端会截断所有的数据块和校验块，之后就完成了截断，否则，客户端读取包含在截断位置的所有的数据条带，如果有些数据块是无效的，为了重构丢失的数据条带，客户端也需要读取包含在截断位置的校验条带；然后，为截断的数据计算新的条带组的长度和新的校验数据，最终，客户端截断DataNode上的所有的数据块，并截断校验块，使用条带组的长度重写最后一个校验条带。

    如果正在进行升级或者截断一个快照的文件，为了支持回滚或者从快照中读取数据，首先需要复制最后一个块现有的数据。

6.4.11. BlockGroup 状态

    当BlockGroup被创建，它处于UNDER_CONSTRUCTION状态，一旦ECClient完成了写入BlockGroup，它将发送所有剩余的R个数据块写入NameNode（某些块可能由于失败被排除），如果NameNode接收到的R个块大于等于最小需求的块数M（例如：策略(6,3)�Reed�Solomon的M是6），BlockGroup 会被转换为COMMITTED状态，当NameNode从M个DataNodes接收到M个块的信息时，BlockGroup 会被转换为COMPLETE状态，当一个块组被恢复时，它是UNDER_RECOVERY状态。

6.4.12. 生成时间戳

在一个块组中的所有的数据块和校验块共用相同的生成时间戳，块组自己没有生成时间戳，为了内存的效率，共用的时间戳被存储在块组对象的实现中。

6.4.13. BlockGroup 恢复

    BlockGroup的恢复是一个过程，它将更新所有当前有效的块的生成时间戳，使得有效的块的生成时间戳变新了，无效的块的生成时间戳保留不变，这样，如果将来出现无效的块，它们可以被排除和删除，这个用于故障处理、追加和截断。

6.4.14. Client-Datanode 连接

    为了写一个EC文件，客户端会并行的写入到9个DataNodes，它的写入速度是现存的3副本写管道的方式的9倍，读取一个EC文件会并行的从6个DataNodes读取，它需要6倍的连接，这会导致一个客户端同时读写多个文件是个问题（连接数太多了），这个问题可以通过改变DataTransferProtocol 的实现采用复用连接的方式来修复，以便从客户端到DataNode的多个并发的块的读写仅使用一个连接。

7.NameNode Extensions

    当前，HDFS的NameNode运行了ReplicationMonitor守护进程周期的执行块的复制和失效任务，这些任务分别是对队列UnderReplicatedBlocks 和 InvalidateBlocks 的插入和维护的，这种机制非常适合调度后台块编解码任务，包括主动块恢复和进行副本方式和EC方式的切换。

    下面的图4说明了 在NameNode上提议的扩展（主要在BlockManagement上）

图4:NameNode 扩展

7.1. ECManager

    这个组件用于管理BlockGroups和相关的编解码约束，举个简单的例子，当一个 {Striping+EC} 文件被创建并开始写入，ECManager将用于服务来自客户端的请求去分配新的BlockGroups并存储它们到INodeFile下，在当前阶段，初始在线编码和从副本到EC的转换中都会被分配BlockGroups，ECManager还为块恢复工作中查找BlockGroup信息提供工具。

7.1.1. EC块重构

    当一个块组中的一个或多个EC块丢失，NameNode会为重构EC块调度块组，对于(6,3)�Reed�Solomon策略，因为它能容忍丢失3个块，1个或者2个块的丢失情况是处于低优先级的，丢失3个块的情况是处于高优先级，我们用NameNode中现存的副本调度框架进行EC块重构，如下所述：

7.1.2.UnderReplicatedBlocks

    UnderReplicatedBlocks会将新的优先队列（例如：QUEUE_CONVERSION）添加到5个现存的队列中，去维护编解码和复制任务相对的顺序，

    1）当发现校验块或者在ENCODED状态的原生块丢失，丢失的块会被添加到UnderReplicatedBlocks中，它的优先级由所在组的条件决定，例如：如果组中所有的校验块都丢失，它们应该被添加到QUEUE_HIGHEST_PRIORITY优先级中，可以为细粒度的区分添加新的优先级（例如：相对于校验块原生块的丢失）

    2）新的优先级QUEUE_CONVERSION，被用于转换副本块到EC块，反之亦然，因为这个转换与块的可用性无关，在UnderReplicatedBlocks中新的优先级应该比现存的更低。

    3）与常规的块复制任务相比，编解码一个块会消耗更多的I/O带宽和CPU周期，因此，应该对块的编解码任务限制总的系统资源的消耗。

7.2. ErasureCodecWork

    ReplicationMonitor将会被扩展以区别副本和编码任务，如果校验块被创建，或者在BlockGroup中的原始块被修复，会催生一个ErasureCodecWork 任务去替换ReplicationWork，它会做如下的事：

    1）从ECManager中获取所有的编解码相关的信息，包括BlockGroup 和相关的编解码约束，一个新的块替换算法需要选择目标DataNode进行编码工作和主持恢复或转换块，最终的BlockGroup 应该分布在不重复的DataNodes上（在多余的副本被删除后），理想的状态是放在不重复的机架上，所以任何节点/机架的损坏最多会影响块组中的一个块，可以应用几个有意义的优化，首先，分发编码工作到多个DataNodes节点以减少目标节点上的CPU负载，其次，将校验块放在组中原生块尽可能多的副本的附近，以便编码可以部分的在本地数据上完成 ，应将这些副本作为多余副本删除，以维护组中条带分布模式。

    2）发送编解码命令选择DataNode

    3）在接收到来自DataNode的确认成功的编码的回应之后，通过添加任务到InvalidateBlocks删除多余的副本

    4）当正在恢复丢失的原生块时，一旦解码块被初始化完成，选择的DataNode应该回应ErasureCodecWork ，之后在blocksMap中的块的存储位置需要被更新，允许客户端在重构时去读取部分块的数据。

8. DataNode扩展

图5:DataNode 扩展

8.1.ECWorker

    这是在DataNode上的主要的纠删码组件，如图5所示，当接收到来之NameNode的编解码命令后，ECWorker 解析命令并获取组中包含原始块的DataNodes主机的列表 -- 在修复原始块的情况下，组中校验块对应的一个或多个DataNodes主机也应该包含在列表中，之后它尝试去连接这些节点的DataXceiver ，接收数据包去逐渐的重构校验块（或者恢复原始块），在校验块被成功的构建（或者原始块被修复）后，ECWorker 会发送一个回应给NameNode，此时，可以计划删除组中多余的块副本。

9.优化

9.1. 减少NameNode 内存使用

条带方式通过引入更多的块增加NameNode的内存的使用，例如，HDFS当前将一个128MB的文件存储为带有3个副本的块，在blocksMap中产生一个条目，使用条带方式和Reed�Solomon (6,3)约束，文件会使用9个块，每个块有一个副本，这个可以通过使用连续的IDs（或者其它的可预测的方式）对块进行编号来减缓NameNode内存压力，下面提供了一个编号方案，如图6所示。

    1）64位的块ID空间被分成2部分，正常的块ID空间和EC块ID空间，最高的位表示这个块是否是一个EC块（因此属于一个块组）

    2）对于EC块：

        a. 最高位是1。

        b. 使用最低4位标记一个块在BlockGroup中的序号

        c. 块组中第一个块的ID的最低4位是0

        d. BlockGroup不是一个ID

    3）对于正常的块，最高位是0，使用剩余的63位生成IDs

    4）除了BlockGroup中第一个块的ID被放入到blocksMap中外，还要保留一个blockGroupsMap ，当DataNode汇报一个块时，它可以很容易的推断出它是否是一个编码的块，如果是的，则确定它的BlockGroup。

图 6:连续的NameNode的块

    这次优化再加上其它的一些正在进行的努力，应该可以帮助避免大多数生产集群中的内存不足：

    1）HDFS�6658 (optimizing block replicas list)

      在没有使用压缩的情况下节省11%的内存使用。

    2）HDFS�7244 （享元模式）

    在堆外内存的情况下，......，BlockInfo对象的内存的使用可以减少到一个非常小的常量值

    3）将blockId从long类型缩小到一个6字节的数组

    这将为每个块节省8 - 6 = 2字节

9.2.与随机块ID的冲突

    因为早期的HDFS支持随机的块IDs，为EC块保留的块IDs可能已经被集群中现有的块使用，在NameNode启动期间，它会检测是否有保留的EC块IDs被非EC块使用，如果有，当在blockGroupsMap 中查找失败时，NameNode将会在额外的blocksMap中查找。

9.3. Datanode 退役

    比起副本机制EC块的重构是昂贵的，因为副本可以从任意有效的拥有该副本的源DataNode上拷贝，然而，如果一个EC块是无效的，它需要从6个DataNodes读取数据用于恢复失效的块，因此，当一个DataNode要被从集群中移除时，在DataNode退役前移除它上面的所有的EC块是个好的主意。对于重启DataNode,为了指示该DataNode将很快就重新加入集群，为DataNode引入了一个新的睡眠状态，在重启期间，NameNode不会为这个DataNode上的任意EC块调度重构工作。

9.4. MapReduce数据本地性

    MapReduce工作在 record 的粒度，因此，我们需要对齐record和条带边界，这种对齐可以使用隔离的MapReduce作业来完成，MapReduce任务的调度算法也应该知道条带模式。

9.5. Block 移动

    Balancer和Mover用于跨DataNodes移动块副本（可能跨机架），它可能将块放置在同一编码组的同一机架或者DataNode上，从而降低了容错级别，这种兼容性的问题可以通过2个选项来解决：

1）一个简单的方式是禁用对EC块的balance操作，同时，因为数据存储策略（例如：HOT/WARM/COLD）是被用户准确的定义的，如果编码的块要被移动，我们应该跳过它们。

2）一个更有效的方式是让Balancer和Mover对EC组是感知的，避免上述的放置决定Appendix: 3-replication vs (6,3)-Reed-Solomon

10.附录：3-replication vs (6,3)-Reed-Solomon

我们在这部分比较3副本方式和 (6,3)-Reed-Solomon方式

10.1. 容错：

对于数据的访问最小需要的块数：

磁盘空间使用：

命名空间使用：

客户端到DataNode的连接数：

10.2. 网络流量

假设一个机架最多2个块，

Keys: LN = local node, LR = local rack, RR = remote rack 

写数据：

读数据假设客户端可以被移动到任意的DataNode，并且集群有足够的大以至于2个不同的块总是存储在不同的机架。

 3-replication(6,3)-Reed-Solomon

对于1个块的丢失重构假设机架本地化是可能：

11.引用:

[Fan09] “DiskReduce: RAID for Data�Intensive Scalable Computing”, PDSW 2009 [Ford10] “Availability in Globally Distributed Storage Systems”, OSDI 2010

[Harter14] “Analysis of HDFS Under HBase: A Facebook Messages Case Study", FAST 2014 [Huang12] “Erasure Coding in Windows Azure Storage”, USENIX ATC 2012

[Khan12] “Rethinking Erasure Codes for Cloud File Systems: Minimizing I/O for Recovery and Degraded Reads”, FAST 2012

[HDFS-265] Append/Hflush/Read Design

[HDFS-3689] Add support for variable length block

[Intel-ISA] https://01.org/intel@�storage�acceleration�library�open�source�version [Muralidhar14] “f4: Facebook’s Warm BLOB Storage System”, OSDI 2014 [Nightingale12] “Flat Datacenter Storage”, OSDI 2012

“The Quantcast File System”, VLDB 2013

[Sathiamoorthy13] “XORing Elephants: Novel Erasure Codes for Big Data”, VLDB 2013