一类基于极图理论的局部修复编码的性质及构造
|
摘要
由于分布式存储系统大量使用廉价的磁盘构建,磁盘故障往往不可避免导致数据丢失.数据编码是一种防止数据丢失的必要容错机制.局部修复码与经典的最大距离可分(MDS)码相比,以一定的存储空间开销,能够有效提高数据修复的效率,降低网络带宽占用.为了降低该码的存储空间开销,本文研究以极图理论来描述该类编码.将存储节点与编码块抽象为二分图中的X、Y两类顶点,从而存储空间占用最小化等价于计算二分图中边数的极小值.这种求极值问题可以归结为Zarankiewicz问题.本文使用极值二分图对局部修复码进行建模与分析,并给出了相应的构造算法.
Because distributed storage systems are typically built with a great quantity of inexpensive disks,disk failures often inevitably lead to data loss. Data encoding is a necessary fault-tolerant mechanism to prevent data loss. Compared with the classical Maximum Distance Separable(MDS)code,the local repair code can effectively improve the efficiency of data repair and reduce the bandwidth usage with a certain storage space overhead. This paper uses the theory of extremal graph to reduce the storage overhead of local repair code. Taking the storage nodes and coded blocks as X-class and Y-class vertices in binary graph respectively,the minimum storage space occupancy is correspondingly equivalent to calculating the minimum number of edges in this graph. Such extreme problem can be attributed to the Zarankiewicz problem. This paper uses extremal bipartite graph to model and analyze the local repair code,and gives the corresponding construction algorithm.
Because distributed storage systems are typically built with a great quantity of inexpensive disks,disk failures often inevitably lead to data loss. Data encoding is a necessary fault-tolerant mechanism to prevent data loss. Compared with the classical Maximum Distance Separable(MDS)code,the local repair code can effectively improve the efficiency of data repair and reduce the bandwidth usage with a certain storage space overhead. This paper uses the theory of extremal graph to reduce the storage overhead of local repair code. Taking the storage nodes and coded blocks as X-class and Y-class vertices in binary graph respectively,the minimum storage space occupancy is correspondingly equivalent to calculating the minimum number of edges in this graph. Such extreme problem can be attributed to the Zarankiewicz problem. This paper uses extremal bipartite graph to model and analyze the local repair code,and gives the corresponding construction algorithm.
引文
[1]Li J,Yang S,Wang X,et al.Treestructured data regeneration with network coding in distributed storage systems[C]//Quality of Service.Charleston,SC,USA:IEEE,2009.
[2]Gerami M,Xiao M,Skoglund M.Optimal-cost repair in multihop distributed storage systems[C]//Information Theory Proceedings(ISIT).St.Petersburg,Russia:IEEE,2011.
[3]Ernvall T,El Rouayheb S,Hollanti C,et al.Capacity and Security of Heterogeneous Distributed Storage Systems[J].IEEE Journal on Selected Areas in Communications,2013,31(12):2701-2709.
[4]Yu Q,Sung C W,Chan T H.Irregular fractional repetition code optimization for heterogeneous cloud storage[J].IEEEJournal on Selected Areas in Communications,2014,32(5):1048-1060.
[5]Khan O,Burns R,Plank J,et al.Rethinking erasure codes for cloud file systems:miniminizing I/O for recovery and degraded reads[C]//10th USENIX Conference on File and Storage Technologies.SAN JOSE,CA:FAST,2012.
[6]Huang C,Simitci H,Xu Y,et al.Erasure coding in windows azure storage[C]//Usenix Conference on Technical Conference.Berkeley,CA,USA:USENIX,2012.
[7]Dimakis A G,Godfrey P B,Wu Y,et al.Network coding for distributed storage systems[J].IEEE Information Theory Society,2010,56(9):4539-4551.
[8]Dimakis A G,Ramchandran K,Wu Y,et al.A Survey on network codes for distributed storage[J].Proceedings of the IEEE,2011,99(3):476-489.
[9]Papailiopoulos D S,Dimakis A G.Locally repairable codes[J].IEEE Transactions on Information Theory,2014,60(10):5843-5855.
[10]Rashmi K V,Shah N B,Kumar P V,et al.Explicit construction of optimal exact regenerating codes for distributed storage[J].IEEE Transactions on Information Theory,2011,57(8):5227-5239.
[11]Gopalan P,Huang C,Simitci H,et al.On the locality of codeword symbols[J].IEEE Transactions on Information Theory,2012,58(11):6925-6934.
[12]Oggier F,Datta A.Self-repairing homomorphic codes for distributed storage systems[C]//IEEE Infocom.Shanghai,China:IEEE,2011.
[13]Tamo I,Papailiopoulos D S,Dimakis A G.Optimal locally repairable codes and connections to matroid theory[J].IEEETransactions on Information Theory,2013,62(12):6661-6671.
[14]Silberstein N,Rawat A S,Koyluoglu O O,et al.Optimal locally repairable codes via rank-metric codes[C]//IEEEInternational Symposium on Information Theory.Istanbul,Turkey:IEEE,2013.
[15]Kamath G M,Prakash N,Lalitha V,et al.Codes with local regeneration[C]//Information Theory&Applications Workshop.San Diego,CA,USA:IEEE,2013.
[16]Silberstein N,Etzion T.Optimal fractional repetition codes based on graphs and designs[J].IEEE Transactions on Information Theory,2015,61(8):4164-4180.
[17]LászlóBabai,Guiduli B.Spectral extrema for graphs:the zarankiewicz problem[J].Electronic Journal of Combinatorics,2009,16(1):1878-1892.
[18]Sierpinski S.Problems in the theory of numbers[M].Pergamon:Oxford,1964.
[19]Culik K.Teilweise losung eines verall gemeinerten problems von zarankiewicz[J].Anna.Soc.Polon,1956,3(3):165-168.
[20]Zoltán Füredi.An upper bound on zarankiewicz'problem[J].Combinatorics Probability and Computing,1996,5(1):29-33.
[21]Guy R K,Znam S.A problem of zarankiewicz in recent progress in:combinatorics[M].New York:Academic Press,1969.
[22]Balbuena C,García-Vázquez P,Marcote X,et al.Extremal K(s,t)-free bipartite graphs[J].Discrete Mathematics&Theoretical Computer Science DMTCS,2008,10(3):35-48.
[2]Gerami M,Xiao M,Skoglund M.Optimal-cost repair in multihop distributed storage systems[C]//Information Theory Proceedings(ISIT).St.Petersburg,Russia:IEEE,2011.
[3]Ernvall T,El Rouayheb S,Hollanti C,et al.Capacity and Security of Heterogeneous Distributed Storage Systems[J].IEEE Journal on Selected Areas in Communications,2013,31(12):2701-2709.
[4]Yu Q,Sung C W,Chan T H.Irregular fractional repetition code optimization for heterogeneous cloud storage[J].IEEEJournal on Selected Areas in Communications,2014,32(5):1048-1060.
[5]Khan O,Burns R,Plank J,et al.Rethinking erasure codes for cloud file systems:miniminizing I/O for recovery and degraded reads[C]//10th USENIX Conference on File and Storage Technologies.SAN JOSE,CA:FAST,2012.
[6]Huang C,Simitci H,Xu Y,et al.Erasure coding in windows azure storage[C]//Usenix Conference on Technical Conference.Berkeley,CA,USA:USENIX,2012.
[7]Dimakis A G,Godfrey P B,Wu Y,et al.Network coding for distributed storage systems[J].IEEE Information Theory Society,2010,56(9):4539-4551.
[8]Dimakis A G,Ramchandran K,Wu Y,et al.A Survey on network codes for distributed storage[J].Proceedings of the IEEE,2011,99(3):476-489.
[9]Papailiopoulos D S,Dimakis A G.Locally repairable codes[J].IEEE Transactions on Information Theory,2014,60(10):5843-5855.
[10]Rashmi K V,Shah N B,Kumar P V,et al.Explicit construction of optimal exact regenerating codes for distributed storage[J].IEEE Transactions on Information Theory,2011,57(8):5227-5239.
[11]Gopalan P,Huang C,Simitci H,et al.On the locality of codeword symbols[J].IEEE Transactions on Information Theory,2012,58(11):6925-6934.
[12]Oggier F,Datta A.Self-repairing homomorphic codes for distributed storage systems[C]//IEEE Infocom.Shanghai,China:IEEE,2011.
[13]Tamo I,Papailiopoulos D S,Dimakis A G.Optimal locally repairable codes and connections to matroid theory[J].IEEETransactions on Information Theory,2013,62(12):6661-6671.
[14]Silberstein N,Rawat A S,Koyluoglu O O,et al.Optimal locally repairable codes via rank-metric codes[C]//IEEEInternational Symposium on Information Theory.Istanbul,Turkey:IEEE,2013.
[15]Kamath G M,Prakash N,Lalitha V,et al.Codes with local regeneration[C]//Information Theory&Applications Workshop.San Diego,CA,USA:IEEE,2013.
[16]Silberstein N,Etzion T.Optimal fractional repetition codes based on graphs and designs[J].IEEE Transactions on Information Theory,2015,61(8):4164-4180.
[17]LászlóBabai,Guiduli B.Spectral extrema for graphs:the zarankiewicz problem[J].Electronic Journal of Combinatorics,2009,16(1):1878-1892.
[18]Sierpinski S.Problems in the theory of numbers[M].Pergamon:Oxford,1964.
[19]Culik K.Teilweise losung eines verall gemeinerten problems von zarankiewicz[J].Anna.Soc.Polon,1956,3(3):165-168.
[20]Zoltán Füredi.An upper bound on zarankiewicz'problem[J].Combinatorics Probability and Computing,1996,5(1):29-33.
[21]Guy R K,Znam S.A problem of zarankiewicz in recent progress in:combinatorics[M].New York:Academic Press,1969.
[22]Balbuena C,García-Vázquez P,Marcote X,et al.Extremal K(s,t)-free bipartite graphs[J].Discrete Mathematics&Theoretical Computer Science DMTCS,2008,10(3):35-48.