HDFS文件纠删码技术

HDFS文件纠删码技术学习笔记

HDFS的三副本技术

HDFS（Hadoop Distributed File System）是基于 流数据 访问模式的 分布式文件系统 ，其设计建立在 “一次写入、多次读取” 的基础上，提供高吞吐量、高容错性、高可靠性的数据访问，能很好地解决海量数据的存储问题。

高可靠性。数据自动保存多个副本，通过多副本提高可靠性。

HDFS 默认保存 3 份副本。

第一个副本：放置在 上传文件 的数据节点（第一个副本如果是在 集群外 提交，则随机挑选一个 CPU 比较空闲 、 磁盘不太满 的节点）；
第二个副本：放置在与 第一个副本 不同 的机架的节点上；
第三个副本：放在与 第二个副本 相同 的机架的其他节点上。

缺点：冗余度高：3

(HDFS过去使用暴力的三副本技术，随着数据量越来越大，现代数据中心越来越多的使用纠删码技术来减少冗余度，同时保证了数据的容错性。)

Hadoop3.x 使用纠删码，将冗余度从3倍降低到1.4倍左右

纠删码（ErasuredCode/EC）

Erasure Code是一种编码技术，它可以将n份原始数据，增加m份数据，并能通过n+m份中的任意n份数据，还原为原始数据。即如果有任意小于等于m份的数据失效，仍然能通过剩下的数据还原出来。 纠删码技术在分布式存储 系统中的应用主要有三类，阵列纠删码（Array Code: RAID5、RAID6等）、RS(Reed-Solomon)里德-所罗门类纠删码和LDPC(LowDensity Parity Check Code)低密度奇偶校验纠删码。 LDPC码目前主要用于通信、视频和音频编码等领域。

多副本策略即将数据存储多个副本（一般是三副本，比如HDFS），当某个副本丢失时，可以通过其他副本复制回来。三副本的磁盘利用率为1/3。

纠删码技术主要是通过纠删码算法将原始的数据进行编码得到冗余，并将数据和冗余一并存储起来，以达到容错的目的。其基本思想是将n块原始的数据元素通过一定的计算，得到m块冗余元素（校验块）。对于这n+m块的元素，当其中任意的m块元素出错（包括原始数据和冗余数据）时，均可以通过对应的重构算法恢复出原来的n块数据。生成校验的过程被成为编码（encoding），恢复丢失数据块的过程被称为解码（decoding）。磁盘利用率为n/(n+m)。基于纠删码的方法与多副本方法相比具有冗余度低、磁盘利用率高等优点。

两种技术	冗余度	计算开销	网络消耗	恢复效率
多副本(3副本)	3	几乎没有	较低	较高
纠删码(n+m)	(n+m)/n	高	较高	较低

RS码原理

以n=5，m=3为例。即5个原始数据块，乘上一个(n+m)*n的矩阵，然后得出一个(n+m)*1的矩阵。根据矩阵特点可以得知结果矩阵中前面5个值与原来的5个数据块的值相等，而最后3个则是计算出来的校验块。

以上过程为编码过程。D是原始数据块，得到的C为校验块。

假设丢失了m块数据。如下：

那我们如何从剩余的n个数据块（注意，这里剩余的n块可能包含几个原始数据块+几个校验块）恢复出来原始的n个数据块呢，就需要通过下面的decoding（解码）过程来实现。

第一步：从编码矩阵中删去丢失数据块和丢失编码块对应行。 将删掉m个块的(n+m)1个矩阵变形为n1矩阵，同时B矩阵也需要删掉对应的m个行得出一个B’的变形矩阵，这个B’就是n*n矩阵。如下：假设D1、D4、C2丢失，我们得到如下B’矩阵及等式。

第二步：求出B’的逆矩阵。

第三步：等式两边分别乘上B’的逆矩阵。

B’和它的逆矩阵相乘得到单位矩阵I，如下：

左边只剩下原始数据矩阵D：

至此完成解码过程。

注1：图中黄色部分为范德蒙矩阵。至于如何生成B矩阵，以及如何求B’的逆矩阵，请查看其他相关文献，这里不再赘述。

注2：m的值决定了最多可同时容忍的坏块数量。m越大，容错越强，但冗余度也越大。

优缺点

低冗余度，高磁盘利用率。

数据更新代价高。 数据更新相当于重新编码， 代价很高， 因此常常针对只读数据，或者冷数据。

数据恢复代价高。 丢失数据块或者编码块时， RS需要读取n个数据块和校验块才能恢复数据， 数据恢复效率也在一定程度上制约了RS的可靠性。

优化方案

最佳的解决方案是分组，把单个磁盘故障的影响范围缩小到各个组内部，当磁盘出现故障时，在该组内部解决，在恢复过程中读组内更少的盘，跑更少的网络流量，从而减小对全局的影响。

LRC

LRC(Locally Repairable Codes)意为局部校验编码，其核心思想为:

将校验块分为全局校验块和局部校验块，在故障恢复时分组计算。

微软 Azure 和 Facebook 通过这项技术将数据冗余度降低到 1.33x 和 1.4x。

以微软 Azure 的云存储(Windows Azure Storage)实现为例：

它采用LRC(12，2，2)编码，12个数据块为一组编码，并进一步将这12个数据块平均分为两个本地组，每个本地组包括6个数据块，并分别计算出一个局部校验块，之后把所有12个数据块计算出两个全局校验块。
当发生任何一个数据块错误时，只需将本地组内的数据和校验块用于计算，即可恢复出原始数据。
恢复代价(通过网络传输的数据块数量)就由传统RS(12，4)编码的12变为6，恢复过程的网络IO开销减半，同时空间冗余率保持不变，仍为(12+2+2)/12=1.33

当前LRC的主流优化方向之一就是选取合适的分组方式和校验块数量，保证容错的同时尽可能降低冗余度。

基于修复分层的纠删码技术-DRC

在节点内部做一定的计算，从而减少修复时的传输流量

DoubleR 提出修复分层这一概念，该概念将修复操作分成内部机架和交叉机架 层。具体而言，DoubleR 选择分层块放置，每个机架放置一个条带的多个块，从而以减少机架级别容 错为代价，最小化交叉机架恢复流量。为了修复一个坏块，每个机架一个选定节点能使用相同机架中 其他可用块来执行部分修复操作，然后发送该机架的部分修复结果到目的节点，目的节点结合多个部 分修复结果来重建坏块。通过修复分层，理论上证明了通过名为 double regenerating codes(DRC) 的一类新的再生码，能最小化交叉机架修复流量。

DRC基础架构

修复过程：考虑一个由多个机架组成的分层数据中心，每个机架包含多个存储节点。同一个机架 内的多个节点通过机架顶部的交换结构连接，不同机架通过名为网络核心的抽象交换结构连接。修复 坏块是通过位于同一机架（本地机架）和不同机架（非本地机架）的其他节点检索可用块来完成的。 DoubleR 选择一个本地机架节点负责重构坏块，同时在每个非本地机架选择一个 relayer 节点来聚 合转发该机架的修复结果。通常来说，一个中继节点应该是本地存储用于修复的可用块之一，以便节 省内部机架网络传输流量。每个非本地机架中，每个节点发送编码子块到中继节点，中继节点重新编 码这些子块。这些中继节点将重新编码的子块发送到目标处，该目标重构这个坏块。在 DoubleR 部 署中，我们可以指定不同中继节点和目标节点来修复坏块，从而实现并行。

两大系列 DRC 结构

两大系列 DRC 分别是 DRC(n, k, n/n-k) 和 DRC(3z, 2z−1, 3)，两大系列 DRC 的修复过程有 差别，但核心思路是一样的。编码后的 n 个数据块存在线性相关，当出现坏块需要修复时，现在本 地机架将一个条带的多个块进行组合，然后将组合结果传输到目标节点即可。组合这一关键步骤大 幅度减少了修复坏块时的交叉流量。图 1展示了两大系列中各一个案例的结构图。

实验验证

实验设备：在 11 台机器的集群上进行的。每台机器都有一个四核 3.4 GHz Intel Core I5-3470,16 GIB RAM，以及希捷 ST1000DM003 7200 RPM 1 TIB SATA 硬盘。所有机器都通过 10 GB / S 以太网交换机互连。我们在 10 台机器上部署 Facebook 的 HDFS。一台机器运行 NameNode 和 RaidNode，其他 N 个机器中的每一个都运行（n，k，r）代码的 DataNode，其中 N 在我们的评估 中最多 9 个

在数据恢复性能的实验评估：只有当交叉机架传输是数据中心的性能瓶颈时，我们才能声称 DRC 与其它纠删码相比具有显著优势。

在错误读取性能的实验评估：DRC 显示了性能提升通过最小化跨机架修复流量来降低读取性能。

条带大小和块大小影响评估：条带大小过大或者过小都会引起性能下降，大小适中时块修复吞吐 量均处于较高水准。块大小较小时，块修复吞吐量随着块大小增加而增加，块大小达到一定时（该文 献实验为 64MiB），修复吞吐量达到最大值。