Regenerating codes construction method based on sparse random matrix

doi:10.11772/j.issn.1001-9081.2017.07.1948

Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (7): 1948-1952.DOI: 10.11772/j.issn.1001-9081.2017.07.1948

Previous Articles Next Articles

Regenerating codes construction method based on sparse random matrix

XU Zhiqiang^1,2, YUAN Dezhai^1,2, CHEN Liang^1,2

1. Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu Sichuan 610041, China;
2. School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049, China

Received:2016-12-28 Revised:2017-03-07 Online:2017-07-18 Published:2017-07-10
Supported by:
This work is partially supported by Sichuan Science & Technology Support Program (2015GZ0088).

基于稀疏随机矩阵的再生码构造方法

徐志强^1,2, 袁德砦^1,2, 陈亮^1,2

1. 中国科学院成都计算机应用研究所, 成都 610041;
2. 中国科学院大学计算机与控制学院, 北京 100049

通讯作者: 徐志强
作者简介:徐志强(1993-),男,河南信阳人,硕士研究生,主要研究方向:存储系统可靠性、网络编码;袁德砦(1989-),男,江苏泰州人,博士研究生,主要研究方向:编码理论、信息安全;陈亮(1990-),男,江西丰城人,博士研究生,主要研究方向:存储系统可靠性、磁盘阵列编码。
基金资助:
四川省科技厅支撑计划项目（2015GZ0088）。

Abstract

Abstract: Concerning the problem that the calculations of the existing regenerating code schemes is based on GF(q), and it has high computational complexity and low efficiency, a regenerating code construction method based on sparse random matrix over GF(2) and product matrix framework was proposed. Firstly, file data was arranged in a matrix and the row XOR operation was performed according to encoding matrix. Secondly, local data was encoded by helper nodes according to failed node's encoding vector and sent to repair node. Finally, the failed node's data was decoded by repair node according to received data. The experimental results show that the repair bandwidth of the proposed method is only one-tenth of traditional erasure code at most, and the encoding rate increases by 70% and decoding recovery rate increases by 50% compared with regenerating code based on conventional Vandermonde matrix, which facilitates the application of regenerating code in massive storage system.

Key words: distributed storage reliability, regenerating code, sparse random matrix, repair bandwidth, node failure

摘要： 针对已有的再生码编码方案的运算是基于有限域GF（q）、运算复杂度高、效率低的问题，提出了一种将GF（2）上的稀疏随机矩阵和乘积矩阵框架相结合的再生码构造方法。首先，将文件数据矩阵式排布后根据编码矩阵进行行异或运算；其次，节点失效后，参与帮助节点根据失效节点的编码向量编码本地数据并发送至修复节点；最后，修复节点根据接收到的数据译码出失效节点原有的数据。实验结果表明修复带宽至多只有传统纠删码修复方案的1/10，相比基于传统范德蒙编码矩阵的再生码，编码速率提升了70%，译码恢复速率提升了50%，方便了再生码在大规模存储系统中的应用。

关键词: 分布式存储可靠性, 再生码, 稀疏随机矩阵, 修复带宽, 节点失效

CLC Number:

TP302.8

XU Zhiqiang, YUAN Dezhai, CHEN Liang. Regenerating codes construction method based on sparse random matrix[J]. Journal of Computer Applications, 2017, 37(7): 1948-1952.

徐志强, 袁德砦, 陈亮. 基于稀疏随机矩阵的再生码构造方法[J]. 计算机应用, 2017, 37(7): 1948-1952.

References

[1] 罗象宏,舒继武.存储系统中的纠删码研究综述[J].计算机研究与发展,2012,49(1):1-11.(LUO X L, SHU J W. Summary of research for erasure code in storage system[J]. Journal of Computer Research and Development, 2012, 49(1):1-11.)
[2] SATHIAMOORTHY M, ASTERIS M, PAPAILIOPOULOS D, et al. XORing elephants:novel erasure codes for big data[J]. Proceedings of the VLDB Endowment, 2013, 6(5):325-336.
[3] MCKUSICK K, QUINLAN S. GFS:evolution on fast-forward[J]. Communications of the ACM, 2010, 53(3):42-49.
[4] HUANG C, SIMITCI H, XU Y, et al. Erasure coding in windows azure storage[C]//Proceedings of the 2012 USENIX Conference on Technical Conference. Berkeley:USENIX Association, 2012:2-2.
[5] REED I S, SOLOMON G. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial & Applied Mathematics, 1960, 8(2):300-304.
[6] SUN W, WANG Y, FU Y, et al. A discrete data dividing approach for erasure-code-based storage applications[C]//Proceedings of the 2014 IEEE International Symposium on Service Oriented System Engineering. Piscataway, NJ:IEEE, 2014:308-313.
[7] 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.
[8] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216.
[9] HO T, MéDARD M, KOETTER R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006, 52(10):4413-4430.
[10] SUH C, RAMCHANDRAN K. Exact regeneration codes for distributed storage repair using interference alignment[EB/OL].[2016-12-20]. https://arxiv.org/pdf/1001.0107.pdf.
[11] RASHMI K V, SHAH N B, KUMAR P V. Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction[J]. IEEE Transactions on Information Theory, 2011, 57(57):5227-5239.
[12] 陈亮,张景中,滕鹏国,等.随机二元扩展码:一种适用于分布式存储系统的编码[EB/OL].[2016-12-10]. http://kns.cnki.net/kcms/detail/11.1826.TP.20160929.1711.012.html. (CHEN L, ZHANG J Z, TENG P G, et al. Random Binary Extensive Code (RBEC):an efficient code for distributed storage system[EB/OL].[2016-12-10]. http://kns.cnki.net/kcms/detail/11.1826.TP.20160929.1711.012.html.)
[13] DIMAKIS A G, RAMCHANDRAN K, WU Y, et al. A survey on network codes for distributed storage[J]. Mathematics, 2010, 99(3):476-489.
[14] WU Y, DIMAKIS A G, RAMCHANDRAN K. Deterministic regenerating codes for distributed storage[C]//Proceedings of the 2007 Allerton Conference on Control, Computing, and Communication. Monticello:University of Illinois, 2007:1-5.
[15] SHAH N B, RASHMI K V, KUMAR P V, et al. Distributed storage codes with repair-by-transfer and non-achievability of interior points on the storage-bandwidth tradeoff[J]. IEEE Transactions on Information Theory, 2010, 58(3):1837-1852.
[16] COOPER C. On the rank of random matrices[J]. Random Structures & Algorithms, 2000, 16(2):209-232.
[17] 郝杰,逯彦博,刘鑫吉,等.分布式存储中的再生码综述[J].重庆邮电大学学报(自然科学版),2013,25(1):30-38.(HAO J, LU Y B, LIU X J, et al. Survey for regenerating codes for distributed storage[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2013, 25(1):30-38.)

Regenerating codes construction method based on sparse random matrix

基于稀疏随机矩阵的再生码构造方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 5

Recommended Articles

Metrics

[1]	Lixia XIE, Liping YAN, Hongyu YANG. Node failure ripple effect analysis model for aircraft ad hoc network [J]. Journal of Computer Applications, 2022, 42(2): 493-501.
[2]	LI Jing, LUO Jinfei, LI Bingchao. Reliability analysis models for replication-based storage systems with proactive fault tolerance [J]. Journal of Computer Applications, 2021, 41(4): 1113-1121.
[3]	ZHUO Zhongliu, ZHANG Xiaosong, LI Ruixing, CHEN Ting, ZHANG Jingzhong. Anonymous circuit control method for the onion router based on node failure [J]. Journal of Computer Applications, 2015, 35(10): 2843-2847.
[4]	YANG Yuxing WANG Shiying. Recursive algorithm for k-cycle preclusion problem in k-ary n-cubes [J]. Journal of Computer Applications, 2013, 33(09): 2401-2403.
[5]	XU Xiao-dong Jian-guo CHENG ZHU Shi-rui. Robustness analysis of unstructured P2P botnet [J]. Journal of Computer Applications, 2011, 31(12): 3343-3345.