郑杰辉

(厦门海洋学院 信息技术系,福建 厦门 361000)

分布式存储系统是大量普通PC服务器通过Internet互联,对外作为一个整体提供存储服务[1]。分布式存储系统具备如下几个特性:1)可扩展。分布式系统可以扩展到几百台到几千台的集群规模,而且,随着集群规模的增长,系统整体性能表现为线性增长。2)低成本。分布式存储系统的自动容错、自动负载均衡机制使其可以构建在普通PC机之上。另外,线性扩展能力也使得增加、减少机器非常方便,可以使用较低的成本实现自动运维。3)高性能。无论是整个集群还是单机服务,都要求分布式系统具备高性能。4)易用。分布式存储系统需要提供通用的对外接口,另外也要求具备完善的监控、运维工具,并能够方便地与其它系统集成[2]。如 Hadoop云计算系统导入数据。在现代信息技术和互联网技术不断发展的当今社会,分布式存储系统的挑战主要在于数据、状态信息的持久化,要求在自动迁移、自动容错、并发读写的过程中保证数据的一致性[3],所涉及的技术主要包括分布式系统和数据库[4]。无论分布式存储系统中哪个节点发生故障,如何有效提升存储系统可靠性和修复效率都是必须面对的关键技术难点。在此基础上,本文选取目前分布式存储系统中常见的集中节点修复技术进行对比分析,以期更好地实现节点故障修复效率和质量。

1 层次码与循环RS码

在分布式存储系统中,层次码(HC)可以实现纠错/删除码和局部修复码的结合,但是如果存储系统发生故障时,由于连接节点的个数比原始数据节点数少,在修复过程中如果仅仅连接任意k个节点并不能实现数据恢复[5]。例如对于包含k个数据块的文件,基于层次码的具体编码规则主要包括:1)构件第0层编码HC-(k0,r0),即由k0个原始数据块与r0个校验块构成;2)构件第1层编码HC-(k1,r1);3)重复构件编码并增加编码层数,直至第i层编码为HC-(ki,ri)[6]。图1中列出了层次码的编码图,图1(a)中G2,1为0层编码组,b1、b2和b3为原始数据块,如果某一数据块发生丢失的情况下(如b1),编码图中可通过b2和局部校验块进行修复(如b3),在这个情况下,要想恢复b1的数据块,则需要读取b2和b3数据块信息,此时的修复局部性为2;图1(b)中G4,1为1层编码组,如果某一数据块发生丢失的情况下(如b7),需要读取的数据块包括b1、b2、b4和b5,此时的修复局部性为4。综合而言,在采用层次码进行分布式存储系统的节点修复时,修复带宽开销和局部修复性都会发生不同程度降低。

图1 层次码的编码图

循环RS码是线性循环编码,即编码后的码组T(X)左移或右移都必然还是有限组码组中的一组,并且T(X)码组能够被g(X)整除,g(X)为生成多项式[7],这种由传统RS码衍生而来的编码可以通过调节校验块的生成方式来降低分布式存储系统中的节点故障[8]。图2为循环RS码的编码图,其中原始数据节点s、校验节点数m和节点数t分别为6、2和3,左侧部分的N0、N1、N2、N3、N4和N5为原始数据节点,右侧部分的N6、N7为校验节点,左侧部分编码图中的圆圈和三角形分别表示N6、N7的生成方式。从图2中可见,在分布式存储系统中若发生某个节点故障,编码图中读取15个数据块即可完成数据修复,这种循环RS码的方法相对传统RS码方法的数据处理量减少了约16%,此外,即使在分布式存储系统中发生多个节点故障,循环RS码也会相较于传统RS码具备更优的数据处理能力。

图2 循环RS码的编码图

2 旋转交织码

实际应用过程中的分布式存储系统通常会出现较多用户访问一个节点的情况,此时的节点超负荷运行会影响分布式存储系统的整体运行能力[9],尤其是当分布式存储系统中出现某个节点故障时,其它节点的超负荷会更加严重,极端情况下还会发生系统瘫痪。因此,需要设计一种能够均衡节点负载的编码,旋转交织码即在这种情况下应运而生。从图3的旋转交织码的编码图中可见,该编码可以对三组存储单元进行标号并形成位置标识,这样A组、B组和C组中相同位置处的数据块可以实现旋转交织,即分布式存储系统中某节点发生故障时,可通过另外两组标号位置相同的数据块对节点实现修复,并均衡运行过程中节点负载状况;但是,与此同时,由于修复过程中参与节点的数量较多(约占整个系统节点数的67%),旋转交织码存在较大的修复局部性。

A组

B组

C组

图3旋转交织码的编码图

Fig.3 Coding diagram of rotary interleaved code

进一步对旋转交织码进行层次构造,以降低分布式存储系统中节点故障的修复局部性,具体包括将旋转交织码中的层次码按照层次化进行扩展,从而降低残余节点修复的数据块,值得注意的是,虽然重新层次构造的旋转交织码的节点修复数据块会减小,但是不会影响到节点负载均衡。

图4为分布式存储系统中单节点故障的修复示意图,其中,故障节点位于节点p1,0处,用灰色阴影标识,相应的单元数据片也用阴影标识(1,9,5)。从图中可见,如果运行过程中节点p1,0处发生故障,则可以通过下一层p0,0处和p0,1处节点进行修复,也可以通过上一层p2,0处节点和同层p1,1处节点进行修复。相应地,如果阴影标识处位置标号为1,9,5处的数据块发生故障或者丢失,可用前述的旋转交织码的方法找到相同位置标号处的数据进行修复。此外,如果单元数据片中同时出现了几个或者多个节点故障,参照旋转交织码的修复处理方法,相应地通过其他单元数据片相同位置编号处的数据来进行修复,修复过程中还可以较好地满足节点负载要求。

当分布式存储系统中出现多节点故障,采用旋转交织码进行节点故障修复时的示意图如图5,其中,出现故障的节点处都用阴影进行标识。可见,该套分布式存储系统中同时出现了7处故障,分别位于p3,0处、p2,0处、p1,0处、p0,2处、p1,2处、p0,4处和p0,6处。通过前述的旋转交织码修复方法可知,不同位置处的故障可以通过其他两个单位数据片中的数据进行修复,则可以先通过p0,0和p0,1修复p1,0,通过p1,1和p0,3修复p0,2,通过p07和p1,3修复p0,6,通过p2,1和p1,3修复p1,2;再通过p1,0和p1,1修复p2,0,通过p1,2和p0,5修复p0,4;最后再通过p2,0和p2,1修复p3,0,从而实现了整个分布式存储系统中多节点故障的修复,且在整个过程中,旋转交织码的修复都为均衡修复。

在分布式存储系统的多节点故障修复过程中,修复带宽开销、修复局部性和修复复杂度直接决定了编码的优劣,在此基础上,对前述的层次码、循环RS码和旋转交织码的性能进行了对比分析,并设定层次码中第0层包括的节点数为2m。从图6和图7的节点故障时修复带宽开销的变化可知,单节点发生故障时,旋转交织码的修复带宽最小,而两节点发生故障时,旋转交织码的层次码技术可以发挥明显优势,其修复带宽开销明显要低于层次码、循环RS码。

图6 单节点故障时修复带宽开销的变化

图7 两节点故障时修复带宽开销的变化

从图8和图9的节点故障时修复局部性的变化可知,分布式存储系统中任意单节点发生故障时,旋转交织码的层次码技术的修复局部性最小,而当两节点发生故障时,旋转交织码的层次码技术也可以发挥明显优势,其修复局部性的最大值和最小值都要低于层次码、循环RS码相应的修复局部性的最大值和最小值。

图8 单节点故障时修复局部性的变化

图9 两节点故障时修复修复局部性的变化

3 故障节点快速修复性能

表1为层次码、循环RS码和旋转交织码在分布式存储系统中节点故障修复时的性能对比结果,其中,k和r分别表示元素数据库节点数和存储校验块的节点数,a和m分别表示节点数据块和源文件大小。从修复带宽开销、修复局部性和复杂度的综合性能对比结果可知,基于旋转交织码的层次码技术在分布式存储系统中节点故障修复中具有明显的优势,其修复复杂度要明显低于层次码和循环RS码,从而可以提升节点故障修复效率。

表1 不同编码方案下节点修复性能的对比分析结果

4 结论

1)在采用层次码进行分布式存储系统的节点修复时,修复带宽开销和局部修复性都会发生不同程度的降低,即使在分布式存储系统中发生多个节点故障,循环RS码也会相较于传统RS码具备更优的数据处理能力。

2)分布式存储系统中某节点发生故障时,旋转交织码技术可通过另外两组标号位置相同的数据块对节点实现修复,并均衡运行过程中节点负载状况,但是旋转交织码存在较大的修复局部性。

3)基于旋转交织码的层次码在修复带宽开销、修复局部性和复杂度方面相较于层次码和循环RS码具有明显优势,可以提升分布式存储系统中节点故障的修复效率。