摘 要

信息化时代的发展离不开互联网技术，而互联网技术的关键就是信息的存储和传输。当存储的编码信息发生故障时，如何最高效、低成本地修复故障节点也就成为人们研究的重点。最大距离可分(MDS)码可以减少系统修复带宽，但同时有着修复时间过长的缺点。而部分重复（FR）码因为可以对故障节点进行精准修复得到了人们的广泛研究和应用，其缺点在于系统存储成本开销过高。本文主要包含以下内容：

1. 研究异构云存储系统的构造方法，用数学模型来构建一个小型的异构云存储系统，理解系统中的编码存储和修复。
2. 基于最大距离可分(MDS)码和不规则重复（IFR）码，提出一种新的编码方式：MDS-IFR码，该码理论上兼具了最大距离可分(MDS)码和部分重复（FR）码的优点。阐述该码的构造原理和修复原理。
3. 用线性优化对MDS-IFR码的修复开销进行计算分析，并利用MATLAB软件仿真异构云存储系统，对编码的存储成本以及修复成本进行比较，证明，即存储成本优化和修复成本优化。

关键词：最大距离可分（MDS）码；不规则重复（IFR）码；故障节点；异构云存储系统

Abstract

The development of the information age is inseparable from Internet technology, and the key to Internet technology is the storage and transmission of information. When the stored encoded information fails, how to repair the failed node most efficiently and at low cost has become the focus of research. The maximum distance separable (MDS) code can reduce the repair bandwidth of the system, but it also has the disadvantage of too long repair time. Fractional repetition (FR) codes have been widely studied and applied because they can accurately repair faulty nodes. The disadvantage is that the system storage cost is too high. This paper mainly includes the following:

(1) Study the construction method of heterogeneous cloud storage systems, use mathematical models to build a small heterogeneous cloud storage system, and understand the code storage and repair in the system.

(2) Based on the maximum distance separable (MDS) code and irregular fractional repetition (IFR) code, a new coding method is proposed: MDS-IFR code, which theoretically combines the advantages of the maximum distance separable (MDS) code and fractional repetition (FR) codes. Explain the construction principle and repair principle of the code.

(3) Use linear optimization to calculate and analyze the repair cost of MDS-IFR code, and use MATLAB software to simulate the heterogeneous cloud storage system, compare the encoded storage cost and repair cost, and prove that storage cost optimization and repair cost optimization.

Key Word：maximum distance separable (MDS) code; irregular fractional repetition (IFR) code; failure node; heterogeneous cloud storage system

目 录

第1章 绪论 1

1.1 研究背景及意义 1

1.2 研究现状 1

1.2.1异构云存储系统 2

1.2.2异构云存储系统纠错技术研究现状 2

1.3 论文研究内容及章节安排 3

第2章 系统模型 4

2.1 存储和通信模型 4

2.2 修复和检索模型 4

2.2.1 检索集 4

2.2.2 帮助节点 4

2.2.3 修复和检索模型 5

2.3 MDS-FR码范例 5

2.4 MDS-IFR码范例 7

2.5小结 8

第3章 编码介绍 9

3.1 MDS码 9

3.1.1 MDS码构造 9

3.1.2 MDS码修复 9

3.1.3 MDS码优缺点 9

3.2 FR码 9

3.2.1 FR码构造 9

3.2.2 FR码修复 10

3.2.3 FR码优缺点 10

3.3 小结 10

第4章 MDS-IFR码构造 11

4.1 超图 11

4.2 MDS-IFR码构造 11

4.3 数据分发 11

4.4 数据修复 11

4.5 小结 12

第5章 系统性能优化 13

5.1 单节点修复成本 13

5.2 系统修复成本优化 13

5.2.1 系统修复成本 13

5.2.2 目标函数 14

5.2.3 约束条件 14

5.2.4系统优化变量 15

5.3 小结 15

第6章 数值仿真与结果分析 16

6.1 仿真软件介绍 16

6.1.1 MATLAB 16

6.1.2 YALMIP工具箱 16

6.1.3 MOSEK求解器 16

6.2 仿真程序 17

6.2.1程序编写 17

6.2.2程序运行 17

6.3 仿真结果 17

6.4 小结 20

第7章 总结 21

参考文献 22

致谢 23

绪论

互联网技术的飞速发展带来数据海量化，数据的存储、传输和访问成为了当前系统的共性问题。因此，提高信息存储效率和增加数据修复能力也就显得尤为重要。本文基于异构云存储系统进行部分重复编码的传输和修复研究：首先介绍论文的研究背景及意义，然后介绍异构云存储系统以及国内外相关研究现状，最后介绍本文的主要研究内容和章节安排。

研究背景及意义

信息化时代的到来，数据也开始爆发增长，人们生活的方方面面都已经离不开大数据，云计算和云服务的出现更是促进了云存储系统的发展。广泛使用的同时，云存储系统也开始面临着巨大的挑战，如由分布式存储系统的异常引起的存储节点中的数据丢失，也称之为节点故障。当出现故障时，新来者需要通过从幸存的存储节点中检索数据来修复丢失的数据(称为帮助点)，从而保持分布式存储系统的可靠性^[1]。同时，云存储系统被要求能够提供可靠数据，使用户能够在任何地方通过互联网访问他们的数据，还需要保证信息传输的效率和稳定性。与传统的集中式存储相比，分布式存储系统具有更高的可扩展性和容错能力^[2]，因为数据被分别存储在多个廉价的存储节点中，降低了系统的存储要求和成本。

早在2014年，中国互联网百度公司单个集群的节点数量就超过了10000。近两年，腾讯云的分布式调度系统 VStation管理和调度单集群的节点数量可达100000。然而数量庞大的节点集群经常会产生如电源损坏、系统维修及网络中断等故障致使节点失效频发^[3]。因此如何提高节点修复速率，减少修复开销，确保数据能够正常地传输就显得非常重要。具有节点修复能力的数据容错技术可以保证系统的容错能力，优秀的容错技术要求云存储系统具有较低存储冗余、较低修复带宽、简单的编译码复杂度等特点^[4]。不同的编码方式在系统中的存储和修复方法都不完全相同，也就有了不同的存储效率和修复能力。因此我们研究不同编码方式的目的就在于找到一种能有效降低节点修复带宽，降低存储系统编译码的复杂度并提高系统的存储效率的编码。

研究现状

在云存储系统的容错技术研究中，最常见的策略主要有：复制、纠删码等。复制策略指用其他节点存储原始文件副本，在发生故障时从其他节点重新下载数据信息，因此存储开销偏高；纠删码则偏向于对数据信息进行分块、编码然后生成冗余数据块，分别存储于不同节点当中，在发生一定限度的节点故障时，能通过其他节点还原原始数据并重新存储于新的节点中。通过编码进行容错.与多副本容错技术相比, 纠删码容错技术可以在显著降低存储空间消耗的同时提供相同甚至高得多的数据容错能力^[5],但因为修复时需要还原原始数据，所以修复带宽偏高。基于这两种策略，人们提出了不同的编码方式，并通过仿真或实验等方法进行验证，来证明不同编码的优化能力，从而找到更优的编码方式。同时，编码方式的发展也有效推进了云存储系统的发展，并且在人们的生活中得到了广泛使用，提高了人们的生活水平。

1.2.1异构云存储系统

云存储是一种网上在线存储模式，由大量的同构或者异构的存储设备组成, 同构指的是一个存储环境中的所有存储节点部件都来自于同一个供应商，或者是间接来自于伙伴关系；异构则指存储系统来自于不同供应商的混合环境。云存储系统允许用户随时随地访问数据并提供下载，这种体系结构也被称为分布式存储系统(DSS)。目前云存储系统被广泛应用于我们生活中，我们无法保证系统中的所有节点部件都完全一样，因此研究重点更多的是异构方向。

1.2.2异构云存储系统纠错技术研究现状

目前部分重复码在国内外的主要研究方向有：