计算机应用   2017, Vol. 37 Issue (4): 936-940  DOI: 10.11772/j.issn.1001-9081.2017.04.0936 0

### 引用本文

TANG Dan, YANG Haopeng, WANG Fuchao. Array erasure codes based on coding chains with multiple slopes[J]. Journal of Computer Applications, 2017, 37(4): 936-940. DOI: 10.11772/j.issn.1001-9081.2017.04.0936.

### 文章历史

Array erasure codes based on coding chains with multiple slopes
TANG Dan, YANG Haopeng, WANG Fuchao
College of Software Engineering, Chengdu University of Information Technology, Chengdu Sichuan 610225, China
Abstract: In view of the problem that the fault tolerance capability is low and strong constraint conditions need to be satisfied in the construction of most array erasure codes at present, a new type of array erasure codes based on coding chains was proposed. In the new array erasure codes, coding chains with different slopes were used to organize the relationship among data elements and check elements, so as to achieve infinite fault tolerance capability in theory; the strong constraint conditions like the prime number limitation was avoided in construction, which is easy to be practical and extensible. Simulation results show that, compared with Reed-Solomon codes (RS codes), the efficiency of the proposed array erasure codes based on coding chains is more than 2 orders of magnitude; under the condition of fixed fault tolerance, its storage efficiency can be improved with the increase of the strip size. In addition, the update penalty and repair cost of the array codes is a fixed constant, which will not increase with the expansion of the storage system scale or the increase of fault tolerance capability.
Key words: array erasure code    fault tolerance    coding chain    strip size
0 引言

1 基本概念和定义

 $({y_2}-{y_1})\% n = ({y_3}-{y_2})\% n = \cdots = ({y_t}-{y_{t - 1}})\% n$ (1)

 图 1 斜率为1的码链 Figure 1 Coding chain with slope 1

El(i, j):该符号用于标识存储阵列中第i行第j列的元素, 当有多个元素需要表示时, 可以使用符号“:”表示出一个范围区间, 如El(i, 2:5) 表示存储阵列第i行上的第2到5个元素集合, El(:, j) 则用于表示阵列中第j列的所有元素。

Dji:该符号表示存储阵列的列间距离, 定义Dji=(j-i-1)%n+1, 其中n为条带尺寸, ij为不大于n的正整数。需要说明的是, 在计算失效列ij之间距离时, 两个失效列之间若还存在一个及以上的失效列, 则失效列ij之间不存在距离, 记作Dji=0。将一个存储阵列中f个失效列记作1, 2, …, f, 则失效列 (i-2)%f+1称为失效列i的左邻失效列, 失效列i%f+1称为失效列i的右邻失效列。

2 基于多斜率码链的阵列码

2.1 编码及数据重构方法

 图 2 存储阵列的元素标识 Figure 2 ID of storage array

 $\begin{array}{l} c(t) = \sum\limits_{i = 1}^m {d(i, {l_c} + i \cdot (2 \cdot ({l_r}\% 2)-1) \cdot } \\ \;\;\;\;\;\;\;\;\;\left\lceil {{l_r}/2} \right\rceil-1)\% n + 1) \end{array}$ (2)

 ${l_r} = \left[{(t-1)/n} \right] + 1$ (3)
 ${l_c} = (t-1)\% n + 1$ (4)

 图 3 斜率为1、-1、2的码链部署 Figure 3 Deployment of coding chains with slopes 1, -1 and 2

 图 4 失效数据的成功恢复过程 Figure 4 Successful recovery process of invalid data

 图 5 失败的数据恢复 Figure 5 Failed data recovery
2.2 约束条件及容错能力保证

3 实验与分析 3.1 运算工作量

 图 6 条块尺寸对运算量的影响 Figure 6 Influence of strip size on operational burden
 图 7 容错能力对运算量的影响 Figure 7 Influence of fault tolerance on operational burden
3.2 存储效率

 图 8 存储效率的变化 Figure 8 Changes on storage efficiency
3.3 修复代价和更新代价

4 结语

 [1] SATHIAMOORTHY M, ASTERIS M, PAPAILIOPOULOS D, et al. XORing elephants: novel erasure codes for big data[J]. Proceedings of the VLDB Endowment, 2013, 6 (5) : 325-336. doi: 10.14778/2535573 [2] SCHROEDER B, GIBSON G A. Disk failures in the real world: what does an MTTF of 1000000 hours mean to you?[C]//FAST 2007: Proceedings of the 5th USENIX Conference on File and Storage Technologies. Berkeley, CA: USENIX Association, 2007:1-16. [3] PLANK J S, XU L. Optimizing Cauchy Reed-Solomon codes for fault-tolerant network storage applications[C]//NCA 2006: Proceedings of the Fifth IEEE International Symposium on Network Computing and Applications. Washington, DC: IEEE Computer Society, 2006:173-180. [4] PLANK J S, GREENAN K M, MILLER E L. Screaming fast Galois field arithmetic using Intel SIMD instructions[C]//FAST 2013: Proceedings of the 11th USENIX Conference on File and Storage Technologies. Berkeley, CA: USENIX Association, 2013: 299-306. [5] JANAKIRAM B, CHANDRA M G, ARAVIND K G, et al. SpreadStore: a LDPC erasure code scheme for distributed storage system[C]//Proceedings of the 2010 International Conference on Data Storage and Data Engineering. Piscataway, NJ: IEEE, 2010: 154-158. [6] 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 [7] XU L, BRUCK J. X-code: MDS array codes with optimal encoding[J]. IEEE Transactions on Information Theory, 1999, 45 (1) : 272-276. doi: 10.1109/18.746809 [8] HUANG C, XU L. STAR: an efficient coding scheme for correcting triple storage node failures[J]. IEEE Transactions on Computers, 2008, 57 (7) : 889-901. doi: 10.1109/TC.2007.70830 [9] 孟庆春. 应用于分布式存储系统上的纠删码技术研究[D]. 北京: 中国科学院研究生院, 2007. ( MENG Q C. Research of erasure codes applied in distributed storage system[D]. Beijing: Graduate University of the Chinese Academy of Sciences, 2007. ) [10] HAFNER J L. WEAVER codes: highly fault tolerant erasure codes for storage systems[C]//FAST 2005: Proceedings of the 4th Conference on USENIX Conference on File and Storage Technologies. Berkeley, CA: USENIX Association, 2005, 4: 211-224. [11] HAFNER J L. HoVer erasure codes for disk arrays[C]//DSN 2006: Proceedings of the 2006 International Conference on Dependable Systems and Networks. Washington, DC: IEEE Computer Society, 2006: 217-226. [12] LI M, SHU J, ZHENG W. GRID codes: strip-based erasure codes with high fault tolerance for storage systems[J]. ACM Transactions on Storage, 2009, 4 (4) : Article No. 15. [13] 陈峥. 一类新的阵列纠删码理论及应用研究[D]. 北京: 中国科学院研究生院, 2009. ( CHEN Z. A class of array erasure codes and their applications[D]. Beijing: Graduate University of the Chinese Academy of Sciences, 2009. ) [14] 唐聃, 舒红平. 一类多容错的阵列纠删码[J]. 中国科学:信息科学, 2016, 46 (4) : 523-538. ( TANG D, SHU H P. A class of array erasure codes with high fault-tolerance[J]. Science China: Information Sciences, 2016, 46 (4) : 523-538. )