Fast failure recovery method based on local redundant hybrid code

doi:10.11772/j.issn.1001-9081.2021111917

Abstract

Abstract:

The parity blocks of the Maximum-Distance-Separable （MDS） code are all global parity blocks. The length of the reconstruction chain increases with the expansion of the storage system， and the reconstruction performance gradually decreases. Aiming at the above problems， a new type of Non-Maximum-Distance-Separable （Non-MDS） code called local redundant hybrid code Code-LM（s，c） was proposed. Firstly， two types of local parity blocks called horizontal parity block in the strip-set and horizontal-diagonal parity block were added in any strip-sets to reduce the length of the reconstruction chain， and the parity layout of the local redundant hybrid code was designed. Then， four reconstruction formulations of the lost data blocks were designed according to the generation rules of the parity blocks and the common block existed in the reconstruction chains of different data blocks. Finally， double-disk failures were divided into three situations depending on the distances of the strip-sets where the failed disks located and the corresponding reconstruction methods were designed. Theoretical analysis and experimental results show that with the same storage scale， compared with RDP （Row-Diagonal Parity）， the reconstruction time of CodeM（s，c） for single-disk failure and double-disk failure can be reduced by 84% and 77% respectively； compared with V²-Code， the reconstruction time of Code-LM（s，c） for single-disk failure and double-disk failure can be reduced by 67% and 73% respectively. Therefore， local redundant hybrid code can support fast recovery from failed disks and improve reliability of storage system.

Key words: RAID6 (Redundant-Array-of-Independent-Disks-6), Non-Maximum-Distance-Separable (Non-MDS) code, local redundant hybrid code, reconstruction, failure recovery

摘要：

最大距离可分（MDS）码中校验块均为全局校验块，重构链长度随着存储系统规模扩大而增长，重构性能逐渐降低。针对上述问题提出一种新型的非最大距离可分（Non-MDS）码：局部冗余混合编码Code-LM（s，c）。首先，为缩小重构链长度，任意条带单元组内只有局部校验块，分别为组内水平校验块和水平对角校验块，并设计了局部冗余混合编码的校验布局；然后，根据不同校验块的生成规则，设计了失效数据块的4种重构方式，不同失效块的重构链具有公共块；最后，根据两个故障磁盘所在条带单元组距离不同，将双盘故障分为3种情况，并设计了对应的重构算法。理论分析和实验结果表明，存储规模相同时，与RDP相比，Code-LM（s，c）的单盘重构时间和双盘重构时间可减少84%和77%；与V²-Code相比，Code-LM（s，c）的单盘重构时间和双盘重构时间可减少67%和73%。因此局部冗余混合编码可支持故障磁盘快速恢复，提高存储系统可靠性。

关键词: RAID6, 非最大距离可分码, 局部冗余混合编码, 重构, 故障恢复

CLC Number:

TP302.8

Jingyu LIU, Qiuxia NIU, Xiaoyan LI, Qiaoshuo SHI, Youxi WU. Fast failure recovery method based on local redundant hybrid code[J]. Journal of Computer Applications, 2022, 42(4): 1244-1252.

刘靖宇, 牛秋霞, 李萧言, 史巧硕, 武优西. 基于局部冗余混合编码的故障快速恢复方法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1244-1252.

Figures/Tables 12

Fig. 1 Parity layout of HoVer code

Fig. 2 Parity layout of Code-LM（3，4）

Fig. 3 Reconstruction with single-strip-failure in Code-LM（3，4）

Fig. 4 Reconstruction with double-strip-failure in one strip-set in Code-LM（3，4）

Fig. 5 Reconstruction with double-strip-failure in two adjoining strip-sets in Code-LM（3，4）

Fig. 6 Reconstruction with double-strip-failure in two different strip-sets with strip-set distance of 1 in Code-LM（4，4）

Fig. 7 Comparison results of coding efficiency

Fig. 8 Comparison of storage efficiency with same numbers of disks

Fig. 9 Comparison of reconstruction time between Code-LM（s，c） and RDP-Code（n-2，n）

Fig. 10 Comparison of reconstruction time of single disk failure between Code-LM（s，c） and RDP-Code（n-2，n）， RDOR

Fig. 11 Comparison of reconstruction time between Code-LM（s，c） and Code-M（s，c）

Fig. 12 Comparison of reconstruction time between Code-LM（s，c） and V2-Code（m，n）

References 22

1	WANG T， QIU L， SANGAIAH A K， et al. Energy-efficient and trustworthy data collection protocol based on mobile fog computing in Internet of Things ［J］. IEEE Transactions on Industrial Informatics， 2019， 16（5）： 3531-3539. 10.1109/tii.2019.2920277
2	YU H， HU Q， YANG Z， et al. Efficient continuous big data integrity checking for decentralized storage ［J］. IEEE Transactions on Network Science and Engineering， 2021， 8（2）： 1658-1673. 10.1109/tnse.2021.3068261
3	YE Z， ZHENG J， TU R. Network evolution analysis of e-business entrepreneurship： big data analysis based on Taobao intelligent information system ［J］. Information Systems and e-Business Management， 2020， 18（4）： 665-679. 10.1007/s10257-018-0390-2
4	HONG A， XIAO W， GE J L. Big data analysis system based on cloudera distribution hadoop ［C］// Proceedings of the 7th International Conference on High Performance and Smart Computing and IEEE International Conference on Intelligent Data and Security. Piscataway： IEEE， 2021： 169-173. 10.1109/bigdatasecurityhpscids52275.2021.00040
5	HUANG S， LIANG S， FU S， et al. Characterizing disk health degradation and proactively protecting against disk failures for reliable storage systems ［C］// Proceedings of the 2019 International Conference on Autonomic Computing. Piscataway： IEEE， 2019： 157-166. 10.1109/icac.2019.00027
6	COOK B. Formal reasoning about the security of Amazon Web Services ［C］// Proceedings of the 2018 International Conference on Computer Aided Verification. Cham： Springer， 2018： 38-47. 10.1007/978-3-319-96145-3_3
7	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/971701.50214
8	LIU J， ZHANG J， LI J， et al. A high-performance storage system based with dual Raid engine ［C］// Proceedings of the 2019 International Conference on Smart Computing and Communication. Cham： Springer， 2019： 53-62. 10.1007/978-3-030-34139-8_6
9	BLAUM M， HETZLER S R. Array codes with local properties［J］. IEEE Transactions on Information Theory， 2020， 66（6）： 3675-3690. 10.1109/tit.2019.2951693
10	HAFNER J L. Weaver codes： highly fault tolerant erasure codes for storage systems ［C］// Proceedings of the 4th Conference on USENIX Conference on File and Storage Technologies. New York： ACM， 2005： 16.
11	HAFNER J L. HoVer erasure codes for disk arrays ［C］// Proceedings of the 2006 International Conference on Dependable Systems and Networks. Piscataway： IEEE， 2006： 217-226.
12	WAN S， CAO Q， XIE C， et al. Code-M： A non-MDS erasure code scheme to support fast recovery from up to two-disk failures in storage systems ［C］// Proceedings of the 2010 IEEE/IFIP International Conference on Dependable Systems & Networks. Piscataway： IEEE， 2010： 51-60. 10.1109/dsn.2010.5545009
13	YAN G， CHEN R， GUAN Q， et al. DLS： a delay-life-aware I/O scheduler to improve the load balancing of SSD-based Raid-5 arrays ［C］// Proceedings of the 21st International Conference on High Performance Computing and Communications. Piscataway： IEEE， 2019： 2445-2450. 10.1109/hpcc/smartcity/dss.2019.00341
14	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
15	XIAO F， FAN D， TANG D.A fast recovery method for single disk failure based on EVENODD ［J］. International Journal of Network Security， 2019， 21（3）： 392-401.
16	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. Berkeleg： USENIX Association， 2004： 1-14.
17	XIE P， YUAN Z， HUANG J， 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： 34.1-34.10. 10.1145/3337821.3337829
18	FU Y， SHU J， LUO X， et al. Short code： an efficient Raid-6 MDS code for optimizing degraded reads and partial stripe writes ［J］. IEEE Transactions on Computers， 2017， 66（1）： 127-137. 10.1109/tc.2016.2576461
19	SHEN Z， SHU J， FU Y. HV 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
20	XIE P， HUANG J， CAO Q， et al. V²-code： a new non-MDS array code with optimal reconstruction performance for Raid6 ［C］// Proceedings of the 2013 IEEE International Conference on Cluster Computing. Piscataway： IEEE， 2013： 1-8. 10.1109/cluster.2013.6702621
21	谢平.存储系统重构优化技术研究［J］.物理网技术， 2017， 7（5）： 113-116. 10.16667/j.issn.2095-1302.2017.05.037
	XIE P. Research on optimization technology of storage system reconfiguration［J］. Physical Web Technology， 2017， 7（5）： 113-116. 10.16667/j.issn.2095-1302.2017.05.037
22	XIANG L， XU Y， 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]	Leping LIN, Hongmin ZHOU, Ning OUYANG. Compressed sensing image reconstruction method fusing spatial location and structure information [J]. Journal of Computer Applications, 2022, 42(3): 930-937.
[2]	Junbo LI, Pinle QIN, Jianchao ZENG, Meng LI. CT three-dimensional reconstruction algorithm based on super-resolution network [J]. Journal of Computer Applications, 2022, 42(2): 584-591.
[3]	ZHANG Cheng, WAN Yuan, QIANG Haopeng. Deep unsupervised discrete cross-modal hashing based on knowledge distillation [J]. Journal of Computer Applications, 2021, 41(9): 2523-2531.
[4]	GUAN Qijie, ZHANG Ting, LI Deya, ZHOU Shaojing, DU Yi. Indefinite reconstruction method of spatial data based on multi-resolution generative adversarial network [J]. Journal of Computer Applications, 2021, 41(8): 2306-2311.
[5]	SHI Xuesong, LI Xianhua, SUN Qing, SONG Tao. Noise image segmentation by adaptive wavelet transform based on artificial bee swarm and fuzzy C-means [J]. Journal of Computer Applications, 2021, 41(8): 2312-2317.
[6]	NIU Kangli, CHEN Yuzhang, SHEN Junfeng, ZENG Zhangfan, PAN Yongcai, WANG Yichong. Dual-channel night vision image restoration method based on deep learning [J]. Journal of Computer Applications, 2021, 41(6): 1775-1784.
[7]	WANG Xianwu, ZHANG Ting, JI Xin, DU Yi. 3D shale digital core reconstruction method based on deep convolutional generative adversarial network with gradient penalty [J]. Journal of Computer Applications, 2021, 41(6): 1805-1811.
[8]	LIANG Min, WANG Haorong, ZHANG Yao, LI Jie. Image super-resolution reconstruction method based on accelerated residual network [J]. Journal of Computer Applications, 2021, 41(5): 1438-1444.
[9]	DUAN Youxiang, ZHANG Hanxiao, SUN Qifeng, SUN Youkai. Image super-resolution reconstruction algorithm based on Laplacian pyramid generative adversarial network [J]. Journal of Computer Applications, 2021, 41(4): 1020-1026.
[10]	BIAN Pengcheng, ZHENG Zhonglong, LI Minglu, HE Yiran, WANG Tianxiang, ZHANG Dawei, CHEN Liyuan. Attention fusion network based video super-resolution reconstruction [J]. Journal of Computer Applications, 2021, 41(4): 1012-1019.
[11]	WANG Yongjin, ZUO Yu, WU Lian, CUI Zhongwei, ZHAO Chenjie. Image super-resolution reconstruction based on attention mechanism [J]. Journal of Computer Applications, 2021, 41(3): 845-850.
[12]	Haiyong WANG, Kaixin ZHANG, Weizheng GUAN. Single image super-resolution reconstruction method based on dense Inception [J]. Journal of Computer Applications, 2021, 41(12): 3666-3671.
[13]	ZHANG Yanjiao, QIAO Zhiwei. High-precision sparse reconstruction of CT images based on multiply residual UNet [J]. Journal of Computer Applications, 2021, 41(10): 2964-2969.
[14]	TU Hongyan, ZHANG Ting, XIA Pengfei, DU Yi. Reconstruction method for uncertain spatial information based on improved variational auto-encoder [J]. Journal of Computer Applications, 2021, 41(10): 2959-2963.
[15]	LIN Jing, HUANG Yuqing, LI Leimin. Image super-resolution reconstruction based on spherical moment matching and feature discrimination [J]. Journal of Computer Applications, 2020, 40(8): 2345-2350.