计算机应用 ›› 2017, Vol. 37 ›› Issue (7): 1948-1952.DOI: 10.11772/j.issn.1001-9081.2017.07.1948

• 网络空间安全 • 上一篇    下一篇

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

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

  1. 1. 中国科学院 成都计算机应用研究所, 成都 610041;
    2. 中国科学院大学 计算机与控制学院, 北京 100049
  • 收稿日期:2016-12-28 修回日期:2017-03-07 出版日期:2017-07-10 发布日期:2017-07-18
  • 通讯作者: 徐志强
  • 作者简介:徐志强(1993-),男,河南信阳人,硕士研究生,主要研究方向:存储系统可靠性、网络编码;袁德砦(1989-),男,江苏泰州人,博士研究生,主要研究方向:编码理论、信息安全;陈亮(1990-),男,江西丰城人,博士研究生,主要研究方向:存储系统可靠性、磁盘阵列编码。
  • 基金资助:
    四川省科技厅支撑计划项目(2015GZ0088)。

Regenerating codes construction method based on sparse random matrix

XU Zhiqiang1,2, YUAN Dezhai1,2, CHEN Liang1,2   

  1. 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-10 Published:2017-07-18
  • Supported by:
    This work is partially supported by Sichuan Science & Technology Support Program (2015GZ0088).

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

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

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

中图分类号: