Sparse Random Erasure Code: a Fault Tolerance Scheme for Large-Scale Storage System

doi:10.7652/xjtuxb201705008

您当前的位置：

首页 >

文章列表页 >

Sparse Random Erasure Code: a Fault Tolerance Scheme for Large-Scale Storage System

更新时间：2025-07-09

- Sparse Random Erasure Code: a Fault Tolerance Scheme for Large-Scale Storage System
- Vol. 51, Issue 5, Pages: 48-53(2017)
- 作者机构：
  
  1. 中国科学院成都计算机应用研究所,成都,610041
  2. 中国科学院大学,北京,100049
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201705008
  CLC： TP333
- Online First：10 May 2017，
  
  Published：2017
- 稿件说明：
移动端阅览
Sparse Random Erasure Code: a Fault Tolerance Scheme for Large-Scale Storage System[J]. 2017, 51(5): 48-53.
DOI：

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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

R-dedup: A Performance Improvement Strategy for Fingerprint Calculation of Data De-Duplication

Electrothermal Coupling Research on the Evolutionary Law of Anti-Corona Performance for High-Altitude Air-Cooled Generators

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

A Fast Calculation Method for Thermal Flow Fields in Transformer Windings Based on PI-DeepONet

Research on the Electrohydrodynamic Effects of Ionic Liquid-Modified Fuels

Related Author

王龙翔 1

董凯 2

王鹏博 1

董小社 1

张兴军 1

朱正东 1

张利平 1

Related Institution

School of Computer Science and Technology, Xi’an Jiaotong University

⁰