NTar基于网络拓扑的纠删码树型修复方法

1、ntar:基于网络拓扑的纠删码树型修复方法#许方亮，王意洁，裴晓强*510152025303540（国防科学技术大学计算机学院并行与分布处理国家重点实验室，长沙 410073）摘要：大规模分布式容错存储系统,采用纠删码作为数据冗余技术能够比多副本技术以更低的额外存储空间开销获得相同的数据可靠性。然而，基于纠删码的数据冗余技术在修复一个失效编码块时需要从其他节点下载多个编码块，不仅占用了大量网络资源，也严重降低了修复速度。现有的修复方法都没有考虑网络拓扑的影响。为此，提出并实现了一种基于网络拓扑的纠删码树型修复方法 ntar。ntar 依据网络拓扑将参与修复的节点组织成网络距离最小的树型结构，缩

2、短修复期间数据的传输距离，从而减少占用的网络资源并缩短修复时间。此外，提出了节点选择算法 optree。optree 可快速地从所有可用节点中选出最优的参与修复的节点组合，并同时生成最优的树型修复结构。实验结果表明，相比于传统的星型修复，ntar可将修复占用的网络资源降低 30%-45%，修复时间减少 50%-70%。关键词： 计算机应用；分布式存储系统；网络拓扑；纠删码；数据修复中图分类号：tp393ntar:network topology-based tree-structured datareconstruction scheme for erasure codesxu fanglia

3、ng, wang yijie, pei xiaoqiang(national key laboratory for parallel and distributed processing, college of computer, nationaluniversity of defense technology, changsha 410073)abstract: distributed storage systems are employing erasure codes instead of replicatioin as dataredundant scheme, since the f

4、ormer consume much less storage space than the latter over the samedata reliability. however, erasure codes require multiple blocks to be transmitted from survivingnodes to reconstruct a new block after a node failure, which occupies more network resource andlowers the reconstruction efficiency. pre

5、vious work mainly concerned about how to reduce thedata volume downloaded during repair, and neglected the influence of network topology. for that,a network topology based tree-structured data reconstruction scheme called ntar for erasurecodes is proposed and implemented. ntar builds a regeneration

6、tree with minimum total distanceaccording to the network topology to reduce the path length, which reduces network resourcesconsumption, and improves the reconstruction efficiency. moreover, an algorithm named optreeis also proposed to select the nodes which participate the reconstruction. optree ca

7、n quickly makean optimal selection and generate the optimal reconstruction tree at the same time. the results ofthorough experiments in a real cluster show that, compared with conventional reconstructionscheme, ntar can reduce network resource consumption by 30%-45%, and reduce thereconstruction tim

8、e by 50%-70%.key words: computer applications; disstributed storage system; network topology; erasurecodes; data reconstruction基金项目：国家重点基础研究发展规划(973)项目(2011cb302601)；国家自然科学基金项目(61379052)；国家高技术研究发展计划(863 计划)项目(2013aa01a213)；湖南省自然科学杰出青年基金项目(s2010j5050)；高等学校博士学科点专项科研基金资助课题(20124307110015)作者简介：许方亮(1989-

9、)，男，硕士研究生，主要研究方向：分布式容错存储系统，纠删码通信联系人：王意洁(1971-)，女，教授，博士生导师，主要研究方向：网络计算，数据库，并行与分布处理. e-mail: wangyijie-1-0 引言4550556065707580在云计算等领域应用广泛的大型分布式存储系统，如 gfs1等，往往包含几千甚至几万个存储节点。庞大的规模使节点失效成为了常态。为了保证数据的可靠性，即在部分存储节点失效时仍然能够访问系统中的所有数据，必须对进入系统的所有数据进行冗余存储。常用的数据冗余技术包括多副本技术2和纠删码技术3。多副本技术因其简单和较高的数据访问带宽等优点已在现有存储系统中得到了

10、广泛应用。然而，多副本极高的存储成本，极大地增加了系统构建和运行成本。随着近年来数据规模的爆炸式增长，过高的存储成本使多副本技术越来越不适合用在大型的存储系统中。相比于多副本技术，纠删码技术能以极低的额外存储空间开销获得相同或更高的数据可靠性4。因此，近年来纠删码技术在分布式存储领域受到了广泛关注。然而，纠删码极高的修复成本严重阻碍了它的大规模应用。当某个节点失效时，为了维持原有的数据可靠性，系统需要修复失效节点上的数据块并将其放到其他可用节点中(称为新生节点)。修复一个数据块时，新生节点需要从多个可用数据节点(称为提供者节点)分别下载一个数据块才能修复出丢失的数据块。这不仅占用了大量的网络资

11、源，也极大地降低了数据修复速度。因此，研究如何降低纠删码修复所占用的网络资源和耗费的时间对促进纠删码的广泛应用具有重要意义。在传统的纠删码修复方法中，所有提供者节点都直接将数据块传送给新生节点，提供者节点与新生节点之间形成一个星型结构。显然，这种结构所占用的网络资源为提供者节点到新生节点的网络资源之和，修复的速度也受限于新生节点的网络带宽。为了降低纠删码的修复时间，li jun 等人提出了一种基于节点间可用带宽的树型修复方法5。此方法根据修复时节点间可用带宽来建立树型修复结构，以提高修复速度。然而，此方法是基于一个节点可从多个节点同时接收数据的假设。这与实际情况不符，目前无法实现。因为现有网络

12、接口只能采用分时的方法轮流从不同节点接收数据。传统的星型修复方法和上述基于节点间可用带宽的树型修复方法都没有考虑到网络拓扑对修复占用网络资源的影响。为此，本文提出了一种基于网络拓扑的纠删码树型修复方法ntar。它根据网络拓扑结构来构建最优的树型修复结构(称为修复树)，以缩短修复时数据传输的距离，从而减少修复占用的网络资源。ntar 与上述基于节点间可用带宽的树型修复方法是不同的。首先，ntar 的首要目标是优化修复占用的网络资源，这是阻碍纠删码在实际中广泛应用的首要因素6；其次，ntar根据网络拓扑来构建修复树而非节点间可用带宽，在数据中心中，前者比后者更稳定且非常容易获得；最后，ntar 的

13、修复速度分析和优化基于一个节点在某一时刻只能从一个节点接收数据的假设，完全可以实现。本文的贡献有以下几点。第一，针对现有纠删码修复方法没有考虑网络拓扑影响的不足，提出了基于网络拓扑的纠删码树型修复方法 ntar，证明了最小生成树是最优的修复树，并且分析了其修复时间；第二，提出了从多个可用节点中快速选出最优提供者节点组合并同时生成最优修复树的算法 optree；第三，基于 hdfs-raid 实现了 ntar，对其进行了较全面的测试，并将其与星型修复方法进行了对比。实验结果表明，相比于星型修复方法，ntar可以有效降低修复占用的网络资源并提高修复速度。本文剩余部分组织结构如下。第 1 节介绍了降

14、低纠删码修复成本的相关工作；第 2 节介绍了纠删码的编解码与修复原理；第 3 节提出了一种基于网络拓扑的纠删码树型修复方法-2-ntar，包括快速选取最优提供者节点组合并构建出最优修复树的算法 optree；第 4 节通过实859095100105110115际实验对 ntar 进行了全面的测试；第 5 节总结全文。1 相关工作根据所用方法的不同，现有优化纠删码的工作主要可分为以下三类。第一，基于节点间可用网络带宽的纠删码树型修复方法，由 li jun 等人最先提出5。此方法根据节点间可用带宽构建一棵以新生节点为根，并覆盖所有提供者节点的最大生成树作为修复树。修复时，树中子节点向其父节点发送数

15、据，节点接收到其子节点的数据后，将这些数据与自身存储的数据进行组合，然后再发送给自己的父节点，依次类推，直至到达根节点。相比于星型结构的修复策略，这种树型修复方法能够充分利用网络中的空闲链路，提高修复速度。sun weidong 等人扩展了这一做法，将其应用于多节点失效时的并行修复7。然而，上述方法存在以下三个方面的不足。首先，它只有在一个节点可以从多个节点同时接收数据时才有效，这与目前实际情况不符；其次，节点间可用带宽是动态的，很难精确测量；最后，每次修复时都需要测量提供者节点和新生节点间的所有可用带宽。这将耗费很长时间，并会增加大量额外的数据传输。第二，可用于所有基于异或操作纠删码特殊修复

16、方法。最早由 xiang liping 等人8提出，以优化 rdp9阵列码修复时下载的数据量，osama khan 等人10将其一般化，使其适用于任何基于异或操作(xor)的纠删码。此方法通过尽量使用那些可以修复多个失效块的可用块，来达到降低下载数据量的目的。然而，这种基于 xor 的编码大部分为阵列型编码，容错能力有限，不适合于分布式容错存储系统。第三，新型的纠删码。大部分都是从编码本身来降低修复成本，如 lrcs(locallyrepairable codes)6、pyramid 码11、expyramid 码12、weaver 码13等。这些编码大都是通过分组编码的方法来减少修复时下载的

17、数据量，都是对传统 rs 码14的改进，会增加存储空间开销。另外，ntar 完全可与上述后两类工作结合在一起使用，进一步降低其修复代价。2 纠删码的编码与修复原理通常，纠删码可以用三元组 (n, k, k ) 来表示。(n, k, k ) 纠删码的基本思想是将数据对象 d分成 k 个大小相等的数据块 d1, d2,l, dk ，通过特定的编码算法对这 k 个数据块进行运算，产生 n 个大小不变的编码块 c1,c2 ,l,cn ( n k )，使得其中任意 k 个块都能通过相应的解码算法得到原数据 d 对应的 k 个数据块( k k )。2.1 纠删码的编解码原理目前用于分布式存储系统中的纠删码

18、基本上都是线性的，即每个编码块 ci 都是数据块d1, d2,l, dk 的线性组合，如式(1)所示，其中 gij fq ， i = 1,2,l, n ， j = 1,2,l, k ， fq 是大小为 q 的有限域(galois field)。( gi1 d1 d2 m dk -3-(1)gi 2 l gik ) = ci , i = 1, 2,l, n 2.2 纠删码的修复原理与编码相同，修复时失效编码块也是用来修复这个块的编码的线性组合。哪些块可以用120125来修复失效块以及组合系数的计算方法取决于具体的纠删码，一般都需要对编码时的系数矩阵求逆5。对于 rs 码14，修复时需要下载 k

19、个编码块。而对于改进型纠删码，需要下载的编码块数在大部分情况都小于 k ，只有少数情况下会大于 k。本文以后统一以 r 表示任意线性纠删码在修复一个失效块时需要下载的编码块数。记要修复的失效块为 c0 ，用以修复 c0 的所有编码块为 c1 ,c2 ,l,cr ，c0 与这些编码块的组合系数为 (b1 b2 l b r ) ， b j fq ， j = 1,2,l, r 。则纠删码的修复可统一表示成公式(2)。ri =1(2)3 基于网络拓扑的树型修复方法在传统的星型修复方法中，所有提供者节点都将自己的数据直接发送给新生节点，公式(2)的计算工作全部由新生节点完成。在图 1(a)中显示了一个星

20、型修复实例中的数据传输情130况。其中，节点 n1、n2、n3 和 n4 为提供者节点，节点 n6 为新生节点。从图 1(a)可以看出，这种方法中所有编码块的传输距离都很长，给链路 s2-s1-s3-n6 造成了很大压力，而在数据中心中如 s2-s1 和 s1-s3 这样的高层链路往往已经是整个网络中数据传输的瓶颈。此外，这种方法也在节点 n6 处形成了严重的网络堵塞，严重降低了修复速度。s1s1s2s3s2s3n1n2n3n4n5n6n1n2n3n4n5n6(a) 星型修复时的数据流(b) ntar修复时的数据流135140145150图 1 星型修复与基于网络拓扑的树型修复的数据流fig.

21、1 data streams of star-structured reconstruction and ntar实际上，没有必要将 c1 ,c2 ,l,cr 全部直接发送给新生节点，再由新生节点来完成所有的计算。根据有限域上运算的交换律和结合律，可以利用分层汇聚的方式分布式并行化这个数据传输和计算过程。另外，在大规模数据中心的网络拓扑当中，不同节点之间的距离是不同的，即不同节点之间的链路长度是不同的。在修复过程中，如果能先把相距较近的提供者节点上的编码块组合到一起，然后再发送到距离更远的提供者节点上与其数据进行进一步的组合，就可以缩短数据的传输距离，从而降低占用的网络资源，并提高修复速度。图

22、 1(b)显示了用 ntar 对图 1(a)中实例进行修复时的数据传输情况。可以看出，ntar 有效缩短了节点 n1 和节点 n2 中编码块的传输距离，极大地减轻了链路 s2-s1-s3-n6 的负载，并且使节点 n6 需要接收的编码块从 4 个减少到了 2 个，这有利于提高修复的速度。另外，在没有增加任何交换机负载的情况下，极大地减轻了交换机 s1 的负载。3.1 ntar基于网络拓扑的纠删码树型修复方法 ntar 的具体修复过程可以分为两大步。第一步，构建修复树。具体步骤如下。1)根据所采用的纠删码确定可用来修复失效块 c0 的编码块 c1 ,c2 ,l,cr 并计算出相应的修复系数向量

23、(b1 b2 l b r ) ；2)从系统中获得用以修复的编码块 c1 ,c2 ,l,cr 分别所在节点，记为v1,v2 ,l,vr ，并根据系统的数据放置策略确-4-c0 = bici 定出新生节点，记为v0 ；3)根据系统网络拓扑信息初始化表示节点v0,v1,l,vr 相互之间网络距离的矩阵 adjmatrix。其中，adjmatrixij表示节点 vi 和节点 vj 之间的网络距离，0 i, j r ；4)根据节点之间的网络距离矩阵 adjmatrix构建出以新生节点v0 为根的总网络155160距离最小的修复树，树中节点为v0,v1,l,vr ；5)将节点 vi 在修复树中的父节点、子

24、节点、所存储的编码块 ci 及其对应的系数 b i 等信息发送给节点 vi， 0 i r 。第二步，数据修复。节点 vi 根据其在修复树中位置的不同，工作也不同，具体如下。1)vi 如果是叶节点，则负责从本地存储系统中读取编码块 ci ，计算出 bici 并将其发送给自己 的 父 节 点 ； 2)vi 如 果 是 内 部 节 点 ， 则 负 责 接 收 其 子 节 点 发 送 来 的 数 据 ， 记 为c1 ,c2 l cn (v ) ，其中 in(v ) 为 vi 的在修复树中的子节点数，并从本地存储系统中读取编码块 ci ，然后计算出in (vi )j =1j + bici 并将结果发送给

25、自己的父节点；3)vi 如果是根节点，则负责接收其子节点发送来的数据，记为 c1 ,c2 ,l,cin (v j ) ，计算出in (vi )j =1j ，即 c0 ，然后将结果写入本地存储系统。这样就成功地修复了失效块 c0 。图 2 显示了用 ntar 修复图 1 中实例时第二步各节点计算的数据和节点之间传输的数据。n6c02=c01+c03+2c2c0=c02+c04c04=4c4n2c01=1c1c2c03=3c3c4n4165n1c1c3n3图 2 纠删码的树型修复过程实例fig.2 an example of erasure codes tree-structured recons

26、truction3.2 最优修复树的构建3.2.1网络资源度量指标:网络代价170175180纠删码修复所占用网络资源的传统度量指标是修复时所需下载的总数据量。这一指标可以较好地评价一种编码在修复方面的优劣，也在一定程度上反映了修复过程所带来的网络资源开销。然而，它是一个比较笼统的量，并不能精确反映修复过程真正占用网络资源的多少。这是因为它只考虑了修复所需下载的数据量，并没有考虑网络拓扑结构对数据传输的影响。显然，在由一个交换设备相连的两个节点之间和在由三个交换设备相连的两个节点之间分别传输等量的数据所占用的网络资源量是完全不相等的。因此，为了更加精确地描述修复所占用的网络资源，本文用传输的数

27、据量和传输的距离的乘积，称之为数据传输的网络代价。定义 1.节点 u 和节点 v 之间的网络距离 d(u，v)等于它们之间的物理链路数目，其单位为跳(hop)。如果节点 u 和节点 v 之间传输数据时经过的交换设备数目为 h(u，v)，则 d(u，v) = h(u，v)+1。这里的交换设备指网络中任何具有数据转发功能的设备，包括集线器、交换机、路由器以及具有转发功能的服务器等。定义 2. 节点 u 和节 v 之间传输数据量为 a (u,v )时的网络代价为公式(3)，其单位为bytehop，以 表示。c(u, v) = a(u, v) d (u, v)-5-(3) , i, j i c c18

28、5网络代价既包含了传输的数据量，也包含了数据传输的距离。数据经过的链路数越多，它占用的网络资源，如网络端口和链路等也就越多。网络链路和端口负载的轻重直接影响着网络的数据传输性能，对上层应用性能具有重要影响。因此，网络代价能更精确地反映数据传输对网络造成的影响。3.2.2问题建模190195200不失一般性，以v = v0 ,v1,l,vr表示所有参与修复失效块 c0 的节点组成的集合。其中，v0 为新生节点，v1,v2 ,l,vr 为提供者节点。不妨假设存储编码块 ci 的节点为 vi，1 i r ，每个编码块的大小为 s 字节。边集 e = (vi ,v j ) | i, j = 0,1,l

29、, r,i j表示各个节点之间的路径，函数 w(vi ,v j ) 表示节点vi 和v j 之间的网络距离，即 w(vi ,v j ) = d (vi ,v j ) 。这样，可以用有权完全图 gr = (v , e, w) 来表示用编码块 c1 ,c2 ,l,cr 来修复失效块 c0 时的网络。li jun 等人已经证明 gr 的生成树可以用来修复失效数据块5。定义 3. 纠删码的修复树是 gr 的生成树。记修复树为 tr = v , e ，gr 中的边 (vi ,v j ) e 当且仅当在修复时节点 vi 向节点 vj 发送数据，其中 0 i, j r ，且 i j 。根据节点间传输数据的网

30、络代价定义可得树型修复的网络代价。定义 4. 在 gr 使用修复树 tr = v , e 进行数据修复的网络代价 c(tr)为公式(4)。c(tr ) =本文的目标是使 c(tr)最小。问题求解3.2.3 ( w(u, v) a (u, v)( u ,v )e (4)引理 15. 修复树 tr 中各边在修复过程中传输的数据量都相等且为 s 字节，即 a(u, v) = s205字节，其中 (u, v) e 。定理 1. gr 的最小生成树是具有最低网络代价的修复树。证明. 根据引理 1，可以将公式(4)化为 c(tr ) = s( u ,v )e w(u, v) 。因为在修复时 s 是常量，所

31、以 c(tr ) 最小当且仅当( u ,v )e w(u, v) 最小。显然，其表示的是修复树 tr 各边权重之和，而修复树 tr 是 gr 的生成树，又权重之和最小的生成树是最小生成树。所以，gr 的最小生成树是210215具有最低网络代价的修复树。证毕。定理 1 同时也说明，使用现有的最小生成树构建算法，如 prime 算法，即可从 gr 构建出最优的修复树。星型修复方法和 ntar 的修复结构分别如图 3(a)和图 3(b)所示。由于所有节点间传输的数据量都为 m 字节，根据节点间网络距离，易得星型修复和 ntar 的网络代价分别为 14s和 10s。可见，ntar 比星型修复方法占用的

32、网络资源减少了约 28.6%。-6-v1v2v04242v0v1v2v344v4v322v4(a)传统星型修复结构(b)基于网络拓扑的树型修复结构图 3 星型修复与 ntar 的修复结构fig.3 reconstruction structure of star-structured reconstruction and ntar3.3 最优提供者节点组合的选择算法 optree220225230实际中，修复时可用来修复失效块的存活数据块数一般都多于 r，假设其为 a (a r) 。这时就会有 car 种提供者节点组合可供选择，选用不同的提供者节点组合会有不同的最优网络代价。如果能够从中选取最

33、优网络代价最小的组合，将进一步降低修复占用的网络资源。但是如果穷举所有选择，分别计算它们的最优网络代价，再从中选出最优的组合将会花费很长时间。为了尽快找到最优的提供者节点组合，本文提出了一种基于 prime 最小生成树算法的节点选择算法 optree。optree 能快速选出最优的提供者节点组合，并同时生成修复时所需的最优修复树。optree 的基本思想和过程与 prime 算法相同，只是让新生节点和所有 a 个可用节点都参加生成树的构建，并且在选取了 r 条边后就终止算法，而不是像 prime 算法那样选取 a 条边后才终止。由于 prime 算法的每一步都是最优的，所以 optree 能产

34、生最优的结果。optree的具体过程如算法 1。算法 1. 最优提供者节点组合的选择算法 optree输入:root:新生节点;candidateproviders:可选提供者节点集合;r:需要选择的提供者节点个数;adjmatrix:节点间网络距离矩阵;输出:reconstructiontree:修复树;chosenproviders:最优的提供者节点集合;过程:1:reconstructiontree:= ;2:chosenproviders:= ;3:chosennumber:=0;4:candidateedges:= ;5:for each provider in candidatep

35、roviders do6:7:linklengthprovider,root: = adjmatrix root, provider ;将 edgeroot,provider 加到 candidateedges 中;8:end for9:while chosennumber r do10:11:12:从 candidateedges 中选出最短的边 edgefrom,to;将 edgefrom,to 加到 reconstructiontree 中;从 candidateedges 中删除 edgefrom,to;-7-13:14:15:16:17:18:19:20:21:将 from 加入到

36、chosenproviders 中;chosennumber: = chosennumber+1;for each edgeu,v in candidateedges dolinklengthu,to: =adjmatrix u, to;if linklengthu,to = linklengthu,v then从 candidateedges 中删除 edgeu,v;将 edgeu,to 加入到 candidateedges 中;end ifend for22:end while23:return reconstructiontree 和 chosenproviders;3.4 修复时间分析

37、假设每个节点的网络带宽都为 b 字节/秒，网络中交换设备各端口的带宽都大于 b 字节/秒。这些在现有数据中心中都是比较常见的情况。另外，如果一个节点接收了整个编码块后才进行合并或将其发送给自己的父节点会严重地浪费时间，实现修复过程最优的方式应该是235240245250255流水线。一个节点一旦从其各个子节点都收到了一个数据包后就立刻开始将它们合并，在合并数据的同时继续从其各子节点接收数据并将合并好的数据包发送给自己父节点。显然，在这种情况下修复时间受限于需要接收最多编码块的节点。若以 y(tr ) 表示修复树 tr 所有节点的最大子节点数，则可得其最短修复时间 t(tr)为y(tr ) s(

38、5)b其中t (tr ) 是从修复开始到新生节点从其各子节点都收到第一个数据包的时间。一般情况下，编码块的大小都在几十 mb 甚至几百 mb，远远大于一个数据包的大小(几 kb)。因此，t (tr )可以忽略不计。根据公式(5)可得图 3 中星型修复和 ntar 的最短修复时间分别为 4s b 秒和 2s b 秒。可见，ntar 将修复时间缩短了 50%。4 实验结果与分析虽然已有一些关于树型修复的研究，但大都是基于理论分析和模拟实验的研究方法。本文基于 hdfs-raid 实现了对 rs 码14的 ntar(称之为 hdfs-ntar)，其核心机制可以不加修改地用于其它的线性纠删码。在一个真

39、实的集群上，对 ntar 修复树的构建时间、网络代价以及修复时间等方面进行了测试，并且与传统的星型修复方法做了对比。星型修复在有多于r 个节点可以作为提供者节点时，不同的组合也具有不同的网络代价。为了公平，星型修复时也选择了网络代价最小的节点组合，不妨称之为基于网络拓扑的星型修复 (networktopology based star-structured reconstruction，ntsr)。对于每一个测试，固定每个条带产生的校验块数目为 4，条带长度分别取 4、6、8、10、12 各做一组实验，以考察条带长度对测试结果的影响。ntar 采用的最优提供者节点组合选择算法和最优修复树构建算

40、法为 optree。ntsr 的最优提供者节点组合选择方法是取与新生节点网络距离最小的前 r 个可用节点。hdfs 文件块大小取 64mb。4.1 实验环境实验使用的 hdfs-ntar 集群由 19 个节点组成，包含一个 namenode 节点和 18 个datanode 节点。所有 datanode 平均连接在三个交换机上。连接在同一交换机上的节点之间-8-+t (tr )t(tr ) =260265的网络距离为 2，连接于不同交换机的节点之间的网络距离为 4。hdfs-ntar 集群中所有节点均为配置相同的宝德服务器，各配有 4 颗 intel xeon e-2640处理器，64gb 内

41、存，1tb 硬盘和千兆网卡。集群中所有交换机均具有 48 个 10/100/1000mbps自适应端口。4.2 修复树的构建时间和修复的网络代价测试时，先向 hdfs-ntar 中写入 180 个大小均为 1gb 的文件，当编码完成后，关闭其中一个 datanode，分别统计采用 ntar 和 ntsr 修复所有失效块时获得节点间网络距离和构建各自的修复结构所花费的总时间和网络代价，然后计算出平均的构建时间和网络代价。实验结果分别如图 4(a)和图 4(b)所示。0.10.080.06ntarntsr25002000ntarntsr15000.0410000.024 6 8 10 12条带长度

42、(块)(a) 修复结构的平均建立时间46 8 10条带长度(块)(b) 平均网络代价12270275280图 4 ntar 和 ntsr 修复结构的平均建立时间和网络代价fig.4 averaged building time and network cost of ntar and ntsr从图 4(a)可以看出，ntar 和 ntsr 修复结构的建立时间都随着条带长度的增大而延长，且 ntar 修复树的建立时间比 ntsr 稍长。然而，即使当条带长度为 12 时，建立一个修复树所需时间也只有 0.1 毫秒左右。这说明，ntar 选择最优提供者节点组合并建立最优修复树的时间开销非常小，相对于

43、修复一个失效块所需的时间，这完全可以忽略不计。从图 4(b)可以看出，相比于 ntsr，ntar 将修复的网络代价减少了 30%-45%，并且 ntar的网络代价随着条带长度的增大而增长的速度明显慢于 ntsr。这是因为随着条带长度的增大，会有更多的编码块在修复时可以就近组合，ntar 相比于 ntsr 产生的网络代价也就更少。这表明，ntar 有效减少网络资源占用。4.3 修复时间测试时，向 hdfs-ntar 中写入了 180 个大小恰为一个条带的文件，当编码完成后关闭一个 datanode 节点，然后分别用串行和并行的方法进行修复，并计算出单块的平均修复时间，结果分别如图 5(a)和图

44、5(b)所示。并行修复时的并行度为 18。2.564ntarntsr21.5ntarntsr120.546 8 10条带长度(块)1246 8 10条带长度(块)12(a)串行修复(b)并行修复285图 5 ntar 和 ntsr 的串行与并行修复时间fig.5 averaged sequential and parallel reconstruction time of ntar and ntsr从图 5(a)可以看出，ntar 的平均串行修复时间比 ntsr 缩短了 60%-85%，并且 ntar的平均修复时间不随条带长度的增大而变化，而 ntsr 的平均修复时间则随条带长度的增大线性增加

45、。这是因为，在树型网络拓扑结构中，ntar 产生的最低网络代价修复树中节点的-9-建立时间(ms）平均网络代价(ms)修复时间(s)修复时间(s)290295300305310315320325330335最大孩子数是固定的。可见，ntar 分布式并行化的特点明显提高了修复速度。从图 5(b)可以看出，ntar 比 ntsr 并行修复的时间短 40%-70%，且前者随条带长度增大而增加的速度远慢于 ntsr。这一方面是因为 ntar 占用的网络资源更少，尤其是有效减轻了网络中高层链路的负载，从而提高了整个网络的传输性能;另一方面是因为 ntar 将数据的发送和传输任务均匀地分布在了所有参与修复

46、的节点上，避免了 ntsr 中的网络瓶颈。5 总结采用纠删码作为大规模分布式容错存储系统的数据冗余技术，能够比多副本在相同可靠性的情况下节省大量的存储空间。然而，纠删码高昂的修复成本，严重阻碍了其在实际存储系统中的广泛应用。本文首先针对现有纠删码修复方法没有考虑网络拓扑影响的不足，提出了基于网络拓扑的树型修复方法 ntar。其次，提出了从所有可用节点中选取最优提供者节点组合的算法optree。它能够在快速选出最优提供者节点组合的同时构建出最优的修复树。最后，基于hdfs-raid 实现了 ntar 和 optree，并通过大量实际实验验证了 ntar 和 optree 的有效性。实验结果表明，

47、ntar 相比于传统的星型修复方法，有效地减少了纠删码修复时占用的网络资源，并极大地提高了串行和并行修复速度。参考文献 (references)1 ghemawat s, gobioff h, leugn s t. the google file systemc. proceedings of the 9th acm symposium onoperating systems principles. new york: acm, 20032 wang yijie, li sijun. research and performance evaluation of data replication

48、 technology in distributedstorage systemsj. international journal of computers and mathematics with applications, 2006,51(11):1625-16323 罗象宏, 舒继武. 存储系统中的纠删码研究综述. 计算机研究与发展, 2012, 49(1):1-114 lin w k, chiu d m, lee y b. erasure code replication revisitedc. proceedings of the 4th internationalconference on peer-to-peer computing. washington, dc: ieee computer society, 20045 li jun, yang shuang, wang xin, et al. tree-structured data regeneration with network coding in distributedstorage systemsc. proceedings of the 17th international workshop on quality of service. 2009:1-96 sathiamoorthy m,