摘 要

大数据时代，面对爆炸式增长的数据存储需求，云存储等大规模分布式存储系统应运而生，有效地整合和利用分散在网络上的各个节点资源，从而使用户能够无缝地访问和分享数据。如何有效地保障数据存储的可靠性是当前分布式存储系统面临的主要问题。局部修复码作为一种具有高效修复机制的容错编码方案受到广泛关注。然而，目前关于局部修复码的研究工作大都忽略了系统的异构性和网络的拓扑结构。根据网络的拓扑信息，如何设计适用于异构分布式存储系统的局部修复码存储方案是值得深入研究的问题。本论文将研究如何根据存储网络的拓扑结构设计适用于云存储系统的局部修复码，在编码和数据修复过程中考虑网络的拓扑结构。

在本毕业论文中，假设一个节点除了具有存储转发的功能外，还可以计算或编码自己存储的本地数据和输入数据，并可以将编码后的数据传递给邻居节点。根据符号局部性和节点局部性的定义，选取满足修复通信开销限制的修复组。修复组内每一个节点的数据都可以由组内其他节点的数据再生出来。由可行修复组的定义和寻找可行修复组算法，找出特定的树形存储网络的某个节点i的所有可行修复组。然后考虑二进制的局部修复码编码，并将可行修复组规约为最小r 1集合覆盖问题。然后通过设计一个贪婪算法来选择出所有可行的修复组，然后选择一个修复组集合使得所有的存储节点都被所有的修复组覆盖，最后根据选择的修复组来设计局部修复码的奇偶校验矩阵，并优化编码速率。

关键词：云存储；分布式存储系统；局部修复码；编码速率

Abstract

In the era of big data, facing the explosive growth of data storage demands, large-scale distributed storage systems such as cloud storage provide an elegant solution. They efficiently group and utilize the storage nodes that are distributed across a wide geographical area and connected by a network, such that enable users seamlessly access and share their data. How to efficiently guarantee the system reliability is urgently to be solved. Locally repairable codes, which have an efficient repair mechanism, received more and more attention. However, in most existing works of locally repairable codes, the system heterogeneity and network topology are not taken into consideration when constructing LRC codes. According to the network topology, how to design locally repairable codes for heterogeneous distributed storage systems, is deserved to be researched in depth. This thesis will design the locally repair code which is suitable for heterogeneous distributed storage system according to the storage network topology, and consider the network topology in the process of coding and data repairing.

In this thesis, it is assumed that in addition to the store-and-forward function, a node can also calculate or encode its stored local data and input data, and can pass the encoded data to neighbor nodes. According to the definition of symbol locality and node locality, select the repair group that meets the limit of repair communication overhead. The data of each node in the repair group can be reproduced from the data of other nodes in the group. According to the definition of feasible repair group and the algorithm of searching for a feasible repair group, all feasible repair groups of a certain node i in a specific tree storage network are found. Then consider the binary local repair code encoding, and reduce the feasible repair group to the minimum r 1 set coverage problem. Then design a greedy algorithm to select all feasible repair groups, then select a repair group set so that all storage nodes are covered by all repair groups, and finally design the parity check matrix of the locally repair code according to the selected repair group and optimize the encoding rate.

Key word: cloud storage; distributed storage systems; locally repairable codes; code rate

目录

第1章 绪论 1

1.1分布式存储系统介绍 1

1.2分布式存储系统编码方式介绍 2

1.2.1多副本机制 2

1.2.2纠删码 2

1.2.3再生码 3

1.2.4局部修复码 3

1.3研究方向概述 3

1.3.1研究动机 4

1.3.2当前研究现状 4

1.3.3研究价值 4

1.4小结 4

第2章 局部修复码 5

2.1线性码的基本概念 5

2.2传统局部修复码基本概念 6

2.3异构DSS上局部修复码基本概念 6

2.4小结 7

第3章异构网络上的局部修复码 9

3.1可行修复组选择算法 9

3.1.1斯坦纳树和最小生成树 9

3.1.2算法 11

3.2二进制局部修复码的归约问题 12

3.2.1归约问题的研究 12

3.2.2集合覆盖简述 13

3.3码率最大化问题 13

3.3.1符号局部性讨论 14

3.3.2贪心算法简述 15

3.3.3基于贪心算法的修复组选择算法 15

3.3.4算法性能分析 16

3.4 局部修复码构造案例 17

3.5小结 17

第4章 MATLAB仿真 19

4.1算法实现 19

4.1.1生成矩阵函数 19

4.1.2 最小生成树函数 19

4.1.3 修复组选择函数 21

4.1.4整合修复组函数 21

4.1.5最小修复组选择函数 22

4.2局部修复码编码 23

4.3仿真实验数据 23

4.4小结 24

第5章 总结和未来工作 25

5.1总结 25

5.2未来工作 25

参考文献 26

附录A缩写词列表 28

致谢 29

第1章 绪论

本章主要介绍分布式存储系统的国内外基本现状和其系统编码策略，根据基本现状和编码策略的优劣来综合评价本课题研究的价值。

1.1分布式存储系统介绍

如今我们正处于信息化时代，云计算、大数据、互联网、移动终端、物联网、智慧城市等以及金融领域产生的信息量不断增长。根据英特尔预测，全球数据总量在2020年将达到44ZB（约1万亿GB）之多，中国数据总量将达到8ZB，约占地球的五分之一。5G时代的到来，数据的上传和存储量将会再次迎来跨越式增长。随着数据流量速率的加快，数据存储量日渐庞大，存储系统的存储性能和扩展性面临着更严峻的挑战。传统的存储系统采取集中式存储方式，数据的安全性和可靠性均不能满足时代的要求。在分布式存储系统中，数据被分散存在多个物理存储设备中，降低了存储节点的存储负载。由于其成本低、扩展性好、易于管理和维护的特点，分布式存储系统在云存储技术中被广泛应用。由于磁盘技术的不断提升，云存储供应商会选择在分布式存储系统中使用过保时间短、价格低的存储设备。

云存储系统的一个重要目标是提高数据的可靠性，保证持续地为用户提供数据访问服务。排除人为因素和系统故障，数据丢失的主要原因是磁盘故障。尤其是超过了过保年限的老旧磁盘，其故障几率会大大增加。仅在2018年就发生过几起较为严重的云存储服务故障。2018年7月，腾讯云云硬盘故障导致部分用户信息不可逆丢失；2018年9月，Windows Azure云存储服务故障导致宕机时间超过24小时，许多云存储服务如Office365、Active Directory、Visual Studio Online、Visual Studio Team Services 等，这些服务已下线了数个小时之久；2018年11月，谷歌公有云中的Kubernetes容器服务宕机约19个小时，造成了巨大的经济损失^[1]。