近年来，云数据中心故障频发，常导致其中数据长时间不可访问^[1-6]. 同时，云际计算技术的逐渐成熟使得部署跨云数据中心存储系统更加便捷^[7]. 因此，各机构纷纷采用跨云数据中心多副本技术来实现重要数据的容灾存储^[8].

相较于跨云数据中心多副本技术，跨云数据中心纠删码技术具有更高的可靠性和更低的冗余度^[9-12]. 然而，跨云数据中心纠删码技术要在生产系统中得到普遍运用，还需满足3方面要求：

1）低跨云数据中心修复流量. 纠删码技术在跨云数据中心存储系统中修复故障节点中的数据时，需跨云数据中心传输大量数据，即纠删码技术的跨云数据中心修复流量较大. 由于云数据中心间带宽往往远低于云数据中心内带宽，所以纠删码技术在跨云数据中心存储系统中修复数据的时间较长^[13-15]. 因此，亟需降低纠删码的跨云数据中心修复流量.

2）高编码参数适应性. 在生产中，用户通常对存储节点数n、冗余度n/k、容错度d和容灾度D等纠删码编码参数具有多样化需求. 因此，有必要提高跨云数据中心纠删码的编码参数适应性. 编码参数为 （n, k, d, D） 的纠删码将每k个数据块编码为n个编码块，并将其分别存储在位于多个云数据中心的n个存储节点，且当任意${d}-{1}$个存储节点或任意D个云数据中心故障时，其中存储的编码块可由其他编码块修复.

3）高纠删码构造效率. 因为纠删码编解码数据的过程与存储系统的读写过程深度耦合，所以开发和部署存储系统前需先完成纠删码的构造，因而用户通常对纠删码构造用时较为敏感. 因此，有必要提高跨云数据中心纠删码的构造效率.

现有工作提出的跨云数据中心纠删码^[13-18]虽然能在一定程度上降低跨云数据中心修复流量，但普遍存在编码参数适应性较低的问题，无法在满足用户对编码参数的多样化需求的同时有效降低跨云数据中心修复流量. 此外，有工作提出了面向跨云数据中心存储的自适应纠删码ACIoT^[19]，可求得不同编码参数 （n,k,d） 下的跨云数据中心修复流量下限，并构造能达到该下限的纠删码，即最优码. 但是，ACIoT需要消耗较长时间来检验纠删码修复组分布方案与编码参数 （n,k,d） 的匹配性，故其纠删码构造效率较低. 纠删码修复组分布方案E与指定编码参数P相匹配是指存在一个编码参数为P的纠删码的修复组分布方案为E.

综上，现有工作无法兼顾编码参数适应性、纠删码跨云数据中心修复流量和纠删码构造效率. 本文提出一种低跨云数据中心修复流量的纠删码的快速构造方法 （fast construction method of the erasure code with small cross-cloud data center repair traffic）FMEL，可在不同的编码参数下快速构造出具有较低跨云数据中心修复流量的纠删码. FMEL的主要思想为：

首先，FMEL将纠删码修复组分布方案及相应的编码参数 （n,k,d,D） 转换为定长特征向量，并将检验纠删码修复组分布方案与指定编码参数匹配性的问题转换为定长特征向量的二分类问题. 其中，特征向量属于正类表示纠删码修复组分布方案与相应编码参数相匹配. 然后，FMEL采用具有较高分类效率的支持向量机（support vector machine, SVM）来对各个特征向量进行分类以实现其所对应纠删码修复组分布方案的快速检验. 在检验的同时，FMEL不断采集新的训练集对SVM分类器进行增量更新，从而不断提高其分类准确率. 随后，FMEL采用一种并行搜索方法来快速地从所有可通过SVM检验的纠删码修复组分布方案中选出跨云数据中心修复流量最小的一个方案. 最后，FMEL采用一种基于试错的纠删码修复组分布方案转换方法将搜索到的纠删码修复组分布方案转换为具有低跨云数据中心修复流量的纠删码的生成矩阵.

在跨云数据中心环境中的实验表明，FMEL在大部分编码参数下可构造出能达到平均跨云数据中心修复流量下限的最优码，且其构造纠删码的时间仅为现有工作构造最优码时间的11%.

1.   相关工作

1.1   单云数据中心纠删码

现有工作提出了2类低修复流量纠删码——再生码和局部性码. 再生码通过降低新生节点从各提供者节点里的编码块中读取的数据量来减少修复流量，局部性码通过降低各个编码块的提供者节点数量来减少修复流量. 与再生码相比，局部性码更容易实现且灵活性更高，因而被广泛地应用于Amazon AWS^[20]，Microsoft WAS^[21]，Facebook HDFS-RAID^[22]等生产系统中. 特别地，Shahabinejad等人^[23]提出了一种可达到平均修复流量下限的纠删码ACAL.

虽然现有单云数据中心纠删码能够降低平均修复流量，但是跨云数据中心修复流量并不与修复流量正相关. 因此，这些纠删码在跨云数据中心环境下不能充分降低跨云数据中心修复流量.

1.2   跨云数据中心纠删码

Yu等人^[13]提出了一种跨域容错纠删码DFC，其基本思想是在传统的RS码的基础上引入局部校验块，首先使用RS码将k个数据块编码为w个编码块并在N个云数据中心中各存储${w/N}{\left( w/N \leqslant w-k\right)}$个数据块. 由于RS码可以保证在这w个编码块中的任意${w}-{k}$个编码块失效时重构原始数据，所以在任意一个云数据中心故障时，仍可以通过其他云数据中心里的${w}-{w/N\left( w-w/N \geqslant k\right)}$个编码块恢复出原始数据. 然后，DFC为每个机架存放的编码块生成局部校验块，使得在任意一个编码块失效时，可以使用机架内的编码块和局部校验块对其进行修复. 因此，DFC的跨云数据中心修复流量较小. 但是，DFC对编码参数具有严格的限制，要求${n}-{k}-{d}{+1}{\geqslant N}$.

Caneleo等人^[14]提出了一种多倍异或码MXOR，其基本思想是将数据块分为2行k/2列，而后通过异或计算分别求得各行各列的局部校验块，然后将所有编码块和局部校验块按行分散到各云数据中心. 当单个编码块失效时，MXOR可通过对云数据中心内部的其他编码块和局部校验块进行异或计算对其进行修复，因此MXOR的跨云数据中心修复流量较小. 但是，MXOR对编码参数具有严格的限制，要求${n}{/}{k}{\geqslant 2.4}$且${d}{\leqslant 4}$.

Chen等人^[15-16]和Hu等人^[17]分别提出FMSR码和DRC码均能有效降低跨云数据中心修复流量. 然而，FMSR和DRC均对编码参数有严格的限制，FMSR要求n−k=2，而DRC码要求n, k, N （云数据中心数） 至少满足2个条件中的1个：1） n=3z, k=2z, N=3 （z为正整数）；2） N=n/（n−k）.

虽然上述纠删码均能在一定程度上降低跨云数据中心修复流量，但它们普遍存在编码参数适应性较差的问题，无法在满足用户对编码参数的多样化需求的同时有效降低跨云数据中心修复流量. 为此，有工作^[19]提出了面向跨云数据中心存储的自适应纠删码ACIoT，可求得不同编码参数 （n,k,d） 下的最小跨云数据中心修复流量码，即最优码. 具体而言，ACIoT首先定义了纠删码的修复组分布方案，该方案决定了纠删码的跨云数据中心修复流量. 然后，ACIoT可枚举指定编码参数 （n, k） 下的纠删码修复组分布方案，并检验它们是否与指定编码参数 （n,k,d） 相匹配. 最后，ACIoT可从所有与编码参数 （n,k,d） 相匹配的纠删码修复组分布方案中找出具有最小跨云数据中心修复流量的1个并将其转换为最优码生成矩阵. 然而，ACIoT忽略了容灾度对跨云数据中心修复流量下限的影响. 此外，因ACIoT需要消耗较长时间来检验纠删码修复组分布方案与编码参数 （n,k,d） 的匹配性，故其纠删码构造用时较长.

综上，现有的跨云数据中心纠删码无法同时满足低跨云数据中心修复流量、高编码参数适应性和高纠删码构造效率，这严重限制了其在生产系统中的运用.

除以上聚焦于数据修复的工作外，Saeed等人^[24]还考虑到RS码等纠删码技术在读取数据时具备多种读取方案，可以通过访问不同云数据中心的节点来重构用户数据. 因此，他们提出了距离优先读取策略和负载均衡优先读取策略，分别用于对读取过程的网络开销和各存储节点的负载进行优化. 同时，他们对用户读取数据时的网络开销和各节点的负载进行了综合建模，得到了一个综合考虑2方面因素的开销模型，并基于此模型提出了跨数据中心纠删码数据读取节点选择算法Sandooq，能够有效降低数据读取的综合开销. 此外，我们在之前的工作中提出了一种跨云数据中心纠删码增量写入方法^[25]和一种基于生成矩阵变换的跨云数据中心纠删码写入方法^[26]，可分别通过提高编码并行度和降低跨云数据中心写入流量来提高写入效率.

2.   重要定义及定理

定义1.生成矩阵. 跨云数据中心纠删码技术将用户数据划分为若干数据块，并将每k个数据块 （记为${{x}}_{{t}}{,}{t}{\in}{[1}{,}{k}{]}$） 编码为n个编码块 （记为${{y}}_{{i}}{,}{i}{\in}{[1,}{n}{]}$），这n个编码块被称为一个条带，编码过程如式 （1） 所示，其中G为纠删码的生成矩阵. 生成矩阵G的秩必须为k ,否则G^T(z₁,…,z_k)^T=(y₁,…,y_n)^T没有唯一解，即无法将一个条带中的n个编码块解码为原始数据块.

定义2. 校验矩阵. 如果${{{\boldsymbol{h}}}}_{{1^*}}^{{{\rm{T}}}}{,}{{{\boldsymbol{h}}}}_{{2}^*}^{{{\rm{T}}}}{,…,}{{{\boldsymbol{h}}}}_{\left({n}-{k}\right)^*}^{{{\rm{T}}}}$为${{\boldsymbol{G}}}{\left[{{z}}_{{1}}{,…,}{{z}}_{{k}}\right]}^{{{\rm{T}}}}{=} {{\bf{0}}}$的基础解系，那么${{\boldsymbol{H}}}={{[}{{{\boldsymbol{h}}}}_{{1}^*}^{{{\rm{T}}}}{,…,}{{{\boldsymbol{h}}}}_{{(}{n}-{k}{)}^*}^{{{\rm{T}}}}{]}}^{{{\rm{T}}}}$为对应于生成矩阵G的校验矩阵. 因为G的秩为k，所以H的秩为n−k.

定义3. 修复组. 由生成矩阵${{\boldsymbol{G}}}$与校验矩阵${{\boldsymbol{H}}}$的定义有，${{\boldsymbol{G}}}{{{\boldsymbol{H}}}}^{{{\rm{T}}}}{=}{{\bf{0}}}$，故${(}{{y}}_{{1}}{,…,}{{y}}_{{n}}{{)}{{\boldsymbol{H}}}}^{{\rm{{T}}}}{=(}{{x}}_{{1}}{,…,}{{x}}_{{k}}{)}{{\boldsymbol{G}}}{{{\boldsymbol{H}}}}^{{{\rm{T}}}}{=}{{\boldsymbol{0}}}$. 因此，每个编码块都可以通过对其他若干个编码块进行线性计算重构. 如果编码块${{y}}_{{i}}$可以通过对${{y}}_{{i}{,1}}{,}{{y}}_{{i,}{2}}{,}{…}{,}{{y}}_{{i}{,}{r}}$进行线性计算重构，那么{${{y}}_{{i}},{{y}}_{{i},{1}},{{y}}_{{i},{2}},…,{{y}}_{{i,r}}\}$为${{y}}_{{i}}$的一个修复组 （用于修复${{y}}_{{i}}$的存储节点被称为新生节点，存储${{y}}_{{i,}{1}}{,}{{y}}_{{i,}{2}}{…,}{{y}}_{{i,r}}$的节点被称为提供者节点）. 一个编码块可能有多个修复组. 此外，由于编码块之间的线性关系由生成矩阵G或校验矩阵H决定，所以编码块的修复组也是由生成矩阵G或校验矩阵H决定的.

定义4. 编码块分布方案. 一个条带中的编码块所在的云数据中心的编号组成的集合为该条带的编码块分布方案$R=\left\{{{z}}_{{1}}{,}{{z}}_{{2}}{,}{…}{,}{{z}}_{{n}}\right\}$，其中z_i表示该条带中第i个编码块位于第z_i个云数据中心.

定义5. 编码块修复组分布方案. 设${{T}}_{{i}{,}{w}}$为编码块${{y}}_{{i}}$的第w个修复组，如果${{T}}_{{i,w}}$中的编码块分布于t个编号分别为${{z}}_{{1}}{,}{{z}}_{{2}}{,}{…,}{{z}}_{{t}}$的云数据中心中 （这t个云数据中心分别记为${{DC}}_{{{z}}_{{1}}},{{DC}}_{{{z}}_{{2}}}$,…,${{DC}}_{{{z}}_{{t}}}$），那么令${{R}}_{{i,w}}{=}\left\{ {{z}}_{{1}}{,}{{z}}_{{2}}{,}{…,}{{z}}_{{t}}\right\}$. 设编码块${{y}}_{{i}}$共有${{Q}}_{{i}}$个修复组，记为${{T}}_{{i,}{1}}{,}{{T}}_{{i,}{2}}{,}{…,}{{T}}_{{i,}{{Q}}_{{i}}}$，且$\left|{{R}}_{{i,q}}\right|=\mathop{\rm{min}}\limits_{{w=1}}^{Q_i}\left(\left|{{R}}_{{i,w}}\right|\right)$ （q$\in$[1,Q_i]），那么${{R}}_{{i,q}}$为编码块${{y}}_{{i}}$的修复组分布方案. 其中，$\left|{{R}}_{{i,w}}\right|$表示${{R}}_{{i,w}}$中含有的云数据中心编号个数.

定义6. 纠删码修复组分布方案.如果${{}{{C}}_{{1}}{,}{{C}}_{{2}}{,}{…,}{{C}}_{{n}}{}}$分别为编码块${{}{{y}}_{{1}}{,}{{y}}_{{2}}{,…,}{{y}}_{{n}}{}}$的修复组分布方案，那么$\left\{{{C}}_{{1}}{,}{{C}}_{{2}}{,}{…,}{{C}}_{{n}}\right\}$为条带$\left\{{{y}}_{{1}}{,}{{y}}_{{2}}{,…,}{{y}}_{{n}}\right\}$的修复组分布方案. 通常而言，纠删码的不同编码条带中的编码块在各个云数据中心间的分布相同. 在此情况下，纠删码的各个条带的修复组分布方案相同，因而条带的修复组分布方案也被称为纠删码修复组分布方案.

为了降低跨云数据中心修复流量，在基于纠删码技术的跨云数据中心存储系统修复编码块时，含有提供者节点的云数据中心通常会先将其中的提供者节点的编码块合并为一个和各个编码块大小相同中间块，然后再将中间块发往新生节点. 此外，为了保持系统的容灾度和负载均衡性不变，失效编码块的新生节点通常和该失效编码块位于同一云数据中心. 在此情况下，如果编码块${{y}}_{{i}}$的修复组分布方案为${{C}}_{i}$且编码块大小为m，那么在修复${{y}}_{{i}}$时需要向其新生节点发送中间块的云数据中心 （含新生节点所在云数据中心） 的个数为${{C}}_{{i}}$中含有的云数据中心编号个数$\left|{{C}}_{{i}}\right|$，因而修复${{y}}_{{i}}$的最小跨云数据中心传输量为m（$\left|{{C}}_{{i}}\right|-{1}$）. 所以，一个纠删码的修复组分布方案为E的纠删码的编码条带的平均跨云数据中心流量为m$\mathop{\sum}\limits_{{C}\in E}\left(\left|{C}\right|-1\right)/{n}$，其中，C为E中的编码块修复组分布方案，n为一个编码条带中的编码块数. 因此，纠删码的平均跨云数据中心修复流量由其修复组分布方案决定.

定义7. 纠删码Tanner图^[23]. 若一个编码参数为 （n,k,d,D） 的纠删码C_O的校验矩阵为H，那么该纠删码的Tanner图$\mathcal{T}$为满足3个条件的二分图：1$)\mathcal{T}$的一个端点集包含n个变量端点 （variable node, VN）；2$)\mathcal{T}$的另一个端点集包含n−k个校验端点 （check node, CN）；3） 当且仅当H的第i行、第j列的元素不为0，$\mathcal{T}$的第j个校验端点覆盖其第i个变量端点，即$\mathcal{T}$中有一条以第j个校验端点和第i个变量端点为端点的边. 图1举例说明了纠删码的Tanner图与纠删码校验矩阵H间的关系.

图  1  纠删码Tanner图

Figure  1.  Erasure code’s Tanner graph

下载: 全尺寸图片 幻灯片

令${\boldsymbol{H}}={\left({h}_{ji}\right)}_{(n-k)\times n}$为纠删码C_O的校验矩阵，{y₁, y_2,…,y_n}为C_O的任意一个条带、$\mathcal{T}$为C_O的Tanner图. 因为（y₁,…,y_n）H^T=0，所以${{h}}_{{j}{1}}{{y}}_{{1}}{+}{{h}}_{{j}{2}}{{y}}_{{2}}+{…+}{{h}}_{{jn}}{{y}}_{{n}}{=}{0}$. 由定义7有，如果CN_j仅覆盖${{VN}}_{{{l}}_{{1}}}{,}{{VN}}_{{{l}}_{{2}}},{…,}{{VN}}_{{{l}}_{{r}}}$ （对于任意${t}{\in}\left[{1}{,r}\right]$有${{l}}_{{t}}{\in}{[1}{,}{n}{]}$），那么${{h}}_{{j}{1}}{,}{{h}}_{{j_2}},{…,}{{h}}_{{j}{n}}$中仅有${{h}}_{{j}{{l}}_{{1}}}{,} {{h}}_{{jl_2}},{…,}{{h}}_{{j}{{l}}_{{r}}}$不为0. 因此，${{h}}_{{j}{{l}}_{{1}}}{{y}}_{{{l}}_{{1}}}{+}{{h}}_{{j}{{l}}_{{2}}}{{y}}_{{{l}}_{{2}}}{+}{…}{+}{{h}}_{{j}{{l}}_{{r}}}{{y}}_{{{l}}_{{r}}}{=}{0}$，其中${{h}}_{{j}{{l}}_{{1}}}{,}{{h}}_{{j}{{l}}_{{2}}}, {…,}{{h}}_{{j}{{l}}_{{r}}}$均不为0，即${{y}}_{{{l}}_{{1}}}{,}{{y}}_{{{l}}_{{2}}},{…,}{{y}}_{{{l}}_{{r}}}$为一个修复组. 因此，纠删码Tanner图的每个变量端点对应于1个编码块$({{VN}}_{{i}}$对应于${{y}}_{{i}})$且每个校验端点对应1个修复组.

图2举例说明了纠删码Tanner图与编码块和修复组之间的关系. 纠删码的一个编码条带中的6个编码块y₁,y₂,…,y₆分别对应着该纠删码Tanner图的6个变量端点VN₁,VN₂,…,VN₆. 覆盖纠删码Tanner图中的第1,4,5,6个变量端点VN₁,VN₄,VN₅,VN₆的校验端点CN₁对应的修复组为{y₁,y₄,y₅,y₆}，该修复组内各编码块之间的线性关系为y₁+y₄+y₅+y₆=0. 同理，校验端点CN₂对应的修复组为{y₂,y₄,y₅,y₆}，该修复组内各编码块的线性关系为y₂+y₄+2y₅+4y₆=0；校验端点CN₃对应的修复组为{y₃,y₄,y₅,y₆}，该修复组内各编码块的线性关系为y₃+y₄+3y₅+9y₆=0.

图  2  纠删码Tanner图与编码块和修复组之间的关系

Figure  2.  The relationship between the erasure code’s Tanner graph, coded blocks, and the repair groups

下载: 全尺寸图片 幻灯片

本文涉及的常用符号及其含义如表1所示：

表  1  参数符号及其含义

Table  1.  Notations and Presentations of the Parameters

符号	含义
N	数据中心总数
${z_s}$	数据中心编号
$DC_{zs}$	数据中心
n	编码条带中的编码块数
k	原始条带中的数据块数
d	容灾度
D	容错度
CO	纠删码
${y}_{i}$	编码块
${\text{x}}_{j}$	数据块
H	校验矩阵
${\boldsymbol{h} }_{j*},{\boldsymbol{h} }_{*i }$	校验矩阵的行向量、列向量
${h_ji }$	校验矩阵中的元素
G	生成矩阵
${\boldsymbol{g} }_{j* },{\boldsymbol{g} }_{i* }$	生成矩阵的行向量、列向量
${ {g} }_{ji }$	生成矩阵中的元素
$\mathcal{T}$	纠删码Tanner图
${CN}_{j}$	纠删码Tanner图中的校验端点
${VN }_{i }$	纠删码Tanner图中的变量端点
T	修复组
R	编码块分布方案
C	编码块修复组分布方案
E	纠删码修复组分布方案
m	编码块的大小
P	编码参数
Po	抽样概率

下载: 导出CSV 

| 显示表格

定理1. 假设${\boldsymbol{H}}_{{(}{n}-{k}{)}{\times}{n}}$为对应于纠删码Tanner图$\mathcal{T}$的一个校验矩阵、${\boldsymbol{H}}_{1}$为H的任意一个n−k行c列 （${c}{\leqslant}{n}-{k}$） 的子矩阵. 如果$\mathcal{T}$的最大匹配数小于c，那么${\boldsymbol{H}}_{1}$的秩小于c，即${\boldsymbol{H}}_{{1}}$不可能列满秩.

证明. 假设：${{{\boldsymbol{H}}}}_{{1}}{=((}{{h}}_{{1}{{l}}_{{1}}}{,…,}{{h}}_{\left({n}-{k}\right){l}_{{1}}}{{)}}^{{{\rm{T}}}}{,…,(}{{h}}_{{1}{{l}}_{{c}}}{,…,} {{h}}_{\left({n}-{k}\right){{l}}_{{c}}}{{)}}^{{{\rm{T}}}}{)}$；H₂为H₁的任意一个c行c列的子矩阵 （不妨设为${((}{{h}}_{{1}{{l}}_{{1}}}{,…,}{{h}}_{{c}{{l}}_{{1}}}{{)}}^{{{\rm{T}}}} {,…,(}{{h}}_{{1}{{l}}_{{c}}}{,…,}{{h}}_{{c}{{l}}_{{c}}}{)}^{{{\rm{T}}}})$）；${\mathcal{T}}'$为$\mathcal{T}$的一个子图，其边集为$\big\{{C}{{N}}_{{1}}{,} {C}{{N}}_{{2}}{,} {…,}{C}{{N}}_{{n}-{k}}{,}{V}{{N}}_{{{l}}_{{1}}}, {V}{{N}}_{{{l}}_{{2}}},…, {V}{{N}}_{{{l}}_{{c}}}\big\}$；${W}{=} \big\{\{{{{l}}_{{{u}}_{{1}}}{,}{{l}}_{{{u}}_{{2}}}{,…,}{{l}}_{{{u}}_{{c}}}{}}\}{|}{{u}}_{{1}}{,} {{u}}_{{2}}{,…,} {{u}}_{{c}}{\in} \left\{{{}{1,}{2}{,…,}{c}}\right\}$，当${a}{\ne}{b}$时一定有${{u}}_{{a}}{\ne}{{u}}_{{b}}\big\}$；${D}_{\mathrm{E}}{=}\big\{{L}{|}{L}{=}\{{{h}}_{{1}{{l}}_{{{u}}_{{1}}}}{,}{{h}}_{{2}{{l}}_{{{u}}_{{2}}}}{,…,} {{h}}_{{c}{{l}}_{{{u}}_{{c}}}}\}; \{{{l}}_{{{u}}_{{1}}}{,} {{l}}_{{{u}}_{{2}}},{…,}{{l}}_{{{u}}_{{c}}}\}{\in}{W}\big\}$.

如果存在一个$L\in {D}_{\mathrm{E}}$不含有零元素 （不妨设${L}{=}\{{{h}}_{{1}{{l}}_{{1}}},{{h}}_{{2}{{l}}_{{2}}},…,{{h}}_{{c}{{l}}_{{c}}}\})$，那么$\mathcal{T}'$的最大匹配数为c （对应的最大匹配为{$\left\langle {{CN}}_{{1}}{,}{VN}_{{{l}}_{{1}}} \right\rangle ,\left\langle {{CN}}_{{2}}{,}{VN}_{{{l}}_{{2}}} \right\rangle , …, \left\langle {{CN}}_{{c}}{,}{VN}_{{{l}}_{{c}}} \right\rangle$}） ，这与假设$(\mathcal{T}$的最大匹配数小于c） 相悖. 因此，每个$L\in {D}_{\mathrm{E}}$至少包含一个零元素. 因此，$\left|{{{\boldsymbol{H}}}}_{{2}}\right|{=}\displaystyle\sum _{{{\{}{{l}}_{{{u}}_{{1}}}{,}{{l}}_{{{u}}_{{2}}}{,…,}{{l}}_{{{u}}_{{c}}}{}}\}{\in}{W}} {\left(-{1}\right)}^{{A}{(}{{l}}_{{{u}}_{{1}}}{,}{{l}}_{{{u}}_{{2}}}{,…,}{{l}}_{{{u}}_{{c}}}{)}}{(}{{h}}_{{1}{{l}}_{{{u}}_{{1}}}}{,}{{h}}_{{2}{{l}}_{{{u}}_{{2}}}}{,…,}{{h}}_{{c}{{l}}_{{{u}}_{{c}}}}{)}{=0}$，其中${A}\left({{l}}_{{{u}}_{{1}}}{,}{{l}}_{{{u}}_{{2}}}{,…,}{{l}}_{{{u}}_{{c}}}\right)$为${{l}}_{{{u}}_{{1}}}{,}{{l}}_{{{u}}_{{2}}}{,…,}{{l}}_{{{u}}_{{c}}}$的逆序数. 因此，${\boldsymbol{H}}_{1}$的任意c行c列的子矩阵都不满秩. 所以，${\boldsymbol{H}}_{1}$的秩小于c，即${\boldsymbol{H}}_{1}$不是列满秩的. 证毕.

定理2. 假设${\boldsymbol{H}}_{{(}{n}-{k}{)}{\times}{n}}$为纠删码C_O的校验矩阵. 当且仅当由H的第${z}_{1}$~${z}_{c}$列组成的矩阵${\boldsymbol{H}}_{1}$的秩为c，C_O能够在其各条带中的第${l}_{1}$~${l}_{c}$个编码块同时失效时修复这些失效编码块.

证明. 从纠删码的校验方程${(}{{y}}_{{1}}{,…,}{{y}}_{{n}}{{)}{{\boldsymbol{H}}}}^{{{\rm{T}}}}{=}{{\bf{0}}}$中得到的以${{y}}_{{{l}}_{{1}}}$,${{y}}_{{{l}}_{{2}}}$,…,${{y}}_{{{l}}_{{c}}}$为未知数的方程组如式 （2） 所示：

因为式 （2） 中的最大线性无关方程数等于${\boldsymbol{H}}_{1}$的秩，所以，当且仅当${\boldsymbol{H}}_{1}$的秩为c时，式 （2） 有唯一解. 因此，当且仅当${\boldsymbol{H}}_{1}$的秩为c时，${{y}}_{{{l}}_{{1}}}$,${{y}}_{{{l}}_{{2}}}$,…,${{y}}_{{{l}}_{{c}}}$能够被同条带中的其他编码块修复. 证毕.

定理3. 假设纠删码的编码块分布方案R已确定，即任意条带中的n个编码块被分配给N个云数据中心，亦即纠删码Tanner图$\mathcal{T}$的n个变量端点和相应的校验矩阵H的n个列被分配给了N个云数据中心 （根据定义7，纠删码Tanner图$\mathcal{T}$的n个变量端点分别对应于校验矩阵H的n个列和任意条带中的n个编码块）. 在此假设下，$\mathcal{T}$匹配于编码参数 （n,k,d,D） 的一个充要条件是：$\mathcal{T}$有n−k个校验端点、n个变量端点 （子条件1） ；$\mathcal{T}$的任意${\gamma}$个校验端点至少覆盖${\gamma}{+}{k}$个变量端点，其中，${\gamma} \in[{J}{,}{n}-{k}]$且${J}{=}{n}-{k}-{d}{+2}$ （子条件2） ；$\mathcal{T}$的最大匹配数不小于${n}-{k}$ （子条件3） ；任意含有${B}{(}{B}{\leqslant}{n}-{k})$个变量端点的D个云数据中心中的任意β(β${\in}\left[{1,}{B}\right]{)}$个变量端点至少覆盖${β}$个校验端点 （子条件4）.

证明. 1）必要性证明.

① 子条件1的必要性.

根据定义7，若$\mathcal{T}$匹配于编码参数 （n,k,d,D），那么其对应的纠删码的生成矩阵一定有k行n列. 根据纠删码Tanner图与纠删码的生成矩阵的关系，$\mathcal{T}$一定有n−k个校验端点、n个变量端点，即$\mathcal{T}$一定满足子条件1.

② 子条件2的必要性.

如果在$\mathcal{T}$中存在${\gamma}$个校验端点 （不妨设为${C}{{N}}_{{1}}{,} {C}{{N}}_{{2}}{,}{…,}{C}{{N}}_{{\gamma }}$） 仅覆盖了${w}$个变量端点 （不妨设为${{VN}}_{{1}}{,} {{VN}}_{{2}}{,…,}{{VN}}_{{w}}$） 且${w}{\leqslant}{\gamma}{+}{k}-{1}$，那么根据定义7，对应于$\mathcal{T}$的校验矩阵如式 （3） 所示. 其中，${\boldsymbol{0}}_{{\gamma}{\times}\left({n}-{w}\right)}$为全零矩阵.

（i） 如果${n}-{w}{\leqslant}{d}-{1}$，从纠删码的校验方程$({{y}}_{{1}}{,…,} {{y}}_{{n}}{)}{{\boldsymbol{H}}}^{{{\rm{T}}}}{=}{0}$中只能得到以${{y}}_{{w}{+1}}{,}{{y}}_{{w}{+}{2}}{,…,}{{y}}_{{n}}$为未知数的线性方程组：

因为${n}-{w}{\leqslant}{d}-{1}$，所以${n}-{w}{\geqslant}{n}-({\gamma}{+}{k}-{1}){=} {n}-{k}- {\gamma}{+1}$. 所以，式 （4） 中的具有${n}-{w}$个未知数和${n}-{k}-{\gamma}$个方程的方程组无唯一解. 因此，${{y}}_{{w}{+1}}{,}{{y}}_{{w}{+}{2}}{,…,}{{y}}_{{n}}$不能由同条带中的其他编码块修复. 因此，$\mathcal{T}$不匹配于编码参数d.

（ii） 如果${n}-{w}{ > }{d}-{1}$，从纠删码的校验方程${[}{{y}}_{{1}}{,…,} {{y}}_{{n}}{{]}{{\boldsymbol{H}}}}^{{{\rm{T}}}}{=}{{\boldsymbol{0}}}$中只能得到以${{y}}_{{n}-{d}{+2}}{,}{{y}}_{{n}-{d}{+}{3}}{,…,}{{y}}_{{n}}$为未知数的线性方程组：

因为${\gamma}{\in}[{J}{,}{n}-{k}]$且${J}{=}{n}-{k}-{d}{+2}$，所以${n}-{k}- {\gamma}{\leqslant}{n}- {k}-({n}-{k}-{d}{+2}){=}{d}-{2}$. 所以，式 （5） 中的具有${d}-{1}$个未知数和${n}-{k}-{\gamma}$个方程的方程组无唯一解. 因此，${{y}}_{{n}-{d}{+2}}{,}{{y}}_{{n}-{d}{+}{3}}{,…,}{{y}}_{{n}}$不能由同条带的其他编码块修复. 因此，$\mathcal{T}$不匹配于编码参数d.

综上，如果$\mathcal{T}$匹配于编码参数 （n,k,d,D），$\mathcal{T}$的任意$\mathrm{\gamma }$个校验端点至少覆盖${\gamma}{+}{k}$个变量端点，其中${\gamma}{\in}[{J}{,}{n}-{k}]$且${J}{=}{n}-{k}-{d}{+2}$.

③ 子条件3的必要性证明.

假设$\mathcal{T}$的最大匹配数为${b}{ < }{n}-{k}$且${{\boldsymbol{H}}}($含有n−k行、n列） 为任意一个对应于$\mathcal{T}$的校验矩阵，那么由定理1有，$\boldsymbol{H}$的每个n−k行、n$-$k列的子矩阵均不满秩. 因此，${{\boldsymbol{H}}}$的秩不为n−k. 因此，根据校验矩阵的定义，${{\boldsymbol{H}}}$不可能是一个 （n,k,d,D） 纠删码的校验矩阵. 因此，$\mathcal{T}$不匹配于 （n,k,d,D）. 因此，若$\mathcal{T}$匹配于编码参数 （n,k,d,D），$\mathcal{T}$的最大匹配数不小于${n}-{k}$.

④ 子条件4的必要性证明.

如果存在D个云数据中心 （不妨设为${{DC}}_{{{z}}_{{1}}}$, ${{DC}}_{{{z}}_{{2}}}$,…,${{DC}}_{{{z}}_{{D}}}$），其中的${\beta}$个变量端点 （不妨设为${V}{{N}}_{{1}}{,}{V}{{N}}_{{2}}{,…,}{V}{{N}}_{{\beta}})$只覆盖了${c}{\leqslant}{\beta}-{1}$个校验端点 （不妨设为${C}{{N}}_{{1}}{,}{C}{{N}}_{{2}}{,…,}{C}{{N}}_{{c}})$，那么根据定义7，对应于$\mathcal{T}$的校验矩阵H中只有c个行中的第1~${\beta}$列中存在非零元素. 因此，从纠删码的校验方程${(}{{y}}_{{1}}{,…,}{{y}}_{{n}}{{)}{{\boldsymbol{H}}}}^{{{\rm{T}}}}{=}{{\boldsymbol{0}}}$中只能得到以${{y}}_{{1}}{,}{{y}}_{{2}}{,…,}{{y}}_{\beta }$为变量的线性方程组:

因为式 （6） 中的$\beta$元方程组的最大线性无关方程数为c$({c}{ < }{\beta}{)}{，}$所以该方程组没有唯一解. 因此，对应于$\mathcal{T}$的纠删码的任意编码条带$\{y_{{1}}{,}{{y}}_{{2}}{,…,}{{y}}_{{n}}\}$中的${{y}}_{{1}}{,}{{y}}_{{2}}{,…,}{{y}}_{{\beta}}$不能被同条带的其他编码块修复$(\mathcal{T}$对应的纠删码不能容忍${{DC}}_{{{z}}_{{1}}}$,${{DC}}_{{{z}}_{{2}}}$,…,${{DC}}_{{{z}}_{{D}}}$同时失效）. 因此，$\mathcal{T}$不匹配于编码参数 （n,k,d,D）.

综上，若$\mathcal{T}$匹配于编码参数 （n,k,d,D），任意含有${B}{(}{B}{\leqslant}{n}-{k}{)}$个变量端点的D个云数据中心中的任意${\beta}{(}{\beta}{\in}\left[{1,}{B}\right]{)}$个变量端点至少覆盖${\beta}$个校验端点.

2）充分性证明.

证明. 假设纠删码Tanner图$\mathcal{T}$符合定理3中的充要条件，那么可按5个步骤构造出一个纠删码Tanner图为$\mathcal{T}$的匹配于编码参数 （n,k,d,D） 的纠删码的生成矩阵，即$\mathcal{T}$匹配于编码参数 （n,k,d,D）.

① 求得$\mathcal{T}$的最大匹配. 因为$\mathcal{T}$满足定理3中的充要条件的子条件3，所以其最大匹配包含n−k个变量端点. 如果$\mathcal{T}$的最大匹配包含${V}{{N}}_{{{l}}_{{1}}}{,}{V}{{N}}_{{{l}}_{{2}}}{,…,}{V}{{N}}_{{{l}}_{{n}-{k}}}$，那么令H₁为由H的第${{l}}_{{1}}{,}{{l}}_{{2}}{,…,}{{l}}_{{n}-{k}}$列组成的矩阵. 由于H₁的行数和列数均为n−k，所以其为方阵. 然后，我们将H₁加入集合LS.

② 求得H的所有的包含n−k行、d−1列的子矩阵的集合SM₁以及H的所有的包含其对应于任意D个云数据中心的列的子矩阵组成的集合SM₂.

③ 根据纠删码Tanner图的定义，SM₁和SM₂中每个矩阵都对应于$\mathcal{T}$的一个子图. 因此，我们求得对应于SM₁和SM₂中每个矩阵所对应的$\mathcal{T}$的子图的最大匹配. 而后，对于SM₁和SM₂中的每个矩阵Z，如果其对应的$\mathcal{T}$的子图的最大匹配包含${C}{{N}}_{{{l}}_{{1}}}{,}{C}{{N}}_{{{l}}_{{2}}}{,}{…,}{C}{{N}}_{{{l}}_{{c}}}$，则将其第${{l}}_{{1}}{,}{{l}}_{{2}}{,…,}{{l}}_{{c}}$行组成的子矩阵加入集合LS.

可以证明，如果SM₁或SM₂中的某个矩阵有q列，那么其对应的$\mathcal{T}$的子图的最大匹配一定为q （即LS中的矩阵均为方阵），证明过程为：

首先，证明如果SM₁中的某个矩阵有q列，那么它的最大匹配数一定为q. 由于SM₁的矩阵的列数恒为d−1，因此只需要证明SM₁中的矩阵对应的$\mathcal{T}$的子图的最大匹配数恒为d−1.

（i） 令${{\partial}=}{n}-{k}-{\gamma}{+1}($因为${\gamma}{\in}[{J}{,}{n}-{k}]$且${J}{=}{n}-{k}- {d}{+2}$，所以${\partial}{\in}[{1,}{d}-{1}])$，可以证明$\mathcal{T}$中任意${\partial}$个变量端点至少覆盖${\partial}$个校验端点：如果存在${\partial}$个变量端点仅仅覆盖${u}{\leqslant}{\partial}-{1}$个校验端点，那么剩下的${n}-{k}-{u}{\geqslant}{\gamma}$个校验端点最多覆盖${n}-{\partial}{=}{k}{+}{\gamma}-{1}$个变量端点，这与定理3中的充要条件的子条件2 （任意${\gamma}$个校验端点至少覆盖${\gamma}{+}{k}$个变量端点） 相矛盾. 因此，任意${\partial}$个变量端点至少覆盖${\partial}$个校验端点.

（ii） 根据Hall定理^[27]，在$\mathcal{T}$的任意含有d−1个变量端点、n−k个校验端点 （d−1<n−k） 的子图存在完全匹配的充要条件是该子图中任意${\partial}$个变量端点至少覆盖${\partial}$个校验端点 （${\partial}{\in}[{1,}{d}-{1}]$）. 由 （i） 有，$\mathcal{T}$中任意${\partial}$个变量端点至少覆盖${\partial}$个校验，所以$\mathcal{T}$的任意含有d−1个变量端点、n−k个校验端点 （d−1<n−k） 的子图存在完全匹配，即$\mathcal{T}$中任意d−1个变量端点可以一对一地覆盖d−1个校验端点.

（iii） 假设Z为SM₁中的任意矩阵且Z包含H的第${{l}}_{{1}}{,}{{l}}_{{2}}{,…,}{{l}}_{{d}-{1}}$列. 由 （ii） 有，${{VN}}_{{{l}}_{{1}}}{,}{{VN}}_{{{l}}_{{2}}}{,…,}{{VN}}_{{{l}}_{{d}-{1}}}$一定一对一地覆盖d−1个校验端点 （不妨设为${{CN}}_{{1}}{,}{{CN}}_{{2}}, {…,}{{CN}}_{{d}-{1}})$. 因此，$\left\{ \left\langle {CN}_{{1}}{,}{{VN}}_{{{l}}_{{1}}} \right\rangle ,\left\langle{CN}_{{2}}{,}{{VN}}_{{{l}}_{{2}}} \right\rangle ,…, \left\langle {{CN}}_{{d}-{1}}{,} {{VN}}_{{{l}}_{{d}-{1}}} \right\rangle\right\}$为对应于Z的$\mathcal{T}$的子图的最大匹配. 因此SM₁中任意矩阵对应的$\mathcal{T}$的子图的最大匹配数为d−1.

然后，证明如果SM₂中的某个矩阵有B列，那么它的最大匹配数一定为B.

（i） 不妨假设$\mathcal{T}$中对应于任意D个云数据中心的任意B个变量端点为${{VN}}_{{1}}$,${{VN}}_{{2}}$,…,${{VN}}_{{B}}$. 根据Hall定理^[27]，$\mathcal{T}$的由其${{VN}}_{{1}}$,${{VN}}_{{2}}$,…,${{VN}}_{{B}}$和n−k个校验端点组成的子图存在完全匹配的充要条件是该子图中任意${\beta}$个变量端点至少覆盖${\beta}$个校验端点 （${\beta}{\in}\left[{1,}{B}\right]$）. 因为$\mathcal{T}$满足定理3中的充要条件的子条件4，即任意含有${B}{(}{B}{\leqslant}{n}−{k}{)}$个变量端点的D个云数据中心中的任意${\beta}{(}{\beta}{\in}\left[{1,}{B}\right]{)}$个变量端点至少覆盖${\beta}$个校验端点，所以$\mathcal{T}$的由其${{VN}}_{{1}}$,…,${{VN}}_{{B}}$和n−k个校验端点组成的子图存在完全匹配，即$\mathcal{T}$中对应于任意D个云数据中心的任意B个变量端点一定可以一对一地覆盖B个校验端点.

（ii） 假设Z为SM₂中的任意矩阵且Z包含了H的第${{l}}_{{1}}{,}{{l}}_{{2}}{,…,}{{l}}_{{B}}$列. 由 （i） 有，${{VN}}_{{{l}}_{{1}}}{,}{{VN}}_{{{l}}_{{2}}}{,…,}{{VN}}_{{{l}}_{{B}}}$一定一对一地覆盖d−1个校验端点 （不妨设为${{CN}}_{{1}}{,}{{CN}}_{{2}}{,…,} {{CN}}_{{{l}}_{{B}}})$. 因此，$\big\{\left\langle {CN}_{{1}}{,}{{VN}}_{{{l}}_{{1}}} \right\rangle ,\left\langle {CN}_{{2}}{,}{{VN}}_{{{l}}_{{2}}} \right\rangle ,…, \left\langle {{CN}}_{{B}}{,} {{VN}}_{{{l}}_{{B}}} \right\rangle\big\}$为对应于Z的$\mathcal{T}$的子图的最大匹配. 因此SM₂中任意矩阵对应的$\mathcal{T}$的子图的最大匹配的边数为B.

④ 根据以上推导，LS中的矩阵均为方阵，且它们对应的$\mathcal{T}$的子图的最大匹配等于它们的秩. 对任意${\boldsymbol{Z}}_{{t}}{\in}{{{LS}}}$，不妨设对应于${\boldsymbol{Z}}_{t}$的$\mathcal{T}$的子图的最大匹配为${M}{=}\big\{\left\langle{CN}_{{{l}}_{{t}{,1}}}{,}{{VN}}_{{{s}}_{{t}{,1}}} \right\rangle ,\left\langle{CN}_{{{l}}_{{t}{,}{2}}}{,}{{VN}}_{{{s}}_{{t}{,}{2}}} \right\rangle ,…,\left\langle{CN}_{{{l}}_{{t}{,}{{b}}_{{t}}}}{,}{{VN}}_{{{s}}_{{t}{,}{{b}}_{{t}}}}\right\rangle\big\}$，那么可以通过对${\boldsymbol{Z}}_{{t}}$进行初等变换得到矩阵：

其中，${{h}}_{{{l}}_{{t}{,1}}{{s}}_{{t}{,1}}}$,${{h}}_{{{l}}_{{t}{,}{2}}{{s}}_{{t}{,}{2}}}$,…,${{h}}_{{{l}}_{{t}{,}{{b}}_{{t}}}{{s}}_{{t}{,}{{b}}_{{t}}}}$不为0.

因此，对${\boldsymbol{Z}}_{t}^{\mathrm{{'}}}$进行初等行变换可得矩阵：

其中，${{A}}_{{{l}}_{{a}}{{s}}_{{a}}}$为不包含${{h}}_{{{l}}_{{a}}{{s}}_{{a}}}$的线性多项式${(}{a}{\in}{[1,}{b}{])}{. }$

因为${{A}}_{{{l}}_{{t}{,}{a}}{{s}}_{{t}{,}{a}}}$为不包含${{h}}_{{{l}}_{{t}{,}{a}}{{s}}_{{t}{,}{a}}}$的线性多项式 （${t}{\in} {\{}{1,|}{LS}{|\}}$, ${a}{\in}\{{1,}{2}{,}{…,}{{b}}_{{t}}{\}}$），$\displaystyle\prod_{{t}{\in}{[}{1,|}{LS}{|]}}\prod _{{a}{\in}\{{1,}{2}{,}\;{…,}\;{{b}}_{{t}}{}\}}\left({{h}}_{{{l}}_{{t}{,}{a}}{{s}}_{{t}{,}{a}}}\;-\;{{A}}_{{{l}}_{{t}{,}{a}}{{s}}_{{t}{,}{a}}}\right){\;\neq \;0}$ 一定有解. 该不等式的解可以使所有的${{{\boldsymbol{Z}}}}_{{t}}^{{''}}$的行列式均不为0，即所有的${{{\boldsymbol{Z}}}}_{{t}}^{{''}}$满秩. 这意味着: （i） LS中的H₁满秩，即H满秩；（ii） SM₁和SM₂中的矩阵满秩. 由定理2可知，此时H对应的纠删码C_O能够容忍任意d−1个编码块失效或任意D个云数据中心失效 （即H为一个匹配于 （n,k,d,D） 的校验矩阵）.

⑤ 由于生成矩阵${{\boldsymbol{G}}}$和校验矩阵${{\boldsymbol{H}}}$满足${{\boldsymbol{G}}}{{{\boldsymbol{H}}}}^{{{\rm{T}}}}{=}{{\bf{0}}}$，所以在得到匹配于编码参数 （n,k,d,D） 的校验矩阵$\boldsymbol{H}$后即可求得相应的匹配于编码参数的 （n,k,d,D） 的生成矩阵$\boldsymbol{G}.$ 证毕.

定理4. 纠删码修复组分布方案E匹配于编码参数 （n,k,d,D） 的一个必要条件为：设ST为E中所有编码块修复组分布方案的无重复集合，对于任意D个共含有B个编码块的云数据中心 （不妨设这些云数据中心的编号为${{z}}_{{1}}{,}{{z}}_{{2}}{,…,}{{z}}_{{D}}$，即设这些云数据中心为${{DC}}_{{{z}}_{{1}}}{,}{{DC}}_{{{z}}_{{2}}}{,…,}{{DC}}_{{{z}}_{{D}}}$），ST中仅含有不多于${n}-{k}-{B}$个不包含这些云数据中心的编号集合{${{z}}_{{1}}{,}{{z}}_{{2}}{,…,}{{z}}_{{D}}$}中任意元素的编码块修复组分布方案.

证明. 根据定义6，如果ST中含有超过${n}-{k}-{B}$个不包含{${{z}}_{{1}}{,}{{z}}_{{2}}{,…,}{{z}}_{{D}}$}中任意元素的编码块修复组分布方案，那么相应的纠删码有超过${n}-{k}-{B}$个不含有${{DC}}_{{{z}}_{{1}}}{,}{{DC}}_{{{z}}_{{2}}}{,…,}{{DC}}_{{{z}}_{{D}}}$中编码块的修复组. 因此，根据定义7，在任何对应于${E}$的纠删码Tanner图 （不妨设为$\mathcal{T})$中，一定有超过${n}-{k}-{B}$个校验端点没有覆盖对应于${{DC}}_{{{z}}_{{1}}}{,}{{DC}}_{{{z}}_{{2}}}{,…,}{{DC}}_{{{z}}_{{D}}}$中编码块的变量端点. 因此，在$\mathcal{T}$中，对应于${{DC}}_{{{z}}_{{1}}}{,}{{DC}}_{{{z}}_{{2}}}{,…,}{{DC}}_{{{z}}_{{D}}}$中编码块的变量端点 （不妨设为${{VN}}_{{{l}}_{{1}}}{,}{{VN}}_{{{l}}_{{2}}}{,…,}{{VN}}_{{{l}}_{{B}}})$覆盖的校验端点少于B个. 因此，根据定义7，任意对应于$\mathcal{T}$的校验矩阵H中的第${{l}}_{{1}}{,}{{l}}_{{2}}{,…,}{{l}}_{{B}}$列组成的矩阵H₁最多只有B−1个非零行. 因此，H₁的秩小于B. 因此，根据定理2，校验矩阵为H的纠删码不能容忍任意编码条带中的第${{l}}_{{1}}{,} {{l}}_{{2}}{,…,}{{l}}_{{B}}$个编码块失效，即不能容忍${{DC}}_{{{z}}_{{1}}}{,}{{DC}}_{{{z}}_{{2}}}{,…,}{{DC}}_{{{z}}_{{D}}}$同时失效. 因此，纠删码修复组分布方案E不匹配于编码参数 （n,k,d,D）. 证毕.

定理5. 所有匹配于指定编码参数 （n,k,d,D） 的纠删码修复组分布方案的平均跨数据中心修复流量的最小值为编码参数 （n,k,d,D） 下的纠删码的平均跨数据中心修复流量下限.

证明. 令所有匹配于指定编码参数 （n,k,d,D） 的纠删码修复组分布方案的平均跨数据中心修复流量的最小值为T. 假设存在一个满足编码参数 （n,k,d,D） 且平均跨数据中心修复流量小于T的纠删码 （不妨设为C_O），那么C_O的修复组分布方案${E}_{{C}_{\mathrm{O}}}$的平均跨数据中心修复流量小于T. 因为所有匹配于指定编码参数 （n,k,d,D） 的纠删码修复组分布方案的平均跨数据中心修复流量的最小值为T，所以${E}_{{C}_{\mathrm{O}}}$不匹配于编码参数 （n,k,d,D），因而不存在一个满足编码参数 （n,k,d,D） 的纠删码的修复组分布方案为${E}_{{C}_{\mathrm{O}}}$，这与C_O的修复组分布方案为${E}_{{C}_{\mathrm{O}}}$相矛盾. 因此，不存在一个匹配于编码参数 （n,k,d,D） 且平均跨数据中心修复流量小于T的纠删码，即T为编码参数 （n,k,d,D） 下的纠删码的平均跨数据中心修复流量下限. 证毕.

3.   低跨云数据中心修复流量的纠删码的快速构造方法FMEL

本节提出了一种低跨云数据中心修复流量的纠删码的快速构造方法FMEL （如图3所示），可在不同编码参数下快速求得具有低跨云数据中心修复流量的纠删码.

图  3  FMEL的结构

Figure  3.  The structure of FMEL

下载: 全尺寸图片 幻灯片

具体而言，基于第2节推导出的相关定理，本节首先得出纠删码修复组分布方案匹配指定编码参数 （n,k,d,D） 的条件，并以此为依据提出了一种基于SVM的纠删码修复组分布方案检验算法 （erasure code repair group distribution scheme verification algorithm based on SVM）EVA，可对纠删码修复组分布方案与编码参数匹配性进行快速检验.

然后，本节提出了一种具有近似最小跨云数据中心修复流量的纠删码修复组分布方案的并行搜索算法 （distributed search algorithm of the erasure code repair group distribution scheme with the approximate minimum cross-cloud data center repair traffic）DSAOE，可从所有通过EVA检验的纠删码修复组分布方案中选出平均跨云数据中心修复流量较小的一个纠删码修复组分布方案.

最后，本节提出一种纠删码修复组分布方案转换算法（erasure code repair group distribution scheme transformation algorithm）EST，可将DSAOE搜索到的修复组分布方案转换为具有低跨云数据中心修复流量的纠删码的生成矩阵.

3.1   纠删码修复组分布方案匹配于指定 （n,k,d,D） 的条件

1）纠删码修复组分布方案匹配于指定（n,k,d,D）的充要条件

纠删码修复组分布方案是由纠删码的编码块的修复组和位置决定. 如果将一个纠删码Tanner图的各个变量端点分配给不同的云数据中心，那么纠删码Tanner图可以同时反映相应纠删码的编码块的修复组及位置. 因此，每个纠删码Tanner图对应一个纠删码修复组分布方案. 因为多个纠删码Tanner图可能对应同一个纠删码修复组分布方案，所以每个纠删码修复组分布方案通常对应多个纠删码Tanner图. 纠删码Tanner图$\mathcal{T}$匹配于编码参数 （n,k,d,D）是指存在一个Tanner图为$\mathcal{T}$的纠删码的编码参数为 （n,k,d,D）. 因此，若一个纠删码修复组分布方案所对应的纠删码Tanner图中，有不少于一个纠删码Tanner图匹配于编码参数 （n,k,d,D），则该方案匹配于编码参数 （n,k,d,D），反之则该方案不匹配于编码参数 （n,k,d,D）. 即纠删码修复组分布方案匹配于编码参数 （n,k,d,D） 的充要条件是至少存在一个与之对应的Tanner图满足定理3中的子条件1~4.

2）纠删码修复组分布方案匹配于指定（n,k,d,D）的必要条件

纠删码修复组分布方案匹配于编码参数（n,k,d,D）的一个必要条件如定理4所示.

3.2   EVA 算法

基于3.1节得出的纠删码修复组分布方案匹配指定编码参数 （n,k,d,D） 的条件，首先，EVA把纠删码修复组分布方案和对应的编码参数转换为便于分类算法高效处理的定长特征向量，转换过程能够保留判断纠删码修复组分布方案是否匹配于指定编码参数所需的全部信息，因而能够保证分类的准确性. 此外，EVA使用一个SVM来对定长特征向量进行分类以达到快速检验纠删码修复组分布方案是否匹配于对应的编码参数的目的. 在分类过程中，EVA可以持续收集更多带标签定长特征向量，并使用这些定长特征向量对SVM分类器进行增量更新，从而达到不断提高分类准确率的目的. EVA使用3.1节推导出的纠删码修复组分布方案匹配于指定编码参数 （n,k,d,D） 的条件为定长特征向量打标签，以得到SVM分类器的初始训练数据集和增量更新数据集.

3.2.1   特征向量构造

基于SVM的EVA对纠删码修复组分布方案进行转换：

首先，由定义6有，如果可用云数据中心的数目为N，那么编码块的修复组分布方案C一共有${{2}}^{{N}}-{1}$个可能的取值. 因此，EVA将把这${{2}}^{{N}}-{1}$个可能的取值一一映射为1,2,…,${{2}}^{{N}}-{1}$，映射函数如式 （9） 所示.

然后，对于每个云数据中心，EVA将统计出纠删码修复组分布方案中对应于该云数据中心中的编码块的修复组分布方案的映射值中1,2,…,${{2}}^{{N}}-{1}$出现的次数，从而得到了一个长度为${{N}{(}{2}}^{{N}}-{1)}$的定长特征向量X'，该向量中的第${a}{\times}{b}$个元素的值为$c$表示第$a$个云数据中心中有c个编码块的修复组分布方案的映射值为b. 例如，如图4所示，如果纠删码修复组分布方案为{{1},{1,2},{1,2},{2,3},{1,2,3},{1,2,3}}、云数据中心总数为3、编码条带中的第1, 2个编码块位于第1个云数据中心、编码条带中的第3, 4个编码块位于第2个云数据中心、编码条带中的第5, 6个编码块位于第3个云数据中心，那么其中各个编码块修复组分布方案的映射值分别为1,3,3,6,7,7，因而相应的X'=(1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2).

图  4  特征向量构造示意图

Figure  4.  Illustration of feature vectors construction

下载: 全尺寸图片 幻灯片

因为X'中含有各个云数据中心中的对应于不同修复组分布方案的编码块数目，所以使用X'可以恢复出各个云数据中心中的编码块的修复组分布方案的无序集合. 例如，从X'=(1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 2)的第3${\times}$7个元素为2可以推导出第3个云数据中心中有2个编码块的修复组分布方案的映射值为7，即它们的修复组分布方案为{1,2,3}. 因此，和原始的纠删码修复组分布方案相比，X'中仅仅丢失了各个编码块在各云数据中心内的顺序信息. 因为各个编码块在各云数据中心内的顺序并不影响纠删码的冗余度、容错度和容灾度，因此纠删码修复组分布方案转换过程没有丢失判断一个其是否匹配于编码参数 （n,k,d,D） 所需的有效信息.

在将纠删码修复组分布方案转换为一个数值型的定长特征向量X'后，EVA将n, k, d, D追加到X'即可得到用于表示纠删码修复组分布方案及其对应编码参数 （n, k, d, D） 的特征向量X，其长度恒为${{N}{(}{2}}^{{N}}-{1)+4}$.

3.2.2   基于SVM的特征向量分类

由于匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案之间以及不匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案之间均有一定的相似性，所以匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案对应的特征向量之间以及不匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案对应的特征向量之间存在一定的相似性. 因此，可以采用有监督学习算法^[28-29]来对纠删码修复组分布方案对应的特征向量进行分类：使用一些已知匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案对应的特征向量和已知不匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案对应的特征向量作为训练集来训练一个分类器. 分类器会判断新的纠删码修复组分布方案对应的特征向量是否和已知匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案对应的特征向量相似，如果相似则判断其匹配于编码参数 （n,k,d,D），反之则判断其不匹配于编码参数 （n,k,d,D）. 由于SVM具有分类速度快以及可对线性不可分的数据进行分类等优点^[30-32]，所以可以基于SVM对纠删码修复组分布方案对应的特征向量进行分类，以达到快速检验纠删码修复组分布方案的目的.

EVA的工作流程如算法1所示.

算法1. EVA算法.

输入：编码参数 （n,k,d,D），编码块分布方案R，纠删码修复组分布方案E，云数据中心数N ；

输出：检验结果result.

① if（系统初始化）

② 　TE$\leftarrow$随机抽取纠删码修复组分布方案的集合　　　　{n,N,R}；

③ 　for（TE中的每个元素e）；

④ 　　vector$\leftarrow$特征向量转换（e）；

⑤ 　　label$\leftarrow$枚举检验Tanner图（n,k,d,D,R,e）；

⑥ 　　将〈vector,label〉加入初始训练集 ；

⑦ 　 end for

⑧ end if

⑨ svm$\leftarrow$使用初始训练集训练分类器；

⑩ result.isPass$\leftarrow$false；

⑪ vector $\leftarrow$特征向量转换（E,n,k,d,D,N,R）；

⑫ p₁$\leftarrow$分类器分类 （svm,vector）；

⑬ p₂$\leftarrow$判断E是否满足必要条件（n,k,d,D,R）；

⑭ if（p₁==true且p₂==true）

⑮ 　T$\leftarrow$枚举纠删码Tanner图（E）；

⑯ 　for（每一个T中的纠删码Tanner图t）

⑰ 　　if（t满足充要条件的子条件2（n,k,d,D,R））

⑱ 　　　result.isPass$\leftarrow$true；

⑲ 　　　result.value=〈E,t〉；

⑳ 　　　break；

㉑ 　　end if

㉒ 　　if（result.isPass==false）

㉓ 　　　将〈vector,false〉加入新训练集；

㉔ 　　end if

㉕ 　　更新误分率；

㉖ 　end for

㉗ end if

㉘ if（p₁==false）

㉙ 　 p$\leftarrow$0~1间的随机数；

㉚ 　if（p小于误分率）

㉛ 　　T$\leftarrow$枚举纠删码Tanner图（E）；

㉜ 　　for（每一个T中的纠删码Tanner图t）

㉝ 　　　if（t满足充要条件的子条件2（n,k,　　　　　　　d,D,ND））

㉞ 　　　　　result.isPass$\leftarrow$true；

㉟ 　　　　　result.value=〈E,t〉；

㊱ 　　　　　将〈vector,true〉加入新训练集；

㊲ 　　　　　break

㊳ 　　　　end if

㊴ 　　end for

㊵ 　　更新误分率；

㊶ 　end if

㊷ end if

㊸ if（p₁==true且p₂==false）

㊹ 　将〈vector,false〉加入新训练集

㊺ end if

㊻ if（新训练集大小大于阈值）

㊼ 　使用新训练集更新分类器（svm）；

㊽ end if

㊾ return result.

1）初始训练集获取

EVA按4步获取用于构造初始SVM分类器的训练集：

① 随机抽取部分编码参数下的部分纠删码修复组分布方案 （不妨设纠删码修复组分布方案的集合为TE）；

② 将TE中的纠删码修复组分布方案及其对应的编码参数转换为定长特征向量；

③ 对于TE中的任意一个纠删码修复组分布方案E，枚举其对应的纠删码Tanner图，并使用纠删码Tanner图匹配于指定编码参数 （n,k,d,D） 的充要条件来检验这些纠删码Tanner图是否存在1个匹配 （n,k,d,D） ，从而判断E是否匹配于 （n,k,d,D），即得到E对应定长特征向量的类别标签；

④ 将所有打上类别标签的特征向量组合为SVM分类器的初始训练集 （算法1的行①~⑧），由于当云数据中心数N固定时，所有纠删码修复组分布方案的特征向量长度相同，所以同一套部署环境下只需要准备一份初始训练集.

2）分类器增量更新

SVM的分类器的本质是一个能将高维空间一分为二的决策超平面，而其分类特征向量的本质则是判断被投射到高位空间后的特征向量位于决策超平面的哪一侧. 在SVM中，能够对决策超平面（分类器）的构造造成影响的特征向量为有效特征向量. 当初始训练集中的有效特征向量的数目有限时，首次训练出的分类器很难反映真实的数据分布情况，使得其无法对特征向量进行准确分类. 针对这个问题，基于SVM的EVA将在训练分类器时筛选出训练集中的有效特征向量，并在分类的同时持续收集新的已知确切类别的特征向量. 然后，EVA将挑选部分新收集的特征向量与旧训练集中的有效特征向量组成新的训练集，并使用新的训练集训练出一个新的分类器 （算法1的行 ㊻ ~㊽）. 因为新的训练集同时包含新收集的特征向量中的有效特征向量和旧训练集中有效特征向量，所以新的分类器的分类准确性更高.

增量学习的关键是如何从旧训练集中挑选出有效特征向量以及如何获取新的有效特征向量：

① 旧的训练集的有效特征向量. EVA会在训练分类器的同时获取一组支持向量，这些支持向量决定了决策超平面. 也就是说，这些支持向量即为旧训练集中的有效特征向量. 因此，EVA直接将这些支持向量加入到新的训练集中.

② 新收集的特征向量中的有效特征向量. 如果分类器对一个特征向量进行了误分类，那么意味着现有的分类器 （决策超平面） 缺少该特征向量的信息. 因此，如果将该特征向量加入到新的训练集中，新的决策超平面将与旧的决策超平面有所不同. 所以，新收集的特征向量中被旧分类器错误分类的部分即为有效特征向量. 因此，EVA将这些支持向量加入到新的训练集中.

具体而言，EVA搜集新的有效特征向量以及检验纠删码修复组分布方案的具体过程如图5所示.

图  5  纠删码修复组分布方案检验过程

Figure  5.  Verification process of erasure code repair group distribution scheme

下载: 全尺寸图片 幻灯片

首先，EVA分别用纠删码修复组分布方案匹配于指定编码参数的必要条件和分类器来检验输入的纠删码修复组分布方案.

如果分类器和纠删码修复组分布方案匹配于指定编码参数的必要条件的检验结果均为某个纠删码修复组分布方案E 匹配于编码参数 （n,k,d,D），EVA则使用纠删码Tanner图匹配于指定编码参数的充要条件来检验E的纠删码Tanner图. 如果存在一个E的纠删码Tanner图匹配于编码参数 （n,k,d,D），则可确定E匹配于编码参数 （n,k,d,D）. 反之，如果不存在任何一个E的纠删码Tanner图匹配于编码参数 （n,k,d,D），则可确定E不匹配于编码参数 （n,k,d,D） 且分类器对E对应的的特征向量进行了错误分类，此时E对应的特征向量将被加入新的训练集 （算法1的行⑭~㉗）.

如果分类器的分类结果是某个纠删码修复组分布方案 E 不匹配于编码参数 （n,k,d,D），EVA将在较小的概率P_o下使用纠删码Tanner图匹配于指定编码参数的充要条件对E进行检验 （以检验分类器的分类结果）——因为分类器误分类频率越小，检验它的分类结果的必要性越小，所以P_o始终等于分类器的当前误分率. 如果存在一个E的纠删码Tanner图符合其匹配于指定编码参数的充要条件，可以确定E匹配于编码参数 （n,k,d,D） 且分类器对E进行了错误分类，此时E对应的特征向量将被加入新的训练集. 如果EVA没有使用纠删码Tanner图匹配于指定编码参数的充要条件对E进行检验或者不存在一个对应于E的纠删码Tanner图符合其匹配于指定编码参数的充要条件，那么EVA将E视为不通过检验的纠删码修复组分布方案 （算法1的行㉘~㊷）.

如果分类器的分类结果是某个纠删码修复组分布方案 E 匹配于编码参数 （n,k,d,D） 但E不符合其匹配于指定编码参数的必要条件，那么可以确定E不匹配于编码参数 （n,k,d,D） 且分类器对其进行了误分类，此时E对应的特征向量将被加入新的训练集 （算法1的行㊸~㊺）.

3.3   近似最优纠删码修复组分布方案搜索算法

3.2节提出EVA可快速检验纠删码修复组分布方案是否匹配于指定编码参数 （n,k,d,D）. DSAOE可从所有能通过EVA检验的纠删码修复组分布方案中挑选出具有最小平均跨云数据中心修复流量的一个纠删码修复组分布方案.

根据定义6，当云数据中心数目N、编码参数n以及条带分布方案确定时，相应的所有纠删码修复组分布方案均可被枚举出来. 此外，每个纠删码修复组分布方案对应一个平均跨云数据中心修复流量.

因此，DSAOE的主要思想是：当云数据中心数N, 编码块数n和编码块分布方案被指定后，枚举出所有与它们相对应的纠删码修复组分布方案，并将这些纠删码修复组分布方案按它们对应的平均跨云数据中心修复流量递增的顺序排序. 然后，对纠删码修复组分布方案进行分组并采用多个计算节点对各组纠删码修复组分布方案进行并行检验——各个计算节点使用EVA对其进行检验. 各个计算节点中第一个通过EVA检验的纠删码修复组分布方案即为局部最小跨云数据中心修复流量纠删码修复组分布方案. 各个计算节点的局部最小跨云数据中心修复流量纠删码修复组分布方案中具有最小平均跨云数据中心修复流量的一个纠删码修复组分布方案即为DSAOE的输出.

DSAOE使用1个协调者节点和多个工作节点来并行完成最优纠删码修复组分布方案的搜索，其具体分工为：

1）协调者节点

协调者节点的工作流程如算法2所示.

算法2. DSAOE的协调节点的工作流程.

输入：编码参数 （n,k,d,D），云数据中心总数N，编码块分布方案R，Worker总数W；

输出：全局最优解GO （包括近似最小跨云数据中心修复流量修复组分布方案及其对应的最优纠删码Tanner图和平均跨云数据中心修复流量）.

① 已完成工作的Worker数$\leftarrow$0；

② ES$\leftarrow$枚举纠删码修复组分布方案（n,k,d,D,R）；

③ subSets$\leftarrow$对纠删码修复组分布方案随机分组 （ES,W）；

④ 将subSets中的各个组分别分发到各个Worker；

⑤ while true do

⑥ 　 if 接收到局部最优解LO

⑦ 　　GO$\leftarrow$LO；

⑧ 　　将GO分发到各个Worker；

⑨ 　　完成工作的Worker数$\leftarrow$完成工作的 Worker数+1；

⑩ 　end if

⑪ 　if 完成工作的Worker数==Worker总数

⑫ 　　break；

⑬ 　end if

⑭ end while

⑮ return GO.

当协调者节点接收到编码参数 （n,k,d,D）、云数据中心总数 N 以及条带的编码块分布方案 R 后，协调者节点将枚举所有可能的纠删码修复组分布方案并计算出这些纠删码修复组分布方案的平均跨云数据中心修复流量 （算法2的行②）——根据定义6，纠删码的修复组分布方案E的平均跨云数据中心流量为m$\displaystyle\sum_{{C}\in E}\left(\left|{C}\right|-1\right)/{n}$，（C为E中的编码块修复组分布方案、n为一个编码条带中的编码块数），所以协调者节点计算纠删码修复组分布方案的平均跨云数据中心修复流量的开销较低.

然后，协调者节点将这些纠删码修复组分布方案随机分成若干子集并分发到若干工作节点进行检验 （算法2的行③④）. 工作节点检验这些子集时，协调者节点负责维护临时全局近似最小跨云数据中心修复流量纠删码修复组分布方案及其对应的临时全局近似最小平均跨云数据中心修复流量 （算法2的行⑤~⑮）.

2）工作节点

工作节点的工作流程如算法3所示.

算法3. DSAOE的工作节点的工作流程.

输入：编码参数 （n,k,d,D），编码块分布方案R，纠删码修复组分布方案组subSet，云数据中心数N，分类器svm；

① subSet$\leftarrow$将subSet按平均跨云数据中心修复流 量的升序排序；

② for 每一个i,1$\le$i$\le$subSet中的纠删码修复组分 布方案数

③ 　if 接收到了新的GO

④ 　　GO$\leftarrow$新的GO；

⑤ 　end if

⑥ 　if subSet[i]的平均跨云数据中心修复流量 小于GO的平均跨云数据中心修复流量

⑦ 　　result$\leftarrow$EVA（n,k,d,D,R,subSet[i],N,svm）；

⑧ 　　if result.isPass==true

⑨ 　　LO的平均跨云数据中心修复流量$\leftarrow$subSet[i] 的平均跨云数据中心修复流量；

⑩　　 LO的纠删码修复组分布方案$\leftarrow$ subSet[i]；

⑪　　 LO的纠删码Tanner图$\leftarrow$ result.value.get Tanner（）；

⑫ 　　将LO传送到协调者；

⑬ 　　结束程序；

⑭ 　　end if

⑮ 　end if

⑯ end for

在接收到协调者节点发来的纠删码修复组分布方案的集合后，各个工作节点首先将这些纠删码修复组分布方案按平均跨云数据中心修复流量递增的顺序进行排列 （算法3的行①）.然后，工作节点依次读取这些纠删码修复组分布方案. 如果一个纠删码修复组分布方案的平均跨云数据中心修复流量小于临时全局近似最小平均跨云数据中心修复流量，那么工作节点将使用EVA对其进行检验. 第1个通过EVA的检验的即为局部最低跨云数据中心修复流量纠删码修复组分布方案，其对应的平均跨云数据中心修复流量即为局部近似最小平均跨云数据中心修复流量. 一旦一个工作节点得到了局部最低跨云数据中心修复流量纠删码修复组分布方案和局部近似最小平均跨云数据中心修复流量，它便立即停止后续纠删码修复组分布方案的检验，并分别用它的局部最低跨云数据中心修复流量纠删码修复组分布方案和局部近似最小平均跨云数据中心修复流量来更新协调者节点中的临时全局最低跨云数据中心修复流量纠删码修复组分布方案和临时全局近似最小平均跨云数据中心修复流量 （算法3的行②~⑭）.

当所有的工作者节点均停止检验纠删码修复组分布方案时，协调者节点中的临时全局近似最小跨云数据中心修复流量纠删码修复组分布方案和临时全局近似最小平均跨云数据中心修复流量即为 DSAOE得到的近似最小跨云数据中心修复流量纠删码修复组分布方案和平均跨云数据中心修复流量近似下限.

由于在EVA的分类器将一个纠删码修复组分布方案分为正类后，EVA还会使用纠删码Tanner图匹配于指定编码参数的充要条件对其进行检验，因此DSAOE得到的全局最优纠删码修复组分布方案一定匹配于编码参数 （n,k,d,D）.

如果EVA的误报率为0，DAOSE可获得所有通过EVA检验的纠删码修复组分布方案中平均跨数据中心修复流量最小的一个. 根据定理5，该纠删码修复组分布方案能达到相应编码参数下的平均跨数据中心修复流量下限，即该纠删码修复组分布方案为最优纠删码修复组分布方案. 若EVA的误报率P>0，且一共存在Q个最优纠删码修复组分布方案，那么DAOSE错过所有最优纠删码修复组分布方案的概率不超过${{P}}^{{Q}}$. 因此，FMEL 可以得到最优码的概率不低于${1}-{{P}}^{{Q}}$.

此外，因为DSAOE使用EVA来对大多数纠删码修复组分布方案进行快速检验，所以其效率较高.另外，DSAOE的并行度高的特点可进一步保证其搜索效率.

3.4   基于试错的纠删码修复组分布方案转换算法

3.3节提出了DSAOE能搜索到近似最小跨云数据中心修复流量纠删码修复组分布方案. 本节提出了一种基于试错的纠删码修复组分布方案转换算法EST，用于将近似最小跨云数据中心修复流量纠删码修复组分布方案转换为相应的纠删码生成矩阵.

EST的工作流程如算法4所示.

算法4. EST算法.

输入：全局最优解GO （包括近似最小跨云数据中心修复流量纠删码修复组分布方案及其对应的最优纠删码Tanner图和平均跨数据中心修复流量）；

输出：近似最小跨云数据中心修复流量纠删码的生成矩阵G.

① OT$\leftarrow$GO.Tanner；

② H$\leftarrow$构造准柯西矩阵OT；

③ SM$\leftarrow$获得子矩阵集合SM₁和SM₂的集合{OT,H}；

④ ST$\leftarrow$获得子图（SM,OT）；

⑤ H₁$\leftarrow$获得子矩阵H₁（OT,H）；

⑥ 将H₁添加到集合LS中；

⑦ for 每一个i, 1$\le$i$\le$ST中子图数

⑧ 　maxM$\leftarrow$获得ST_i的最大匹配；

⑨ 　Z$\leftarrow$获得对应于最大匹配的子矩阵（SM_i,ST_i）；

⑩ 　将Z添加到集合LS中；

⑪ end for

⑫ NE$\leftarrow$获得对角元素（转换为上三角矩阵（LS））；

⑬ for（每一个i, 1$\le$i$\le NE$中的元素数）

⑭ 　if NE[i]的值==0

⑮ 　　更新H和LS；

⑯ 　　跳转到行⑩；

⑰ 　end if

⑱ end for

⑲ G$\leftarrow$获取H对应的生成矩阵；

⑳ return G.

1）对于指定的纠删码修复组分布方案，DSAOE只有在找到一个与其相对应的匹配于编码参数 （n,k,d,D） 的纠删码Tanner图时才会确认该纠删码修复组分布方案匹配于编码参数 （n,k,d,D）. 因此，DSAOE在搜索近似最小跨云数据中心修复流量纠删码修复组分布方案的同时也得到了与之相对应的近似最小跨云数据中心修复流量纠删码Tanner图 $\mathcal{T}$，如算法4的行①所示.

2）令U为如式 （10） 所示的柯西矩阵，基于试错的纠删码修复组分布方案转换算法EST 将构造一个对应于$\mathcal{T}$的校验矩阵H：如果$\mathcal{T}$的第j个校验端点覆盖其第i个变量端点，那么H的第j行i列$\left({{h}}_{{ji}}\right)$的值等于U的第j行i列$\left({{u}}_{{ji}}\right)$的值. 如果$\mathcal{T}$的第j个校验端点不覆盖其第i个变量端点，那么${h}_{ji}$的值为0 ，如算法4的行②所示.

3）EST获取H的所有包含n−k行d−1列的子矩阵的集合SM₁以及H的所有包含其对应于任意D个云数据中心的列的子矩阵的集合SM₂. 根据定义7，SM₁和SM₂中的任意矩阵均对应于一个$\mathcal{T}$的子图，如算法4的行③④所示.

4）EST获取$\mathcal{T}$的最大匹配. 因为$\mathcal{T}$符合其匹配于指定编码参数的充要条件的子条件3，其最大匹配中包含n−k个变量端点，不妨设$\mathcal{T}$的最大匹配包含$V{N}_{{z}_{1}}, V{N}_{{z}_{2}},…,V{N}_{{z}_{n-k}}$. 随后，EST求得由H的第${{l}}_{{1}}{,}{{l}}_{{2}}{,…,}{{l}}_{{n}-{k}}$列组成的子矩阵${\boldsymbol{H}}_{1}$. 显然，${\boldsymbol{H}}_{1}$是一个方阵 （n−k行、n−k列）. 同时，EST将${\boldsymbol{H}}_{1}$加入到集合LS中，如算法4的行⑤⑥所示.

5）基于试错的纠删码修复组分布方案转换算法EST获取对应于SM₁和SM₂中各个矩阵$\mathcal{T}$的各个子图的最大匹配. 对于SM₁和SM₂中的各个矩阵Z，如果它对应$\mathcal{T}$的子图的最大匹配中包含的所有校验端点为${C}{{N}}_{{{l}}_{{1}}}{,}{C}{{N}}_{{{l}}_{{2}}}{,…,}{C}{{N}}_{{{l}}_{{a}}}$，则将Z的第${{l}}_{{1}}{,}{{l}}_{{2}}{,…,}{{l}}_{{a}}$行组成的子矩阵添加到集合LS中. 根据定理3中的纠删码Tanner图匹配于指定编码参数的充要条件的充分性证明的步骤③，LS中的矩阵均为方阵，如算法4的行⑦~⑩所示.

6）EST通过初等行变换将LS中的各个矩阵转换为如式 （11） 所示的上三角矩阵（转换过程见定理3中的纠删码Tanner图匹配于指定编码参数的充要条件的充分性证明的步骤④），并获得这些上三角矩阵的对角元素的集合${NE}{=\big\{}{{h}}_{{{l}}_{{t}{,}{a}}{{s}}_{{t}{,}{a}}}-{{A}}_{{{l}}_{{t}{,}{a}}{{s}}_{{t}{,}{a}}}{|} {t}{\in}{[1,|} {LS}{|];}{a}{\in} \{{1,}{2,}{…,}{{b}}_{{t}}{\}\big\}}$,其中，${A}_{{z}_{t,a}{s}_{t,a}}$为不包含${{h}}_{{{l}}_{{t}{,}{a}}{{s}}_{{t}{,}{a}}}$的线性多项式，如算法4的行⑫所示.

7）EST考察NE中的各个对角元素是否为0. 如果NE中某个元素的值为0 （不妨设${{h}}_{{{l}}_{{o,}{q}}{{s}}_{{o,}{q}}}-{{A}}_{{{l}}_{{o,}{q}}{{s}}_{{o}{,}{q}}}$=0） ，则进行操作：对${{h}}_{{{l}}_{{o,}{q}}{{s}}_{{o,}{q}}}$进行加1操作；更新H，LS；重新构造上三角矩阵并更新集合NE；重新考察NE中各个元素的值. 直到NE中的各个元素的值均不为0，如算法4的行⑬~⑱所示，根据定理3中的纠删码Tanner图匹配于指定编码参数的充要条件的证明过程，此时LS中的矩阵均满秩. 其中，LS中的H₁满秩意味着H满秩. 此外，由定理2可知，LS中的其他矩阵满秩意味着此时的H对应的纠删码C_O能够容忍任意d−1个编码块失效或任意D个云数据中心失效 （即H为一个匹配于 （n,k,d,D） 的校验矩阵）. 事实上，在我们的多次实验中，初始NE中的各个元素的值全不为0. 也就是说，在大多数情况下，不需要对NE、LS和H进行更新即可一次性得到最终的校验矩阵H.

8）EST对H执行初等行变换以得到矩$H'= {{\boldsymbol{H}}}{{\boldsymbol{\varDelta}}}^{-{1}}{=} \left[{{{\boldsymbol{I}}}}_{{(}{n}-{k}{)\times(}{n}-{k}{)}}{,}{{{\boldsymbol{P}}}}_{{(}{n}-{k}{)\times}{k}}\right]$（H${'}{{\boldsymbol{\varDelta}}}{=}{{\boldsymbol{H}}})$. 然后，EST构造${{\boldsymbol{G}}}{'}{=} {[}{-{(}{{{\boldsymbol{P}}}}^{{{\rm{T}}}}{)}}_{{k \times}{(}{n}-{k}{)}}{,} {{{\boldsymbol{I}}}}_{{k}{\times k}}{]}$和${{\boldsymbol{G}}}{=}{{\boldsymbol{G}}}{'}{\cdot}{\left({{{\boldsymbol{\varDelta}}}}^{{{\rm{T}}}}\right)}^{-{1}}$. 显然，${{\boldsymbol{G}}}{'}{{(}{{\boldsymbol{H}}}{'}{)}}^{{{\rm{T}}}}{=}{{\bf{0}}}$. 因此${{\boldsymbol{G}}}{{{\boldsymbol{H}}}}^{{{\rm{T}}}}{=}{{\boldsymbol{G}}}{'}{\cdot}{{(}{{\boldsymbol{\varDelta}}}^{\rm{T}}{)}}^{-1} {{{\boldsymbol{\varDelta}}}}^{{{\rm{T}}}}{{(}{{\boldsymbol{H}}}{'}{)}}^{{{\rm{T}}}}{=}{{\boldsymbol{G}}}{'}{{{\boldsymbol{I}}}}_{{n}{\times}{n}}{{(}{{\boldsymbol{H}}}{'}{)}}^{{{\rm{T}}}}{=}{\bf 0}$. 因此，G为对应于H的生成矩阵，即对应于近似最小跨云数据中心修复流量纠删码修复组分布方案的生成矩阵，如算法4的行⑲所示.

3.5   FMEL方法描述

低跨云数据中心修复流量的纠删码的快速构造方法FMEL的工作流程如算法5所示.

算法5. 算法FMEL.

输入：编码参数 （n,k,d,D），云数据中心总数N，编码块分布方案R，Worker总数W，云数据中心数N；

输出：G.

① 全局最优解GO$\leftarrow$DSAOE （n,k,d,D,N,R,W, N）；

② G$\leftarrow$EST （GO）；

③ return G.

首先，FMEL通过DSAOE从所有能通过基于SVM的EVA的检验的纠删码修复组分布方案中选出具有较小平均跨云数据中心修复流量的一个纠删码修复组分布方案，如算法5的行①所示. 挑选出的纠删码修复组分布方案即为近似最小跨云数据中心修复流量纠删码修复组分布方案. 然后，FMEL通过EST将近似最小跨云数据中心修复流量纠删码修复组分布方案转换为相应编码参数下的近似最小跨云数据中心修复流量纠删码生成矩阵G，如算法5的行②所示.

4.   实验与结果

4.1   方法实现

为了评估FMEL构造出的近似最小跨云数据中心修复流量纠删码的实际性能，我们基于OpenEC^[33]和FastDFS^[34]实现了FMEL构造出的纠删码. 其中，OpenEC是一种用于在已有的分布式文件系统中实现不同的纠删码编码方法和修复方法的可定制框架，FastDFS是一种轻量级的文件系统.

具体而言，我们首先在原始的FastDFS上增加了对OpenEC的支持. 然后，我们在OpenEC上实现了FMEL，用于构造近似最小跨云数据中心修复流量纠删码生成矩阵. 最后，基于OpenEC的编码方法和修复方法定制功能，实现了近似最小跨云数据中心修复流量纠删码的数据编码方法和数据修复方法.

4.2   实验环境与参数

实验部署于UCloud^[35]的6个云数据中心，其中2个位于北京 （记为PEK1和PEK2）、1个位于上海 （记为SHA）、1个位于洛杉矶 （记为LOS）、1个位于台北 （记为TPE）、1个位于广州 （记为CAN）. 实验使用了每个云数据中心的10个存储节点 （云主机），每个节点配备4核Intel Cascadelake 6248R 3.0 GHz 处理器，8 GB 内存和1 TB磁盘，外网最大带宽为800 Mbps，内网最大带宽为25 Gbps.

为了评估FMEL构造出的近似最小跨云数据中心修复流量纠删码的性能，我们将其与典型的纠删码进行了比较：最优码构造方法ACIoT构造出的最优码 （因为原始的ACIoT只能构造出指定编码参数 （n,k,d） 下的最优码，我们对其进行了扩展，使其能够构造出指定编码参数 （n,k,d,D） 下的最优码）、一种能够达到平均局部性下限的纠删码ACL码^[23]、经典的RS码^[36]、一种典型的局部性码Xorbas码^[22]和一种典型的跨云数据中心纠删码DFC码^[13].

为了评估FMEL构造出的近似最小跨云数据中心修复流量纠删码在不同环境中的性能，我们将UCloud的6个云数据中心分为了2个实验环境. 由于大多数的跨云数据中心存储系统均是部署在3个云数据中心^[1,14]，所以我们的每个实验环境均包含3个云数据中心. 具体而言，实验环境1包含PEK1, PEK2, SHA，实验环境2包含LOS, TPE, CAN. 由于各个实验环境包含3个云数据中心，因而容灾度D的合理取值范围为[1,2]，所以实验中D$\in$[1,2]. 此外，在实际应用中，为了便于条带管理，单个条带内的编码块数n通常较小. 因此，我们在实验中将n的范围限制在$\left[{6,11}\right]$ （常见的生产系统中的n均处于该范围内^[37-39]）. 另外，实验中单个条带内的数据块数${k}$的取值范围为$\left[{n}{/}{3,2}{n}{/}{3}\right]$，因为当k属于此范围时D的取值范围为[1,2]. 最后，容错度${d}$的取值范围为${[}{2,}{n}-{k}{+1}{]}$，即d的合理取值范围^[1,12-18].

在本文实验中，各个编码条带的编码块被平均分配到各个云数据中心中，以获取较高的容灾度和负载均衡性. 此外，新生节点与其相应的失效编码块位于同一云数据中心，以保持系统的容灾度和负载均衡性. 实验中的编码块大小和HDFS一致^[35]，为128 MB.

4.3   评价指标

我们用4个指标来评价FMEL的性能：

1）分类器误报率（false-negative rate, FN）.假设被FMEL中的SVM分类器误分类为负类 （不满足编参数 （n,k,d,D） 的类） 的纠删码修复组分布方案的数目为f₁，EVA检验过的纠删码修复组分布方案中匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案数为f₂，那么分类器误报率为f₁/f₂.

2）纠删码构建时间（construction time, CT）.纠删码构造时间是指ACIoT构造最优码的时间或FMEL构造近似最小跨云数据中心修复流量纠删码的时间.

3）平均跨云数据中心修复流量${\overline T}$.令某纠删码修复它的一个条带中的n个编码块产生的跨云数据中心修复流量分别为${{T}}_{{1}}{,}{{T}}_{{2}}{,…,}{{T}}_{{n}}$且每个编码块的大小为m，那么该纠删码的平均跨云数据中心修复流量$\overline{T}$=${\displaystyle\sum_{i}} {{T}}_{{i}}{/}{m}{n}$.

4）平均修复用时$\overline t$.令某纠删码在实验环境1中修复它的一个条带中的n个编码块所消耗的时间分别为${{t}}_{{1,1}}{,}{{t}}_{{1,}{2}}{,…,}{{t}}_{{1,}{n}}$，在实验环境2中修复它的一个条带中的n个编码块所消耗的时间分别为${{t}}_{{2,1}}{,} {{t}}_{{2,}{2}}{,}{…,}{{t}}_{{2,}{n}}$,每个编码块的大小为m. 因为${{t}}_{{j}{,}{i}}$受到云数据中心的排列顺序的影响，令${{{\overline t}}_{{j}{,}{i}}}$为${t}_{j,i}$在不同云数据中心的排列顺序下的平均值. 那么，该纠删码的平均修复用时$\overline{{t}}$=$\left({{\displaystyle\sum_{i} }}{{\overline{t}}_{{1,}{i}}}+{{\displaystyle\sum_{i} }}{{\overline{t}}_{{2,}{i}}}\right){/}{m}{n}$.

4.4   分类器误报率

在FMEL中，SVM分类器将一个纠删码修复组分布方案分为正类后，还会使用纠删码Tanner图匹配于指定编码参数的充要条件对其进行检验，因此FMEL不会将不匹配于编码参数 （n,k,d,D） 纠删码修复组分布方案错误分为正类. 此外，如果SVM分类器将一个匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案错误分为负类，FMEL可能会错过具有较小平均跨云数据中心修复流量且匹配于编码参数 （n,k,d,D） 的纠删码修复组分布方案. 因此，我们主要关注分类器将纠删码修复组分布方案错误分为负类的概率，即误报率.

我们的测试数据包括所有编码参数下的所有纠删码修复组分布方案. 在分类器初始化时，首先在各组编码参数下随机挑选了50个纠删码修复组分布方案并将这些纠删码修复组分布方案转换为对应的特征向量. 然后，使用纠删码修复组分布方案匹配于编码参数 （n,k,d,D） 的充要条件判断这些纠删码修复组分布方案是否满足各自的编码参数，并以此为依据为对应的特征向量打上标签. 因此，我们可以得到这些纠删码修复组分布方案对应的带标签的特征向量，它们组成了分类器的初始训练集（10次实验的平均初始训练集构造用时为1711 s、平均初始分类器构造用时为192 s）. 然后，我们按编码参数n递增的顺序将其他的纠删码修复组分布方案输入到分类器中进行分类. 与此同时，FMEL不断搜集新的训练集对分类器进行增量更新.

分类器分类每组 （n,k） 对应的所有纠删码修复组分布方案的误报率如图6所示. 因为在分类过程中含有效信息的特征向量被逐渐加入到新的训练集中，并不断更新分类器，因此分类器的误报率随着n的增加而逐渐降低.

图  6  SVM分类器的误报率

Figure  6.  False-negative rate of SVM’s classifier

下载: 全尺寸图片 幻灯片

因为同一组编码参数下的最优码往往存在多个，所以最优纠删码修复组分布方案也往往存在多个. 假设一共存在Q个最优纠删码修复组分布方案且分类器的误报率为P，那么FMEL错过所有最优纠删码修复组分布方案的概率不超过${{P}}^{{Q}}$. 因此，FMEL 可以得到最优码的概率不低于${1}-{{P}}^{{Q}}$. 由图6可知，P总是小于27%的. 所以，如果Q>1， FMEL有92.7%的概率得到最优码；如果Q>2， FMEL则有98%的概率得到最优码.

4.5   纠删码构造时间

每组 （n,k） 对应多组 （n,k,d,D），FMEL和ACIoT在每组 （n,k） 对应的所有 （n,k,d,D） 下的纠删码构造时间如图7所示 （FMEL的工作节点数和ACIoT的工作进程数均为5）. 在构造最优码或近似最小跨云数据中心修复流量纠删码时，ACIoT和FMEL均需要枚举和检验部分纠删码修复组分布方案的纠删码Tanner图. 由于编码参数 （n,k,d,D） 下的纠删码Tanner图的总数为${{2}}^{{n}\left({n}-{k}\right)}$，所以，通常而言，${n}{(}{n}-{k}{)}$越大，ACIoT和FMEL需要检验的纠删码Tanner图越多. 因此，ACIoT和FMEL的纠删码构造时间均呈现出随着${n}{(}{n}-{k}{)}$的减少而减少的趋势.

图  7  ACIoT和FMEL的纠删码构造时间

Figure  7.  Erasure code construction time of ACIoT and FMEL

下载: 全尺寸图片 幻灯片

对于大部分的纠删码修复组分布方案，FMEL仅需要用SVM分类器对它们分类即可，无需枚举和检验它们对应的纠删码Tanner图. 因此，FMEL的平均纠删码构造时间仅为ACIoT的11%. 特别地，当${n}{(}{n}-{k}{)}$较小时，总的纠删码构造时间较短. 所以，此时FMEL中更新分类器的时间占总的纠删码构造时间的比例较大. 因此，此时FMEL的纠删码构造时间比ACIoT略长.

4.6   平均跨云数据中心修复流量

因为不同的纠删码适应的编码参数不同，我们首先在除RS码外的所有纠删码都适应的编码参数下比较了各个纠删码的平均跨云数据中心修复流量 （RS码使用和其他纠删码相近的编码参数），如图8所示. 在这些编码参数下，DFC码和ACIoT均可为每个云数据中心分配一个局部校验块， 因此，DFC和ACIoT均能够在不跨云数据中心传输数据的情况下完成编码块的修复，因而它们的平均跨云数据中心修复流量为0. 大多数情况下，FMEL的平均跨云数据中心修复流量也为0，即FMEL有较大概率得到最优码.

图  8  ACL码、Xorbas码、DFC码、RS码、ACIoT和FMEL的平均跨云数据中心修复流量

Figure  8.  Average cross-cloud data center repair traffic of ACL, Xorbas, DFC, RS, ACIoT and FMEL

下载: 全尺寸图片 幻灯片

因为RS码在修复任意一个编码块时均需要读取k个编码块，而在实验中使用的全部编码参数下各编码条带在同一个云数据中心的编码块数始终小于k （如果要使各编码条带在同一个云数据中心的编码块数始终不小于k，那么冗余度将十分大），所以RS码在修复任意一个编码块时均需要跨云数据中心传输数据. 因此，RS码跨云数据中心修复流量最大.

因为Xorbas码和ACL码具有较低的修复流量（其中ACL码能够达到平均修复流量的下限），所以它们能在一定程度上降低平均跨云数据中心修复流量，进而使得它们的平均跨云数据中心修复流量相较于局部性为k−1的RS码更小. 但是，由于修复流量不与跨云数据中心修复流量严格正相关，所以ACL码和Xorbas码的平均跨云数据中心修复流量大于ACIoT, FMEL, DFC码.

因为RS码和DFC码对编码参数的限制较为严格，我们在更多的编码参数下比较了其他纠删码. 如图9所示，在这些编码参数下，FMEL的平均跨云数据中心修复流量比ACL码和Xorbas码分别低了24.0%和34.8%，这是因为FMEL能在这些参数下达到平均跨云数据中心修复流量的近似下限.

图  9  ACL码、Xorbas码、ACIoT和FMEL的平均跨云数据中心修复流量

Figure  9.  Average cross-cloud data center repair traffic of ACL, Xorbas, ACIoT and FMEL

下载: 全尺寸图片 幻灯片

平均而言，FMEL的平均跨云数据中心修复流量比ACL码、Xorbas码和RS码分别低了42.9%, 51.1%, 56.0%. 此外，FMEL的平均跨云数据中心修复流量与DFC码相近，但DFC码对编码参数限制严格.

另外，FMEL的平均跨云数据中心修复流量是ACIoT的100%~133%，并且在实验采用的15组编码参数中的13组编码参数下，FMEL的平均跨云数据中心修复流量与ACIoT相同，即FMEL构造出最优码的概率较高.

容错度d和FMEL构造的近似最小跨云数据中心修复流量纠删码的平均跨云数据中心修复流量$\overline L$之间的关系如图10所示，当d小于一个特定值 d'后，近似最小跨云数据中心修复流量纠删码的平均跨云数据中心修复流量$\overline L$,即平均跨云数据中心修复流程近似下限. 这是因为当d<d'时，$\overline L$的主要影响因素为容灾度D. 基于这一发现，不仅能够得到编码参数 （n,k,D） 下的平均跨云数据中心修复流量的近似下限，还可以得到满足该近似下限时的d的上限，即图中的最优d.

图  10  不同n, k, D下d与平均跨云数据中心修复流量近似下限的关系

Figure  10.  Relationship between d and average cross-cloud data center repair traffic’s approximate lower bound under different n, k, D

下载: 全尺寸图片 幻灯片

因为与最优d相对应的编码参数和近似最小跨云数据中心修复流量纠删码能够在冗余度($\overline T$)、容错度(d)、容灾度(D)和平均跨云数据中心修复流量($\overline L$)之间取得较好权衡，因此关于最优d的这一发现对于实际应用具有指导意义. 比如说，基于这一发现，我们找到了2个能够在冗余度、容错度、容灾度和平均跨数据修复流量之间取得较好权衡的纠删码——FMEL （n=6, k=2） 和FMEL （n=9, k=5，其生成矩阵如式 （12） 和式 （13） 所示.

如表2所示，FMEL （n=6, k=2） 的d值比3副本技术高66.7%，同时，FMEL （n=6, k=2） 的D、$\overline T$和$\overline L$和3副本技术相同. 此外，FMEL （n=9, k=5） 的D比2副本技术高33.3%，同时FMEL （n=9, k=5） 的$\overline T$和$\overline L$比2副本技术低10%和33%且二者D相同.

表  2  FMEL与多副本的对比

Table  2.  Comparison Between FMEL and Replications

评估指标	FMEL （n=6, k=2）	3副本	FMEL （n=9, k=5）	2副本
$\bar{T}$	1	1	0.67	1
$\bar{t}$ / （ms·MB-1）	86.6	83.2	62.1	82.1
d	5	3	1	1
D	2	2	1	1
n/k	3	3	1.8	2

下载: 导出CSV 

| 显示表格

4.7   平均修复用时

因为不同的纠删码适应的编码参数不同，我们首先在除RS码外的所有纠删码都适应的编码参数下比较了各个纠删码的平均修复用时 （RS码使用和其他纠删码相近的编码参数），如图11所示.

图  11  ACL码、Xorbas码、DFC码、RS码、ACIoT和FMEL的平均修复用时

Figure  11.  Average repair time of ACL, Xorbas, DFC, RS, ACIoT and FMEL

下载: 全尺寸图片 幻灯片

由于FMEL和ACIoT的平均跨云数据中心修复流量小于对照组中的其他纠删码，其修复数据时跨云数据中心传输数据的时间较短，使得其平均修复用时也比其他纠删码少. 具体地，FMEL的平均修复用时比ACL码、Xorbas码和RS码分别少了36.9%, 46.1%, 50.6%. 此外，ACIoT的平均修复用时与FMEL相近，但是ACIoT的纠删码构造时间更长.

因为RS码和DFC码的编码参数适应性较差，我们在更多的编码参数下对除这2种纠删码之外的纠删码进行了对比，如图12所示. 在这些编码参数下，FMEL和ACIoT的平均修复用时少于ACL码和Xorbas码，这是因为基于FMEL和ACIoT的平均跨云数据中心修复流量较小. 特别地，在编码参数为 （8,3,5,1） 时，FMEL和ACIoT的平均修复用时远低于其他纠删码，因为此时只有它们能够在不跨云数据中心传输数据的情况下完成数据修复.

图  12  ACL码、Xorbas码、ACIoT和FMEL的平均修复用时

Figure  12.  Average repair time of ACL, Xorbas, ACIoT and FMEL

下载: 全尺寸图片 幻灯片

此外，如表2所示，因为FMEL （n=9, k=5） 的平均跨云数据中心修复流量低于2副本技术，因此其平均修复用时也短于2副本技术. 特别地，虽然FMEL （n=6, k=2） 的平均跨云数据中心修复流量与3副本技术相同，但其平均修复用时略长于3副本技术，这是因为FMEL （n=6, k=2） 在修复数据时的计算量大于3副本技术.

5.   总　　结

针对现有纠删码构造方法无法兼顾编码参数适应性、跨云数据中心修复流量和纠删码构造效率的问题，本文提出了一种低跨云数据中心修复流量的纠删码的快速构造方法FMEL，可在不同编码参数下快速求得低跨云数据中心修复流量纠删码. 在真实跨云数据中心环境中的实验表明，相较于现有的可构造能达到平均跨云数据中心修复流量下限的最优码的方法，FMEL构造纠删码的时间少了89%，且在大部分编码参数下二者构造的纠删码的平均跨云数据中心修复流量相同. 此外，我们利用FMEL评估了大量编码参数，并挑选出2组编码参数. FMEL在这2组编码参数下构造的纠删码的平均修复流量低于已得到广泛使用的多副本技术，同时其容灾性、容错性和冗余度相较于多副本技术具有明显优势.

作者贡献声明：包涵提出了算法思路和实验方案，并负责完成实验和撰写论文；王意洁提出指导意见并修改论文.