拓扑感知局部修复码在云存储系统中的研究与应用开题报告

全文总字数：3717字

1. 研究目的与意义（文献综述）

1.目的及意义（含国内外研究现状）

近年来，随着信息技术的快速发展，人们生活中产生的数据量不断增长，随之存储系统的规模也在日益扩大，廉价的存储设备也逐渐被广泛应用。随着廉价磁盘的应用和存储规模的扩大，在数据存储的过程中，常常由于存储设备故障或者软件故障等原因造成数据丢失[1][2][3][4]。为了应对这种情况的发生，最简单的办法是直接复制所有的数据，即副本技术。虽然副本技术优点在于算法简单，易于实现且恢复速度很快。但由于这项技术的存储开销过大，这种方法已经不适用于当今海量数据的存储需求[5][6]。随后产生了纠删码容错技术。(n, k)纠删码将包含k个数据块的源文件编码成n个编码块，n个编码块中的任意k个编码块可以重构源文件。在相同的容错能力下，纠删码可以达到最小的存储开销。当数据丢失时，则首先通过k个编码块重构源文件，然后由重构的源文件通过线性编码再生丢失的数据块[7]。纠删码技术是当前分布式存储系统的主要容错策略。但是纠删码技术在修复丢失数据时会造成大量的i/o开销和网络拥堵。

根据实际需求选用特定的编码方案是分布式存储系统中的一项关键技术。由于云存储系统中影响节点修复的主要性能瓶颈是磁盘的i/o开销，该开销与修复一个失效节点所需要连接的帮助节点数目，即局部性，成正比。因此，一种可以降低修复局部性且可以保证低修复带宽的编码方式，即局部修复码 (locally repairable codes, lrc) 应运而生[8][9]。局部修复码能够通过降低修复过程中所需要访问的节点数量，从而降低全局的修复开销。虽然局部修复码没有做到存储效率的最优，但由于其具有低i/o开销和低修复带宽受到了来自学术界和工业界的广泛关注，局部修复码技术已被运用和部署到azure、facebook、ceph等云存储系统中。

2. 研究的基本内容与方案

2. 研究（设计）的基本内容、目标、拟采用的技术方案及措施

本设计将专注于根据存储网络的拓扑结构设计适用于异构分布式存储系统的局部修复码。在编码和数据修复过程中考虑网络的拓扑结构[14]。如果当存储节点可能没有完全连接，给定一个具有任意拓扑结构的存储网络，引入节点局部性这个新的定义。在本毕业设计中，假设一个节点除了具有存储转发的功能外，还可以计算或编码自己存储的本地数据和输入数据，并可以将编码后的数据传递给邻居节点，参与一次修复过程的总节点数称为节点局部性。除了节点局部性这一限制条件，在局部修复码的设计过程中还需要满足符号局部性，也就是说把存储的数据块编码成有限域中的符号，其中任意一个符号都可以表示为少量的其它几个符号的线性组合。根据符号局部性和节点局部性的定义，选取满足修复通信开销限制的修复组。修复组内每一个节点的数据都可以由组内其他节点的数据再生出来。由于本毕业设计中假设了节点具有计算和编码本地数据和输入数据的功能，故在整个设计过程中，节点局部性要大于符号局部性。首先，基于[12]中对于可行修复组的定义和寻找可行修复组算法，找出特定的树形存储网络的某个节点i的所有可行修复组。然后考虑二进制的局部修复码编码，通过[16]中的化简方式将可行修复组规约为最小r 1集合覆盖问题。然后通过设计一个贪婪算法来选择出所有可行的修复组，然后选择一个修复组集合使得所有的存储节点都被所有的修复组覆盖，最后根据选择的修复组来设计局部修复码的奇偶校验矩阵，并优化编码速率。

3. 研究计划与安排

3.进度安排

1-3周：查阅相关文献资料，提交开题报告，并完成英文文献翻译；

4. 参考文献（12篇以上）

4.参考文献

[1]基于对象的进化存储系统研究[j]. 董晓明,谢长生.计算机科学. 2005(11)

[2]优化提升存储系统性能技术探讨[j]. 张静娴,梁勇,张海清,林碧怡.通讯世界. 2014(08)