基于多斜率码链的阵列纠删码

doi:10.11772/j.issn.1001-9081.2017.04.0936

计算机应用 ›› 2017, Vol. 37 ›› Issue (4): 936-940.DOI: 10.11772/j.issn.1001-9081.2017.04.0936

• 大数据与云计算及其应用 • 上一篇下一篇

基于多斜率码链的阵列纠删码

唐聃, 杨昊澎, 王福超

成都信息工程大学软件工程学院, 成都 610225

收稿日期:2016-10-08 修回日期:2016-11-25 出版日期:2017-04-10 发布日期:2017-04-19
通讯作者: 唐聃
作者简介:唐聃(1982-),男,四川成都人,副教授,博士,CCF会员,主要研究方向:大数据、云计算、编码理论。
基金资助:
国家自然科学基金资助项目（61501064，61501063）；四川省青年科技基金资助项目（2017JQ0057）。

Array erasure codes based on coding chains with multiple slopes

TANG Dan, YANG Haopeng, WANG Fuchao

College of Software Engineering, Chengdu University of Information Technology, Chengdu Sichuan 610225, China

Received:2016-10-08 Revised:2016-11-25 Online:2017-04-10 Published:2017-04-19
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61501064, 61501063), the Youth Science and Technology Fund of Sichuan Province (2017JQ0057).

摘要/Abstract

摘要： 针对当前大多阵列纠删码容错能力偏低以及构造时需要满足的约束条件较强的问题，提出一类基于码链构造的阵列纠删码。该阵列纠删码使用不同斜率码链组织数据元素和校验元素间的关系，从而能达到理论上不受限制的容错能力；而在构造时避开了类似素数约束的强约束条件，易于实用和扩展。仿真实验结果表明，相对于RS（Reed-Solomon）码，基于多斜率码链阵列纠删码在运算效率上的提升超过了2个数量级；在固定的容错能力下，存储效率能随着条块尺寸的增加而提高。此外，该类阵列码的修复代价和更新代价为一个固定常量，不会随着系统规模的扩大或容错能力的提高而增加。

关键词: 阵列纠删码, 容错, 码链, 条块尺寸

Abstract: In view of the problem that the fault tolerance capability is low and strong constraint conditions need to be satisfied in the construction of most array erasure codes at present, a new type of array erasure codes based on coding chains was proposed. In the new array erasure codes, coding chains with different slopes were used to organize the relationship among data elements and check elements, so as to achieve infinite fault tolerance capability in theory; the strong constraint conditions like the prime number limitation was avoided in construction, which is easy to be practical and extensible. Simulation results show that, compared with Reed-Solomon codes (RS codes), the efficiency of the proposed array erasure codes based on coding chains is more than 2 orders of magnitude; under the condition of fixed fault tolerance, its storage efficiency can be improved with the increase of the strip size. In addition, the update penalty and repair cost of the array codes is a fixed constant, which will not increase with the expansion of the storage system scale or the increase of fault tolerance capability.

Key words: array erasure code, fault tolerance, coding chain, strip size

中图分类号:

TP302.8

唐聃, 杨昊澎, 王福超. 基于多斜率码链的阵列纠删码[J]. 计算机应用, 2017, 37(4): 936-940.

TANG Dan, YANG Haopeng, WANG Fuchao. Array erasure codes based on coding chains with multiple slopes[J]. Journal of Computer Applications, 2017, 37(4): 936-940.

参考文献

[1] 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.
[2] SCHROEDER B, GIBSON G A. Disk failures in the real world: what does an MTTF of 1000000 hours mean to you?[C]//FAST 2007: Proceedings of the 5th USENIX Conference on File and Storage Technologies. Berkeley, CA: USENIX Association, 2007:1-16.
[3] PLANK J S, XU L. Optimizing Cauchy Reed-Solomon codes for fault-tolerant network storage applications[C]//NCA 2006: Proceedings of the Fifth IEEE International Symposium on Network Computing and Applications. Washington, DC: IEEE Computer Society, 2006:173-180.
[4] PLANK J S, GREENAN K M, MILLER E L. Screaming fast Galois field arithmetic using Intel SIMD instructions[C]//FAST 2013: Proceedings of the 11th USENIX Conference on File and Storage Technologies. Berkeley, CA: USENIX Association, 2013: 299-306.
[5] JANAKIRAM B, CHANDRA M G, ARAVIND K G, et al. SpreadStore: a LDPC erasure code scheme for distributed storage system[C]//Proceedings of the 2010 International Conference on Data Storage and Data Engineering. Piscataway, NJ: IEEE, 2010: 154-158.
[6] 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.
[7] XU L, BRUCK J. X-code: MDS array codes with optimal encoding[J]. IEEE Transactions on Information Theory, 1999, 45(1): 272-276.
[8] HUANG C, XU L. STAR: an efficient coding scheme for correcting triple storage node failures[J]. IEEE Transactions on Computers, 2008, 57(7): 889-901.
[9] 孟庆春. 应用于分布式存储系统上的纠删码技术研究[D]. 北京: 中国科学院研究生院, 2007.(MENG Q C. Research of erasure codes applied in distributed storage system[D]. Beijing: Graduate University of the Chinese Academy of Sciences, 2007.)
[10] HAFNER J L. WEAVER codes: highly fault tolerant erasure codes for storage systems[C]//FAST 2005: Proceedings of the 4th Conference on USENIX Conference on File and Storage Technologies. Berkeley, CA: USENIX Association, 2005, 4: 211-224.
[11] HAFNER J L. HoVer erasure codes for disk arrays[C]//DSN 2006: Proceedings of the 2006 International Conference on Dependable Systems and Networks. Washington, DC: IEEE Computer Society, 2006: 217-226.
[12] 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): Article No. 15.
[13] 陈峥. 一类新的阵列纠删码理论及应用研究[D]. 北京: 中国科学院研究生院, 2009.(CHEN Z. A class of array erasure codes and their applications[D]. Beijing: Graduate University of the Chinese Academy of Sciences, 2009.)
[14] 唐聃, 舒红平. 一类多容错的阵列纠删码[J]. 中国科学: 信息科学, 2016, 46(4): 523-538.(TANG D, SHU H P. A class of array erasure codes with high fault-tolerance[J]. Science China: Information Sciences, 2016, 46(4): 523-538.)

[1]	杨龙海, 王学渊, 蒋和松. 改进SM2签名方法的区块链数字签名方案[J]. 计算机应用, 2021, 41(7): 1983-1988.
[2]	李静, 罗金飞, 李炳超. 主动容错副本存储系统的可靠性分析模型[J]. 计算机应用, 2021, 41(4): 1113-1121.
[3]	刘宇, 朱朝阳, 李金泽, 劳源基, 覃团发. 检测型的联盟区块链共识算法d-PBFT[J]. 计算机应用, 2021, 41(3): 756-762.
[4]	林腾涛, 查思明, 陈蕾, 龙显忠. 图趋势过滤诱导的噪声容错多标记学习模型[J]. 计算机应用, 2021, 41(1): 8-14.
[5]	李靖, 景旭, 杨会君. 基于实用拜占庭容错算法的区块链电子计票方案[J]. 计算机应用, 2020, 40(4): 954-960.
[6]	王可可, 陈志德, 徐健. 基于联盟区块链的农产品质量安全高效追溯体系[J]. 计算机应用, 2019, 39(8): 2438-2443.
[7]	甘俊, 李强, 陈子豪, 张超. 区块链实用拜占庭容错共识算法的改进[J]. 计算机应用, 2019, 39(7): 2148-2155.
[8]	王海勇, 郭凯璇, 潘启青. 基于投票机制的拜占庭容错共识算法[J]. 计算机应用, 2019, 39(6): 1766-1771.
[9]	贾梦瑶, 王兴伟, 张爽, 易波, 黄敏. 基于软件定义网络的卫星网络容错路由机制[J]. 计算机应用, 2019, 39(6): 1772-1779.
[10]	潘建国, 李豪. 基于实用拜占庭容错的物联网入侵检测方法[J]. 计算机应用, 2019, 39(6): 1742-1746.
[11]	杨玉星, 李晓慧. 超立方体网络的3路结构连通度及子结构连通度[J]. 计算机应用, 2019, 39(2): 509-512.
[12]	郭荣佐, 冯朝胜, 秦志光. 物联网智能物流系统容错服务组合建模与分析[J]. 计算机应用, 2019, 39(2): 589-597.
[13]	李静, 刘冬实. 主动容错云存储系统的可靠性评价模型[J]. 计算机应用, 2018, 38(9): 2631-2636.
[14]	白平, 张薇. 多属性环境下基于容错学习的全同态加密方案[J]. 计算机应用, 2018, 38(5): 1377-1382.
[15]	徐佳庆, 万文, 蔡东京, 唐付桥, 何杰, 张磊. 高维胖树系统中确定性路由容错策略实现[J]. 计算机应用, 2018, 38(5): 1393-1398.

基于多斜率码链的阵列纠删码

Array erasure codes based on coding chains with multiple slopes

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics