与副本结合的部分再生码
|
摘要
(n,k,d)再生码允许存储节点传送所存数据的线性组合以及增加修复入度d,显著地降低了修复带宽,但是引入了更多的参与节点数及磁盘I/O。针对这一不足,提出了一种将复制方式与再生码结合的(n,k,d,λ,θ)部分再生码,并得到了与再生码类似的阈值函数和2个特殊点——最小存储量点和最小修复带宽点。部分再生码可以综合利用修复入度d和副本因子θ同时降低修复带宽和磁盘I/O。当所有的节点存储量相等时,部分再生码的单点修复带宽和磁盘I/O均优于再生码。定量比较的结果也显示,在最小存储量点,部分再生码比再生码有更低的平均修复带宽和平均磁盘I/O;在最小修复带宽点,部分再生码有更低的平均磁盘I/O以及与再生码相近的平均修复带宽。更重要的是,部分再生码适用于d≤n-2的所有情形。
(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 dand 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.
(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 dand 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.
引文
[1]Weatherspoon H,Kubiatowicz J D.Erasure coding vs.replication: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,49(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 elephants: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 coding 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:USE-NIX,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 Transactions 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.Cooperative Recovery 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 multiple failures with coordinated and adaptive regenerating codes[C]∥International Symposium on Network Coding.Beijing:IEEE,2011:1-6
[2]Luo Xiang-hong,Shu Ji-wu.Summary of Research for Erasurce Code in Storage System[J].Journal of Computer Research and Development,2012,49(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 elephants: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 coding 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:USE-NIX,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 Transactions 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.Cooperative Recovery 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 multiple failures with coordinated and adaptive regenerating codes[C]∥International Symposium on Network Coding.Beijing:IEEE,2011:1-6