面向云存储容错系统的RS再生码

doi:10.11959/j.issn.1000-436x.2016197

摘要/Abstract

摘要：

面向云存储容错系统提出了一种 RS 再生纠删码，该编码继承了 RS 编码容多错的可靠性，又能实现容三错的高效性。对RS再生码中单节点故障混合修复方法进行了介绍，并求出了混合修复时磁盘读取数的理论下界。从理论上对RS再生码的存储开销、译码效率、修复带宽进行了性能评估。实验结果表明，RS再生纠删码比同类纠删码的修复性能有较大的提升，特别是采用混合修复算法以后，系统单故障恢复时间下降20.8%~28.2%。

关键词: 云存储, 容错, 纠删码, RS码, RDP码

Abstract:

RS(Reed-Solomon) regenerating erasure codes was proposed for cloud storage fault-tolerant system,which not only inherited the reliability of the RS encoding,but also achieved the high efficiency of tolerance three faults.Hybrid recovery method of the single fault node based on RS regenerating erasure codes was introduced.And the theoretical lower bound of the number of accessing disks was computed.In theory,the performance evaluation of the storage overhead,decoding efficiency,and repair bandwidth of the RS regenerating erasure codes was carried out.Experiments results show that the repair performance of RS regenerating erasure codes is improved greatly than the similar erasure codes,and the total recovery time of the system is reduced by 20.8%~28.2% using hybrid recovery algorithm in the case of single fault.

Key words: cloud storage, fault tolerance, erasure codes, RS encoding, RDP encoding

鄢喜爱,张大方,杨金民,张波云. 面向云存储容错系统的RS再生码[J]. 通信学报, 2016, 37(10): 65-74.

Xi-ai YAN,Da-fang ZHANG,Jin-min YANG,Bo-yun ZHANG. RS regenerating codes for cloud storage fault-tolerant system[J]. Journal on Communications, 2016, 37(10): 65-74.

图/表 12

图1

图2

图3

表1

图4

图5

表2

单节点故障修复带宽比较"

编码	修复带宽/MB
RS码	(p?1)n
RDP码传统修复	(p?1)²
RS-ERDP码混合修复	$\frac{2}{3} {(p - 1)}^{2}$

表2

表3

图6

表4

图7

图8

参考文献 20

[1]	王意洁, 孙伟东, 周松 ,等. 云计算环境下的分布存储关键技术[J]. 软件学报, 2012,23(4): 962-986. WANG Y J , SUN W D , ZHOU S ,et al. Key technologies of distributed storage for cloud computing[J]. Journal of Software, 2012,23(4): 962-986.
[2]	谭鹏许, 陈越, 兰巨龙 ,等. 用于云存储的安全容错编码[J]. 通信学报, 2014,35(3): 109-115. TAN P X , CHEN Y , LAN J L ,et al. Secure fault-tolerant code for cloud storage[J]. Journal on Communications, 2014,35(3): 109-115.
[3]	LUO J Q , MOCHAN S , XU L H ,et al. Efficient encoding schedules for XOR-based erasure codes[J]. IEEE Transactions on Computers, 2014,63(9): 2259-2272.
[4]	LI M , SHU J . On cyclic lowest density MDS array codes constructed using starters[J]. IEEE International Symposium on Information Theory, 2010,41(3): 1315-1319.
[5]	万武南, 吴震, 陈运 ,等. 一种基于3容错阵列码的RAID数据布局[J]. 计算机学报, 2007,30(10): 1722-1730. WAN W N , WU Z , CHEN Y ,et al. A data placement based on toleration on triple failures array codes in RAID[J]. Chinese Journal of Computers, 2007,30(10): 1722-1730.
[6]	KVASHENNIKOV V V . Application of fast polynoamial transformations over GALOIS GF(2m) fields in Reed-Solomon coding and decoding[J]. Telecommunications and Radio Engineering, 2012,71(10): 85-90.
[7]	BURGISSER P , CLAUSEN M , SHOKROLLAHI MA . Algebraic complexity theory[M]. Springer Verlag Heidelberg. 1996.
[8]	LACAN J , FIMES J . Systematic MDS erasure codes based on Vandermonde matrices[J]. IEEE Communications Letters, 2004,8(9): 570-582.
[9]	PLANK J S , XU L . Optimizing cauchy Reed-Solomon codes for fault-tolerant network storage applications[C]// The 5th IEEE International Symposium on Network Computing and Applications (IEEE NCA06). Cambridge,MA, 2006: 1-8.
[10]	KALCHER S , LINDENSTRUTH V . Accelerating Galois field arithmetic for Reed-Solomon erasure codes in storage applications[C]// IEEE International Conference on Cluster Computing. 2011: 290-298.
[11]	KHAN O , BURNS R , PLANK J S . Rethinking erasure codes for cloud file systems:minimizing I/O for recovery and degraded reads[C]// USENIX.FAST 2012:10th USENIX Conference on File and Storage Technologies. San Jose,CA, 2012: 1-14.
[12]	李小兵, 许胤龙, 林一施 ,等. 再生码:一类适用于云存储的准确修复编码[J]. 计算机应用与软件, 2014,31(8): 241-244. LI X B , XU Y L , LIN Y S ,et al. X regenerating codes:a class of accurate repair codes for cloud storage[J]. Computer Applications and Software, 2014,31(8): 241-244.
[13]	PLANK J S . A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems[J]. Software:Practice and Experience, 1997,27(9): 995-1012.
[14]	CORBETT P , ENGLISH B , GOEL A ,et al. Row diagonal parity for double disk failure correction[C]// Proceedings of the Third USENIX Conference on File and Storage Technologies. Berkeley,CA,USA, 2004: 1-14.
[15]	邱丽娜, 王芳, 李楚 ,等. 一种容三盘失效纠删码的单数据盘失效快速重建方法[J]. 计算机学报, 2013,36(10): 2041-2051. QIU L N , WANG F , LI C ,et al. EDS:a novel scheme for boosting single disk failure recovery of triple erasure correcting code storage systems[J]. Chinese Journal of Computers, 2013,36(10): 2041-2051.
[16]	XIANG L , XU Y , LUI J C S ,et al. Optimal recovery of single disk failure in RDP code storage systems[J]. ACM Sigmetrics Performance Evaluation Review[J]. ACM, 2010,38(1): 119-130.
[17]	BLOEMER J M , KALFANE M , KARPINSKI R . An XOR-based erasure-resilient coding scheme[R]. Technical Report at ICSI, 1995.
[18]	万武南, 王拓, 索望 . 一种三容错数据布局[J]. 电子与信息学报, 2013,35(10): 2341-2346. WAN W N , WANG T , SUO W ,et al. A data placement based on toleration triple failures[J]. Journal of Electronics ＆ Information Technology, 2013,35(10): 2341-2346.
[19]	LI J , LI B . Erasure coding for cloud storage systems:a survey[J]. Tsinghua Science and Technology, 2013,18(3): 259-272.
[20]	HU Y , YU M C , LEE P P C ,et al. NCFS:on the praticatity and extensibility of a network-coding based distributed file system[C]// International Symposium on Network Coding. Beijing, 2011: 1-6.

D₀	D₁	D₂	D₃	D₄	D₅	D₆(c_i,₆)	D₇	D₈
d_0,0	d_0,1	d_0,2	c_0,3	c_0,4	c_0,5	d_0,0⊕d_0,1⊕d_0,2⊕c_0,3⊕c_0,4⊕c_0,5	c_0,5⊕c_1,4⊕c_2,3⊕d_3,2⊕c_4,1⊕c_5,0	c_5,5⊕c_4,4⊕c_3,3⊕d_2,2⊕d_1,1⊕d_0,0
d_1,0	d_1,1	d_1,2	c_1,3	c_1,4	c_1,5	d_1,0⊕d_1,1⊕d_1,2⊕c_1,3⊕c_1,4⊕c_1,5	c_0,4⊕c_1,3⊕d_2,2⊕d_3,1⊕c_4,0⊕c_5,6	c_5,4⊕c_4,3⊕d_3,2⊕d_2,1⊕d_1,0⊕c_0,6
d_2,0	d_2,1	d_2,2	c_2,3	c_2,4	c_2,5	d_2,0⊕d_2,1⊕d_2,2⊕c_2,3⊕c_2,4⊕c_2,5	c_0,3⊕d_1,2⊕d_2,1⊕d_3,0⊕c_5,5⊕c_4,6	c_5,3⊕d_4,2⊕d_3,1⊕d_2,0⊕c_0,5⊕c_1,6
d_3,0	d_3,1	d_3,2	c_3,3	c_3,4	c_3,5	d_3,0⊕d_3,1⊕d_3,2⊕c_3,3⊕c_3,4⊕c_3,5	d_0,2⊕d_1,1⊕d_2,0⊕c_5,4⊕c_4,5⊕c_3,6	d_5,2⊕d_4,1⊕d_3,0⊕c_0,4⊕c_1,5⊕c_2,6
d_4,0	d_4,1	d_4,2	c_4,3	c_4,4	c_4,5	d_4,0⊕d_4,1⊕d_4,2⊕c_4,3⊕c_4,4⊕c_4,5	d_0,1⊕d_1,0⊕c_5,3⊕c_4,4⊕c_3,5⊕c_2,6	d_5,1⊕d_4,0⊕c_0,3⊕c_1,4⊕c_2,5⊕c_4,6
d_5,0	d_5,1	d_5,2	c_5,3	c_5,4	c_5,5	d_5,0⊕d_5,1⊕d_5,2⊕c_5,3⊕c_5,4⊕c_5,5	d_0,0⊕d_5,2⊕c_4,3⊕c_3,4⊕c_2,5⊕c_1,6	d_5,0⊕d_0,2⊕c_1,3⊕c_2,4⊕c_3,5⊕c_5,6

m+n中节点故障数(u)	ERDP中校验节点故障数(v)	方案选择
u＞m	?v	无法修复
3＜u≤m	?v	RS
u=3	v＞0	RS
u=3	v= 0	RS-ERDP
u=2	v 1＞	RS
u=2	v≤ 1	RS-ERDP
u 1=	v＞2	RS
u 1=	v≤ 2	RS-ERDP

身份	CPU	硬盘	内存	网络带宽
存储客户端	酷睿i5，3.3 GHz	WD4T	DDR3,8 GB	100 Mbit/s
主从文件服务器	酷睿i7，4.0 GHz	WD 6T	DDR3,8 GB	100 Mbit/s
存储节点	酷睿i5，3.3 GHz	WD 4T	DDR3,8 GB	100 Mbit/s