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