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!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!