低编译复杂度的双容错阵列码

doi:10.11772/j.issn.1001-9081.2022091344

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (9): 2766-2774.DOI: 10.11772/j.issn.1001-9081.2022091344

低编译复杂度的双容错阵列码

解峥¹^,², 王子豪¹^,², 唐聃¹^,²(), 张航³, 蔡红亮¹^,²

^1.成都信息工程大学软件工程学院, 成都 610225
^2.四川省信息化应用支撑软件工程技术研究中心, 成都 610225
^3.中国电子科技集团第三十研究所, 成都 610041

收稿日期:2022-09-15 修回日期:2022-12-16 接受日期:2022-12-21 发布日期:2023-02-24 出版日期:2023-09-10
通讯作者: 唐聃
作者简介:解峥（1997—），男，河南濮阳人，硕士研究生，主要研究方向：编码理论、分布式存储
王子豪（1997—），男，重庆人，硕士研究生，主要研究方向：编码理论、分布式存储
张航（1995—），男，四川乐山人，硕士，主要研究方向：编码理论、分布式存储
蔡红亮（1983—），男，山西临汾人，讲师，博士，主要研究方向：编码理论、视觉密码。
基金资助:
四川省科技厅重大专项(2022ZDZX0001);四川省科技厅重点研发项目(2022YFG0033)

Double fault tolerant array code with low compilation complexity

Zheng XIE¹^,², Zihao WANG¹^,², Dan TANG¹^,²(), Hang ZHANG³, Hongliang CAI¹^,²

^1.School of Software Engineering，Chengdu University of Information Technology，Chengdu Sichuan 610225，China
^2.Sichuan Province Informatization Application Support Software Engineering Technology Research Center，Chengdu Sichuan 610225，China
^3.The 30th Research Institute of China Electronics Technology Group Corporation，Chengdu Sichuan 610041，China

Received:2022-09-15 Revised:2022-12-16 Accepted:2022-12-21 Online:2023-02-24 Published:2023-09-10
Contact: Dan TANG
About author:XIE Zheng， born in 1997， M. S. candidate. His research interests include coding theory， distributed storage.
WANG Zihao， born in 1997， M. S. candidate. His research interests include coding theory， distributed storage.
ZHANG Hang， born in 1995， M. S. His research interests include coding theory， distributed storage.
CAI Hongliang， born in 1983， Ph. D.， lecturer. His research interests include coding theory， visual cryptography.
Supported by:
Major Project of Science and Technology Department of Sichuan Province(2022ZDZX0001);Key Research and Development Program of Science and Technology Department of Sichuan Province(2022YFG0033)

摘要/Abstract

摘要：

纠删码技术是独立磁盘冗余阵列-6（RAID-6）的双容错能力的底层实现技术，它的性能是左右RAID-6性能的重要因素。针对RAID-6中常用阵列纠删码的I/O不平衡和数据恢复速度慢的问题，提出一种基于异或（XOR）的混合阵列码——J码（J-code）。J-code采用新的校验生成规则，首先，利用原始数据构造的二维阵列计算出对角校验位并构造新的阵列；然后，利用新阵列中数据块之间的位置关系计算得到反对角校验位。此外，J-code将原始数据与部分校验位存储于同一磁盘，能减少编译码过程中的异或（XOR）操作次数和单盘恢复过程中读取数据块的个数，从而降低编译码复杂度和单盘故障修复的I/O成本，缓解磁盘热点集中现象。仿真实验结果表明，相较于RDP（Row-Diagonal Parity）、EaR（Endurance-aware RAID-6）等阵列码，J-code的编码时间减少了0.30%~28.70%，单磁盘故障和双磁盘故障的修复用时分别减少了2.23%~31.62%和0.39%~36.00%。

关键词: 独立磁盘冗余阵列-6, 阵列纠删码, 容错, 编译码复杂度, 磁盘故障修复

Abstract:

Erasure coding is the underlying implementation technology of double fault tolerance for Redundant Array of Independent Disks-6 （RAID-6）， and the performance of erasure code is one of the important factors affecting the performance of RAID-6. Aiming at the problems of I/O imbalance and slow data recovery of array erasure codes commonly used in RAID-6， an Exclusive OR （XOR） based hybrid array code was proposed， namely J-code. A new parity check generation rule was adopted by J-code. Firstly， two-dimensional array constructed from the original data was used to calculate the diagonal parity bits and construct a new array. Then， the positional relationship between the data blocks in the new array was used to calculate the anti-diagonal parity bits. Besides， the original data and part of the parity bits were stored by J-code on the same disk， which reduced the number of XOR operations in the process of encoding and decoding as well as the number of data blocks read in the recovery process of a single disk， thereby reducing the complexity of encoding and decoding as well as the I/O cost for repairing a single disk， and alleviating the phenomenon of disk hotspot concentration. Simulation results show that compared with array codes such as RDP （Row-Diagonal Parity） and EaR （Endurance-aware RAID-6）， J-code has the encoding time reduced by 0.30% to 28.70%， the single disk failure repair time reduced by 2.23% to 31.62%， and the double disk failure repair time reduced by 0.39% to 36.00%.

Key words: Redundant Array of Independent Disks-6 (RAID-6), array erasure code, fault tolerance, encoding and decoding complexity, disk failure repair

中图分类号:

TP302.8

解峥, 王子豪, 唐聃, 张航, 蔡红亮. 低编译复杂度的双容错阵列码[J]. 计算机应用, 2023, 43(9): 2766-2774.

Zheng XIE, Zihao WANG, Dan TANG, Hang ZHANG, Hongliang CAI. Double fault tolerant array code with low compilation complexity[J]. Journal of Computer Applications, 2023, 43(9): 2766-2774.

图/表 15

图1 J-code的生成过程

Fig. 1 Process of J-code generation

图2 J-code的反对角校验集

Fig. 2 J-code anti-diagonal parity set

图3 反对角校验集与磁盘3的对应关系

Fig. 3 Relationship between anti-diagonal parity set and disk3

图4 双磁盘故障恢复过程

Fig. 4 Double disk failure repair process

图5 由式（7）构造的矩阵的一般形式

Fig. 5 General form of matrix constructed by equation （7）

图6 由式（9）构造的矩阵的一般形式

Fig. 6 General form of matrix constructed by equation （9）

图7 由式（10）构造的矩阵的一般形式

Fig. 7 General form of matrix constructed by equation （10）

图8 两种校验集与不相交磁盘的关系

Fig. 8 Relationships between tow parity sets and disjoint disks

表1 不同纠删码的存储利用率计算公式

Tab. 1 Formulas for calculating storage utilization of different erasure codes

纠删码	存储利用率
EVENODD	$p / p + 2$
RDP	$p - 1 / p + 1$
X-code	$p - 2 / p$
N-code	$p - 1 / p + 1$
EaR	$(p - 1) 2 / p 2$
J-code	$p p - 2 / p 2 - 1$

表1 不同纠删码的存储利用率计算公式

Tab. 1 Formulas for calculating storage utilization of different erasure codes

纠删码	存储利用率
EVENODD	$p / p + 2$
RDP	$p - 1 / p + 1$
X-code	$p - 2 / p$
N-code	$p - 1 / p + 1$
EaR	$(p - 1) 2 / p 2$
J-code	$p p - 2 / p 2 - 1$

图9 不同纠删码的存储利用率对比

Fig. 9 Comparison of storage utilization of different erasure codes

表2 不同纠删码的编码和译码复杂度计算公式

Tab. 2 Calculation formulas of encoding and decoding complexity of different erasure codes

纠删码	编码复杂度	译码复杂度
EVENODD	$2 p 2 - 5 p + 2 (p - 1) 2$	$2 p 2 - 4 p + 1 (p - 1) 2$
RDP	$2 p 2 - 6 p + 2 (p - 1) 2$	$2 p 2 - 6 p + 4 (p - 1) 2$
X-code	$2, p = 3 2 (p - 3) p - 2, p > 3$	$2, p = 3 2 (p - 3) p - 2, p > 3$
N-code	$2 (p - 2) p - 1$	$2 (p - 2) p - 1$
EaR	$2 p 2 - 6 p + 3 (p - 1) 2$	$4 p 2 - 13 p + 9 2 (p - 1) 2$
J-code	$2 p 2 - 6 p + 2 p (p - 2)$	$2 p 2 - 7 p + 4 p (p - 2)$

表2 不同纠删码的编码和译码复杂度计算公式

Tab. 2 Calculation formulas of encoding and decoding complexity of different erasure codes

纠删码	编码复杂度	译码复杂度
EVENODD	$2 p 2 - 5 p + 2 (p - 1) 2$	$2 p 2 - 4 p + 1 (p - 1) 2$
RDP	$2 p 2 - 6 p + 2 (p - 1) 2$	$2 p 2 - 6 p + 4 (p - 1) 2$
X-code	$2, p = 3 2 (p - 3) p - 2, p > 3$	$2, p = 3 2 (p - 3) p - 2, p > 3$
N-code	$2 (p - 2) p - 1$	$2 (p - 2) p - 1$
EaR	$2 p 2 - 6 p + 3 (p - 1) 2$	$4 p 2 - 13 p + 9 2 (p - 1) 2$
J-code	$2 p 2 - 6 p + 2 p (p - 2)$	$2 p 2 - 7 p + 4 p (p - 2)$

图10 编码复杂度和译码复杂度对比

Fig. 10 Comparison of encoding complexity and decoding complexity

表3 不同纠删码的单磁盘故障修复硬盘读取次数计算公式

Tab. 3 Calculation formulas of read times for single disk failure repair of different erasure codes

纠删码	单磁盘修复硬盘读取次数
EVENODD	$3 (p - 1) 2 / 4$
RDP	$3 (p - 1) 2 / 4$
X-code	$3, p = 3 3 p 2 - 8 p + 13 / 4, p > 3$
N-code	$3 (p - 1) 2 / 4$
EaR	$3 p 2 - 8 p + 9 / 4$
J-code	$2, p = 3 3 p 2 - 8 p + 5 / 4, p > 3 且 p - 1 / 2 为偶数 3 p 2 - 8 p + 9 / 4, p > 3 且 p - 1 / 2 为奇数$

表3 不同纠删码的单磁盘故障修复硬盘读取次数计算公式

Tab. 3 Calculation formulas of read times for single disk failure repair of different erasure codes

纠删码	单磁盘修复硬盘读取次数
EVENODD	$3 (p - 1) 2 / 4$
RDP	$3 (p - 1) 2 / 4$
X-code	$3, p = 3 3 p 2 - 8 p + 13 / 4, p > 3$
N-code	$3 (p - 1) 2 / 4$
EaR	$3 p 2 - 8 p + 9 / 4$
J-code	$2, p = 3 3 p 2 - 8 p + 5 / 4, p > 3 且 p - 1 / 2 为偶数 3 p 2 - 8 p + 9 / 4, p > 3 且 p - 1 / 2 为奇数$

图11 不同纠删码的单磁盘故障修复磁盘读取次数对比

Fig. 11 Comparison of read times among different erasure codes for single disk failure repair

表4 不同编码参数p下的用时对比

Tab. 4 Comparison of time consumption under different encoding parameter p

p	纠删码	编码用时/ms	单磁盘故障修复用时/ms	双磁盘故障修复用时/ms
3	EVENODD	2 091	103	2 141
	RDP	1 869	100	1 812
	X-code	1 010	136	2 372
	N-code	1 952	102	1 800
	EaR	1 932	104	1 733
	J-code	1 491	93	1 518
5	EVENODD	1 805	338	1 114
	RDP	1 692	327	1 074
	X-code	1 507	349	1 245
	N-code	1 663	333	1 072
	EaR	1 859	307	1 013
	J-code	1 653	279	1 009
7	EVENODD	1 581	472	1 416
	RDP	1 475	463	1 363
	X-code	1 432	490	1 386
	N-code	1 506	470	1 353
	EaR	1 580	448	1 330
	J-code	1 471	438	1 170

参考文献 25

1	PATTERSON D A， GIBSON G， KATZ R H. A case for redundant arrays of inexpensive disks （RAID）［C］// Proceedings of the 1988 ACM SIGMOD international conference on Management of data. New York： ACM， 1988： 109-116. 10.1145/50202.50214
2	PLANK J S， LUO J Q， SCHUMAN C D， et al. a performance evaluation and examination of open-source erasure coding libraries for storage［C］// Proceedings of the 7th USENIX Conference on File and Storage Technologies. Berkeley， CA： USENIX Association， 2009， 9： 253-265.
3	CORBETT P， ENGLISH B， GOEL A， et al. Row-diagonal parity for double disk failure correction［C］// Proceedings of the 3rd USENIX Conference on File and Storage Technologies. Berkeley： USENIX Association， 2004： 1-14.
4	SCHROEDER B， GIBSON G A. Understanding disk failure rates： what does an MTTF of 1，000，000 hours mean to you？［J］. ACM Transactions on Storage， 2007， 3（3）： No.8. 10.1145/1288783.1288785
5	PINHEIRO E， WEBER W D， BARROSO L A. Failure trends in a large disk drive population［C］// Proceedings of the 5th USENIX Conference on File and Storage Technologies. Berkeley： USENIX Association， 2007： 17-28.
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. 10.1109/12.364531
7	XU L H， BRUCK J. X-code： MDS array codes with optimal encoding［J］. IEEE Transactions on Information Theory， 1999， 45（1）： 272-276. 10.1109/18.746809
8	罗象宏，舒继武. 存储系统中的纠删码研究综述［J］. 计算机研究与发展， 2012， 49（1）：1-11.
	LUO X H， SHU J W. Summary of research for erasure code in storage system［J］. Journal of Computer Research and Development， 2012， 49（1）：1-11.
9	XIE P， YUAN Z， HUANG J Z， et al. N-Code： an optimal RAID-6 MDS array code for load balancing and high I/O performance［C］// Proceedings of the 48th International Conference on Parallel Processing. New York： ACM， 2019： No.34. 10.1145/3337821.3337829
10	LIANG N J， ZHANG X J， WU X R， et al. An endurance-aware RAID-6 code with low computational complexity and write overhead［C］// Proceedings of the 19th IEEE International Symposium on Parallel and Distributed Processing with Applications/ 11th International Conference on Big Data and Cloud Computing/ 14th International Conference on Social Computing and Networking/ 11th International Conference on Sustainable Computing and Communications. Piscataway： IEEE， 2021： 939-946. 10.1109/ispa-bdcloud-socialcom-sustaincom52081.2021.00132
11	LIANG N J， ZHANG X J， CHEN H， et al. Thou code： a triple-erasure-correcting horizontal code with optimal update complexity［J］. The Journal of Supercomputing， 2022， 78（7）： 10088-10117. 10.1007/s11227-021-04271-9
12	HUANG S Y， HOU H X， YU X S. A lower bound on disk reads for single information disk failure recovery and one recovery scheme for EVENODD（p， 3）［C］// Proceedings of the 9th International Workshop on Signal Design and its Applications in Communications. Piscataway： IEEE， 2019： 1-5. 10.1109/iwsda46143.2019.8966126
13	DENG M Z， ZHU L Y， XIAO N， et al. X-code+： a compromised coding scheme with smaller rebuild window and load-balance［C］// Proceedings of the 4th International Conference on Computer Science and Network Technology. Piscataway： IEEE， 2015： 254-261. 10.1109/iccsnt.2015.7490747
14	FU Y X， SHU J W， SHEN Z R， et al. Reconsidering single disk failure recovery for erasure coded storage systems： optimizing load balancing in stack-level［J］. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（5）： 1457-1469. 10.1109/tpds.2015.2442979
15	LI Y K， WANG N， TIAN C J， et al. A hierarchical RAID architecture towards fast recovery and high reliability［J］. IEEE Transactions on Parallel and Distributed Systems， 2018， 29（4）： 734-747. 10.1109/tpds.2017.2775231
16	CHEN X， CAI S H， MA X. HVD code： a class of MDS array codes for tolerating triple disk failures［J］. IET Communications， 2019， 13（6）： 748-757. 10.1049/iet-com.2018.6126
17	SHEN Z R， SHU J W， FU Y X. HY code： an all-around MDS code for RAID-6 storage systems［J］. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（6）： 1674-1686. 10.1109/tpds.2015.2464800
18	HUANG Z J， JIANG H， SHEN Z R， et al. Optimal encoding and decoding algorithms for the RAID-6 Liberation codes［C］// Proceedings of the 2020 IEEE International Parallel and Distributed Processing Symposium. Piscataway： IEEE， 2020： 708-717. 10.1109/ipdps47924.2020.00078
19	PLANK J S. The RAID-6 Liberation Codes［C］// Proceedings of the 6th USENIX Conference on File and Storage Technologies. Berkeley： USENIX Association， 2008： 97-110.
20	REED I S， SOLOMON G. Polynomial codes over certain finite fields［J］. Journal of the Society for Industrial and Applied Mathematics， 1960， 8（2）： 300-304. 10.1137/0108018
21	PLANK J S. A tutorial on Reed-Solomon coding for fault‐tolerance in RAID‐like systems［J］. Software： Practice and Experience， 1997， 27（9）： 995-1012. 10.1002/(sici)1097-024x(199709)27:9<995::aid-spe111>3.0.co;2-6
22	CASSUTO Y， BRUCK J. Cyclic lowest density MDS array codes［J］. IEEE Transactions on Information Theory， 2009， 55（4）： 1721-1729. 10.1109/tit.2009.2013024
23	JIN C， JIANG H， FENG D， et al. P-Code： a new RAID-6 code with optimal properties［C］// Proceedings of the 23rd International Conference on Supercomputing. New York： ACM， 2009： 360-369. 10.1145/1542275.1542326
24	JIN C， FENG D， JIANG H， et al. A comprehensive study on RAID-6 codes： horizontal vs. vertical［C］// Proceedings of the IEEE 6th International Conference on Networking， Architecture， and Storage. Piscataway： IEEE， 2011： 102-111. 10.1109/nas.2011.31
25	XIANG L P， XU Y L， LUI J C S， et al. Optimal recovery of single disk failure in RDP code storage systems［J］. ACM SIGMETRICS Performance Evaluation Review， 2010， 38（1）： 119-130. 10.1145/1811099.1811054

[1]	穆凌霞, 周政君, 王斑, 张友民, 薛向宏, 宁凯凯. 多无人机编队避障和编队重构方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2938-2946.
[2]	牛科迪, 李敏, 姚中原, 斯雪明. 面向物联网的区块链共识算法综述[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3678-3687.
[3]	王春东, 姜鑫. 基于可验证延迟函数的改进实用拜占庭容错算法[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3484-3489.
[4]	王谨东, 李强. 基于Raft算法改进的实用拜占庭容错共识算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 122-129.
[5]	任秀丽, 张雷. 基于实用拜占庭容错的改进的多主节点共识机制[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1500-1507.
[6]	杨龙海, 王学渊, 蒋和松. 改进SM2签名方法的区块链数字签名方案[J]. 计算机应用, 2021, 41(7): 1983-1988.
[7]	李静, 罗金飞, 李炳超. 主动容错副本存储系统的可靠性分析模型[J]. 计算机应用, 2021, 41(4): 1113-1121.
[8]	刘宇, 朱朝阳, 李金泽, 劳源基, 覃团发. 检测型的联盟区块链共识算法d-PBFT[J]. 计算机应用, 2021, 41(3): 756-762.
[9]	林腾涛, 查思明, 陈蕾, 龙显忠. 图趋势过滤诱导的噪声容错多标记学习模型[J]. 计算机应用, 2021, 41(1): 8-14.
[10]	李靖, 景旭, 杨会君. 基于实用拜占庭容错算法的区块链电子计票方案[J]. 计算机应用, 2020, 40(4): 954-960.
[11]	王可可, 陈志德, 徐健. 基于联盟区块链的农产品质量安全高效追溯体系[J]. 计算机应用, 2019, 39(8): 2438-2443.
[12]	甘俊, 李强, 陈子豪, 张超. 区块链实用拜占庭容错共识算法的改进[J]. 计算机应用, 2019, 39(7): 2148-2155.
[13]	潘建国, 李豪. 基于实用拜占庭容错的物联网入侵检测方法[J]. 计算机应用, 2019, 39(6): 1742-1746.
[14]	王海勇, 郭凯璇, 潘启青. 基于投票机制的拜占庭容错共识算法[J]. 计算机应用, 2019, 39(6): 1766-1771.
[15]	贾梦瑶, 王兴伟, 张爽, 易波, 黄敏. 基于软件定义网络的卫星网络容错路由机制[J]. 计算机应用, 2019, 39(6): 1772-1779.

低编译复杂度的双容错阵列码

Double fault tolerant array code with low compilation complexity

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 25

相关文章 15

编辑推荐

Metrics