TA-Update: An Adaptive Update Scheme with Tree-Structured Transmission in Erasure-Coded Storage Systems

被引:32
作者
Wang, Yijie [1 ]
Pei, Xiaoqiang [1 ]
Ma, Xingkong [1 ]
Xu, Fangliang [1 ]
机构
[1] Natl Univ Def Technol, Coll Comp, Natl Key Lab Parallel & Distributed Proc, Changsha 410073, Hunan, Peoples R China
基金
中国国家自然科学基金;
关键词
Distributed storage system; data update; update tree; erasure codes; REPLICATION; RECOVERY;
D O I
10.1109/TPDS.2017.2717981
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Erasure coding has received considerable attentions due to the better tradeoff between the space efficiency and reliability. The frequent update of the stored data in the distributed storage systems has posed a new challenge for erasure codes: how to update the erasure-coded data in a general, efficient and adaptive way. However, existing update schemes of erasure codes are inadequate to meet these requirements, since their code-related update manners lead to a low generality, their star-structured data transmission manners lead to a low update efficiency, and their redo manners when encountering the node failure lead to a low adaptivity. In this paper, we propose an adaptive update scheme with the tree-structured transmission, called TA-Update, which consists of a code-independent update framework and three algorithms: the rack-aware tree construction algorithm, the top-down data processing algorithm and the rollback-based failure processing algorithm. For generality, we propose a code-independent update framework with the tree structure to support the MDS code with any coding parameter. For efficiency, a rack-aware tree construction algorithm is proposed to achieve the high available bandwidth, which organizes the data node and parity nodes as an update tree. Moreover, a top-down data processing algorithm is proposed to achieve the high transmission and computation efficiency, which pipelines the data transmission along the update tree and distributes the encoding computations among all the participating nodes. For adaptivity, we propose a rollback-based failure processing algorithm to achieve high adaptivity, which handles the node failure during update with the existing update tree in a rollback manner. To evaluate the performance of TA-Update, we conduct experiments on HDFS-RAID under various parameter settings on both 30 physical and 200 virtual machines. Extensive experiments confirm that TA-Update could support the various erasure codes with any parameter, improve the update efficiency by 30 percent and the adaptivity by 47 percent on average compared with the state-of-the-art approaches under various parameter settings.
引用
收藏
页码:1893 / 1906
页数:14
相关论文
共 26 条
[1]   Analysis of Workload Behavior in Scientific and Historical Long-Term Data Repositories [J].
Adams, Ian F. ;
Storer, Mark W. ;
Miller, Ethan L. .
ACM TRANSACTIONS ON STORAGE, 2012, 8 (02)
[2]  
[Anonymous], 2003, P 19 ACM S OP SYST P, DOI [10.1145/1165389.945450, DOI 10.1145/1165389.945450]
[3]  
Anthapadmanabhan N. P., 2010, 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), P376, DOI 10.1109/ALLERTON.2010.5706931
[4]  
Chan J.C., 2014, 12th USENIX Conference on File and Storage Technologies (FAST 14), P163
[5]  
Ellard D. J, 2004, THESIS
[6]   Cooperative Recovery of Distributed Storage Systems from Multiple Losses with Network Coding [J].
Hu, Yuchong ;
Xu, Yinlong ;
Wang, Xiaozhao ;
Zhan, Cheng ;
Li, Pei .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2010, 28 (02) :268-276
[7]  
Huang C., 2012, 2012 USENIX ANN TECH, P15
[8]   An Efficient I/O-Redirection-Based Reconstruction Scheme for Erasure-Coded Storage Clusters [J].
Huang, Jianzhong ;
Qin, Xiao ;
Liang, Xianhai ;
Xie, Changsheng .
IEEE TRANSACTIONS ON COMPUTERS, 2015, 64 (11) :3037-3050
[9]  
Jin C, 2011, 2011 IEEE POW EN SOC, P1
[10]  
Li J., 2010, INFOCOM, P2892, DOI DOI 10.1109/INFCOM.2010.5462122