非均匀故障保护的分组修复码构造

doi:10.13190/j.jbupt.2019-026

北京邮电大学学报 ›› 2019, Vol. 42 ›› Issue (5): 75-82.doi: 10.13190/j.jbupt.2019-026

非均匀故障保护的分组修复码构造

王静¹, 刘艳¹, 余春雷¹, 王秘¹, 刘向阳²

1. 长安大学信息工程学院, 西安 710064;
2. 国防科技大学信息通信学院, 西安 710106

收稿日期:2019-03-15 出版日期:2019-10-28 发布日期:2019-11-25
作者简介:王静(1982-),女,教授,硕士生导师,E-mail:jingwang@chd.edu.cn.
基金资助:
陕西省自然科学基金项目（2019JM-386）；中央高校基本科研业务费专项资金项目（300102248104，300102248201，300102248401）；大学生创新创业训练计划项目（201910710071）

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

摘要： 考虑到实际分布式存储系统中存在热度不同的文件，构造了一种基于非均匀故障保护的分组修复码（GRC-NFP），可对热文件和高故障概率节点提供更高等级保护，并降低多故障节点修复的磁盘读取开销.在文件冷热分组后，用所存目标节点故障概率表征数据块故障概率，并排序，存入长度依次递增的多个数据分组，并生成组编码块.性能分析和实际系统部署结果表明，与里德-所罗门码和分组修复码相比，GRC-NFP可在存储开销较小的条件下拥有较高的容错能力和较低的修复局部性，并且使热文件能够受到更有效地保护.系统部署下较少的编码和故障修复时间进一步证明了GRC-NFP的可行性.

关键词: 分布式存储系统, 非均匀故障保护, 分组修复码, 文件可靠性

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

中图分类号:

TN911.2

王静, 刘艳, 余春雷, 王秘, 刘向阳. 非均匀故障保护的分组修复码构造[J]. 北京邮电大学学报, 2019, 42(5): 75-82.

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.

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 1

编辑推荐

Metrics

本文评价