基于FRC码的分布式存储编码优化算法研究

发布时间：2017-11-08 07:26

  本文关键词：基于FRC码的分布式存储编码优化算法研究

  更多相关文章： 分布式存储 纠删编码 分片复制码 杨氏矩阵 禁忌搜索

【摘要】：随着计算机技术的快速进步,数据的爆炸性增长迫使人们对计算机存储系统提出了越来越高的要求。分布式存储系统由于其低廉的价格和优异的性能而被人们所青睐。由分布式存储系统所衍生的云存储技术被各大IT企业采用且全面走向商业化。然而,网络存储节点的不可靠性使得系统需使用大量的存储空间存放冗余数据,同时在节点失效时进行高频的节点修复。这严重浪费了系统有限的网络带宽和存储资源,降低存储服务的质量。因此,分布式存储系统不仅需要保证容多节点故障,而且需要降低修复过程中的网络消耗。于是,各种容错编码技术,尤其是再生码,得到深入研究。文献[1]提出一种Fractional Repetition(分片复制)编码,在修复过程中不需要编码计算,带宽消耗最小,并且具有比最小带宽再生(MBR)编码更优的存储能力。已有的FRC编码往往依赖于特定的组合构造,仅仅适用于有限的参数情形。对于一般参数下情形,如何构造最优的存储能力的FRC编码被认为是一个开放性的问题。本文对基于分片复制码(FRC码)的分布式存储系统,抽象出编码矩阵的数学模型,提出了在任意参数下给出FRC码数据分布策略的方法,使得用户在取数据时需连接的存储节点数量达到最小。本文的主要工作在以下几个方面。(1)为了找到FRC码的最优编码矩阵,本文提出了基于杨氏矩阵遍历搜索最优编码矩阵的方法。首先将FRC码抽象为布尔矩阵,然后利用杨氏矩阵和布尔矩阵间的双射实现FRC码编码矩阵与杨氏矩阵间的对应,之后根据杨氏矩阵的特殊性质提出了几种剪枝优化方法。本文提出的枚举算法能在任意参数下完整的遍历存在最优FRC码的编码矩阵集合,且算法的剪枝优化方法能减少95%以上的搜索项。通过实验表明算法的效果较好。(2)在FRC编码的布尔矩阵描述的基础上,本文提出了一种在基于布尔矩阵交换操作的禁忌搜索算法。根据FRC码的性质,本文研究了其存储能力与编码矩阵中1的分布间的关系,提出并证明了FRC码存储能力与编码矩阵中的充分条件定理。在此基础上,本文提出了以C4圈计数为启发式准则的禁忌搜索算法。算法可在任意参数下给出具有最优存储能力的FRC码编码矩阵。同时本文针对算法的核心运算,提出了更快速的C4圈计数矩阵法,降低了算法的时间复杂度。实验表明,算法以不同的编码矩阵为初始搜索节点都能得到存储能力基本相同的编码矩阵,且结果编码矩阵的存储能力较为接近上界。
【学位授予单位】：天津理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP333

【相似文献】

中国期刊全文数据库 前10条

1 王征;刘心松;李美安;;企业信息分布式存储的热点处理策略[J];计算机集成制造系统;2006年09期

2 李磊;沈海斌;黄凯;严晓浪;Han Sangil;Ahmed A Jerraya;;分布式存储管理在多核设计中的高层建模[J];电子与信息学报;2008年11期

3 刘翔;汪海玲;;分布式存储中的一种数据放置策略[J];计算机与数字工程;2009年05期

4 陈卫卫;吴海佳;胥光辉;;分布式存储中文件分割的最优化模型[J];解放军理工大学学报(自然科学版);2010年04期

5 崔忠强;左德承;张展;;在云间可重构的分布式存储[J];系统工程理论与实践;2011年S2期

6 郝杰;逯彦博;刘鑫吉;夏树涛;;分布式存储中的再生码综述[J];重庆邮电大学学报(自然科学版);2013年01期

7 唐京伟;;基于云计算的分布式存储技术[J];中国传媒科技;2013年15期

8 郭栋;王伟;曾国荪;;基于一致性树分布的数据分布式存储方法[J];计算机应用;2013年12期

9 苏李亮;王云福;侯斌;;海量设计文档分布式存储及负载均衡的研究与实现[J];电信科学;2013年12期

10 谢然;;敢问存储之路在何方?见分布式存储摇曳在数据枝头[J];互联网周刊;2014年02期

中国重要会议论文全文数据库 前7条

1 苏李亮;王云福;侯斌;;海量设计文档分布式存储及负载均衡的研究与实现[A];2013电力行业信息化年会论文集[C];2013年

2 苏李亮;王云福;侯斌;;海量设计文档分布式存储及负载均衡的研究与实现[A];2013电力行业信息化年会论文集[C];2013年

3 郑文武;李先绪;黄植勤;邱红飞;;云存储关键技术[A];2012全国无线及移动通信学术大会论文集（下）[C];2012年

4 蒋轶林;郭淑琴;;分布式存储在数字集群移动通信系统中的应用[A];浙江省电子学会2013学术年会论文集[C];2013年

5 姜继忱;陈钢;;P2P之路——缔造“分布式对等”的Internet3.0[A];全面建设小康社会：中国科技工作者的历史责任——中国科协2003年学术年会论文集（下）[C];2003年

6 付伟;肖侬;卢锡城;;QoS感知的副本放置问题研究综述[A];第15届全国信息存储技术学术会议论文集[C];2008年

7 张彦;刘欣然;徐慧彬;;一种基于虚拟计算环境的分布式存储体系结构[A];2009全国计算机网络与通信学术会议论文集[C];2009年

中国重要报纸全文数据库 前8条

1 京东架构委员会主任 云平台首席架构师 系统技术部负责人 刘海锋;京东:分布式存储体系成为业务基石[N];中国信息化周报;2014年

2 《网络世界》记者 于翔;京东分布式存储体系研发历程[N];网络世界;2014年

3 《网络世界》记者 于翔;融合一体机投入大规模商用[N];网络世界;2013年

4 记者 余荣华;大数据，，催生大变革[N];人民日报;2014年

5 本报记者 张佳星;新生产业布局如何“云”中索骥[N];科技日报;2014年

6 本报记者 甘露;物联网让管理更美妙[N];计算机世界;2013年

7 本报记者 郭涛;华为帮用户定制HANA一体机[N];中国计算机报;2013年

8 临江;手机浏览器,3G时代的采矿机？[N];人民邮电;2009年

中国博士学位论文全文数据库 前8条

1 胡q

本文编号：1156176