Hadoop3中将java版本从7升级到8,且引入了纠删码(Erasure Coding),HDFS中的默认3副本方案在存储空间中具有200%的额外开销。

但是,对于I/O活动相对较少冷数据集,在正常操作期间很少访问其他块副本,但仍然会消耗与第一个副本相同的资源量。

也就是说HDFS上只能采用多副本冗余的方式做数据备份,以实现数据可靠性目标(比如,三副本11个9,双副本8个9)。多副本冗余的方式虽然简单可靠,却浪费了成倍的存储资源,随着数据量的增长,将带来大量额外成本的增加。

纠删码能勾在不到50%数据冗余的情况下提供和3副本相同的容错能力,因此,使用纠删码作为副本机制的改进是自然而然,也是未来的趋势。所以为了解决冗余数据的成本问题,在Hadoop3.0版本上,HDFS引入了EC技术。

EC技术深度应用于RAID和通信领域,通过对数据编解码以实现在部分数据丢失时仍能够将其恢复。

我们可以这样理解EC的目标和作用:对n个同样大小的数据块, 额外增加m个校验块, 使得这n+m个数据中任意丢失m个数据块或校验块时都能恢复原本的数据。

以HDFS的RS-10-4-1024k策略为例,可以实现在1.4倍的数据冗余的情况下,达到近似于5副本的数据可靠性,也就是说以更小的数据冗余度获得更高的数据可靠性。

EC算法

常见的EC算法有XOR、RS:

简单EC算法: XOR

XOR是一种基于异或运算的算法,通过对两个数据块进行按位异或,就可以得到一个新的数据块,当这三个数据块中有任意一个数据块丢失时,就可以通过另外两个数据块的“异或”恢复丢失的数据块。

HDFS通过XOR-2-1-1024k的EC策略实现了该算法,这种方式虽然降低了冗余度,但是只能容忍三个数据块中一个丢失,在很多情况下其可靠性依然达不到要求。

改进的EC算法:RS

另一种降低冗余度的编码方式为Reed-Solomon(RS),它有两个参数,记为RS(n,m)。其中,n表示数据块,m表示校验块,需要注意的是,RS算法下,有多少个校验块,就表示最多可容忍多少个数据块(包括数据块和校验块)丢失。

RS 算法使用生成矩阵(GT,Generator Matrix)与n个数据单元相乘,以获得具有n个数据单元(data cells)和m个奇偶校验单元(parity cells)的矩阵。如果存储失败,那么只要n+m个cells中的n个可用,就可以通过生成器矩阵来恢复存储。

RS算法克服了XOR算法的限制,使用线性代数运算生成多个parity cells,以便能够容忍多个失败。

image

  • 编码过程(图左):

    • 把m个有效数据组成一个向量D。
    • 生成一个变换矩阵B:由一个n阶的单位矩阵和一个n * M的范德蒙特矩阵(Vandemode)组成。
    • 两矩阵B和D,相乘,得到一个新的具备纠错能力的矩阵。
  • 解码过程(图右):

    • 取范德蒙矩阵B中没有丢失的行,构成矩阵B`。
    • 取编码过程最后计算的矩阵中没有丢失的行,构成矩阵Survivors。
    • 用B`的逆,乘以Survivors矩阵,即可得到原始的有效数据。

为了更通俗地说明编解码过程,我们以RS-3-2-1024k策略为例,回顾使用EC算法进行编解码的过程。

假设有三块数据:d1,d2,d3,我们需要额外存储两块数据,使得这五块数据中,任意丢失两块数据,都能将它们完整找回。

首先按编码过程构建纠错矩阵:

得到向量D

image

生成一个变换矩阵B

image

得到纠错矩阵D*B

image

假设d1,d2数据丢失,我们通过解码做数据恢复:

取B中没有丢失的行,构成矩阵B`
image

取纠错矩阵中没有丢失的行,构成矩阵Survivors
image

计算B`的逆为:
image

B`的逆,乘以Survivors矩阵,即可得到原始的有效数据:
image

至此,我们完成了在原本3个数据块外再额外存储2个数据块,使得这5个数据块中任意丢失两个都能将其找回的目标。

与三副本的方式对比,在可靠性方面,三副本方式可以容忍存储该文件(数据d1,d2,d3)的机器中任意两台宕机或坏盘,因为总还有一个副本可用,并通过复制到其他节点恢复到三副本的水平。同样,在RS-3-2策略下,我们也可以容忍5个数据块所在的任意2台机器宕机或坏盘,因为总可以通过另外的3个数据块来恢复丢失的2个数据块。

由此可见,三副本方式和RS-3-2策略,在可靠性方面基本相当。

在冗余度(冗余度=实际存储空间/有效存储空间)方面,三副本方式下,每1个数据块都需要额外的2个数据块做副本,冗余度为3/1=3,而在RS-3-2的策略下,每3个数据块只需要额外的2个数据块就能够实现可靠性目标,冗余度为5/3=1.67。

最终,我们通过RS-3-2的方式能够在1.67倍冗余的情况下,实现近似三副本的可靠性。

下图为Hadoop上,不同策略下的有效数据与冗余数据占比示意图。可以看到,三副本方式的存储成本是最高的:

image

条带布局

副本策略以块(Block)为单位,将数据连续写入Block中,直至达到该Block上限(默认128M),然后再去申请下一个Block。以最常见的三副本方式为例,每个Block会有3个相同数据的副本存储于3个DataNode(DN)上。

HDFS EC策略采用的是条带式存储布局(Striping Block Layout)。条带式存储以块组(BlockGroup)为单位,横向式地将数据保存在各个Block上,同一个Block上不同分段的数据是不连续的,写完一个块组再申请下一个块组。

下图为连续布局和RS(3,2)策略下一个BlockGroup布局对比:

image

相比于连续布局,条带布局有以下优势:

  • 支持直接写入EC数据,不需要做离线转化
  • 对小文件更友好
  • I/O并行能力提高

总体来说,EC在Hadoop3中的效果非常明显。


扫码手机观看或分享: