基于生成矩阵变换的跨数据中心纠删码写入方法

包 涵 王意洁 许方亮

1(并行与分布处理国家重点实验室(国防科技大学) 长沙 410073)2(国防科技大学计算机学院 长沙 410073)

近年来，数据中心(datacenter, DC)故障屡见不鲜[1-8].因此，存放在单数据中心存储系统里的数据面临着永久丢失的风险.为了确保在数据中心故障时仍能恢复其中的数据，各大机构通常选择采用容错技术(纠删码和多副本)将数据存储在跨数据中心存储系统中.

在单数据中心存储系统中，纠删码因其高容错性和低冗余度而得到了广泛应用[9-12].然而，在跨数据中心存储系统中，由于下列原因，纠删码的写入速度较低以至于难以适应于大数据时代日益增长的数据产生速度[13-14]：

1) 纠删码写入数据时，源节点需要向若干节点传输大量的数据块或编码块，因此数据传输量较大.此外，在跨数据中心存储系统中，纠删码写入数据时需要频繁地在数据中心间进行数据传输，因而数据的平均传输距离(跳数)较长[15-16].因此，跨数据中心纠删码写入数据时的网络资源消耗量(数据传输量与平均传输距离之积)较大.当网络资源消耗量较大时，有较大概率需要在低带宽的物理链路上传输较多的数据，这将形成传输瓶颈，导致写入速度低的问题[17].

2) 纠删码写入数据的过程中涉及较多的编码操作，并需要在位于多个数据中心的多个节点间进行频繁的数据传输操作，若无法有效保证编码效率和传输效率，极易造成编码计算瓶颈或传输瓶颈，进而导致写入速度低的问题.

由于跨数据中心纠删码较低的写入速度大大限制了其可用性，本文聚焦于提高跨数据中心纠删码的写入速度.

现有的纠删码写入方法分为集中式写入方法[18-19]和分布式写入方法[20-22]2类：

已有的集中式写入方法主要是面向单数据中心纠删码的.在这类写入方法中，中心编码节点将单独负责完成一个条带中所有编码块的编码生成任务，这将形成严重的编码瓶颈.如图1(a)所示，在我们的实际测试中，集中式写入方法Trad[19]的单个节点最大计算复杂度是2种分布式写入方法D2CP[22]和IncEncoding[23]的4.3～8.8倍.因此，集中式写入方法的整体编码效率较低，这会对写入速度产生不利影响.

为了提高纠删码写入数据时的编码效率，研究者们提出了分布式写入方法(包括面向单数据中心纠删码的分布式写入方法[20-22]的和面向跨数据中心纠删码的分布式写入方法[23]).通过将编码操作分散到多个编码节点上并行执行，分布式写入方法能够提高编码效率.然而，这类方法通常会引入较大的网络资源消耗量，从而对写入速度产生不利影响.尤其是在跨数据中心存储系统中，这一问题更加突出.如图1(b)所示，2种分布式写入方法D2CP和IncEncoding的网络资源消耗量是集中式写入方法Trad的2.1～2.5倍.此外，在涉及节点较多时，分布式写入方法需要在多个节点间多次转发同一数据块.如图1(c)所示，2种分布式写入方法D2CP和IncEncoding的单个数据块最大转发次数为集中式写入方法Trad的6～11倍.由于数据块在节点间进行转发时需要进行额外的磁盘读写操作和排队等待操作[23]，因而数据块的转发次数越多，传输效率越低，这将对写入速度产生不利影响.

Fig. 1 Comparison between the centralized writing method of erasure code and the distributed writing method of erasure code图1 分布式纠删码写入方法和集中式纠删码写入方法的对比

总而言之，在跨数据中心存储中，现有纠删码写入方法由于无法兼顾网络资源消耗量、编码效率和传输效率，使得它们难以达到较高的写入速度.为此，本文提出了一种基于生成矩阵变换的跨数据中心纠删码写入方法(cross-datacenter erasure code writing method based on generator matrix trans-formation, CREW).具体而言，CREW包含以下3个算法:

1) 一种基于贪心策略的传输拓扑构造算法(greedy strategy-based transmission topology con-struction algorithm, GBTC).可构造一种自顶向下边权(网络距离)递增的数据中心级传输树来组织数据中心间的数据传输.同时，GBTC还将构造一种星型拓扑来组织各数据中心内部的数据传输.

2) 一种生成矩阵变形算法(generator matrix transformation algorithm, GMT).可在不改变各编码块间的线性关系的前提下对编码块生成矩阵进行变形，使得需要存储在位于GBTC构造的传输树下端的数据中心里的编码块的生成过程依赖于尽可能少的数据块.因为GBTC构造的传输树自顶向下边权递增，所以使用GMT对生成矩阵进行变形可使写入过程中需要长距离传输的数据块尽可能地少，进而可以降低网络资源消耗量.

3) 一种分布式流水线写入算法(distributed pipelined writing algorithm, DPW).可协调各节点间的数据传输操作和编码操作.为了避免节点的计算能力成为编码瓶颈， DPW在数据中心间进行分布式的数据编码和数据传输.为了避免因数据转发次数过多造成传输瓶颈，DPW在数据中心内部进行集中式的数据编码和数据传输.

1 相关工作

在采用编码参数为(n,k,d)的纠删码的存储系统中写入数据时，原始数据首先将被源节点Src拆分为多个数据块，每k个数据块组成一个条带.接着每个条带的k个数据块X=(x1,x2,…,xk)将被编码节点编码为n个编码块Y=(y1,y2,…,yn)，编码过程如式(1)所示：

Y=XG,

(1)

其中满秩矩阵G被称为纠删码的生成矩阵.对应于每个生成矩阵，存在一个(n-k)×n的满秩矩阵H，使得GHT=0,H被称为纠删码的校验矩阵[24-26].

当编码节点完成编码后，n个编码块将被存储在n个不同的存储节点中，以确保在一个条带中任意d-1个编码块所在的存储节点失效时，系统可以通过其他n-k-d+1个存储节点的编码块来恢复原始数据.

纠删码的写入模式可以分为2类：先副本后编码模式和直接编码模式.与先副本后编码模式相比，直接编码模式对系统的计算资源和存储资源的消耗更低，但对纠删码写入速度的要求更高.因此，本文主要关注于如何提高直接写入模式下的纠删码写入速度.在直接写入模式下，纠删码的写入方法可分为集中式写入方法和分布式写入方法2类.

1.1 集中式写入方法

已有的集中式写入方法Trad主要是面向单数据中心存储的.Trad写入数据时，源节点首先将所有的数据块传送给中心编码节点，然后由中心编码节点将这些数据块编码为若干编码块后分发到若干个存储节点中.由于集中式写入方法简单易实现且便于维护，WAS[27]和Atlas[28]等分布式存储系统均采用集中式写入方法.但是，由于集中式写入方法将所有编码计算负载集中在中心编码节点上，这种方法的编码效率较低，极易造成性能瓶颈.

此外，Fan等人[19]提出了一种新的集中式数据写入方法Trad-MR.在写入数据时，Trad-MR首先会将不同的数据对象发送到不同的MapReduce节点中，然后由不同的MapReduce节点来负责不同数据对象的编码和分发.这种方法可以在一定程度上缓解纠删码写入数据时的性能瓶颈问题，但随着写入数据量的不断增加，MapReduce节点的计算能力仍然可能成为写入过程的瓶颈.

总而言之，集中式写入方法的优点是简单易实现，其缺点是编码效率较低，从而对纠删码写入速度造成不利影响.

1.2 分布式写入方法

分布式写入方法在进行数据写入时，会将数据编码任务分散到多个编码节点上并行执行以提高编码效率.已有的分布式写入方法分为面向单数据中心纠删码的分布式写入方法和面向跨数据中心纠删码的分布式写入方法2类.

1) 面向单数据中心纠删码的分布式写入方法

Lluis等人[21]提出一种网内分布式写入方法In-Network.In-Network在写入数据时首先由源节点将原始数据条带划分为k个数据块.然后，源节点将划分好的k个数据块分发到k个存储节点中.这些存储节点在接收到数据块后将同时进行数据块的存储操作和转发操作.接收到这些存储节点转发的数据块的编码节点将使用这些数据块完成编码块的编码生成任务，同时将一部分编码块(中间编码块)发送到其编码节点中参与其他编码块的编码生成过程.最后，所有编码节点都将接收到编码所需的中间编码块或数据块.总而言之，In-Network通过将数据写入时的编码任务分散到多个节点来提高编码效率.然而，In-Network仅仅适用于局部性码并且对编码参数具有较为严格的要求.因此，In-Network的通用性较差.

针对In-Network通用性差的问题，我们在文献[22]中提出了一种通用性更高的分布式写入方法D2CP，适用于所有的局部性码.在D2CP中，源节点将数据对象分块后先完成部分的编码操作，然后将编码生成的中间编码块发送到相应的编码节点中，这些编码节点在接收到源节点发送的中间编码块后通过相互协作的方式完成剩余的编码操作以得到最终的编码块.与In-Network类似，D2CP通过将编码操作分散到多个节点并行执行的方式提高了编码效率，并且具有比In-Network更高的通用性.

2) 面向跨数据中心纠删码的写入方法

我们在文献[23]中提出了一种面向跨数据中心纠删码的分布式写入方法IncEncoding.在IncEncoding中，所有存储节点都是编码节点，源节点和存储节点以线性拓扑组织，源节点将数据对象分块后沿着线性拓扑以流水的方式依次发送各个数据块，各个存储节点接收到一个数据块后就使用其进行编码得到中间编码块，同时将该数据块转发给下一存储节点.最终，每个存储节点都将收到自己所需的所有数据块，并编码生成最终的编码块.

以上分布式写入方法都能够将编码操作分散到多个节点上并行执行，因而能够有效提高写入时的编码效率.但是，由于通常需要在多个节点间传输数据块和中间编码块，分布式写入方法也带来了较大的网络资源消耗量.此外，在涉及节点较多时，已有的分布式写入方法中数据块在存储节点间的转发次数较多.由于存储节点转发数据时通常会带来额外的磁盘读写耗时和排队耗时[23]，因而数据块的转发次数越多，传输效率较低，进而导致写入速度越低.

2 基于生成矩阵变换的跨数据中心纠删码写入方法(CREW)

已有纠删码写入方法在跨数据中心存储系统中写入数据时面临着写入速度较低的问题.在本节中，我们提出了一种基于生成矩阵变换的分布式流水线跨数据中心纠删码写入方法，可以通过降低数据写入时的网络资源消耗量、提高编码效率和传输效率来提高写入速度，其主要思想是：通过对传输拓扑和生成矩阵同时进行优化达到降低网络资源消耗量的目的；同时，通过将编码操作和传输操作分散到多个节点上并行执行并控制数据块的转发次数达到提高编码效率和传输效率的目的.

在本节中，我们首先通过一个实例来介绍CREW的主要思想.接着，分别介绍CREW包含的3个主要算法：一种基于贪心策略的传输拓扑构造算法GBTC、一种生成矩阵变形算法GMT和一种分布式流水线写入算法DPW.最后给出CREW的整体算法流程.

2.1 主要思想

首先,我们通过一个实例来介绍CREW的主要思想.假设某编码参数为(6,4,2)的纠删码的原始生成矩阵为式(2)中的G.

(2)

存储节点和源节点位于UCloud[29]的6个数据中心中(分别用TPE,PEK1,PEK2,SHA,CAN,LA表示)，这6个数据中心间的网络距离如表1所示.详细数据放置方案为：源节点位于PEK1，存放编码块y4，y5，y6的存储节点位于PEK2，存放编码块y2和y3的存储节点位于TPE， 存放编码块y1的存储节点位于SHA.

Table 1 Network Distances Between 6 DCs of UCloud表1 UCloud的6个数据中心间的网络距离 hop

CREW首先使用GBTC构造一个如图2所示的数据传输拓扑，其中：各个数据中心由一个树形拓扑来组织，该树形拓扑中自顶向下边的权值(网络距离，即跳数)递增；数据中心内部的各节点由一个星型拓扑来组织.

Fig. 2 Transmission topology of CREW图2 CREW的传输拓扑

接着，CREW使用GMT对原生成矩阵G进行初等行变换得到式(3)中的实际生成矩阵G′.

(3)

使用G′对数据进行编码后，树形拓扑中越下端的数据中心要存储的编码块与越少的数据块线性相关(即G′中相应列的非零行越少).

最后，如图2所示，CREW使用DPW按以下方式组织各条带中数据的编码和传输：1)源节点Src先将原数据拆分为4个数据块x1,x2,x3,x4；2)源节点向PEK2中的一个节点(编码节点)发送x1,x2,x3,x4，并向SHA中的一个节点(编码节点)发送x3；3)PEK2中的编码节点收到4个数据块后使用G′对其进行编码得到y6，y5，y4，将y6存储在本地，并将y5和y4发送到PEK2中的另外2个节点中存储；4)SHA中的编码节点接收到x3后使用G′对其进行编码得到y3=x3并将y3存储到本地；5)PEK2在使用x1，x2，x3，x4编码生成y6，y5，y4的同时，将x1，x2转发到TPE中的一个节点(编码节点)中；6)TPE中的编码节点收到x1，x2后使用G′对其进行编码得到y1=x1和y2=x2，将y2存储到本地并将y1发送到TPE中的另一个节点中存储.需要强调的是，各个节点是按流水并行的方式执行各项编码、传输任务的，即同一时间内有多个条带的数据在这些节点中进行编码和传输.

在CREW写入数据的过程中，由于需要长距离传输的数据块较少，所以网络资源消耗量较低.与面向跨数据中心纠删码的分布式写入方法IncEncoding相比，CREW可将写入数据时的网络资源消耗量降低59.4%.此外，由于在数据中心内部采用了集中式的数据编码和传输，CREW的传输效率较高，可将数据块的最大转发次数降低50%.

与集中式写入方法Trad相比，CREW的网络资源消耗量高了12.5%.但由于CREW的数据编码任务是分散到多个节点上以流水并行的方式进行的，与Trad相比CREW的编码效率较高，可将单个节点的最大乘法运算次数降低50%.此外，在集中式写入方法Trad中，中心编码节点除了要负责完成所有的编码操作外，还需要负责完成所有的编码块分发操作，进一步降低了其编码效率.因此，CREW的编码效率远高于Trad.

此外，在计算实际生成矩阵G′时，我们仅仅对原始生成矩阵G进行了初等行变换，所以使用G′编码得到的各编码块间的线性关系与使用G进行编码时相同.也就是说，对生成矩阵进行变换并不改变纠删码原有的修复过程.

2.2 基于贪心策略的传输拓扑构造算法(GBTC)

纠删码数据写入时的传输拓扑可以用一个有向图D=V,E表示.其中，点集合V包含源节点和所有用于存储编码块的存储节点，边集合E中的边e=v1,v2∈E表示写入过程中节点v1将向节点v2传输编码块或数据块.e=v1,v2的权值weight(e)设为节点v1和节点v2之间的网络距离.因此，传输拓扑D的总网络距离为其中，传输拓扑D的数据中心间网络距离定义为为E中连接属于不同数据中心的节点的边的集合).

由于纠删码写入过程中既涉及数据中心间的数据传输又涉及数据中心内的数据传输，因此传输拓扑可以分为2部分：

1) 数据中心间传输拓扑.在CREW构建数据中心间传输拓扑时，首先要求使用一种树形传输拓扑组织数据传输以分散数据的编码任务，从而保证编码效率.其次，要求NDDin尽可能小以降低网络资源消耗量.此外，因为在CREW中越靠近源节点的边上需要传输的数据块数越多，所以要求越靠近源节点的边的权值越小，从而达到充分降低网络资源消耗量的目的.

2) 数据中心内传输拓扑.由于在各个数据中心内只需编码并存储部分编码块，所以在数据中心内编码时的计算量较小.因此，在构建数据中心内传输拓扑时，出于控制数据块的转发次数的目的，CREW将在数据中心内采用集中式编码方法进行编码并使用一种以编码节点为中心的星型拓扑结构来组织数据传输.

为了构造满足以上要求的传输拓扑，我们提出了一种基于贪心策略的传输拓扑构造算法(GBTC)，如算法1所示：

算法1.基于贪心策略的传输拓扑构造算法GBTC.

输入：源节点Src、 存放编码块的存储节点集合N、N中节点所在的数据中心的集合DC、各节点间的网络距离矩阵DIS；

输出：传输拓扑D=V,E.

① for eachDCiinDC

②Venc,i←selectRandomly(N,DCi)；*从

N中随机选择一个属于DCi的节点*

③ for eachvjinDCi

④ ifvj≠Venc,i

⑤E.add(vj,Venc,i)；

⑥ end if

⑦ end for

⑧ end for

⑨Vt.add(Src)；

⑩Venc.add(Src)；

Nenc-Venc)；*Nenc-Venc中选出2个离nd最近的节点*

第1步. GBTC从每个数据中心中随机选择一个存储节点作为该数据中心的编码节点(算法1第①②行).同时，GBTC以各数据中心的编码节点为中心，以星型拓扑结构(数据中心内传输拓扑)组织各个中心的所有节点，具体步骤为：GBTC将各数据中心编码节点与该数据中心的所有非编码节点相连产生若干条边，并将这些边添加到传输拓扑的边集E中(算法1第③～⑦行).

第2步. GBTC将源节点Src添加到一个临时点集Vt和数据中心间传输拓扑的点集Venc中(算法1第⑨⑩行).

第3步. GBTC构造一个以源节点Src为根、自顶向下边权递增的树形拓扑(数据中心间传输拓扑)来组织所有的编码节点和源节点Src.具体步骤如下：对于Vt中的每个节点vt，首先选中所有不在Venc中的2个距离vt最近的2个编码节点tmpN1和tmpN2；然后将tmpN1和tmpN2加入Venc和Vt中；接着将vt与tmpN1和tmpN2分别相连产生2条边，并将这2条边添加到传输拓扑的边集E中；最后将vt从Vt中删除.当Vt中不含有任何节点时，E为传输拓扑的边集，源节点Src与所有存储节点的集合N的并集为传输拓扑的点集V(算法1第～行).

第4步. GBTC将返回传输拓扑D=V,E(算法1第行).

在GBTC构造数据中心间传输拓扑时，由于每次向E中添加边时都是选择权值最小的2条边，所以构造的树形拓扑能够满足NDDin较小且自顶向下边权递减的要求.此外，GBTC的计算复杂度为O(|DC|2).

2.3 生成矩阵变形算法(GMT)

在2.2节中，我们提出一种基于贪心策略的传输拓扑构造算法GBTC.在GBTC构造的数据中心间传输拓扑中，越远离源节点的边的权值越大(网络距离越长).与之相适应地，本节将提出一种生成矩阵变形算法GMT，通过对任意线性纠删码的生成矩阵进行变形使得写入过程中需要在远离源节点的边上传输的数据块数尽可能地少，从而达到降低网络资源消耗量的目标.与此同时，GMT可以保持各编码块的线性关系，因而对纠删码原有的修复过程没有任何影响.此外，GMT可以保持编码的系统性，因而不会降低读取效率.

GMT对生成矩阵进行变形的过程如算法2：

算法2.生成矩阵变形算法GMT.

输入：原始生成矩阵G、传输拓扑D、放置方案P=Y,N；

输出：变形后的生成矩阵G′.

①Y←sortY(D,P)；*根据放置方案P和传输拓扑D对所有的编码块进行排序*

②EX←exchangeScheme(Y,G)；

③G1←columnExchange(G,EX)；*对G进行列交换操作，得到G1*

④G2←RREF(G1)；*使用RREF算法对将G1化为行最简形矩阵G2*

⑤EX′←revert(EX)；

⑥G′←columnExchange(G2,EX′).*对G2进行列交换操作，得到G′*

第1步. GMT按各编码块所在数据中心在GBTC构建的传输拓扑中与源节点Src的距离对这些编码块进行排序(算法2第①行).编码块所在数据中心与源节点Src的距离越远，相应的编码块排序越靠前.

第2步. 设编码块的排序为yi1,yi2,…,yin，GMT将接着对生成矩阵G=(g*1,g*2,…,g*n)进行列交换操作(g*i表示G的第i个列向量)，得到如下矩阵G1=(g*i1,g*i2,…,g*in)(算法2第②③行).

定理1.在GMT算法中，G与G′的校验矩阵相同，即用它们编码得到的编码块之间的线性关系相同.

假设G的校验矩阵为H.若将G转换为G1的列交换操作为EX={e1,e2,e2,e3,…,ex,ex+1}，其中e1,e2表示交换矩阵的第e1列和第e2列.那么，我们定义对H进行EX列交换操作得到的矩阵为H1.因为GHT=0，所以G1H1T=0.

因为G′是通过对G2进行EX′={ex,ex+1,…,e1,e2}操作得到，H是通过对H1进行EX′={ex,ex+1,…,e1,e2}操作得到,所以有G′HT=0,H也是G′的校验矩阵.因此用G′编码得到的编码块之间的线性关系与用G编码得到的编码块之间的线性关系相同.

证毕.

定理2.在GMT算法中，若G为系统码的生成矩阵，则G′也为系统码的生成矩阵.

证明. 因为矩阵G是行满秩的，所以G1也是行满秩的.由于矩阵的秩等于其行最简形矩阵非零行的数量，所以G1的行最简形(G2)一定可以通过列交换操作转化为

[EA],

(4)

其中E为单位矩阵.

所以，G2为系统码的生成矩阵，进而有G′为系统码的生成矩阵.

证毕.

由定理1有，GMT并不会改变纠删码原有的修复过程.由定理2有，若G为系统码的生成矩阵，则G′也为系统码的生成矩阵，所以GMT不会改变原有纠删码的读取性能.此外，由于GMT的输入可以是任意线性纠删码的生成矩阵，所以GMT的适用范围较广.最后，GMT中的主要计算任务为执行RREF算法，其复杂度为O(k2).由于实际应用中k的值较小，因此GMT的计算用时较低.

2.4 分布式流水线写入算法(DPW)

在2.2节和2.3节中，我们分别提出了基于贪心策略的传输拓扑构造算法GBTC和生成矩阵转换算法GMT，对传输拓扑和生成矩阵进行了优化，从而达到效降低写入数据时的网络资源消耗量的目的，进而提高了写入速度.

然而，写入速度不仅受到网络资源消耗量的影响，也受到写入过程中的传输效率和编码效率的影响.传统的集中式写入方法将所有编码操作都集中到了中心编码节点上，导致编码效率低下，进而导致写入速度较低的问题.而在已有的分布式写入方法中，数据块往往需要被多次转发，带来额外的磁盘读写耗时和排队耗时，使得传输效率低下，同样导致了写入速度较低的问题.因此，为了兼顾纠删码写入数据时的编码效率和传输效率，我们在本节提出了一种分布式流水线写入算法DPW.

算法3.分布式流水线写入算法DPM.

输入：数据块向量X、生成矩阵G′、传输拓扑D.

①Src.send(X,D)；

② for eachvtinD.V

③ ifvt.isEncodingNode()

④codedblocks←vt.enc(receivedBlocks)；*使用G′对接收到的数据块进行编码，得到编码块*

⑤vt.storing(codedblocks)；*将编码块存储到本地*

⑥vo←vt.getOffspring；

⑦vt.send(vo,codedblocks)；*将编码块转发到下一级节点*

⑧ else

⑨vt.storing(receivedBlocks)；

⑩ end if

为了避免节点的计算能力成为编码瓶颈，DPW在数据中心间进行分布式的数据编码和数据传输以将计算任务分散到多个节点并行执行.因为实际应用中用来存储一个条带的数据中心数较小，所以数据中心间的传输拓扑的选择对数据在存储节点间转发的次数的影响较小.因此，在数据中心间进行分布式的数据传输和数据编码既可以提高编码效率又不会对传输效率造成过大影响.

此外，为了避免因数据转发次数过多造成的传输瓶颈，DPW在数据中心内部进行集中式的数据编码和数据传输以降低数据块的转发次数.因为DPW在数据中心间采用的是分布式的数据编码，各个数据中心只负责条带中一部分编码块的编码任务，所以各数据中心中需要进行的编码运算量较小.因此，在数据中心内部采用集中式的数据编码和数据传输既可以提高传输效率，又不会导致编码瓶颈.

DPW中涉及的节点有3类：源节点Src、编码节点和普通存储节点.DPW根据GBTC构造的数据中心间传输拓扑向各个编码节点发送该编码节点所需的数据块(算法3第①行).各个编码节点在接收到其所需的数据块后将同时进行2个操作.一方面，各编码节点向它在数据中心间传输拓扑中的子节点(子数据中心)里的编码节点发送这些子节点需要的数据块.由于越远离源节点Src的数据中心需要的数据块越少，传输的数据量是递减的.另一方面，编码节点用自己收到的数据块编码生成本数据中心各个存储节点所需存储的编码块，并以星型拓扑将这些编码块发送到相应的存储节点中(算法3第③～⑦行).由于编码操作对网络资源占用少，而传输操作对计算资源占用小，编码节点能够以较高的效率同时进行这2项操作.为了提高写入效率，以上过程中的数据传输和编码过程都以流水并行的方式进行的.显然，GMT的计算复杂度为O(kn).

2.5 CREW的算法描述

基于生成矩阵变换的分布式流水线跨数据中心纠删码写入方法的算法描述如算法4所示:

算法4.基于生成矩阵变换的跨数据中心纠删码写入方法CREW.

输入：原始数据O、原始生成矩阵G、源节点Src、Src所在的数据中心dcc、数据块数k、数据块大小Sb、存放编码块的存储节点集合N、N中节点所在的数据中心的集合DC、节点间的网络距离矩阵DIS.

①m←O.size()kSb；

②D←Src.GBTC(dcc,N,DC,DIS)；

③G′←Src.GMT(G)；

④ fori

⑤X←Src.splite(O)；

⑥Src.DPW(X,D,G′)；

⑦i←i+1；

⑧ end for

首先，源节点Src调用GBTC得到传输拓扑D并调用GMT对生成矩阵进行变形得到G′(算法4第①～③行)；接着，源节点Src将原始数据划分为若干个条带，每个条带含有k个数据块(算法4第⑤行)；最后，源节点Src不断调用DPW以并行流水的方式完成所有条带的写入任务(算法4第⑥行).

在CREW中，GBTC的计算复杂度为O(|DC|2)，GMT的计算复杂度为O(k2)，DPW的计算复杂度O(kn).其中，GBTC与CMT只执行2次，DPW的执行次数由原始数据的大小决定.所以，CREW的计算复杂度为O(knm).实际应用中，k和n较小，因此CREW的计算复杂度为O(m).

3 实验与结果

为了评估CREW的性能，我们基于Hadoop 3.0.3的HDFS实现了CREW.Hadoop 3.0.3的HDFS中主要有3类节点：Client(即源节点)、NameNode和DataNode.其中，Client负责数据的写入；NameNode负责存储源节点Client写入的元数据、检测编码块失效、选择DataNode来完成失效编码块的修复工作；DataNode则负责存储Client写入的数据并运行ECWorker任务对失效的编码块进行修复.

在实现CREW时，我们主要对Client和Data-Node进行了修改：在Client中添加了拓扑构造模块和生成矩阵变形模块，使其在写入数据前可以运行GBTC来确定传输拓扑并可以运行GMT来对生成矩阵进行变形操作；在DataNode添加了编码模块，使其在写入数据过程中可以进行部分编码操作，从而能够支持DPW的运行.

此外，我们同样基于Hadoop 3.0.3的HDFS实现了一种集中式写入方法Trad[19]、一种分布式写入方法D2CP[22]、一种面向跨数据中心纠删码的分布式写入方法IncEncoding[23]、CREW的2种变形CREW-Star和CREW-Tree.

在Trad中，源节点即为中心编码节点，源节点先将数据对象分块，然后对数据块进行编码得到编码块，最后将编码块分发到各个存储节点中.

在D2CP中，源节点将数据对象分块后完成部分的数据编码操作，然后将编码生成的中间编码块发送到相应的存储节点中，存储节点在接收到源节点的数据后通过相互协作的方式完成剩余的编码操作.

在CREW-Star中，源节点将数据对象分块后以星型拓扑发送给各个数据中心中的编码节点，编码节点在接收到所有需要的数据块后对其进行编码，然后将编码得到的编码块以星型拓扑发送给同数据中心里的其他存储节点.

在CREW-Tree中，源节点将数据对象分块后以树型拓扑(最小网络距离生成树)发送给各个数据中心中的编码节点，编码节点在接收到所有需要的数据块后对其进行编码，然后将编码后的编码块以星型拓扑发送给同数据中心里的其他存储节点.

在IncEncoding中，所有源节点和存储节点以线性拓扑组织，源节点将数据对象分块后沿着线性拓扑以流水的方式依次发送各个数据块，各个存储节点接收到一个数据块就使用其进行编码得到中间编码块，同时将该数据块转发给下一存储节点.最终，每个存储节点都将接收到自己所需的所有数据块，并编码生成最终的编码块.

3.1 实验设置

我们的实验环境为UCloud[29]的6个数据中心，其中2个位于北京(记为PEK1和PEK2)、一个位于上海(记为SHA)、一个位于广州(记为CAN)、一个位于洛杉矶(记为LA)、一个位于台北(记为TPE).我们测试了这6个数据中心间的网络距离，如表1所示.实验用到了每个数据中心的10个节点，每个节点配备了2个6核Intel Xeon-2640 2.5 GHz处理器、6 GB内存和20 GB磁盘.

在实验中，我们首先使用Hadoop源码中提供的ErasureCodeBenchmarkThroughput类来生成不同大小的文件，然后比较了不同写入方法在不同参数下写入这些文件时的各项性能指标.实验中的参数如表2所示.其中，第1列为表示参数的符号，第2列为参数的定义，第3列为参数的取值范围，第4列为参数的默认值.

Table 2 Parameters in Experiments表2 实验参数

3.2 评价指标

由于纠删码写入方法的写入速度受到网络资源消耗量、编码效率和传输效率的影响.因此，我们首先比较了不同写入方法的网络资源消耗量；然后，我们分别用数据块的最大转发次数和节点的最大编码复杂度来量化对比不同写入方法的传输效率和编码效率；最后，我们还直接比较了不同写入方法的写入速度.

1) 平均网络资源消耗量.平均网络资源消耗量定义为M·NavgSd(单位为hop).其中，M为数据写入过程中的各节点间的数据传输总量，Navg为数据的平均传输网络距离，Sd为数据对象的大小.

2) 数据块最大转发次数.由于数据的传输是流水并行的，理想情况下总传输时间由所有数据块的最长传输时间决定.又因为数据块在存储节点上进行转发时会带来额外的磁盘读写耗时和排队等待耗时，所以数据块的最长传输时间受最长转发次数的影响较大.因此可以使用数据块的最大转发次数来衡量传输效率.最大转发次数越短，传输效率越高.

3) 节点最大计算复杂度.各个节点的编码复杂度定义为该节点需要完成的乘法运算次数.由于数据的编码可以分散到不同的节点同步进行，理想情况下总的编码用时由所有节点的最长编码用时决定，而节点的最长编码用时受节点最大计算复杂度的影响较大.因此，节点最大计算复杂度决定了编码效率.节点最大计算复杂度越小，编码效率越高.

4) 写入速度.写入速度定义为SdT(单位为MBps)，其中，T为写入用时，Sd为数据对象的大小.写入速度受到网络资源消耗量、编码效率、传输效率的共同影响，能够综合评估写入方法的优劣.

3.3 平均网络资源消耗量

3.3.1 平均网络资源消耗量与编码参数的关系

图3显示了使用不同编码参数和不同写入方法时的平均网络资源消耗量.随着编码块数n的增加，所有写入方法的平均资源消耗量都增加了，这是由于数据传输量会随着n的增加而增加.在所有写入方法中，由于Trad在中心编码节点中完成全部编码块的编码后只需直接将编码块传输到对应的存储节点中即可，所以其网络资源销量最小.但是，Trad的低网络资源消耗量是通过牺牲编码效率获得的.由于Trad将全部的编码负载集中到了中心编码节点上，其编码效率明显低于其他写入方法.在其他5种写入方法中，CREW具有最小的平均网络资源消耗量，这是因为CREW可以通过同时对传输拓扑和生成矩阵进行优化充分减少写入过程中需要远距离传输的数据块.

Fig. 3 Comparison of the average network resource consumption under different encoding parameters图3 不同的编码参数下的平均网络资源消耗量对比

3.3.2 平均网络资源消耗量与数据中心数的关系

图4表明所有写入方法的平均网络资源消耗量都会随着使用的数据中心数的增加而增加.这是由于使用的数据中心数越多，需要跨数据中心传输的数据越多.此外，在只使用3个数据中心进行数据存储时，CREW的平均网络资源消耗量甚至少于Trad，这是因为CREW此时将需要使用较多数据块编码得到的编码块存放在源节点所在的数据中心中，从而大大减少了需要跨数据中心传输的数据块的数目.

Fig. 4 Comparison of the average network resource consumption when different numbers of DCs are used图4 不同的数据中心数下的平均网络资源消耗量对比

3.4 数据块最大转发次数

3.4.1 数据块最大转发次数与编码参数的关系

Fig. 5 Comparison of the maximum number of forwards of data blocks under different encoding parameters图5 不同的编码参数下的数据块最大转发次数对比

图5显示了选择不同的编码参数时CREW,CREW-Tree,CREW-Star,Trad的数据块最大转发次数没有明显变化.这是由于这些写入方法在数据中心内采用的是集中式的数据传输和数据编码，因而其数据块最大转发次数只受到数据中心间传输拓扑的影响，而数据中心间传输拓扑只受到使用的数据中心数的影响.此外，由于D2CP和IncEncoding在数据中心间和数据中心内部均采用分布式的数据传输和数据编码，因而它们的数据块最大转发次数随着编码块数n的增加而增加，并且明显高于其他方法.最后，由于Trad和CREW-Star在数据中心间使用了无需转发数据的星型传输拓扑，它们的数据块最大转发次数最小.但是，由于实际应用中数据中心的数目通常较小，所以数据中心间传输拓扑对数据块的最大转发次数影响较小.因此，CREW和CREW-Star的数据块最大转发次数在各种编码参数下均只比Trad和CREW-Star多1～2次.

3.4.2 数据块最大转发次数与数据中心数的关系

图6显示了使用不同纠删码写入方法时，数据块最大转发次数随着数据中心数的增长而缓慢增长.这是由于随着数据中心数的增多，各种方法的传输拓扑的深度均逐渐加深.此外，由于D2CP和IncEncoding在数据中心间和数据中心内部均采用分布式的数据传输和数据编码，因而它们的数据块最大转发次数明显高于其他方法.最后，由于Trad和CREW-Star在数据中心间使用了无需转发数据的星型传输拓扑，所以它们的数据块最大转发次数最小.但是，由于数据中心的数目通常较小，所以数据中心间传输拓扑对数据块的最大转发次数影响较小.因此，实验中CREW和CREW-Star的数据块最大转发次数仅比Trad和CREW-Star多1～2次.

Fig. 6 Comparison of the maximum number of forwards of data blocks when different numbers of DCs are used图6 不同的数据中心数下的数据块最大转发次数对比

3.5 节点最大计算复杂度

3.5.1 节点最大计算复杂度与编码参数的关系

图7显示了不同编码参数对节点最大计算复杂度的影响.可以看到，随着编码块数和数据块数的增加，节点最大计算复杂度逐渐增加.这是由于越多的编码块和数据块意味着越多的乘法计算.此外，由于IncEncoding和D2CP在数据中心间和数据中心内部均采用分布式的数据传输和数据编码，所以它们的节点最大计算复杂度最低.但是，这2种方法的低节点最大计算复杂度是通过牺牲传输效率获得的.如图5所示，在不同的编码参数下，IncEncoding和D2CP的数据块最大转发次数均明显多于其他方法，因而它们传输效率明显低于其他方法.在其他写入方法中，CREW具有最低的节点最大计算复杂度，这是由于CREW在数据中心间采用分布式的数据编码和数据传输，起到了分散计算负载的作用.

Fig. 7 Comparison of the maximum computational complexity of encoding nodes under different encoding parameters图7 不同的编码参数下的节点最大计算复杂度对比

3.5.2 节点最大计算复杂度与数据中心数的关系

Fig. 8 Comparison of the maximum computational complexity of encoding nodes when different numbers of DCs are used图8 不同的数据中心数下的节点最大计算复杂度对比

图8显示了不同数据中心数对节点最大计算复杂度的影响.可以看到，随着数据中心数的增加，节点最大计算复杂度逐渐降低.这是由于越多的数据中心意味着编码计算越分散.此外，由于IncEncoding和D2CP在数据中心间和数据中心内部均采用分布式的数据传输和数据编码，所以它们的节点最大计算复杂度最低.但是，这2种方法的低节点最大计算复杂度是通过牺牲传输效率获得的.如图6所示，在不同的数据中心数下，IncEncoding和D2CP的数据块最大转发次数明显多于其他方法，因而它们传输效率明显低于其他方法.在其他写入方法中，CREW具有最低的节点最大计算复杂度，这是由于CREW在数据中心间采用分布式的数据编码和数据传输，起到了分散计算负载的作用.

3.6 写入速度

3.6.1 写入速度与数据包大小的关系

如图9所示，随着数据包大小的不断增大，6种写入方法的写入速度都在不断提高.这是因为更大的数据包能够减少数据包的数量，从而提高传输速度.值得注意的是，当数据包大小从48 KB增大到64 KB时，数据传输速度又略微降低.这是由于超过一定大小的数据包在通过TCP传输时会被分为多个包，从而增加了数据包的数据量.此外，在不同的数据包大小下，CREW均能取得最高的写入速度，这是因为CREW可在网络资源消耗量、编码效率和传输效率之间取得较好的权衡.

Fig. 9 Comparison of the writing rate when different data package sizes are used图9 不同的数据包大小下的写入速度对比

3.6.2 写入速度与线程数目的关系

如图10所示，随着线程数目的增加，6种写入方法的写入速度都得到提高.这是由于线程的增加提高了编码的效率.特别的是，随着线程数的增加，Trad的写入速度的增加较为明显.这是因为Trad的写入瓶颈在于编码效率，而提高线程数能够有效提高编码效率.此外，在不同的线程数目下，CREW均能取得最高的写入速度，这是因为CREW可在网络资源消耗量、编码效率和传输效率之间取得较好的权衡.

3.6.3 写入速度与编码参数的关系

图11显示了不同编码参数对写入速度的影响.可以看到，随着编码块数的增加，编码速度降低.这是因为编码块数的增加同时增大了网络资源消耗量和节点最大计算复杂度.此外，在不同的编码参数下，CREW均能取得最高的写入速度，这是因为CREW可在网络资源消耗量、编码效率和传输效率之间取得较好的权衡.

3.6.4 写入速度与数据中心数的关系

图12显示了数据中心数对写入速度的影响.可以看到，随着数据中心数的增加，写入速度降低.这是因为数据中心数的增加同时增大了网络资源消耗量和数据块最大传输距离.此外，在不同的数据中心数下，CREW均能取得最高的写入速度，这是因为CREW可在网络资源消耗量、编码效率和传输效率之间取得较好的权衡.

总体而言，Trad的网络资源消耗量少且数据块最长传输网络距离短，但其节点最大计算复杂度最高.D2CP和IncEncoding的节点最大计算复杂度低，但其数据块最长传输网络距离长且网络资源消耗量大.CREW-Star的网络资源消耗量大，CREW-Tree的数据块最长传输网络距离长.而CREW能在网络资源消耗量、数据块最大转发次数(传输效率)和节点最大计算复杂度(编码效率)间取得较好的权衡.因此，平均而言，CREW的写入速度比IncEncoding,Trad,D2CP,CREW-Tree,CREW-Star分别提高了32.4%， 57.9%,36.3%,33.3%,35.2%.

4 总 结

在跨数据中心存储系统中，已有纠删码写入方法面临网络资源消耗量较大、编码效率和传输效率低等问题，使得跨数据中心纠删码的写入速度较低以至于难以适应于日益增长的数据生成速度.为此，本文提出了一种基于生成矩阵变换的跨数据中心纠删码写入方法CREW.具体而言，CREW包含以下3个主要算法：基于贪心策略的传输拓扑构造算法GBTC和生成矩阵变形算法GMT，二者相互协作可降低数据写入时需要远距离传输的数据量，从而达到降低网络资源消耗量的目的.以及分布式流水线写入算法DPW来协调各节点间的数据传输操作和编码操作.为了避免节点的计算能力成为编码瓶颈， DPW在数据中心间进行分布式的数据编码和数据传输.为了避免因数据转发次数过多造成的传输瓶颈，DPW在数据中心内部进行集中式的数据编码和数据传输.在跨数据中心环境下的实验表明，CREW能在网络资源消耗量、编码效率和传输效率之间取得较好的权衡，从而能够有效提高写入速度.