“双码”架构下的云存储多节点修复协作编码

谢显中，黄倩,2，王柳苏

(1. 重庆邮电大学 宽带接入网络研究所，重庆 400065；2. 重庆邮电大学 移通学院 计算机科学系，重庆 401520)

1 引言

随着大数据的迅猛发展，如何在云存储/分布式存储的可靠性与带宽消耗之间找到一个平衡点至关重要。2007年，Dimakis等[1]第一次将网络编码思想应用于云存储/分布式存储，并提出了基于网络编码思想的再生码方案。再生码（regenerating codes）是指在云存储（cloud storage）系统中，将网络编码（network codes）技术和失效节点修复技术相结合的编码方案[2,3]。利用再生码技术可以在提高云存储可靠性的同时，减少修复需要的网络流量和带宽，进一步降低存储和修复代价。因此，各类再生码和失效节点修复方案受到广泛重视。Suh等[4]提出了一种满足最优存储容量-修复带宽折衷曲线的极大距离可分（MDS, maximum distance separable）码，并通过对偶变换的形式将该修复方案同时应用于系统节点和冗余节点的修复。但文献[4]的精确修复MDS（E-MDS, exact MDS）码只能解决单节点失效的问题，而未涉及多节点失效的情况。

对于多节点失效修复问题，多节点协作修复是有效的解决方案[5～12]。文献[5]给出了联合再生节点方案，但需要更多的传输信道，这使修复过程更加繁琐，导致修复的不稳定。文献[6,7]所阐述的多节点灵活再生方案主要是指在修复过程中，中间节点下载所需数据的灵活性，即可同时选择从原健康节点和其他再生节点下载数据并通过干扰对齐来修复失效节点，虽然有效地降低了修复带宽，但仍有修复时间不同步、修复过程复杂等问题。文献[8]在多节点联合修复时把干扰对齐独立地运用其中，提高了修复效率，但在精确修复时这个方案只在k=2时有效，为了使其有更大的适应性，还有很多问题需要解决。文献[9,10]分别将其扩展到其他k值组合时的最小带宽再生码（MBRC, minimum-bandwidth regenerating codes）和最小存储再生码（MSRC, minimum-storage regenerating codes），但在 MBRC 和 MSRC 无法取得折中平衡。Shum等[11]通过改变部分中间节点选取的帮助节点，提出了一种多节点联合修复（MCR, multi-node cooperative regenerating）码。MCR码虽然可以减少修复带宽，但也使修复过程更加繁琐，需要更多的传输信道，导致修复的不稳定。具有健康节点协作的多节点修复模型[12]在进行多节点修复时，帮助节点把用来修复失效节点的数据直接传输到从健康节点中选取的中间节点处。然后在此中间节点上进行相关计算和处理，在保证最低修复带宽的前提下，同步节点修复过程，减少修复链路数目，简化修复过程，减少对网络资源的浪费和依赖，以此增加系统可靠性，从而达到安全高效修复节点的目的。但由于此模型将主要的计算和处理工作放在中间节点上，所以中间节点的存储容量和运算负荷较大，系统稳定性差。

为解决上述多节点协作修复问题，本文首先根据文献[13]的MDS双码(twin-MDS codes)架构模型结合具有健康节点协作的多节点修复模型，给出了一种具有健康节点协作的MDS双码架构模型；这不但能解决具有健康节点协作的多节点修复方案[12]中的存储容量和运算负荷较大的问题，而且具有数据传输链路少、修复带宽小、多节点同步修复的优势。进一步，本文对文献[4]中的E-MDS码进行扩展，给出了一种适用于多个系统节点和冗余节点同时修复的多节点协作的精确修复（MER, multi-node exact repair）编码方案，并证明了其存在性。最后，通过数值仿真对比表明，本文的模型与方案在修复带宽、数据传输链路具有较大改进，且随着云存储中节点数量的增多优势更加明显。

2 MDS双码架构下健康节点协作的多节点修复模型

2.1 健康节点协作的多节点修复模型简介

具有健康节点协作的多节点修复模型的基本思想是在修复r个节点失效时，d个健康节点互相协作，并从d个健康节点中选择一个健康节点作为节点m代替再生节点，失效节点的修复过程就直接在节点m上进行，以此省掉修复过程中的中间节点环节。具有健康节点协作的多节点修复过程如图 1所示。

图1 具有健康节点协作的多节点修复过程

设原始用户文件可分为 4个大小相同的数据块（A1，A2，B1，B2），并存储在2个系统节点（节点1、节点2）中，然后运用具有MDS性质的再生码对原始文件进行网络编码，再生成与系统节点同等大小的2个冗余节点（节点3、节点4）。假设节点1和节点3失效，选择节点4为节点m，节点2直接将其存储的数据块A1和A2传输给节点m，然后节点m将接收到的数据再与其自身存储的数据进行运算，则可以同时得到 2个失效节点的全部数据，并分别输出从而修复出失效节点1和失效节点3。

在具有健康节点协作的多节点修复模型中，其他健康节点传送自己存储的数据到节点m，则需要传送d-1次大小为β的数据，然后再通过线性运算并输出r个大小为α的数据，因此，成功修复所有失效节点所需的总修复带宽为γ=(d-1)β+rα。因此，可以看出图1中的数据传输量为6个数据块，传输次数（传输线路）为 3，并且在一个修复过程就达到了同时修复2个失效节点的目的。

因此在云存储环境中，当存储节点相隔距离非常大的情况下，具有健康节点协作的多节点修复模型能使整个修复过程更加安全、简便。该模型在修复失效节点时下载数据是同步的，且修复步骤简便、安全易实施，有效地减少了所需的数据传输链路数，保证了高效率的修复节点，减少了对资源的浪费。虽然具有健康节点协作的多节点修复模型的优势明显，但仍然有中间节点m存储容量、运算负荷较大的问题。因此，下一节将引入MDS双码架构模型及其编码过程。

2.2 MDS双码架构简介

在MDS双码架构下，云存储系统中的存储节点（n个）被分成类型1（n1个）和类型2（n2个），如图2所示。

图2 MDS双码架构下节点修复和源文件重建的数据下载方式

如果想从类型1的节点下载数据，则该数据可以运用线性码C1进行编码解码操作；而想从类型2的节点下载数据，则数据先通过简单的移位操作改变顺序，然后运用线性码C2进行编码解码操作，并且这2种线性码（C1、C2）可以相同。另外，当一种类型的存储节点失效时，需要从另一种类型的健康存储节点子集下载数据以修复这个失效节点；而如果想要重建出整个原始用户文件，则需要从同一种类型节点子集下载数据。因为MDS双码架构下的两种线性码都满足 MDS特性，因此任意选择k个同类型节点就可以恢复出整个原始用户文件。

假设原始用户文件为在Fq的有限域里的M个信息符号，每个存储节点存储k个信息字符，对于类型i=0，1，令Ci为区间[ni,k]中在有限域Fq中任意的线性码（具有MDS特性），生成矩阵为Gi，把矩阵Gi的第l列表示为g(i,l)(1≤l≤ni)。

首先，用户数据被分为k2个数据片段，然后对于每一个数据片段进行编码。把这k2个数据符号排列在k×k阶信息矩阵A1中，且A2=A1t，其中，上标t表示矩阵的置换。通过编码Ci和信息矩阵Ai来获取这些信息数据，存储在类型i的每一个节点中的k个信息符号对应到k×ni阶矩阵AiGi中的每一列，类型i的节点l(1≤l≤ni)存储的数据字符在对应在矩阵的第l列，表示为Aig(i,l)(1≤l≤ni)。易知，每个类型i的节点l与矩阵Gi中列g(i,l)一一对应，因此称g(i,l)为所对应存储节点的编码向量。如图3所示。

图3 MDS双码架构下2种类型码的编码过程

为更加具体地描述MDS双码架构下的节点修复过程，下面给出一个简单的修复过程示例。假设类型1的节点1和节点4同时失效，除了类型2的节点2、3、4把所需数据传输给修复g(1,1)的中间节点外，类型2的节点1、2、3也要将数据传输到修复g(2,4)的中间节点处，最终修复出这2个失效节点的数据，如图4所示。

图4 MDS双码架构的多节点修复

2.3 具有健康节点协作的MDS双码架构模型

为了进一步提高对失效节点的修复效率、系统可靠性，同时降低成本，可将MER码运用于MDS双码架构模型中，对多节点失效进行修复。利用MDS双码架构模型与具有健康节点协作的多节点修复模型相结合，不仅达到更优的修复效果，而且还可以克服文献[12,13]中存在的诸多问题。

具有健康节点协作的MDS双码架构模型如图5所示。将存储节点根据双码结构进行布局，用户原始文件被存放在2种类型的节点中，并分别用C1码和C2码为类型1和类型2的存储节点编码。然后在两部分各选择一个健康节点作为修复对方失效节点的中间节点m1和m2。假设类型2的r2个节点损坏，则属于类型1的用来修复这些节点的健康节点的个数为d1，传输到m1的链路数为d1-1；同样的，若是类型1的r1个节点损坏，则传输到m2的链路数为d2-1，然后在中间节点进行线性运算，得到失效节点中的数据，输出再生节点。

图5 具有健康节点协作的MDS双码架构模型

假设云存储系统中有总共有r个节点失效，其中，属于C1码和C2码这2种类型的失效节点个数分别为r1和r2。本文分别从d1和d2个节点下载数据来修复所有失效节点，系统管理员从2个类型的健康节点中分别选择 2个节点作为中间节点m1和m2，其他健康节点分别传送数据到与自身同类型的接收端m1或者m2，则需要传送di-1次大小为βi的数据，再通过线性运算并输出ri个α大小的数据。因此，修复全部失效节点所需的修复带宽为γ=γ1+γ2，其中，γi=(di-1)βi+riα。

从上面的分析可以看出，与简单的具有健康节点协作的多节点修复模型相比，只增加了少量的存储节点，但中间节点的数据存储量少了一半，明显地减小了中间节点m的存储及运算负担。同时，在同样的修复条件下，当2种类型的节点中都存在多节点失效的情况时，在传输链路方面，传输链路数减少了1条。因为多了1个中间节点就少了1次健康节点传输数据的过程，在这个方案中d=d1-1+d2-1=d1+d2-2，而具有健康节点协作的多节点修复模型中d=d1+d2-1。在修复带宽方面，每条链路传输的数据量为α没变，但传输链路减少了一条，也就是减少了β大小的修复带宽，这里β=α。

综上所述，整个系统的可靠性、灵活性都大大增加，既保留、甚至优化了具有健康节点协作的多节点修复方案的数据传输链路少、修复带宽小、多节点同步修复的优势；也解决了这个方案中间节点存储、运算负担大的问题，在大量存储节点的网络中，此优势会更加明显。在下一节中，本文将给出一种运用于具有健康节点协作的MDS双码架构模型中的，能适用于多个系统节点或冗余节点的MER码，并证明其存在性。

3 MDS双码架构下具有健康节点协作的MER修复方案

Suh等[4]给出了一种(n,k,d)=(2k,k, 2k-1)的E-MDS码。对于该 E-MDS码，可以计算M=kβ(d-k+1)，β=1，则有这里进一步将E-MDS码再进行简要地概括，并为了强调 E-MDS码的对偶性，将使用与文献[4]不同的符号表述。

设k阶非奇异矩阵X=[xij],Y=[yij],Ψ=[ψij],Φ=Ψ-1=[φij]满足

其中，矩阵Ψ、Φ为初等变换矩阵，矩阵X的列向量为x1,…,xk，矩阵Y的列向量为y1,…,yk。设K={1,…,k}，则对于∀i∈K，式(1)可以表示为

设矩阵X～=(XT)-1，Y～ =(YT)-1。其中，对矩阵X（或Y）的列向量进行转置和求逆操作后得到矩阵X～（或Y～）的列向量x～1,…,x～k（或～y1,…,～yk）。设k×k阶矩阵Θ=[θ1…θk]，D=[δ1…δk]。其中，θi表示节点i中存储的长度为k的列向量，δi表示节点k+i中存储长度为k的列向量。

文献[4]中给出了E-MDS编码方案的两种构造方法：一种方法是将节点1到节点k设为系统节点，节点k+1到节点2k设为冗余节点；另一种方法是将节点k+1到节点2k设为系统节点，节点1到节点k设为冗余节点。首先对于第一种构造方法，系统节点i中存储的是未编码的原始数据分块，而冗余节点k+i中存储的是对系统节点中的数据分块进行线性变换后的编码数据块，其中，∀i∈K。因此，k个冗余节点中的数据可以表示为

但是，该 E-MDS码并不适合多节点修复。为了给具有健康节点协作的MDS双码架构模型构造一种适合的再生码，这里对 E-MDS码进行扩展，从而得到一种适用于多个系统节点或冗余节点的多节点修复网络编码方案——多节点精确修复（MER, multi-node exact repair）码。该修复码不仅保持了 E-MDS码的最小修复带宽，而且可以适用于多节点同时失效的精确修复情况。

定理1若E-MDS码的参数矩阵Y、Ψ和编码系数ω、σ、ω′和σ′满足。

1) 矩阵Y是有限域GF(q)上k×k阶的非奇异矩阵。

2) 矩阵Ψ是有限域GF(q)上k×k阶的柯西矩阵。

3) 系数ω、σ、ω′和σ′是满足式（7）的非零变量。

4) 对于∀i，j∈K有ψijφij≠1。

则存在能同时修复r个失效节点的，并满足再生码割集边界值的MER码。

证明选取 E-MDS码的第一种构造方法。即对于∀i∈K，矩阵Θ的列向量对应于系统节点i的数据，矩阵D的列向量对应于冗余节点k+i的数据。因为MER码至多允许r个节点失效，所以MER码的帮助节点数量d=n-r。

在节点修复过程中，若系统节点i失效，则帮助节点将各自存储的向量与列向量yi做内积操作，然后传给再生节点i′；若冗余节点k+i失效，则帮助节点将各自存储的向量与列向量xi做内积操作，然后传给再生节点(k+i)′。

首先证明当r≥2时，且r个失效节点全为系统节点或r个失效节点全为冗余节点的情况。由于矩阵Θ和矩阵D的对称性，所以这2种情况可以等效处理。

这样完成定理1的证明。

根据以上的证明过程可以看出，MER码作为E-MDS码的扩展，不但保持了E-MDS码在节点修复过程中满足再生码的割集边界的性质，而且可以实现对r个系统节点（冗余节点），或2个节点（单个系统节点和单个冗余节点）的精确修复。

4 架构模型的数值仿真分析对比

在多节点修复问题中，前面本文已经理论上分析了具有健康节点协作的MDS双码架构模型与文献[12,13]中的架构模型比较，本文提出的架构模型在修复带宽、数据传输链路、中间节点存储量运算量、系统可靠灵活性等方面都有一定的改进。

接下来，本文进行数值仿真对比。把几种多节点修复模型（原始修复[1]、依次修复[15]、联合修复[11]、健康节点协作修复[12]）与本文修复方案进行对比。为方便，当k=d,r=n-k，且n＜2k时，把相关参数用集合的形式表示为(n,k,d)(α,B)。

4.1 修复带宽比较

在多节点失效的环境下，MDS双码架构模型的节点的修复过程中用来修复失效节点的每一个健康节点的信息字符都是相互独立的。因此，每个健康节点只需识别中间节点的编码向量。并且在此架构中，整个修复过程是以一种分布式方式完成的。这种方式可以使整个修复系统更容易实现，并进一步减少节点之间的修复带宽消耗。用表示平均每个失效节点所消耗修复带宽的大小，各修复模型的平均修复带宽分析结果如表1所示。可以明显地看出，本文修复模型每个节点平均的修复带宽最优。并且随着云存储中节点数量的增多，优势更加明显。

表1 修复带宽比较

4.2 数据传输链路数比较

在多节点修复过程中，在网络上传输数据所用传输链路数f越小，系统可靠性越大。各修复模型所用的传输链路数结果如表2所示。可以明显地看出，本方案不仅减少了修复带宽，也有效地减少了修复传输链路数目，简化修复过程，增加可靠性，减少对网络资源的浪费，达到了安全高效地修复节点的目的。

表2 数据传输链路数比较

具有健康节点协作的多节点修复方案虽然传输链路数已经大大减少，但是本方案在同等参数下比它的传输链路数少 1，在减少中间节点存储运算负担的同时，减少了数据传输链路数，从而减少链路传输数据失败的几率，使系统更加可靠。

4.3 中间节点上的数据量比较

由于在MDS双码架构下健康节点协作的多节点修复方案中，2种编码均会选择一个健康节点作为修复对方编码中失效节点的中间节点m1和m2，并分别将修复所需的数据传输给相应的中间节点（m1或m2）。因此相比健康节点协作修复方案[12]，分散了当修复多个失效节点时，单个中间节点上的数据量。

各修复模型中，单个中间节点上的最大数据量如表3所示。虽然中间节点的总数据量并没有明显减少，但本文的修复模型通过增加中间节点个数，使得单个中间节点的处理数据量减少，从而分散了中间节点的处理压力。

表3 单个中间节点上的数据量比较

除了以上3个方面的优势外，MDS双码架构模型的另一个主要优势在与它适用于任意的线性纠删码，而MER编码方案即是一种适用于多个系统节点和冗余节点的多节点修复线性网络编码方案。因此只要在E-MDS码的基础上使各参数满足定理1中的约束条件，存在一种 MER码可适用于具有健康节点协作的 MDS双码架构模型，使系统性能更优。

5 结束语

本文首先根据 MDS双码架构模型结合具有健康节点协作的多节点修复模型，给出了一种具有健康节点协作的MDS双码架构模型。该模型在具有健康节点协作的多节点修复方案的基础上，解决了中间节点存储、运算负担大的问题，尤其在海量存储节点的网络中，此优势会更加明显。其次，本文通过约束参数条件，将适用于单节点修复的E-MDS码扩展成了适用于多个系统节点或冗余节点同时修复的MER码，并证明了其存在性。并在理论意义上将MER码与具有健康节点协作的MDS双码架构模型相结合，以达到对多节点修复的同时，降低修复带宽、修复链路数和单个中间节点需要处理的数据量。最后本文将具有健康节点协作的 MDS双码架构模型与现有的几种架构模型进行数值仿真对比。结果表明，在进行多节点修复时，本文给出的架构模型减少了修复带宽和数据传输链路数，降低了中间节点的数据处理量，进一步提高系统可靠性。对于下一步工作，将从MER码的具体构造和双码架构下的MER码在现实网络中的实现进行研究。

[1] DIMAKIS A G, GODFREY P B, WAINWRIGHT M J,et al. Network coding for distributed storage systems[A]. IEEE International Conference on Computer Communications (INFOCOM)[C]. 2007. 2000-2008.

[2] DIMAKIS A G, RAMCHANDRAN K, WU Y,et al. A survey on network codes for distributed storage[J]. Proceedings of the IEEE,2011, 99(3): 476-489.

[3] RASHMI K V, SHAH N B, KUMAR P V. Optimal exact regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction[J]. IEEE Transactions on Information Theory,2011, 57(8): 5227-5239.

[4] SUH C, RAMCHANDRAN K. Exact-repair MDS code construction using interference alignment[J]. IEEE Transactions on Information Theory, 2011, 57(3): 1425-1442.

[5] HU Y, XU Y, WANG X,et al. Cooperative recovery of distributed storage systems from multiple losses with network coding[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(2): 268-275.

[6] WANG X, XU Y, HU Y,et al. MFR: multi-loss flexible recovery in distributed storage systems[A]. IEEE International Conference on Communications (ICC)[C]. 2010. 1-5.

[7] 谢显中, 黄倩, 王柳苏, 等. 一种云存储中基于干扰对齐的多节点精确修复方法[J]. 电子学报，2014, 42 (10): 1873-1881.XIE X Z, HUANG Q, WANG L S,et al. A multi-node exact repair method in cloud storage based on interference alignment[J], Acta Electronica Sinica, 2014, 42 (10): 1873-1881.

[8] LE S N. Exact scalar minimum storage coordinated regenerating codes[A]. IEEE International Symposium on Information Theory Proceedings (ISIT)[C]. 2012. 1197-1201.

[9] WANG A, ZHANG Z. Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage[A]. IEEE International Conference on Computer Communications (INFOCOM)[C].2013. 400-404.

[10] LI J, LI B. Cooperative repair with minimum-storage regenerating codes for distributed storage[A]. IEEE International Conference on Computer Communications (INFOCOM)[C]. 2014. 316-324.

[11] SHUM K W, HU Y. Cooperative regenerating codes[J]. IEEE Transactions on Information Theory, 2013, 59(11): 7229-7258.

[12] 谢显中, 王柳苏, 黄倩, 等. 具有健康节点协作的高效多节点修复方案[J]. 北京邮电大学学报. 2014, 37(1):52-56.XIE X Z, WANG L S, HUANG Q,et al. Efficient multi-node regenerating program with healthy nodes collaboration in distributed storage systems[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(1):52-56.

[13] RASHMI K V, SHAH N B, KUMAR P V. Enabling node repair in any erasure code for distributed storage[A]. IEEE International Symposium on Information Theory(ISIT)[C]. Saint Petersburg, Russia, 2011.1235-1239.

[14] LI X, ZHENG Q, QIAN H,et al. Toward optimizing cauchy matrix for cauchy reed-solomon code[J]. IEEE Communications Letters, 2009,13(8): 603-605.

[15] WU Y, DIMAKIS A G. Reducing repair traffic for erasure coding-based storage via interference alignment[A]. IEEE International Symposium on Information Theory Proceedings (ISIT)[C]. Seoul,2009. 2276-2280.