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

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

Abstract

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

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.

Figures/Tables 12

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

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

RS regenerating codes for cloud storage fault-tolerant system

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 12

References 20

Related Articles 15

Metrics

Recommended 0

[1]	Guanxiong HA, Qiaowen JIA, Hang CHEN, Chunfu JIA. Data popularity-based encrypted deduplication scheme without third-party servers [J]. Journal on Communications, 2022, 43(8): 17-29.
[2]	Yu CHEN, Lianxing JIA. Two-layer grouped Byzantine fault tolerance algorithm for UAV swarm [J]. Journal on Communications, 2022, 43(1): 96-103.
[3]	Tao FENG, Fanqi KONG, Chunyan LIU, Rong MA, Albettar Maher. Dual verifiable cloud storage scheme based on blockchain [J]. Journal on Communications, 2021, 42(12): 192-201.
[4]	Chunfu JIA, Guanxiong HA, Shaoqiang WU, Hang CHEN, Ruiqi LI. AONT-and-NTRU-based rekeying scheme for encrypted deduplication [J]. Journal on Communications, 2021, 42(10): 67-80.
[5]	Junfeng TIAN,Yanbiao WANG,Xinfeng HE,Juntao ZHANG,Wanhe YANG,Ya’nan PANG. Survey on the causal consistency of data [J]. Journal on Communications, 2020, 41(3): 154-167.
[6]	Wenlong KE,Yong WANG,Miao YE,Junqi CHEN. Priority differentiated multicast flow scheduling method in Ceph cloud storage network [J]. Journal on Communications, 2020, 41(11): 40-51.
[7]	Lei SUN,Zhiyuan ZHAO,Jianhua WANG,Zhiqiang ZHU. Attribute-based encryption scheme supporting attribute revocation in cloud storage environment [J]. Journal on Communications, 2019, 40(5): 47-56.
[8]	Xiangsong ZHANG,Chen LI,Zhenhua LIU. Key-exposure resilient integrity auditing scheme with encrypted data deduplication [J]. Journal on Communications, 2019, 40(4): 95-106.
[9]	Miaomiao TIAN,Chuang GAO,Jie CHEN. Identity-based cloud storage integrity checking from lattices [J]. Journal on Communications, 2019, 40(4): 128-139.
[10]	Junfeng TIAN,Mengjia CHAI,Liuling QI. Provable data possession scheme based on public verification and private verification [J]. Journal on Communications, 2019, 40(3): 48-59.
[11]	Ruizhong DU,Pengliang SHI,Xinfeng HE. Cloud data assured deletion scheme based on overwrite verification [J]. Journal on Communications, 2019, 40(1): 130-140.
[12]	Xincheng YAN,Yue CHEN,Hongyong JIA,Yanru CHEN,Xinyue ZHANG. Secure data sharing scheme supporting efficient synchronous evolution for ciphertext and key [J]. Journal on Communications, 2018, 39(5): 123-133.
[13]	Yue CHEN,Longjiang WANG,Xincheng YAN,Xinyue ZHANG. Mimic storage scheme based on regenerated code [J]. Journal on Communications, 2018, 39(4): 21-34.
[14]	Shaohui WANG,Xiaoxiao PAN,Zhiwei WANG,Fu XIAO,Ruchuan WANG. Analysis and improvement on identity-based cloud data integrity verification scheme [J]. Journal on Communications, 2018, 39(11): 98-105.
[15]	Wei-dong LYU,Xue-guang ZHOU,Zhi-min YUAN. Design of tree topology based Byzantine fault tolerance system [J]. Journal on Communications, 2017, 38(Z2): 139-146.