2019, Vol. 40
面对海量信息的存储需求，如何保证数据的可靠性和可用性是分布式存储系统的重要挑战之一[1-2]，而容错是保障数据可靠性的重要手段[3]。常用的容错技术主要有多副本技术[4]和纠删码技术2种[5]，文献[6]指出，对于PB级、EB级、ZB级数据集的存储系统来说，多副本方案的存储开销对硬件成本和运营开支产生巨大压力，而纠删码具有高容错能力和低存储空间开销的优点[7], 已经成为分布式存储的基本容错方案。
现有的纠删码分为传统RS码，阵列码以及分组码。经典的RS码[8]考虑编码效率和容错能力的折中，但存储开销较大。EVENODD码[9]、RDP码[10]、STAR码[11]等基于阵列结构的编码方法则考虑计算复杂度和容错能力之间的折中。分组码的思想是将一个条带内的数据块分组，利用组内的数据块产生局部校验块，就可以降低数据重构时需要下载的数据量。其中微软Azure云存储系统[12]中采用的LRC码[13]就是将条带内的数据块平均分成2个组，每组产生局部校验块并且所有数据块都会再产生全局校验块，这样当组内单块失效可以有效降低数据重构的成本。当组内有多个块失效时，2层分组码仍然需要在全局范围内进行修复。为此，可以对数据块进行更多层次的分组，高层的组包含若干低层较小的组，Pyramid码[14]就是根据这种思想构造的码，随着分组层次的增多，多层分组码的平均重构开销就会降低，但是存储空间开销会增大。SHEC[15]码的思想是使各个分组相互重叠，从而在多个块失效时可以利用较少的组进行局部修复，这样就避免了下载数据量随着失效块数增加而急剧增长的发生。此外还有WEAVER码[16]、GRID码[17]和Hover码[18]等，但不免均有空间利用率不高或是容错能力不理想等方面的不足。
本文基于分组码的思想提出跳跃局部重构码(jump local reconstruction code, JLRC)，保留了LRC码的基本结构，在初始数据块之间跳跃组合计算生成跳跃校验块，加强了校验的互联性，能够提高容错率。因为基于分组码的思想，数据失效在组间就可恢复，降低了重构开销。JLRC保留全局校验，并且跳跃校验块的个数可以动态改变，能够有效提升容错能力。
1 分组码编码算法 1.1 纠删码相关概念目前，对存储系统中纠删码容错技术的相关概念尚无一致的定义。为了便于本文的描述与理解，现将通过文献[19-21]的整理以及本文提出的码的自身结构结合明确相关概念如下：
1) 数据块：初始数据被系统划分而形成的最小编码单位。
2) 校验块：所有块中除数据块以外的部分称为校验块，由初始数据块经过相关计算得到。
3) 全局校验块：全部数据块通过特定的纠删码编码算法计算得出的一块冗余数据。
4) 局部校验块：利用一部分组内数据块，通过特定的分组编码算法计算得出的一块冗余数据。
5) 跳跃校验块：通过隔有不同数量数据块之后取出的初始数据计算而出的一块冗余数据。
6) 条带：多个数据块与其对应的校验块构成的冗余集合。例如一个(n, k, k′)纠删码的条带包含n个编码块。
7) MDS码：如果一个(n, k, k′)-纠删码满足k′=k，则称此纠删码满足MDS性质，也称该纠删码为MDS码。MDS码可以用更简单的二元组(n, k)来表示。MDS码在相同的容错能力下拥有最小的存储空间开销。
8) 数据重构：当一个条带中的一个或多个编码块因节点或磁盘失效等原因而丢失时，利用条带内剩余的编码块重构出丢失的编码块的过程。
9) 存储开销：初始数据块与校验块数量总和。
10) 容错率：当编码块中有n块丢失时，这n块数据可能是数据块、局部校验块和全局校验块的任意组合。容错率就是这些组合中理论上可以被重构的组合数和所有组合数的比值。
11) 容错能力：一个条带理论上可以容忍的最大编码块失效的个数。假设一个纠删码的容错能力为n，则此纠删码能且只能在不多于n个编码块失效的、理论上可修复的情况下，重构出失效块。
12) 重构开销：数据重构时需要从条带中读取的编码块的个数。
1.2 分组码如果将一个条带内的数据块分组，利用组内的数据块产生局部校验块，就可以降低数据修复时需要下载的数据量，以该思想为基础构造的纠删码称为分组码[22]。根据不同的分组方法，分组码可进一步分为层次分组码和交叉分组码2类。
为解决单节点重构效率问题，微软公司在实现他们的云平台Azure时，使用了一种LRC码[15]。该编码通过引入局部校验使得单节点修复需要下载的数据量降低；同时使用全局校验保证系统的容错能力，当发生多个节点同时失效时，系统仍能修复。LRC码可以用一个三元组(k, l, r)表示，k表示初始数据块个数，l表示分组个数，r表示全局校验个数。图 1给出了一个参数为(6, 2, 2)的LRC码的编码示意图。
|
Download:
|
| 图 1 LRC编码示例(k, l, r)=(6, 2, 2) Fig. 1 LRC coding example (k, l, r)=(6, 2, 2) | |
由图 1可以看出，LRC码将6个数据块存放在6个不同的节点上，并且分为2组，每组3个数据块编码产生1个局部校验块，另外还有2个由所有数据块生成的全局校验块。LRC码和RS码一样，编码运算是基于有限域上的。该编码可以容忍任意3个节点同时失效，对于部分4错模式也能恢复，但经计算，容错率只有86%，LRC码是最基本的层次分组码。
最基本的交叉分组码为Miyamae等提出的SHEC(shingled erasure code)码[15]，如图 2所示，展示了一个参数为(10, 6, 5)的交叉分组码，交叉分组码的思想是使各个分组相互重叠，从而在多个块失效时可以利用较少的组进行局部修复。
|
Download:
|
| 图 2 SHEC(10, 6, 5)构造示意 Fig. 2 Code structure diagram of SHEC(10, 6, 5) | |
图 2中的SHEC(10, 6, 5)是将10个数据块分为相互重叠的6个组，每组包含5个数据块，除了第3组和4组，其他任意2组之间重叠3个数据块，每组的校验块均通过组内的5个数据块运算产生，这样，单个块的失效修复只需要下载6或7个块，可见SHEC码避免了下载数据量随着失效块数增加而急剧增长的情况，但是SHEC码中所有冗余校验块均为局部校验，没有保留全局校验，这样就导致了容错能力的下降。
2 JLRC码的编码结构及算法 2.1 JLRC码的编码结构针对分组码各组之间关联性差导致的容错率下降等问题，本文提出了一种JLRC编码。JLRC码中有4个参数(k, m, l, n)，记为JLRC(k, m, l, n)，其中k表示初始数据块的个数，m表示总校验块数，l表示跳跃校验块的个数，n表示全局校验块的个数。该方案设定参数k为偶数，且l+n+2=m。在通常情况下会以k=10或k=12为例来分析编码结构，不失一般性地，下面以k=12的情况来介绍具体的编码思想。如图 3为JLRC(12, 6, 2, 2)的构造示意图。
|
Download:
|
| 图 3 JLRC(12, 6, 2, 2)构造示意 Fig. 3 Code structure diagram of JLRC(12, 6, 2, 2) | |
由图可看出，有d1到d12共12块初始数据块，将这12块初始数据块分为2组，图中黑色部分表示计算过程中运用到的原始数据块，由此得出前6块计算生成一个局部校验p1，后6块计算生成一个局部校验p2，并且利用全部数据块运算产生2个全局校验块q1、q2。另外，从第1个数据块开始，每2块为一组取出其中的第1块，将这6块原始数据进行计算生成跳跃校验块p3，每2块为一组取出其中的第2块，将这6块原始数据进行计算生成跳跃校验块p4。如图 4为JLRC(12, 7, 3, 2)的构造示意图。
|
Download:
|
| 图 4 JLRC(12, 7, 3, 2)构造示意 Fig. 4 Code structure diagram of JLRC(12, 7, 3, 2) | |
如上面的构造图所示，假设初始数据块共有12块，由前6和后6块分别生成2块局部校验，再由全部初始数据块生成2块全局校验，跳跃校验块可能会有2块(每块由6个初始数据块生成)、3块(每块由4个初始数据块生成)、4块(每块由3个初始数据块生成)以及6块(每块由2个初始数据块生成)4种情况，所以动态体现在参数l的变化，即跳跃校验块是如何交叉跳跃生成的。
图 4中的JLRC(12, 7, 3, 2)与JLRC(12, 6, 2, 2)的道理相同，其中有12块原始数据块，将这12块数据块分为2组生成p1和p2，不同之处在于，JLRC(12, 7, 3, 2)中跳跃校验块的计算方法为将12块数据块每3块为一组取出每组的第1块，将这4块进行计算生成跳跃校验p3，同理生成跳跃校验p4和p5。
图 5中的JLRC(12, 8, 4, 2)与图 6中的JLRC(12, 10, 6, 2)的构造方法与上面2种同理，不同之处为表示跳跃校验块个数的参数l的变化，这样就实现了总校验块数目的变化。
|
Download:
|
| 图 5 JLRC(12, 8, 4, 2)构造示意 Fig. 5 Code structure diagram of JLRC(12, 8, 4, 2) | |
|
Download:
|
| 图 6 JLRC(12, 10, 6, 2)构造示意 Fig. 6 Code structure diagram of JLRC(12, 10, 6, 2) | |
编码中一共包含6个校验块，但是由于JLRC码不满足MDS性质，因此并不是所有的6错情况都能重构，而对于理论上可重构的失效模式，仍然需要限定编码矩阵的系数才能实现真正的重构。以JLRC(6, 6, 2, 2)为例讨论对于理论上4错模式可重构时，编码系数需要满足的条件。p1到p4逻辑上等价，q1与q2逻辑上等价。不失一般性地，在算法描述中，选择p3、p4、q1、q24块校验块，容5/6错时可增加校验块至5/6块来进行同样原理的计算。如图 7为JLRC(6, 6, 2, 2)的构造示意图。编码等式如下：
| $ \left\{ \begin{array}{*{35}{l}} {{p}_{1}}={{d}_{1}}+{{d}_{2}}+{{d}_{3}} \\ {{p}_{2}}={{d}_{4}}+{{d}_{5}}+{{d}_{6}} \\ {{p}_{3}}={{d}_{1}}+{{d}_{3}}+{{d}_{5}} \\ {{p}_{4}}={{d}_{2}}+{{d}_{4}}+{{d}_{6}} \\ {{q}_{1}}={{\alpha }_{1}}{{d}_{1}}+{{\alpha }_{2}}{{d}_{2}}+{{\alpha }_{3}}{{d}_{3}}+{{\alpha }_{4}}{{d}_{4}}+{{\alpha }_{5}}{{d}_{5}}+{{\alpha }_{6}}{{d}_{6}} \\ {{q}_{1}}=\alpha _{1}^{2}{{d}_{1}}+\alpha _{2}^{2}{{d}_{2}}+\alpha _{3}^{2}{{d}_{3}}+\alpha _{4}^{2}{{d}_{4}}+\alpha _{5}^{2}{{d}_{6}} \\ \end{array} \right. $ |
|
Download:
|
| 图 7 JLRC(6, 6, 2, 2)构造示意 Fig. 7 Code structure diagram of JLRC(6, 6, 2, 2) | |
上述等式的矩阵形式为：
| $ \left[ \begin{matrix} {{d}_{1}} \\ {{d}_{2}} \\ {{d}_{3}} \\ {{d}_{4}} \\ {{d}_{5}} \\ {{d}_{6}} \\ {{p}_{1}} \\ {{p}_{2}} \\ {{p}_{3}} \\ {{p}_{4}} \\ {{q}_{1}} \\ {{q}_{2}} \\ \end{matrix} \right]=\left[ \begin{matrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ {{\alpha }_{1}} & {{\alpha }_{2}} & {{\alpha }_{3}} & {{\alpha }_{4}} & {{\alpha }_{5}} & {{\alpha }_{6}} \\ \alpha _{1}^{2} & \alpha _{2}^{2} & \alpha _{3}^{2} & \alpha _{4}^{2} & \alpha _{5}^{2} & \alpha _{6}^{2} \\ \end{matrix} \right]\text{ }\!\!\times\!\!\text{ }\left[ \begin{matrix} {{d}_{1}} \\ {{d}_{2}} \\ {{d}_{3}} \\ {{d}_{4}} \\ {{d}_{5}} \\ {{d}_{6}} \\ \end{matrix} \right] $ |
下面通过分析所有可能出现的4错情况，讨论编码系数需要满足的条件。
1) 4个失效块均为数据块，假设d1、d2、d3、d4失效，则编码矩阵可以表示为：
| $ \left[ \begin{matrix} {{d}_{5}} \\ {{d}_{6}} \\ {{p}_{3}} \\ {{p}_{4}} \\ {{q}_{1}} \\ {{q}_{2}} \\ \end{matrix} \right]=\left[ \begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ {{\alpha }_{1}} & {{\alpha }_{2}} & {{\alpha }_{3}} & {{\alpha }_{4}} & {{\alpha }_{5}} & {{\alpha }_{6}} \\ \alpha _{1}^{2} & \alpha _{2}^{2} & \alpha _{3}^{2} & \alpha _{4}^{2} & \alpha _{5}^{2} & \alpha _{6}^{2} \\ \end{matrix} \right]\text{ }\!\!\times\!\!\text{ }\left[ \begin{matrix} {{d}_{1}} \\ {{d}_{2}} \\ {{d}_{3}} \\ {{d}_{4}} \\ {{d}_{5}} \\ {{d}_{6}} \\ \end{matrix} \right] $ |
如果想要在4块初始数据块失效的模式下理论可重构，则需要数据块所在的列向量有解，即编码矩阵的行列式不为0。即：
| $ \left| \begin{matrix} 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ {{\alpha }_{1}} & {{\alpha }_{2}} & {{\alpha }_{3}} & {{\alpha }_{4}} & {{\alpha }_{5}} & {{\alpha }_{6}} \\ \alpha _{1}^{2} & \alpha _{2}^{2} & \alpha _{3}^{2} & \alpha _{4}^{2} & \alpha _{5}^{2} & \alpha _{6}^{2} \\ \end{matrix} \right|\ne 0 $ |
化简计算得到：
| $ ({{\alpha }_{1}}-{{\alpha }_{3}})({{\alpha }_{2}}-{{\alpha }_{4}})({{\alpha }_{1}}+{{\alpha }_{3}}-({{\alpha }_{2}}+{{\alpha }_{4}}))\ne 0 $ |
即：
| $ {{\alpha }_{1}}\ne {{\alpha }_{3}}, {{\alpha }_{2}}\ne {{\alpha }_{4}}, ({{\alpha }_{1}}+{{\alpha }_{3}})\ne ({{\alpha }_{2}}+{{\alpha }_{4}}) $ |
其他可能的失效模式同理计算，可以得到系数需满足的条件。
2) 3个数据块失效，1个校验块失效。
① 失效的校验块为跳跃校验块，且失效的3个数据块与失效的跳跃校验块为同组，则为2个可用方程解3个未知数的问题，则理论上不可重构，不予以讨论。
② 失效的校验块为跳跃校验块，且失效的3个数据块不全与失效的跳跃校验块同组。假设失效的为d1、d2、d3、p3按照上面的方法，可以得到系数需满足的条件为：α1α3(α3-α1)≠0, 即α1≠α3≠0。
③ 失效的校验块为全局校验块，假设失效块为d1、d2、d3、q2。化简后的式子为：(α3-α1)≠0, 即α1≠α3。
3) 2个数据块失效，2个校验块失效。
① 失效的校验块在跳跃校验块和全局校验块中各一块，并且失效的2块数据块与其中一块跳跃校验块同组，假设d1、d3、p3、q2失效。编码矩阵的行列式为：
| $ \left| \begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ {{\alpha }_{1}} & {{\alpha }_{2}} & {{\alpha }_{3}} & {{\alpha }_{4}} & {{\alpha }_{5}} & {{\alpha }_{6}} \\ \end{matrix} \right|=0 $ |
所以在本例中，这种情况理论上不可重构。
② 失效的校验块在跳跃校验块和全局校验块中各一块，并且失效的2块数据块分别来自2个跳跃校验块，假设d1、d2、p3、q2失效，得到-α1≠0, 即α1≠0。
③ 失效的校验块全为跳跃校验块，假设d1、d2、p3、p4失效，得到α1α2(α2-α1)≠0, 即α1≠α2≠0。
④ 失效的校验块全为全局校验块，并且失效的2块数据块与其中一个跳跃校验块同组，假设d1、d3、q1、q2失效，得到编码矩阵的行列式为：
| $ \left| \begin{matrix} 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ \end{matrix} \right|=0 $ |
所以在本例中，这种情况理论上不可重构的。
⑤ 失效的校验块全为全局校验块，并且失效的2块数据块分别来自2个跳跃校验块，假设d1、d2、q1、q2失效，最后计算得出结果为1，所以在本例中，这种情况下理论可重构，对系数没有要求。
4) 1个数据块失效，3个校验块失效。
① 失效的3个校验块中有2块跳跃校验块以及1个全局校验块，假设d1、p3、p4、q2失效，得出-α1≠0, 即α1≠0。
② 失效的3个校验块中有2块全局校验块以及1个跳跃校验块，且1个失效数据块来自于失效的跳跃校验块，假设d1、p3、q1、q2失效，结果恒为0，则在本例中，这种情况理论上不可重构的。
③ 失效的3个校验块中有2块全局校验块以及1个跳跃校验块，且1个失效数据块不在失效的跳跃校验块中，假设d1、p4、q1、q2失效，得出结果恒为-1，所以在本例中，这种情况理论上可重构，对系数没有要求。
5) 4个失效块为校验块，由原始数据块重新编码计算得出校验块即可重构出所有校验块。
在其他失效方案中，计算方式与本例中的情况计算方式相同，在计算容4错情况时，还可以选用其他校验块的组合，在综合了所有校验块的组合情况下计算出的数据为最后的结果。
3 实验结果与分析本节将通过参数的变化对比不同性能的变化，来分析JLRC本身性能，并且通过对比同样在初始数据块为10块的情况下，常用的几种编码方案体现出来的存储开销、容错率、最高容错以及单块最小重构开销等性能来分析JLRC码的性能。
3.1 JLRC参数变化对比实验为了对比不同跳跃校验块个数情况下，JLRC码所表现出的系统性能，分别选取了初始数据块10块和初始数据块12块2种最常见情况来进行分析。其中，初始数据块为10块的情况下，可以有2块跳跃校验块或5块跳跃校验块2种情况；由于初始数据块为10块时分组较少，难以清晰地分析性能变化，所以还引入了初始数据块为12块的情况，并且分为含有2块、3块、4块或6块跳跃校验块4种情况来进行讨论。在这2大种情况下，来对比存储开销、容4错率、容5错率、最高容错以及单块最小重构开销。实验对比数据如表 1所示。
|
表 1 JLRC编码性能对比数据 Table 1 Performance comparison data of JLRC |
从表 1中数据可以看出，在初始数据块有10块的情况下，随着跳跃校验块数量的增加，存储开销增大，容4错率均可达到100%，容5错率随跳跃校验块数量的增加变大，甚至JLRC(10, 9, 5, 2)的容5错率达到了100%，最高容错也随跳跃校验块数量的增加变大，由于组内数据块变少，单块最小重构开销降低；在初始数据块有12块的情况下，随着跳跃校验块数量的增加，存储开销增大，容错率变大，最高容错升高，单块最小重构开销降低。
由此可以看出，对于JLRC码来说，在一定范围内如果跳跃校验块的数量越多，容错率、容错能力以及重构开销等方面的性能都会提升，但是在这种情况下，存储开销会越来越大。所以，可以根据不同系统的性能需求来动态调整跳跃校验块的个数。
3.2 JLRC与其他纠删码对比实验本节对比了JLRC码与传统纠删码RS码以及其他分组码，分析了不同编码方案之间性能的不同。
如表 2所示，分别列举了RS码、LRC码、ESRC码、SHEC码与JLRC码在有10块原始数据块的情况下的存储开销、容4错率、最高容错能力以及单块最小重构开销的性能表现。在表 2中可以看出，与RS码进行对比，JLRC码牺牲了少量的存储开销，提高了最高容错能力，并且单块最小重构开销降低了50%；JLRC码较LRC码牺牲了少量存储开销，但将容4错率从86%提升到了100%，并且将最高容错能力提升50%；对比ESRC码与JLRC码数据，JLRC码较ESRC码虽然牺牲了少量存储开销，但将容4错率从93%提升到了100%，并且同样将最高容错能力提升50%，并且将单块最小重构开销降低了16.7%；与SHEC对比，可以看出JLRC将容4错率从83%提升至100%并且提升了最高容错。
|
|
表 2 JLRC编码和常用纠删码性能对比 Table 2 Performance comparison among JLRC and common erasure codes |
总体来看，JLRC与其他码相比，在牺牲少量存储开销前提下，其他方面的性能均有一定提升和改进。
4 结论1) JLRC码保留了LRC码的构造结构，在此之上添加了跳跃校验块，使生成校验块的初始数据块分散开来，并且保证了常规校验块与跳跃校验块的交叉互联性，这样就能保证各个校验块中初始数据块的联系，而不是完全隔离的，提高了容错率。
2) JLRC码是分组码的一种，采用将数据块分组的方式，使得单个数据块的重构可以在组内进行，相比传统的纠删码减少了单节点故障需要下载的数据量，实际系统中超过90%以上的磁盘故障都是单个磁盘故障[23]，所以降低了重构开销，提升了系统性能。
3) JLRC码保留了2块全局校验，可以更好地提升容错能力。
本文通过改变跳跃校验块的数量以便自身其他参数变化并且进行性能对比，并且进行与传统MDS码(RS码)以及其他经典分组码的对比，结果表明:JLRC码能够在牺牲少量存储开销或在同等的存储开销下，明显提高容错率以及容错能力，并且降低重构开销。但当分组过多时，JLRC码的存储开销较大，在JLRC的基础上如何进一步降低存储开销，是未来研究的一个目标。
| [1] |
黄河燕, 曹朝, 冯冲. 大数据情报分析发展机遇及其挑战[J]. 智能系统学报, 2016, 11(6): 719-727. HUANG Heyan, CAO Chao, FENG Chong. Opportunities and challenges of big data intelligence analysis[J]. CAAI transactions on intelligent systems, 2016, 11(6): 719-727. (  0)
|
| [2] |
JAGADISH H V, GEHRKE J, LABRINIDIS A, et al. Big data and its technical challenges[J]. Communications of the ACM, 2014, 57(7): 86-94. DOI:10.1145/2611567 ( 0)
|
| [3] |
RASHMI K V, SHAH N B, GU D, et al. A solution to the network challenges of data recovery in erasure-coded distributed storage systems:a study on the facebook warehouse cluster[J]. Usenix hotstorage, 2013. ( 0)
|
| [4] |
邵秀丽, 王亚光, 李云龙, 等. Hadoop副本放置策略[J]. 智能系统学报, 2013(6): 489-496. SHAO Xiuli, WANG Yaguang, LI Yunlong, et al. Research in replica placement strategy of Hadoop[J]. CAAI transactions on intelligent systems, 2013(6): 489-496. ( 0)
|
| [5] |
WEATHERSPOON H, KUBIATOWICZ J D. Erasure coding vs. replication: a quantitative comparison[C]//Proceedings of the 1st International Workshop on Peer-to-Peer Systems. Cambridge, 2002: 7-14.
( 0)
|
| [6] |
黄建忠, 曹强, 黄思倜, 等. 面向纠删码存储集群的节点并发重构[J]. 计算机研究与发展, 2016, 53(9): 1918-1929. HUANG Jianzhong, CAO Qiang, HUANG Siti, et al. Concurrent node reconstruction for erasure-coded storage clusters[J]. Journal of computer research and development, 2016, 53(9): 1918-1929. ( 0)
|
| [7] |
FAN Bin, TANTISIRIROJ W, XIAO Lin, et al. DiskReduce: replication as a prelude to erasure coding in data-intensive scalable computing[C]//Proceedings of 2011 International Conference for High Performance Computing Networking, Storage and Analysis. Seattle, WA, USA, 2011: 6-10.
( 0)
|
| [8] |
REED I S, SOLOMON G. Polynomial codes over certain finite fields[J]. Journal of the society for industrial and applied mathematics, 1960, 8(2): 300-304. DOI:10.1137/0108018 ( 0)
|
| [9] |
BLAUM M, BRADY J, BRUCK J, et al. EVENODD:an efficient scheme for tolerating double disk failures in RAID architectures[J]. IEEE transactions on computers, 1995, 44(2): 192-202. DOI:10.1109/12.364531 ( 0)
|
| [10] |
CORBETT P, ENGLISH B, GOEL A, et al. Row-diagonal parity for double disk failure correction[C]//Proceedings of the 3rd USENIX Conference on File and Storage Technologies. San Francisco, CA, 2004: 1.
( 0)
|
| [11] |
HUANG Cheng, XU Lihao. Star: an efficient coding scheme for correcting triple storage node failures[C]//Proceedings of the 4th Conference on USENIX Conference on File and Storage Technologies. San Francisco, CA, 2005: 15.
( 0)
|
| [12] |
CALDER B, WANG Ju, OGUS A, et al. Windows Azure Storage: a highly available cloud storage service with strong consistency[C]//Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. Cascais, Portugal, 2011: 143-157.
( 0)
|
| [13] |
HUANG Cheng, SIMITCI H, XU Yikang, et al. Erasure coding in windows azure storage[C]//Proceedings of 2012 USENIX Conference on Annual Technical Conference. Boston, MA, USA, 2012: 2.
( 0)
|
| [14] |
HUANG Cheng, CHEN Minghua, LI Jin. Pyramid codes: flexible schemes to trade space for access efficiency in reliable data storage systems[C]//Proceedings of the 6th IEEE International Symposium on Network Computing and Applications. Cambridge, USA, 2007: 79-86.
( 0)
|
| [15] |
MIYAMAE T, NAKAO T, SHIOZAWA K. Erasure code with shingled local parity groups for efficient recovery from multiple disk failures[C]//Proceedings of the 10th USENIX Conference on Hot Topics in System Dependability. Broomfield, USA, 2014: 5.
( 0)
|
| [16] |
HAFNER J L. WEAVER codes: highly fault tolerant erasure codes for storage systems[C]//Proceedings of the 4th Conference on USENIX Conference on File and Storage Technologies. San Francisco, USA, 2005: 16.
( 0)
|
| [17] |
LI Mingqiang, SHU Jiwu, ZHENG Weimin. GRID codes:strip-based erasure codes with high fault tolerance for storage systems[J]. ACM transactions on storage, 2009, 4(4): 15. ( 0)
|
| [18] |
HAFNER J L. Hover erasure codes for disk arrays[C]//Proceedings of 2006 International Conference on Dependable Systems and Networks. Philadelphia, USA, 2006: 217-226.
( 0)
|
| [19] |
傅颖勋, 文士林, 马礼, 等. 纠删码存储系统单磁盘错误重构优化方法综述[J]. 计算机研究与发展, 2018, 55(1): 1-13. FU Yingxun, WEN Shilin, MA Li, et al. Survey on single disk failure recovery methods for erasure coded storage systems[J]. Journal of computer research and development, 2018, 55(1): 1-13. ( 0)
|
| [20] |
杨松霖, 张广艳. 纠删码存储系统中数据修复方法综述[J]. 计算机科学与探索, 2017, 11(10): 1531-1544. YANG Songlin, ZHANG Guangyan. Review of data recovery in storage systems based on erasure codes[J]. Journal of frontiers of computer science and technology, 2017, 11(10): 1531-1544. DOI:10.3778/j.issn.1673-9418.1701044 ( 0)
|
| [21] |
钟凤艳, 王艳, 李念爽.异构环境下纠删码的数据修复方法综述[J/OL].计算机应用研究, 2019(8).[2018-11-17].http://kns.cnki.net/kcms/detail/51.1196.TP.20180723.1748.012.html. ZHONG Fengyan, WANG Yan, LI Nianshuang. Review of data repair methods for erasure codes in heterogeneous environments[J/OL]. Application research of computers, 2019(8).[2018-11-17]. http://kns.cnki.net/kcms/detail/51.1196.TP.20180723.1748.012.html. ( 0)
|
| [22] |
王意洁, 许方亮, 裴晓强. 分布式存储中的纠删码容错技术研究[J]. 计算机学报, 2017, 40(1): 236-255. WANG Yijie, XU Fangliang, PEI Xiaoqiang. Research on erasure code-based fault-tolerant technology for distributed storage[J]. Chinese journal of computers, 2017, 40(1): 236-255. ( 0)
|
| [23] |
SCHROEDER B, GIBSON G A. Disk failures in the real world: what does an MTTF of 1, 000, 000 hours mean to you?[C]//Proceedings of the 5th USENIX Conference on File and Storage Technologies. San Jose, CA, 2006: 1.
( 0)
|