Computer Science ›› 2016, Vol. 43 ›› Issue (9): 203-208.doi: 10.11896/j.issn.1002-137X.2016.09.040

Previous Articles     Next Articles

Partially Regenerating Codes Combined with Replicas

DING Bing-chen and LI Wei-zhong   

  • Online:2018-12-01 Published:2018-12-01

Abstract: n,k,d) Regenerating codes(RC) significantly reduce repair bandwidth by allowing storage nodes to send the linear combinations of their data to the newcomer and increasing repair degree d.But they bring in more participating nodes and disk I/O.To solve this problem,this paper introduced partially regenerating codes(PRC) which combine RC (n,k,d,λ,θ) with replicas.PRC have also a threshold function and two special points:minimum-storage point and minimum-bandwidth point.PRC can simultaneously reduce repair bandwidth and disk I/O by utilizing repair degree d and replica factor θ.When the storage capacity of all nodes are the same,the repair bandwidth and disk I/O per node of PRC are superior to that of RC.The results of quantitative comparison also show that,comparing to RC,on minimum-storage point,PRC have less mean repair bandwidth and disk I/O;on minimum-bandwidth point,PRC have less mean disk I/O and mean repair bandwidth to similar RC.What’s more important is that PRC is achievable when d≤n-2.

Key words: Regenerating codes,Replica,Repair bandwidth,Disk I/O,Repair degree

[1] Weatherspoon H,Kubiatowicz J D.Erasure coding vs.repli-cation:A quantitative comparison[C]∥International Workshop on Peer-to-Peer Systems.Cambridge,Massachusetts,United States:Springer Berlin Heidelberg,2002:328-337
[2] Luo Xiang-hong,Shu Ji-wu.Summary of Research for Erasurce Code in Storage System[J].Journal of Computer Research and Development,2012,9(1):1-11(in Chinese) 罗象宏,舒继武.存储系统中的纠删码研究综述[J].计算机研究与发展,2012,49(1):1-11
[3] Huang Cheng,Simitci H,Xu Yi-kang,et al.Erasure coding in windows azure storage[C]∥Usenix Conference on Technical Conference.Berkeley,CA,USA:USENIX,2012:2
[4] Sathiamoorthy M,Asteris M,Papailiopoulos D,et al.XORing ele-phants:Novel erasure codes for big data[C]∥VLDB Endowment.Riva del Garda,Italy:dbTrento,2013:325-336
[5] Rodrigues R,Liskov B.High availability in DHTs:Erasure co-ding vs.replication[C]∥Proc of IPTPS.Ithaca,NY,USA:Springer Berlin Heidelberg,2005:226-239
[6] Rashmi K V,Nakkiran P,Wang Jing-yan,et al.Having Your Cake and Eating It Too:Jointly Optimal Erasure Codes for I/O,Srorage,and Network-banwidth[C]∥USENIX Conference on File and Storage Technologies.Santa Clare,CA,USA:USENIX,2015:81-94
[7] Dimakis A G,Godfrey P B,Wu Yun-nan,et al.Network coding for distributed storage systems[J].IEEE Trans on Information Theory,2010,56(9):4539-4551
[8] Ahlswede R,Cai N,Li S Y R,et al.Network information flow[J].IEEE Trans on Information Theory,2000,46(4):1204-1216
[9] Lin S J,Chung W H.Novel Repair-by-Transfer Codes and Systematic Exact-MBR Codes with Lower Complexities and Smaller Field Sizes[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(12):3232-3241
[10] Hu Yu-chong,Lee P,Shum K W.Analysis and construction of functional regenerating codes with uncoded repair for distributed storage systems[C]∥INFOCOM.Turin:IEEE,2013:2355-2363
[11] Yang Bin,Tang Xiao-hu,Li Jie.A Systematic Piggybacking Design for Minimum Storage Regenerating Codes[J].IEEE Tran-sactions on Information Theory,2015,61(11):5779-5786
[12] Liang Song-tao,Liang Wen-juan,Kan Hai-bin.Construction of one special minimum storage regenerating code when α=2[J].Science China Information Sciences,2015,58(8):1-10
[13] Bhagwan R,Tati K,Cheng Yu-chung,et al.Total recall:System support for automated availability management[J].Nsdi,2004,1:337-350
[14] Shvachko K,Kuang H,Radia S,et al.The Hadoop distributed file system[C]∥Symp.on Mass Storage Systems and Technologies.USA:IEEE,2010:1-10
[15] Bhagwan R,Savage S,Voelker G M.Understanding availability[C]∥International Workshop on Peer-to-Peer Systems.Berkeley,California,USA:Springer Berlin Heidelberg,2003:256-257
[16] Hwang K,Fox G C,Dongarra J J.Distributed and Cloud Computing:From Parallel Processing to the Internet of Things[M].Morgan Kaufmann,2011
[17] Dimakis A G,Ramchandran K,Wu Yun-nan,et al.A Survey on network codes for distributed storage[J].Proceeding of the IEEE,2011,99(3):476-489
[18] Rashmi K V,Shah N B,Kumar P V.Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction[J].IEEE Transaction on Information Theory,2011,57(8):5227-5239
[19] Hu Yu-chong,Xu Yin-long,Wang Xiao-zhao,et al.CooperativeRecovery of Distributed Storage Systems from Multiple Losses with Network Coding[J].IEEE Journal on Selected Areas in Communications,2010,28(2):268-276
[20] Kermarrec A M,Scouarnec N L,Straub G.Repairing multiplefailures with coordinated and adaptive regenerating codes[C]∥International Symposium on Network Coding.Beijing:IEEE,2011:1-6

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .