基于矩阵运算的最小冗余存储再生码MSRRC研究

计算机科学 ›› 2014, Vol. 41 ›› Issue (Z11): 191-194.

基于矩阵运算的最小冗余存储再生码MSRRC研究

王禹,赵跃龙,侯昉

广东技术师范学院教育技术与传播学院广州510665;华南理工大学计算机科学与工程学院广州510640;华南理工大学计算机科学与工程学院广州510640;广东金融学院计算机系广州510520

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受国家自然科学基金(60573145),广东省科技创新项目(2013KJCX0116),广东省教育科学规划项目(2012JK048),广东高校优秀青年创新人才培养计划项目(2012WYM_0088),数字媒体本科专业核心课程体系研究项目资助

Minimum Redundancy Storage Regeneration Code Research MSRRC Based on Matrix Operation

WANG Yu,ZHAO Yue-long and HOU Fang

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： 分布式存储系统常常使用纠删码冗余技术提高数据的安全性和可靠性,从而使系统具有自修复失效数据的能力,但传统纠删码在修复失效节点时需要传输的数据量较大。再生码是纠删码的一种改进形式,它的主要特点是无需下载整个数据文件就能恢复单个节点数据,从而有效减少了数据修复时的网络带宽。相关文献证明数据修复时存在最小存储再生点(MSR),由此提出最小冗余存储再生码MSRRC。本研究主要采用数据矩阵和修复矩阵实现MSRRC再生码,通过实例详细给出再生码的实现过程,并理论证明其正确性,最后仿真实验验证了MSRRC的有效性。

关键词: 分布式系统,再生码,数据修复

Abstract: Distributed storage systems often use erasure code redundancy technology to improve the safety and reliability of the data,so that the system has the ability to self repair failure data,but the traditional erasure codes need to transfer the large amount of data in order to repair failure nodes.Regeneration code is an improved form of erasure code,and its main characteristic is that it does not need to download the entire data file when restoring a single node data,which can effectively reduce the network bandwidth when repairing data.The relevant documents prove that data repair has minimal storage regeneration point(MSR),so presents minimum redundancy storage regeneration code MSRRC.Research mainly used the data matrix and the repair matrix to achieve MSRRC,and through examples,detailly introduced the realization process of regenerating codes,and proved the correctness of the theory.The simulation results verify the validity of MSRRC.

Key words: Distributed system,Regeneration code,Data repairing

王禹,赵跃龙,侯昉. 基于矩阵运算的最小冗余存储再生码MSRRC研究[J]. 计算机科学, 2014, 41(Z11): 191-194. https://doi.org/

WANG Yu,ZHAO Yue-long and HOU Fang. Minimum Redundancy Storage Regeneration Code Research MSRRC Based on Matrix Operation[J]. Computer Science, 2014, 41(Z11): 191-194. https://doi.org/

参考文献

[1] Patterson D A,Gibson G,Katz R H.A case for redundant arraysof inexpensive disks(RAID)[C]∥Proc.ACM SIGMOD Chicage.USA,June 1988:109-116
[2] Kubiatowicz J,Bindel D,Chen Y,et al.OceanStore:An Architecture for Global-Scale Persistent Store[C]∥Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS 2000).2000:190-201
[3] Bhagwan R,Kati K,Cheng Y-C,et al.Total recall:System support for automated availability management[C]∥Proc.of ACM/USENIX NSDI’04.2004:337-350
[4] Wu Y,Dimakis A G,Ramchandran K.Deterministic regenera-ting codes for distributed storage[C]∥Allerton Conference on Control,Computing and Communication.Monticello,October 2007
[5] Wang Z,Dimakis A G,Bruck J.Rebuilding for Array Codes in Distributed Storage Systems[C]∥Workshop on the Application of Communication Theory to Emerging Memory Technologies (ACTEMT).Dec.2010
[6] Akhlaghi S,Kiani A,Ghanavati M R.A Fundamental Tradeoff between the download cost and repair bandwidth in distributed Storage systems[C]∥Proceeding of IEEE International Symposium on network Coding (NetCod).Toronto,Jun.2010
[7] Shah N B,Rashmi K V,Kumar P V.A Flexible Class of generating Codes for Distributed Storage[C]∥Proceeding of IEEE International symposium on information theory (ISIT).Austin,Jun.2010:1943-1947
[8] Gaston B,Pujol J.Double Circulate Minimum Storage generating Codes.2010.http://arXiv:1007.2401[cs.IT]
[9] Wang Z,Mateescu R,Dimakis A G,et al.Array codes for distributed storage:Results and open problems[J].Information Tehory and Application.ITA,2010
[10] Wu Y.Existence and construction of capacity-achieving network codes for distributed storage[J].Journal on Selected Areas in Communications,2010,28(2):277-288
[11] Li J,Yang S,Wang Xin,et al.Tree structured Data Regeneration in Distributed Storage Systems with Regenerating Codes[C]∥Proceedings of IEEE INFOCOM.2010
[12] Shah N B,Rashmi K V,Kumar P V,et al.Distributed Storage Codes with Repair-by-Transfer and Non-achievability of Interior Points on the Storage-Bandwidth Tradeoff[C]∥Allerton Conf..Urbana-Champaign,Sep.2009
[13] Dimakis A G,Godfrey P G,Wainwright M J,et al.Network co-ding for peer-to-peer storage[C]∥Proceeding of INFOCOM.Anchorage,Alaska,May 2007
[14] Wu Y,Dimakis A G,Ramchandran K.Deterministic regenera-ting codes for distributed storage[C]∥Allerton Conference on Control,Computing,and Communication.Monticello,October 2007
[15] Shah N B,Rashmi K V,Kumar P V,et al.Distributed storage codes with repair-by-transfer and non-achievability of interior points on the storage-bandwidth tradeoff[J/OL].http://arxiv.org/abs/1011.236
[16] Wu Y,Dimakis A G,Ramchandran K.Deterministic Regenerating codes for distributed storage[C]∥Proc.Allerton Conf..Urbana-Champaign,Sep.2007
[17] Ramabhadran S,Pasquale J.Analysis of durability in replicated distrusted storage systems[C]∥2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS).Atlanta,GA,April 2010:1-12
[18] 王禹,赵跃龙,侯昉.基于副本管理的P2P存储系统的可靠性问题研究[J].华南理工大学学报,2011,39(2):148-152
[19] 王禹,赵跃龙,侯昉,分布式存储系统最小带宽再生码研究[J].小型微型计算机系统,2012,33(8):1710-1714

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed