Construction of Group Repairable Codes for Non-Uniform Fault Protection

doi:10.13190/j.jbupt.2019-026

JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM ›› 2019, Vol. 42 ›› Issue (5): 75-82.doi: 10.13190/j.jbupt.2019-026

Previous Articles Next Articles

Construction of Group Repairable Codes for Non-Uniform Fault Protection

WANG Jing¹, LIU Yan¹, YU Chun-lei¹, WANG Mi¹, LIU Xiang-yang²

1. School of Information Engineering, Chang'an University, Xi'an 710064, China;
2. College of Information and Communication, National University of Defense Technology, Xi'an 710106, China

Received:2019-03-15 Online:2019-10-28 Published:2019-11-25

Abstract

Abstract: Considering that there are files with different heat in actual distributed storage systems, a class of group repairable codes based on non-uniform fault protection (GRC-NFP) is proposed. GRC-NFP provides higher protection for hot files and nodes with high fault probability, and reduces the disk I/O overhead for repairing multiple failed nodes. Specifically, after hot and cold grouping, the fault probabilities of data blocks are represented and sorted by that of the stored target nodes. Data blocks are stored into multiple data groups with increasing lengths, and group encoded blocks are further generated. Performance analysis and actual system deployment showed that GRC-NFP had higher fault tolerance and lower repair locality under less storage overhead compared with Reed-Solomon codes and group repairable codes. Moreover, the hot files can be protected more effectively by adopting GRC-NFP. The fewer coding and fault repair time under system deployment further proved the feasibility of GRC-NFP.

Key words: distributed storage system, non-uniform fault protection, group repairable codes, file reliability

CLC Number:

TN911.2

WANG Jing, LIU Yan, YU Chun-lei, WANG Mi, LIU Xiang-yang. Construction of Group Repairable Codes for Non-Uniform Fault Protection[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2019, 42(5): 75-82.

References

[1] Shahabinejad M, Khabbazian M, Ardakani M. An efficient binary locally repairable code for Hadoop distributed file system[J]. IEEE Communications Letters, 2014, 18(8):1287-1290.
[2] Ghemawat S, Gobioff H, Leung S T. The Google file system[J]. ACM SIGOPS Operating Systems Review, 2003, 37(5):29-43.
[3] Lee O T, Kumar S D M, Chandran P. Erasure coded storage systems for cloud storage-challenges and opportunities[C]//3^rd International Conference on Data Science and Engineering (ICDSE). Cochin:IEEE Press, 2016:52-58.
[4] Li J, Li B. Erasure coding for cloud storage systems:a survey[J]. Tsinghua Science and Technology, 2013, 18(3):259-272.
[5] Wu Y. Existence and construction of capacity-achieving network codes for distributed storage[J]. IEEE Journal on Selected Areas in Communications, 2010, 28(2):277-288.
[6] Koetter R, Medard M. An algebraic approach to network coding[J]. ACM Transactions on Networking, 2003, 11(5):782-795.
[7] Ahlswede R, Cai N, Li S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216.
[8] Dimakis A G, Godfrey P B, Wu Y, et al. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory, 2010:56(9):4539-4551.
[9] Oggier F, Datta A. Self-repairing homomorphic codes for distributed storage systems[C]//2011 Proceedings IEEE INFOCOM. Shanghai:IEEE Press, 2011:1215-1223.
[10] Gopalan P, Huang C, Simitci H, et al. On the locality of codeword symbols[J]. IEEE Transactions on Information Theory, 2012, 58(11):6925-6934.
[11] Papailiopoulos D S, Dimakis A G. Locally repairable codes[C]//2012 IEEE International Symposium on Information Theory Proceedings (ISIT). Cambridge:IEEE Press, 2012:2771-2775.
[12] 林轩. GRC:一种适用于多节点失效的高容错低修复成本纠删码[J]. 计算机研究与发展, 2014, 51(S):172-181. Lin Xuan. GRC:a high fault tolerant low repair cost erasure code for multi-node failures[J]. Journal of Computer Research and Development, 2014, 51(S):172-181.
[13] Chang L P. Hybrid solid-state disks:combining heterogeneous NAND flash in large SSDs[C]//Proceedings of the 13^th ACM International Conference on Asia and South Pacific Design Automation Conference. Seoul:IEEE Press, 2008:428-433.
[14] Yim K S, Bahn H, Koh K. A flash compression layer for smart media card systems[J]. IEEE Transactions on Consumer Electronics, 2004, 50(1):192-197.
[15] Kim K, Jung S, Song Y H. Compression ratio based hot/cold data identification for flash memory[C]//2011 IEEE International Conference on Consumer Electronics. Las Vegas:IEEE Press, 2011:33-34.
[16] 邓俊杰. 云存储中基于非均匀保护策略的纠删码技术研究与实现[D]. 长沙:湖南大学, 2017.

Construction of Group Repairable Codes for Non-Uniform Fault Protection

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments