SA-RSR：一种适用于异或类纠删码分布式存储系统的数据读取最优恢复方法

张兴军; 梁宁静; 刘云飞; 张长江; 李洋

doi:10.1631/FITEE.2100242

Your Location：

Home >

Browse articles >

SA-RSR：一种适用于异或类纠删码分布式存储系统的数据读取最优恢复方法

常规文章 | Updated：2022-07-11

- SA-RSR：一种适用于异或类纠删码分布式存储系统的数据读取最优恢复方法
- SA-RSR: a read-optimal data recovery strategy for XOR-coded distributed storage systems
- 信息与电子工程前沿（英文） 2022年23卷第6期页码：858-875
- Affiliations：
  
  1.School of Computer Science and Technology, Xi’an Jiaotong University, Xi’an710049, China
  2.Beijing Electronic Engineering General Research Institute, Beijing100854, China
- Author bio：
  
  ‡Corresponding author
  E-mail: l_ningjing@stu.xjtu.edu.cn;
  E-mail: liuyunfei@stu.xjtu.edu.cn;
  E-mail: zcj9527@stu.xjtu.edu.cn
- Funds：
  
  National Natural Science Foundation of China(62172327)
- DOI：10.1631/FITEE.2100242
  中图分类号： TP391.4
- 收稿：2021-05-16，
  
  录用：2021-08-16，
  
  纸质出版：2022-06-0
- Accepted：
Scan QR Code
张兴军, 梁宁静, 刘云飞, 等. SA-RSR：一种适用于异或类纠删码分布式存储系统的数据读取最优恢复方法[J]. 信息与电子工程前沿（英文）, 2022,23(6):858-875.

Xingjun ZHANG, Ningjing LIANG, Yunfei LIU, et al. SA-RSR: a read-optimal data recovery strategy for XOR-coded distributed storage systems[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(6): 858-875.
张兴军, 梁宁静, 刘云飞, 等. SA-RSR：一种适用于异或类纠删码分布式存储系统的数据读取最优恢复方法[J]. 信息与电子工程前沿（英文）, 2022,23(6):858-875. DOI： 10.1631/FITEE.2100242.

Xingjun ZHANG, Ningjing LIANG, Yunfei LIU, et al. SA-RSR: a read-optimal data recovery strategy for XOR-coded distributed storage systems[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(6): 858-875. DOI： 10.1631/FITEE.2100242.

摘要

冗余策略经常被用于分布式存储系统，以保证数据的可靠性与可用性。纠删码是一种代表性的冗余策略，具有低存储开销优势，这种优势促进了它在分布式存储系统中的应用。在各种纠删码机制中，异或类纠删码凭借高计算效率变得越来越流行。采用异或类纠删码机制的存储系统，如果发生单节点故障，便会进行数据恢复，该过程需要从幸存节点中下载数据，然后恢复故障节点中的数据。然而，数据恢复过程中的数据传输通常需要相当长时间。目前研究主要集中在通过减少数据恢复过程所需数据量，减少数据传输所需时间，但存在复杂度高和局部最优解等问题。本文提出一种随机搜索恢复算法，SA-RSR，该算法能加速异或类纠删码单节点故障恢复。SA-RSR利用模拟退火技术寻找读取和传输最少数据量的最优恢复机制，且该搜索过程可在多项式时间内完成。最后，为验证该方法的有效性，使用多种异或类纠删码进行仿真验证，并在真实存储系统Ceph中验证。实验结果表明，与传统恢复方法相比，SA-RSR减少了30%的数据读取与传输量，提高了20.36%的数据恢复性能。

Abstract

To ensure the reliability and availability of data

redundancy strategies are always required for distributed storage systems. Erasure coding

one of the representative redundancy strategies

has the advantage of low storage overhead

which facilitates its employment in distributed storage systems. Among the various erasure coding schemes

XOR-based erasure codes are becoming popular due to their high computing speed. When a single-node failure occurs in such coding schemes

a process called data recovery takes place to retrieve the failed node's lost data from surviving nodes. However

data transmission during the data recovery process usually requires a considerable amount of time. Current research has focused mainly on reducing the amount of data needed for data recovery to reduce the time required for data transmission

but it has encountered problems such as significant complexity and local optima. In this paper

we propose a random search recovery algorithm

named SA-RSR

to speed up single-node failure recovery of XOR-based erasure codes. SA-RSR uses a simulated annealing technique to search for an optimal recovery solution that reads and transmits a minimum amount of data. In addition

this search process can be done in polynomial time. We evaluate SA-RSR with a variety of XOR-based erasure codes in simulations and in a real storage system

Ceph. Experimental results in Ceph show that SA-RSR reduces the amount of data required for recovery by up to 30.0% and improves the performance of data recovery by up to 20.36% compared to the conventional recovery method.

关键词

Keywords

references

Arnold J , 2014 . OpenStack Swift Using, Administering, and Developing for Swift Object Storage . O’Reilly Media , Sebastopol, USA .

Blaum M , Roth RM , 1993 . New array codes for multiple phased burst correction . IEEE Trans Inform Theory , 39 ( 1 ): 66 - 77 . doi: 10.1109/18.179343 http://doi.org/10.1109/18.179343

Blaum M , Brady J , Bruck J , et al. , 1995 . EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures . IEEE Trans Comput , 44 ( 2 ): 192 - 202 . doi: 10.1109/12.364531 http://doi.org/10.1109/12.364531

Blaum M , Bruck J , Vardy A , 1996 . MDS array codes with independent parity symbols . IEEE Trans Inform Theory , 42 ( 2 ): 529 - 542 . doi: 10.1109/18.485722 http://doi.org/10.1109/18.485722

Borthakur D , 2007 . The Hadoop Distributed File System: Architecture and Design . http://hadoop.apache.org/core/docs/current/hdfs_design.html http://hadoop.apache.org/core/docs/current/hdfs_design.html

Calder B , Wang J , Ogus A , et al. , 2011 . Windows azure storage: a highly available cloud storage service with strong consistency . Proc 23 rd ACM Symp on Operating Systems Principles , p. 143 - 157 . doi: 10.1145/2043556.2043571 http://doi.org/10.1145/2043556.2043571

Corbett P , English B , Goel A , et al. , 2004 . Row-diagonal parity for double disk failure correction . Proc 3 rd USENIX Conf on File and Storage Technologies , Article 1 .

Facebook , 2018 . HDFS-RAID . http://wiki.apache.org/hadoop/HDFS-RAID http://wiki.apache.org/hadoop/HDFS-RAID

Gad EE , Mateescu R , Blagojevic F , et al. , 2013 . Repair-optimal MDS array codes over GF(2) . IEEE Int Symp on Information Theory , p. 887 - 891 . doi: 10.1109/ISIT.2013.6620354 http://doi.org/10.1109/ISIT.2013.6620354

Ghemawat S , Gobioff H , Leung ST , 2003 . The Google file system . Proc 19 th ACM Symp on Operating Systems Principles , p. 29 - 43 . doi: 10.1145/945445.945450 http://doi.org/10.1145/945445.945450

Goel A , Corbett P , 2012 . RAID triple parity . ACM SIGOPS Oper Syst Rev , 46 ( 3 ): 41 - 49 . doi: 10.1145/2421648.2421655 http://doi.org/10.1145/2421648.2421655

Hou HX , Lee PPC , 2020 . Binary MDS array codes with optimal repair . IEEE Trans Inform Theory , 66 ( 3 ): 1405 - 1422 . doi: 10.1109/TIT.2019.2939111 http://doi.org/10.1109/TIT.2019.2939111

Hou HX , Han YS , Lee PPC , et al. , 2019a . A new design of binary MDS array codes with asymptotically weak-optimal repair . IEEE Trans Inform Theory , 65 ( 11 ): 7095 - 7113 . doi: 10.1109/TIT.2019.2923992 http://doi.org/10.1109/TIT.2019.2923992

Hou HX , Han YS , Lee PPC , et al. , 2019b . New regenerating codes over binary cyclic codes . IEEE Int Symp on Information Theory , p. 216 - 220 . doi: 10.1109/ISIT.2019.8849354 http://doi.org/10.1109/ISIT.2019.8849354

Hou HX , Lee PPC , Shum KW , et al. , 2019c . Rack-aware regenerating codes for data centers . IEEE Trans Inform Theory , 65 ( 8 ): 4730 - 4745 . doi: 10.1109/TIT.2019.2902835 http://doi.org/10.1109/TIT.2019.2902835

Huang C , Xu LH , 2008 . STAR: an efficient coding scheme for correcting triple storage node failures . IEEE Trans Comput , 57 ( 7 ): 889 - 901 . doi: 10.1109/TC.2007.70830 http://doi.org/10.1109/TC.2007.70830

Huang C , Simitci H , Xu YK , et al. , 2012 . Erasure coding in windows azure storage . Proc USENIX Conf on Annual Technical Conf , Article 2 .

Jiekak S , Kermarrec AM , Le Scouarnec N , et al. , 2013 . Regenerating codes: a system perspective . ACM SIGOPS Oper Syst Rev , 47 ( 2 ): 23 - 32 . doi: 10.1145/2506164.2506170 http://doi.org/10.1145/2506164.2506170

Jin C , Jiang H , Feng D , et al. , 2009 . P-Code: a new RAID-6 code with optimal properties . Proc 23 rd Int Conf on Supercomputing , p. 360 - 369 . doi: 10.1145/1542275.1542326 http://doi.org/10.1145/1542275.1542326

Khan O , Burns R , Plank J , et al. , 2012 . Rethinking erasure codes for cloud file systems: minimizing I/O for recovery and degraded reads . Proc 10 th USENIX Conf on File and Storage Technologies , Article 20 .

Liang NJ , Zhang XJ , Yang HL , et al. , 2020 . An optimal recovery approach for liberation codes in distributed storage systems . IEEE Access , 8 : 137631 - 137645 . doi: 10.1109/ACCESS.2020.3012190 http://doi.org/10.1109/ACCESS.2020.3012190

Miyamae T , Nakao T , Shiozawa K , 2014 . Erasure code with shingled local parity groups for efficient recovery from multiple disk failures . Proc 10 th USENIX Conf on Hot Topics in System Dependability , Article 5 .

Pamies-Juarez L , Blagojevic F , Mateescu R , et al. , 2016 . Opening the chrysalis: on the real repair performance of MSR codes . Proc 14 th USENIX Conf on File and Storage Technologies , p. 81 - 94 .

Plank JS , 2008 . The RAID-6 liberation codes . Proc 6 th USENIX Conf on File and Storage Technologies , p. 97 - 110 .

Plank JS , 2009 . The RAID-6 Liber8Tion code . Int J High Perform Comput Appl , 23 ( 3 ): 242 - 251 . doi: 10.1177/1094342009106191 http://doi.org/10.1177/1094342009106191

Plank JS , Luo JQ , Schuman CD , et al. , 2009 . A performance evaluation and examination of open-source erasure coding libraries for storage . Proc 7 th Conf on File and Storage Technologies , p. 253 - 265 .

Plank JS , Buchsbaum AL , Zanden BTV , 2011 . Minimum density RAID-6 codes . ACM Trans Stor , 6 ( 4 ): 16 . doi: 10.1145/1970338.1970340 http://doi.org/10.1145/1970338.1970340

RedHat , 2018 . Ceph Erasure . http://docs.ceph.com/docs/master/architecture/erasurecodin http://docs.ceph.com/docs/master/architecture/erasurecodin

Reed IS , Solomon G , 1960 . Polynomial codes over certain finite fields . J Soc Ind Appl Math , 8 ( 2 ): 300 - 304 . doi: 10.1137/0108018 http://doi.org/10.1137/0108018

Roth RM , Lempel A , 1989 . On MDS codes via Cauchy matrices . IEEE Trans Inform Theory , 35 ( 6 ): 1314 - 1319 . doi: 10.1109/18.45291 http://doi.org/10.1109/18.45291

Russell SJ , Norvig P , 2016 . Artificial Intelligence: a Modern Approach . Prentice-Hall, Inc. , USA .

Sathiamoorthy M , Asteris M , Papailiopoulos D , et al. , 2013 . XORing elephants: novel erasure codes for big data . Proc VLDB Endow , 6 ( 5 ): 325 - 336 . doi: 10.14778/2535573.2488339 http://doi.org/10.14778/2535573.2488339

Schroeder B , Gibson GA , 2007 . Disk failures in the real world: what does an MTTF of 1 000 000 hours mean to you? Proc 5 th USENIX Conf on File and Storage Technologies , p. 1 - 16 .

Shen ZR , Shu JW , 2014 . HV Code: an all-around MDS code to improve efficiency and reliability of RAID-6 systems . Proc 44 th Annual IEEE/IFIP Int Conf on Dependable Systems and Networks , p. 550 - 561 . doi: 10.1109/DSN.2014.57 http://doi.org/10.1109/DSN.2014.57

Tamo I , Wang ZY , Bruck J , 2011 . MDS array codes with optimal rebuilding . IEEE Int Symp on Information Theory , p. 1240 - 1244 . doi: 10.1109/ISIT.2011.6033733 http://doi.org/10.1109/ISIT.2011.6033733

Tamo I , Wang ZY , Bruck J , 2013 . Zigzag codes: MDS array codes with optimal rebuilding . IEEE Trans Inform Theory , 59 ( 3 ): 1597 - 1616 . doi: 10.1109/TIT.2012.2227110 http://doi.org/10.1109/TIT.2012.2227110

Vajha M , Ramkumar V , Puranik B , et al. , 2018 . Clay codes: moulding MDS codes to yield an MSR code . Proc 16 th USENIX Conf on File and Storage Technologies , p. 139 - 153 .

Wang ZY , Dimakis AG , Bruck J , 2010 . Rebuilding for array codes in distributed storage systems . IEEE Globecom Workshops , p. 1905 - 1909 . doi: 10.1109/GLOCOMW.2010.5700274 http://doi.org/10.1109/GLOCOMW.2010.5700274

Weil SA , Brandt SA , Miller EL , et al. , 2006a . Ceph: a scalable, high-performance distributed file system . Proc 7 th Symp on Operating Systems Design and Implementation , p. 307 - 320 .

Weil SA , Brandt SA , Miller EL , et al. , 2006b . CRUSH: controlled, scalable, decentralized placement of replicated data . Proc ACM/IEEE Conf on Supercomputing , Article 122-es . doi: 10.1145/1188455.1188582 http://doi.org/10.1145/1188455.1188582

Weil SA , Leung AW , Brandt SA , et al. , 2007 . RADOS: a scalable, reliable storage service for petabyte-scale storage clusters . Proc 2 nd Int Workshop on Petascale Data Storage: held in conjunction with Supercomputing , p. 35 - 44 . doi: 10.1145/1374596.1374606 http://doi.org/10.1145/1374596.1374606

Wu CT , Wan SG , He XB , et al. , 2011 . H-Code: a hybrid MDS array code to optimize partial stripe writes in RAID-6 . Proc IEEE Int Parallel & Distributed Processing Symp , p. 782 - 793 . doi: 10.1109/IPDPS.2011.78 http://doi.org/10.1109/IPDPS.2011.78

Xiang LP , Xu YL , Lui JCS , et al. , 2011 . A hybrid approach to failed disk recovery using RAID-6 codes: algorithms and performance evaluation . ACM Trans Stor , 7 ( 3 ): 11 . doi: 10.1145/2027066.2027071 http://doi.org/10.1145/2027066.2027071

Xu LH , Bruck J , 1999 . X-code: MDS array codes with optimal encoding . IEEE Trans Inform Theory , 45 ( 1 ): 272 - 276 . doi: 10.1109/18.746809 http://doi.org/10.1109/18.746809

Xu SL , Li RH , Lee PPC , et al. , 2014 . Single disk failure recovery for X-code-based parallel storage systems . IEEE Trans Comput , 63 ( 4 ): 995 - 1007 . doi: 10.1109/TC.2013.8 http://doi.org/10.1109/TC.2013.8

Ye FW , Liu SQ , Shum KW , et al. , 2020 . On secure exact-repair regenerating codes with a single Pareto optimal point . IEEE Trans Inform Theory , 66 ( 1 ): 176 - 201 . doi: 10.1109/TIT.2019.2942315 http://doi.org/10.1109/TIT.2019.2942315

Zhang YZ , Wu CT , Li J , et al. , 2015 . TIP-Code: a three independent parity code to tolerate triple disk failures with optimal update complextiy . Proc 45 th Annual IEEE/IFIP Int Conf on Dependable Systems and Networks , p. 136 - 147 . doi: 10.1109/DSN.2015.19 http://doi.org/10.1109/DSN.2015.19

Zhu YF , Lee PPC , Xu YL , et al. , 2014 . On the speedup of recovery in large-scale erasure-coded storage systems . IEEE Trans Parall Distrib Syst , 25 ( 7 ): 1830 - 1840 . doi: 10.1109/TPDS.2013.244 http://doi.org/10.1109/TPDS.2013.244

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

DDUC: an erasure-coded system with decoupled data updating and coding