Double fault tolerant array code with low compilation complexity

doi:10.11772/j.issn.1001-9081.2022091344

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (9): 2766-2774.DOI: 10.11772/j.issn.1001-9081.2022091344

• Data science and technology • Previous Articles Next Articles

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)

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

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

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

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

Abstract

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

摘要：

纠删码技术是独立磁盘冗余阵列-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, 阵列纠删码, 容错, 编译码复杂度, 磁盘故障修复

CLC Number:

TP302.8

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.

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

Figures/Tables 15

Fig. 1 Process of J-code generation

Fig. 2 J-code anti-diagonal parity set

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

Fig. 4 Double disk failure repair process

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

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

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

Fig. 8 Relationships between tow parity sets and disjoint disks

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$

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$

Fig. 9 Comparison of storage utilization of different erasure codes

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)$

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)$

Fig. 10 Comparison of encoding complexity and decoding complexity

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 为奇数$

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 为奇数$

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

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

References 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]	Kedi NIU, Min LI, Zhongyuan YAO, Xueming SI. Review of blockchain consensus algorithms for internet of things [J]. Journal of Computer Applications, 2024, 44(12): 3678-3687.
[2]	Chundong WANG, Xin JIANG. Improved practical Byzantine fault tolerance algorithm based on verifiable delay function [J]. Journal of Computer Applications, 2023, 43(11): 3484-3489.
[3]	WANG Jindong, LI Qiang. Improved practical Byzantine fault tolerance consensus algorithm based on Raft algorithm [J]. Journal of Computer Applications, 2023, 43(1): 122-129.
[4]	Xiuli REN, Lei ZHANG. Improved multi-primary-node consensus mechanism based on practical Byzantine fault tolerance [J]. Journal of Computer Applications, 2022, 42(5): 1500-1507.
[5]	YANG Longhai, WANG Xueyuan, JIANG Hesong. Blockchain digital signature scheme with improved SM2 signature method [J]. Journal of Computer Applications, 2021, 41(7): 1983-1988.
[6]	LI Jing, LUO Jinfei, LI Bingchao. Reliability analysis models for replication-based storage systems with proactive fault tolerance [J]. Journal of Computer Applications, 2021, 41(4): 1113-1121.
[7]	LIU Yu, ZHU Chaoyang, LI Jinze, LAO Yuanji, QIN Tuanfa. d-PBFT:detection consensus algorithm for alliance blockchain [J]. Journal of Computer Applications, 2021, 41(3): 756-762.
[8]	LI Jing, JING Xu, YANG Huijun. Blockchain electronic counting scheme based on practical Byzantine fault tolerance algorithm [J]. Journal of Computer Applications, 2020, 40(4): 954-960.
[9]	WANG Keke, CHEN Zhide, XU Jian. Efficient traceability system for quality and safety of agricultural products based on consortium blockchain [J]. Journal of Computer Applications, 2019, 39(8): 2438-2443.
[10]	GAN Jun, LI Qiang, CHEN Zihao, ZHANG Chao. Improvement of blockchain practical Byzantine fault tolerance consensus algorithm [J]. Journal of Computer Applications, 2019, 39(7): 2148-2155.
[11]	PAN Jianguo, LI Hao. Intrusion detection approach for IoT based on practical Byzantine fault tolerance [J]. Journal of Computer Applications, 2019, 39(6): 1742-1746.
[12]	WANG Haiyong, GUO Kaixuan, PAN Qiqing. Byzantine fault tolerance consensus algorithm based on voting mechanism [J]. Journal of Computer Applications, 2019, 39(6): 1766-1771.
[13]	JIA Mengyao, WANG Xingwei, ZHANG Shuang, YI Bo, HUANG Min. Software defined network based fault tolerant routing mechanism for satellite networks [J]. Journal of Computer Applications, 2019, 39(6): 1772-1779.
[14]	YANG Yuxing, LI Xiaohui. Three-length-path structure connectivity and substructure connectivity of hypercube networks [J]. Journal of Computer Applications, 2019, 39(2): 509-512.
[15]	LI Jing, LIU Dongshi. Reliability evaluation model for cloud storage systems with proactive fault tolerance [J]. Journal of Computer Applications, 2018, 38(9): 2631-2636.

Double fault tolerant array code with low compilation complexity

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 25

Related Articles 15

Recommended Articles

Metrics