基于X-RDP阵列码的一种数据分布策略

doi:10.3969/j.issn.1000-436x.2013.z1.009

Abstract

Abstract:

A data distribution strategy based on the X-RDP code was presented for correcting triple storage failures, which is an extension of the double-erasure-correcting RDP code. A theoretical proof that the X-RDP code is an MDS code was given by using algebraic definition. The encoding and decoding procedures were described by geometrical line graphs, which were easily implemented by soft hardware. The theoretical analysis shows that the comprehensive proper-ties of the X-RDP codeis better than other popular MDS codes in encoding and decoding efficiency, small writes and bal-ance performance, thus the X-RDP code is practically meaningful for storage systems.

Key words: coding, erasure-correcting code, RDP code, data placement, RAID

Wu-nan WAN,Wang SUO,Yun CHEN,Tuo WANG. Data distribution strategy based on the X-RDP array codes[J]. Journal on Communications, 2013, 34(Z1): 67-75.

Figures/Tables 5

References 20

[1]	王意洁，孙伟东，周松等．云计算环境下分布存储关键技术[J]．软件学报网络优出版， 2012,23(4):962-986. WANG Y J , SUN W D , ZHOU S , et al. Key technologyies of distributed storage for cloud computing[J]. Journal of Software, 2012,23(4):962-986.
[2]	罗象宏，舒继武．存储系统中的纠删码研究综述[J]．计算机研究与发展， 2012,49(1):1-11. LUO X H , SHU J W . Summary of research for erasure code in storage sys-tem[J]. Journal of Compute Research and Development, 2012,49(1):1-11.
[3]	BLAUM M , BRADY J , BRUCK J , et al. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures[J]. IEEE Trans Compute, 1995,44 (2):192-202.
[4]	XU L , BRUCK J . X-code: MDS array codes with optimal encoding[J]. IEEE Trans on Information Theory, 1999,45 (1):272-276.
[5]	XU L , BOHOSSIAN V , BRUCK J , et al. Low density MDS codes and factors of complete graphs[J]. IEEE Trans on Information Theory, 1999,45 (6):1817-1826.
[6]	LI M Q , SHU J W . C-codes: cyclic lowest-density MDS array codes con-structed using starters or RAID 6[EB/OL]. .
[7]	CORBETT P , ENGLISH B , GOEL A , et al. Row diagonal parity for double disk failure[A]. Proceedings of the Third USENIX Conference on File and Storage Technologies[C]. 2004.1-14.
[8]	WU C T , WAN S G , HE X B , et al. H-code:a hybrid MDS array code to optimize partial stripe writes in RAID-6[A]. Proceedings of the IEEE Congress on International Parallel＆Distributed Processing Symposium[C]. USA, 2011.782-793.
[9]	LI M , SHU J , ZHENG W . GRID codes: strip-based erasure code with high fault tolerance for storage systems[J]. ACM Transactions on Storage, 2009,4 (4):1-22.
[10]	HAFNER J L . HoVer erasure codes for disk arrays[EB/OL]. , 2005.
[11]	HAFNER J L . WEAVER codes: highly fault tolerant erasure codes for storage systems[EB/OL]. , 2005.
[12]	FENG G L , DENG R , BAO F , et al. New efficient MDS array codes for RAID, Part I: reed-solomon-like codes for tolerating three disk failures[J]. IEEE Trans Computers, 2005,54 (9):1071-1080.
[13]	FENG G L , DENG R , BAO F , et al. New efficient MDS array codes for RAID, part II: rabin-like codes for tolerating multiple (4)disk fail-ures[J]. IEEE Trans Computers, 2005,54 (12):1473-1482.
[14]	BLAUM M , BRUCK J , VARDY A . MDS array codes with independent parity symbols[J]. IEEE Trans Inform Theory, 1996,42:529-542.
[15]	SHENG L , GANG W , STONES D S , et al. T-code: 3 erasure longest lowest-density MDS codes[J]. IEEE Journal on Selected Areas in Communications, 2010,28 (2):289-296.
[16]	CHIH-SHING T , TZONE-I W . Efficient parity placement schemes for tolerating triple disk failures in RAID architectures[A]. Proceedings of the 17th International Conference on Advanced Information Networking and Applications(AINA'03)[C]. Washington DC, USA, 2003.132-138.
[17]	HUANG C , XU L . STAR: an efficient coding scheme for correcting triple storage node failures[A]. Proceedings of the 4th USENIX Conf on File and Storage Technologies[C]. Berkeley, CA, 2005.197-210.
[18]	万武南，吴震． RAID-EEOD：一种基于3容错阵列码RAID数据布局研究[J]．计算机学报， 2007,30(10):1-10. WAN W N , WU Z . RAID-EEOD: the study of data placement based on toleration on triple failures array codes in RAID[J]. Chinese Journal of Compute, 2007,30(10):1-10.
[19]	PLANK J S . A tutorial on reed-solomon coding for fault-tolerance in RAID-like systems[J]. Software Practice and Experience(SPE), 1997,27 (9):995-1012.
[20]	BLOEMER J M , KALFANE M , KARPINSKI R . An XOR-Based Erasure-Resilient Coding Scheme[R]. Technical report at ICSI, 1995.

Metrics

Recommended 0

No Suggested Reading articles found!

	数据源			校验数据
C_i0	C_i1	C_i2	C_i3C_i4	C_i5	C_i6
C₀₀	c ₀₁	c₀₂	c₀₃c₀₄=c₀₀⊕c₀₁⊕c₀₂⊕c₀₃	c₀₅=c₁₄⊕c₂₃⊕c₃₂⊕c₀₀	c₀₆=c₃₃⊕c₂₂⊕c₁₁⊕c₀₀
c₁₀	c₁₁	c₁₂	c₁₃c₁₄=c₁₀⊕c₁₁⊕c₁₂⊕c₁₃	c₁₅= c₂₄⊕c₃₃⊕c₀₁⊕c₁₀	c₁₆= c₀₄⊕c₃₂⊕c₂₁⊕c₁₀
c₂₀	c₂₁	c₂₂	c₂₃c₂₄=c₂₀⊕c₂₁⊕c₂₂⊕c₂₃	c₂₅= c₃₄⊕c₀₂⊕c₁₁⊕c₂₀	c₂₆=c₁₄⊕c₀₃⊕c₃₁⊕c₂₀
c₃₀	c₃₁	c₃₂	c₃₃c₃₄=c₃₀⊕c₃₁⊕c₃₂⊕c₃₃	c₃₅=c₀₃⊕c₁₂⊕c₂₁⊕c₃₀	c₃₆=c₂₄⊕c₁₃⊕c₀₂⊕c₃₀

磁盘数	Blaum码	EEOD码	STAR码	X-RDP码	Bloemer码
5	7.2	3.62	3.55	3	9
7	6	3.68	3.714 3	3.8	9
11	4.909	3.81	3.836 4	3.533 3	12
13	4.615	3.846	3.865 4	3.8	12
17	4.235	3.882	3.900 7	3.848 5	15
19	4.105	3.894	3.912 3	3.9	15
23	3.913	3.85	3.928 9	3.926 3	15
29	3.74	3.931	3.944 6	3.952 4	15
31	3.678	3.935	3.948 4	3.956 3	15

Data distribution strategy based on the X-RDP array codes

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 5

References 20

Related Articles 15

Metrics

Recommended 0

[1]	Rongpeng LI, Bingyan WANG, Honggang ZHANG, Zhifeng ZHAO. Design of knowledge enhanced semantic communication receiver [J]. Journal on Communications, 2023, 44(6): 70-76.
[2]	Ping ZHANG, Kai NIU, Shengshi YAO, Jincheng DAI. Semantic communications for future: basic principle and implementation methodology [J]. Journal on Communications, 2023, 44(5): 1-14.
[3]	Ying FANG, Yiwen XU, Tiesong ZHAO. Joint vibrotactile coding for machine recognition and human perception [J]. Journal on Communications, 2023, 44(5): 42-51.
[4]	Rui GUO, Yang LIU. Simplified sequence repetition nodes-based fast successive cancellation decoding algorithm for polar code [J]. Journal on Communications, 2023, 44(5): 158-168.
[5]	Ping ZHANG, Jincheng DAI, Yuming ZHANG, Sixian WANG, Xiaoqi QIN, Kai NIU. Nonlinear transform coding for semantic communications [J]. Journal on Communications, 2023, 44(4): 1-14.
[6]	Wei ZHANG, Yu WANG, Xinyi CHEN, Yanwen WANG, Qingyang JING, Weimin LEI. Background reference frame generation method for surveillance video based on image block codebook model [J]. Journal on Communications, 2023, 44(1): 129-141.
[7]	Ke LAI, Jing LEI, Wei LIU, Lei WEN. HARQ scheme for sparse code multiple access based on network coding [J]. Journal on Communications, 2022, 43(9): 57-69.
[8]	Yanwen WANG, Weimin LEI, Wei ZHANG, Huan MENG, Xinyi CHEN, Wenhui YE, Qingyang JING. Survey on video image reconstruction method based on generative model [J]. Journal on Communications, 2022, 43(9): 194-208.
[9]	Youqing WU, Wenjing MA, Zhaoxia YIN, Yinyin PENG, Xinpeng ZHANG. Reversible data hiding in encrypted image based on bit-plane compression of prediction error [J]. Journal on Communications, 2022, 43(8): 219-230.
[10]	Chuanhong LIU, Caili GUO, Yang YANG, Jiujiu CHEN, Meiyi ZHU, Lu’nan SUN. Intelligent task-oriented semantic communications:theory, technology and challenges [J]. Journal on Communications, 2022, 43(6): 41-57.
[11]	Dacheng ZHOU, Hongchang CHEN, Guozhen CHENG, Weizhen HE, Ke SHANG, Hongchao HU. Design and implementation of adaptive mimic voting device oriented to persistent connection [J]. Journal on Communications, 2022, 43(6): 71-84.
[12]	Xin SONG, Shuyan NI, Zhe ZHANG, Yurong LIAO, Tuofeng LEI. Low error floor LT coding algorithm for unequal error protection [J]. Journal on Communications, 2022, 43(6): 85-97.
[13]	Gangcan SUN, Xinli WU, Wanming HAO, Zhengyu ZHU. Hybrid precoding and power allocation for mmWave NOMA systems based on time delay line arrays [J]. Journal on Communications, 2022, 43(6): 179-188.
[14]	Yanjing SUN, Fengzhi CHENG, Jiasi ZHOU, Song LI. Design of fairness-driven RSMA-SDMA precoding [J]. Journal on Communications, 2022, 43(4): 177-185.
[15]	Yu ZHANG, Xiongwen ZHAO, Xiaoqing WANG, Suiyan GENG, Peng QIN, Zhenyu ZHOU. Robust resource allocation algorithm for multicarrier NOMA security communication system [J]. Journal on Communications, 2022, 43(3): 42-52.