计算机科学 ›› 2019, Vol. 46 ›› Issue (8): 35-41.doi: 10.11896/j.issn.1002-137X.2019.08.006

• 大数据与数据科学* • 上一篇    下一篇

异构分布式存储系统再生码数据修复的节点选择方案

钟凤艳, 王艳, 李念爽   

  1. (华东交通大学软件学院 南昌330013)
  • 收稿日期:2018-07-12 出版日期:2019-08-15 发布日期:2019-08-15
  • 通讯作者: 王艳(1982-),女,博士,副教授,主要研究方向为分布式存储、数据可靠性等,E-mail:wangyann@189.cn
  • 作者简介:钟凤艳(1993-),女,硕士,主要研究方向为分布式存储,E-mail:1215396009@qq.com;李念爽(1993-),男,硕士,主要研究方向为分布式存储
  • 基金资助:
    国家自然科学基金项目(61402172),江西省教育厅项目(GJJ150509),教育部人文社科基金(15YJA860013)

Node Selection Scheme for Data Repair in Heterogeneous Distributed Storage Systems

ZHONG Feng-yan, WANG Yan, LI Nian-shuang   

  1. (School of Software,East China Jiaotong University,Nanchang 330013,China)
  • Received:2018-07-12 Online:2019-08-15 Published:2019-08-15

摘要: 近年来,海量数据的增长给现有的存储系统带来了严峻的挑战,包括存储成本和数据可靠性要求等。纠删码由于在相同的存储开销下可以提供更高的数据可靠性,得到了学术界和工业界的广泛关注。但由于纠删码的编码特性,让使用纠删码的存储系统在数据修复过程中增加了许多其他方面的额外开销,如计算、调度、传输、磁盘读写等。近年来对纠删码数据修复的研究都基于这样一个假定:分布式存储系统中各个节点是无差别的。然而,实际情况是,在大规模的数据中心中,设备替换、硬件故障等原因不仅会导致数据丢失,还会导致数据中心的各个存储节点的存储成本不同,从而使每个存储节点上所存储的数据量并不总是相等,这种现象被称为存储容量异构。存储容量异构场景下的修复过程面临供应节点的选择问题,需要设计一个节点选择策略来降低修复开销,提高存储系统的可靠性和可用性。鉴于实际数据修复过程中参与修复的节点对数据的传输成本不同,提出节点选择策略——树形拓扑修复算法,以降低整个修复过程中的修复成本。仿真结果表明,相对IFR码的固定节点选择策略,文中提出的树形选择策略在平均情况下可以进一步降低数据修复成本。

关键词: 分布式存储系统, 节点异构, 数据修复, 再生码

Abstract: In recent years,the growth of massive data poses severe challenges to existing storage systems,including storage cost and data reliability requirements.Because erasure code can provide higher data reliability under the same storage overhead,it has been paid wide attention.However,the coding characteristics of erasure code increases the extra overhead for the storage system using erasure code,in the process of data repair,such as computing,scheduling,transmission,disk reading and writing,and so on.In recent years,the study of erasure code data recovery is based on the assumption that each node in the distributed storage system is indiscriminate.In a large scale of data center,however,equipment replacement,hardware failure and other reasons may not only cause data loss,but also lead to different sto-rage cost of each storage node in the data center,so that the amount of data stored on each storage node is not always the same,this phenomenon is called storage capacity isomerism.The repair process under the heterogeneous storage capacity is faced with the selection of the providers.It is necessary to design a node selection strategy to make the repair cost lower,and improve the reliability and availability of the storage system.Based on the different transformation cost of nodes participating in repair in the actual repair process of data,this paper proposed a node selection strategy,namely tree topology repair algorithm,to reduce the cost of repair in the whole repair process.The simulation results show that the proposed tree selection strategy can further reduce the cost of data repair compared with the fixed node selection strategy of IFR code

Key words: Data repair, Distributed storage system, Node heterogeneity, Regenerating code

中图分类号: 

  • TP309.3
[1]HUANG C,SIMITCI H,XU Y,et al.Erasure coding in windows azure storage[C]∥Usenix Conference on Technical Conference.USENIX Association,2012:2.
[2]BEAVER D,KUMAR S,LI H C,et al.Finding a needle in Haystack:facebook’s photo storage[C]∥Usenix Conference on Operating Systems Design and Implementation.USENIX Association,2010:47-60.
[3]RASHMI K V,BORTHAKUR D,BORTHAKUR D,et al.A “hitchhiker’s” guide to fast and efficient data reconstruction in erasure-coded data centers[C]∥ACM Conference on SIGCOMM.ACM,2014:331-342.
[4]杨传辉.大规模分布式存储系统:原理解析与架构实战[M].北京:机械工业出版社,2013.
[5]ZOU S C,WANG H Q,FENG G S,et al.Multi-strategy Trust Evolution Model for Cognitive relay Network Based on Moran Process[J].Journal of Chinese Computer Systems,2014,35(10):2209-2214.(in Chinese) 邹世辰,王慧强,冯光升,等.基于Moran过程的认知中继网络多策略信任演化模型[J].小型微型计算机系统,2014,35(10):2209-2214.
[6]SCHROEDER B,GIBSON G.Disk failures in the real world: What does an mttf of 1000000 hours mean to you?[C]∥Proc.of USENIX FAST.2007.
[7]SONG Y,ZHANG F,SHAO Y,et al.Energy efficiency optimization of cognitive relay network based on cooperative spectrum sensing[J].The Journal of China Universities of Posts and Telecommunications,2015,22(3):26-34.
[8]BANG J,LEE J,KIM S,et al.An Efficient Relay Selection Strategy for Random Cognitive Relay Networks[J].IEEE Transactions on Wireless Commsunications,2015,14(3):1555-1566.
[9]BORTHAKUR D.HDFS architecture guide[OL].[2013-08- 04].http://hadoop.apache.org/docs/r1.2.1/hdfs_design.html.
[10]ASTERIS M,ASTERIS M,PAPAILIOPOULOS D,et al.XORing elephants:novel erasure codes for big data[J].Proceedings of the VLDB Endowment,2013,6(5):325-336.
[11]DIMAKIS A G,GODFREY P B,WU Y,et al.Network coding for distributed storage systems[J].IEEE Transactions on Information Theory,2010,56(9):4539-4551.
[12]DIMAKIS A G,BRIGHTEN P,WAINWRIGHT M J,et al.The Benefits of Network Coding for Peer-to-Peer Storage Systems[C]∥Proceedings of the International Conference on Computer Communications (INFOCOM).2007.
[13]WANG Y,YIN X,WANG X.Two New Classes of Two-Parity MDS Array Codes With Optimal Repair[J].IEEE Communications Letters,2016,20(7):1293-1296.
[14]SHEN Z,LEE P P C,SHU J,et al.Encoding-Aware Data Placement for Efficient Degraded Reads in XOR-Coded Storage Systems[C]∥Reliable Distributed Systems.IEEE,2016:239-248.
[15]YE L,FENG D,HU Y,et al.Hybrid-RC:Flexible Erasure Codes with Optimized Recovery Performance and Low Storage Overhead[C]∥Reliable Distributed Systems.IEEE,2017:124-133.
[16]WANG J,LUO W,OUYANG M S,et al.Segmentation Coding Scheme Based on Simple Regenerating Codes[J].Computer Science,2016,43(8):148-153.(in Chinese) 王静,罗威,欧阳明生,等.基于简单再生码的分段编码方案[J].计算机科学,2016,43(8):148-153.
[17]AKHLAGHI S,KIANI A,GHANAVATI M R.Cost-ban- dwidth tradeoff in distributed storage systems[J].Computer Communications,2010,33(17):2105-2115.
[18]GERAMI M,XIAO M,SKOGLUND M.Optimal-cost repair in multi-hop distributed storage systems[C]∥IEEE International Symposium on Information Theory Proceedings.IEEE Xplore,2012:1437-1441.
[19]LI S T,JIN X.Low-cost cloud storage scheme based on hybrid strategy[J].Journal of Computer Applications,2014,34(10):2800-2805.(in Chinese) 李松涛,金欣.基于混合策略的低成本云存储方案[J].计算机应用,2014,34(10):2800-2805.
[20]DU Y,XIONG R,JIN J,et al.A Cost-Efficient Data Placement Algorithm with High Reliability in Hadoop[C]∥International Conference on Advanced Cloud & Big Data.IEEE Computer Society,2017:100-105.
[21]YU Q,SHUM K W,CHI W S.Minimization of Storage Cost in Distributed Storage Systems with Repair Consideration[C]∥Global Telecommunications Conference.IEEE,2012:1-5.
[22]YU Q,CHI W S,CHAN T H.Irregular Fractional Repetition Code Optimization for Heterogeneous Cloud Storage[J].IEEE Journal on Selected Areas in Communications,2014,32(5):1048-1060.
[23]LI J,YANG S,WANG X,et al.Tree-structured data regeneration in distributed storage systems with regenerating codes[C]∥Proc of the IEEE INFOCOM.Piscataway,NJ:IEEE,2010:1-9.
[24]XIA M,SAXENA M,BLAUM M,et al.A tale of two erasure codes in HDFS[C]∥Usenix Conference on File and Storage Technologies.USENIX Association,2015:213-226.
[25]CORMEN T H,LEISERSON C E,RIVEST R L,et al.Introduction to Algorithms(Second Edition)[M].DBLP,2001.
[26]GONG Q,WANG J,WANG Y,et al.Topology-Aware Node Selection for Data Regeneration in Heterogeneous Distributed Storage Systems[J].arXiv preprint arXiv:1506.05579,2015.
[27]SHAH N B,RASHMI K V,KUMAR P V.A flexible class of regenerating codes for distributed storage[C]∥IEEE International Symposium on Information Theory.IEEE,1947:1943-1947.
[28]LI J,YANG S,WANG X,et al.Tree-structured data regeneration with network coding in distributed storage systems[C]∥International Workshop on Quality of Service.IEEE,2009:2892-2900.
[1] 张航, 唐聃, 蔡红亮.
分布式存储系统中的预测式纠删码研究
Study on Predictive Erasure Codes in Distributed Storage System
计算机科学, 2021, 48(5): 130-139. https://doi.org/10.11896/jsjkx.200300124
[2] 张晓, 张思蒙, 石佳, 董聪, 李战怀.
Ceph分布式存储系统性能优化技术研究综述
Review on Performance Optimization of Ceph Distributed Storage System
计算机科学, 2021, 48(2): 1-12. https://doi.org/10.11896/jsjkx.201000149
[3] 王雪冰.
一种参数可变的最小存储再生码
Minimum Storage Regenerating Code with Variable Parameters
计算机科学, 2020, 47(6A): 305-309. https://doi.org/10.11896/JsJkx.190600063
[4] 刘琴.
计算机取证过程中基于约束的数据质量问题研究
Study on Data Quality Based on Constraint in Computer Forensics
计算机科学, 2018, 45(4): 169-172. https://doi.org/10.11896/j.issn.1002-137X.2018.04.028
[5] 丁炳辰,李卫忠.
与副本结合的部分再生码
Partially Regenerating Codes Combined with Replicas
计算机科学, 2016, 43(9): 203-208. https://doi.org/10.11896/j.issn.1002-137X.2016.09.040
[6] 王静,罗威,欧阳明生,姜灿,王新梅.
基于简单再生码的分段编码方案
Segmentation Coding Scheme Based on Simple Regenerating Codes
计算机科学, 2016, 43(8): 148-153. https://doi.org/10.11896/j.issn.1002-137X.2016.08.031
[7] 刘波,蔡美,周绪川.
数据修复与一致性查询处理研究
Study on Data Repair and Consistency Query Processing
计算机科学, 2016, 43(1): 232-236. https://doi.org/10.11896/j.issn.1002-137X.2016.01.050
[8] 王禹,赵跃龙,侯昉.
基于矩阵运算的最小冗余存储再生码MSRRC研究
Minimum Redundancy Storage Regeneration Code Research MSRRC Based on Matrix Operation
计算机科学, 2014, 41(Z11): 191-194.
[9] 陈达智,赵荣彩,姚远,韩林.
MPI自动并行化编译系统中消息传递代码生成算法
Message-passing Code Generation Algorithm in the MPI Automatic Parallelizing Compilation System
计算机科学, 2012, 39(6): 301-304.
[10] .
P2P分布式存储系统

计算机科学, 2007, 34(6): 47-48.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!