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]	Yuxin HUANG, Jialong XU, Zhengtao YU, Shukai HOU, Jiaqi ZHOU. Unsupervised text sentiment transfer method based on generation prompt [J]. Journal of Computer Applications, 2024, 44(9): 2667-2673.
[2]	Yanxin GE, Tao YAN, Jiangfeng ZHANG, Xiaoying GUO, Bin CHEN. 3D shape reconstruction with spatial correlation based on spatio-temporal attention [J]. Journal of Computer Applications, 2024, 44(5): 1570-1578.
[3]	Hualu QIU, Suzhen LIN, Yanbo WANG, Feng LIU, Dawei LI. Reconstruction algorithm for undersampled magnetic resonance images based on complex convolution dual-domain cascade network [J]. Journal of Computer Applications, 2024, 44(2): 580-587.
[4]	Mengmeng CHEN, Zhiwei QIAO. Sparse reconstruction of CT images based on Uformer with fused channel attention [J]. Journal of Computer Applications, 2023, 43(9): 2948-2954.
[5]	Zezhi ZENG, Jianwei YANG. Generalized polar complex exponential transform with more uniform zeros distribution [J]. Journal of Computer Applications, 2023, 43(8): 2499-2504.
[6]	Min LIANG, Jiayi LIU, Jie LI. Image super-resolution reconstruction method based on iterative feedback and attention mechanism [J]. Journal of Computer Applications, 2023, 43(7): 2280-2287.
[7]	Yang LIU, Zhiyang LU, Jun WANG, Jun SHI. Gibbs artifact removal algorithm for magnetic resonance imaging based on self-attention connection UNet [J]. Journal of Computer Applications, 2023, 43(5): 1606-1611.
[8]	Lihua SHEN, Bo LI. Super-resolution reconstruction of lung CT images based on feature pyramid network and dense network [J]. Journal of Computer Applications, 2023, 43(5): 1612-1619.
[9]	Qinghai XU, Shifei DING, Tongfeng SUN, Jian ZHANG, Lili GUO. Improved capsule network based on multipath feature [J]. Journal of Computer Applications, 2023, 43(5): 1330-1335.
[10]	Xiaoyu FAN, Suzhen LIN, Yanbo WANG, Feng LIU, Dawei LI. Reconstruction algorithm for highly undersampled magnetic resonance images based on residual graph convolutional neural network [J]. Journal of Computer Applications, 2023, 43(4): 1261-1268.
[11]	Qingyu JIA, Liang CHANG, Xianyi YANG, Baohua QIANG, Shihao ZHANG, Wu XIE, Minghao YANG. Real-time reconstruction method of visual information for manipulator operation [J]. Journal of Computer Applications, 2023, 43(4): 1255-1260.
[12]	Yuan GU, Zhen ZHANG, Tong DUAN. Fast link failure recovery method for software-defined internet of vehicles [J]. Journal of Computer Applications, 2023, 43(3): 853-859.
[13]	Jiangfeng ZHANG, Tao YAN, Bin CHEN, Yuhua QIAN, Yantao SONG. Multi-depth-of-field 3D shape reconstruction with global spatio-temporal feature coupling [J]. Journal of Computer Applications, 2023, 43(3): 894-902.
[14]	Yating SU, Cuixiang LIU. Three-dimensional human reconstruction model based on high-resolution net and graph convolutional network [J]. Journal of Computer Applications, 2023, 43(2): 583-588.
[15]	Keke WANG, Yu ZHU, Xiaoying WANG, Jianqiang HUANG, Tengfei CAO. Heterogeneous hypernetwork representation learning method with hyperedge constraint [J]. Journal of Computer Applications, 2023, 43(12): 3654-3661.