稀疏随机纠删码:一种大规模数据存储容灾方法

滕鹏国 1; 陈亮 1; 袁德砦 1; 2; 王晓京 1

doi:10.7652/xjtuxb201705008

您当前的位置：

首页 >

文章列表页 >

稀疏随机纠删码:一种大规模数据存储容灾方法

更新时间：2025-07-09

- 稀疏随机纠删码:一种大规模数据存储容灾方法
- Sparse Random Erasure Code: a Fault Tolerance Scheme for Large-Scale Storage System
- 西安交通大学学报 2017年51卷第5期页码：48-53
- 作者机构：
  
  1. 中国科学院成都计算机应用研究所,成都,610041
  2. 中国科学院大学,北京,100049
- 作者简介：
- 基金信息：
  
  : 2016-11-06。作者简介: 滕鹏国(1986—),男,博士生;王晓京(通信作者),男,研究员。基金项目: 国家自然科学基金资助项目(61501064);四川省科技厅支撑计划资助项目(2015GZ0088)
- DOI：10.7652/xjtuxb201705008
  中图分类号： TP333
- 网络首发：2017-05-10，
  
  纸质出版：2017
- 稿件说明：
移动端阅览
滕鹏国 1, 陈亮 1, 袁德砦 1, 等. 稀疏随机纠删码:一种大规模数据存储容灾方法[J]. 西安交通大学学报, 2017,51(5):48-53.

Sparse Random Erasure Code: a Fault Tolerance Scheme for Large-Scale Storage System[J]. 2017, 51(5): 48-53.
滕鹏国 1, 陈亮 1, 袁德砦 1, 等. 稀疏随机纠删码:一种大规模数据存储容灾方法[J]. 西安交通大学学报, 2017,51(5):48-53. DOI： 10.7652/xjtuxb201705008.

Sparse Random Erasure Code: a Fault Tolerance Scheme for Large-Scale Storage System[J]. 2017, 51(5): 48-53. DOI： 10.7652/xjtuxb201705008.

摘要

针对海量数据存储容灾系统中对扩展性、可靠性及高效性方面的需求

提出了一种高容灾可扩展且能够高概率译码恢复的高效大数据存储容灾算法。该算法利用等行重稀疏随机矩阵高概率行满秩的性质

用来实现数据高效可靠的存储容灾。首先

根据存储系统规模及容灾需求设置相应的编码参数; 然后

采用等行重稀疏随机矩阵构造校验矩阵

并且产生相应的生成矩阵; 最后

将数据文件分块编码到n个存储节点上

实现不同规模、不同容灾需求下的数据容灾存储

并通过设置合理的随机冗余

从而实现对译码成功率的控制。实验和理论分析表明:算法所提存储容灾技术可实现容灾能力不受素数或有限域大小的限制

而是根据存储规模及容灾需求灵活扩展; 基于合理的随机冗余

译码成功率趋于1

实现了高可靠的数据容灾存储; 在较大规模存储系统中

算法编译码速率是相应经典RS和CRS编码方案的2倍以上

并在较大码长下具有近似最大距离可分(MDS)的性质

可达到近似最优的存储空间利用率。

Abstract

To meet the requirements for the scalability

reliability and high efficiency of data storage in large-scale storage system

a new kind of efficient storage fault-tolerance algorithm with flexible scalability and high probability of decoding is proposed

named sparse random erasure code(SREC). The property of sparse random matrix with equal row weight is used in the algorithm. Firstly

the coding parameters are designed according to the scale of storage system and the requirement of fault tolerance; then

the parity check matrix and the corresponding generator matrix are constructed by using sparse random matrix; finally

the files are segmented into blocks and the parity blocks are created by encoding procedure

thus the data storage with different fault-tolerance requirements is realized. Meanwhile

by setting proper random redundancy

the probability of successful decoding is made controllable. Simulation results and theoretical analysis show that the proposed algorithm makes the fault-tolerance capability not have to be restricted by the prime or the size of finite field

and that based on the proper random redundancy

the successful decoding probability trends to 1

thus achieving the high reliability of data storage. Furthermore

the speeds of encoding and decoding are twice or more than those of classic RS and CRS algorithms

and when the code length is long enough

this algorithm has approximate optimal storage efficiency.

关键词

Keywords

references

BLAUM M, BRADY J, BRUCK J, et al. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures [J]. IEEE Transactions on Computers, 1995, 44(2): 192-202.

XU L, BRUCK J. X-code: MDS array codes with optimal encoding [J]. IEEE Transactions on Information Theory, 1999, 45(1): 272-276.

CORBETT P, ENGLISH B, GOEL A, et al. Row-diagonal parity for double disk failure correction [EB/OL]. [2016-10-26]. https: ∥www.usenix.org/legacy/publications/library/proceedings/fast04/tech/corbett/corbett_html/.[4] LI M, SHU J, ZHENG W. GRID codes: Strip-based erasure codes with high fault tolerance for storage systems [J]. ACM Transactions on Storage, 2009, 4(4): NO. 15.

PLANK J S, XU L. Optimizing Cauchy Reed-Solomon codes for fault-tolerant network storage applications [C]∥Proceedings of the Network Computing and Applications. Piscataway, NJ, USA: IEEE, 2006: 173-180.

TAMO I, BARG A. A family of optimal locally recoverable codes [J]. IEEE Transactions on Information Theory, 2013, 60(8): 4661-4676.

PLANK J S, BLAUM M. Sector-disk(SD)erasure codes for mixed failure modes in RAID systems [J]. ACM Transactions on Storage, 2014, 10(1): 4-20.

BLAUM M, PLANK J S, SCHWARTZ M, et al. Partial MDS(PMDS)and sector-disk(SD)codes that tolerate the erasure of two random sectors [C]∥Proceedings of the 2014 IEEE International Symposium on Information Theory. Piscataway, NJ, USA: IEEE, 2014: 1792-1796.

LI M, LEE P P. STAIR codes: a general family of erasure codes for tolerating device and sector failures in practical storage systems [EB/OL]. [2016-10-26]. https: ∥www.usenix.org/system/files/conference/fast 14/fast14-paper_li-mingqiang.pdf.

LUBY M G, MITZENMACHER M, SHOKROLLAHI M A, et al. Practical loss-resilient codes [C]∥Proceedings of the 29th Annual ACM Symposium on Theory of Computing. New York, USA: ACM, 1997: 150-159.

KOLCHIN V F. Random graphs [M]. Cambridge, UK: Cambridge University Press, 1999: 16-29.

LUBY M. LT codes [C]∥Proceedings of the 43rd Symposium on Foundations of Computer Science. Piscataway, NJ, USA: IEEE, 2002: 271-280.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

R-dedup: 一种重复数据删除指纹计算的优化方法

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究

超临界水异常区域热力学特性研究

电子级超纯氮深冷空分流程节能优化研究

三塔合一间接空冷系统结构参数对夏季运行特性的影响研究