基于分布式存储系统精确修复再生码的研究

发布时间：2020-04-23 17:33

【摘要】：随着科学技术的不断进步,信息技术的发展已经超出了人们的想象,人类频繁的网络活动导致网络系统产生的数据量迅速地增加。面对海量的存储数据,传统的集中式网络存储已经难以满足日益增长的大规模存储空间的需求,而分布式存储系统因其海量的存储能力、高扩展性以及低成本的优势被广泛使用和开发。但是,分布式存储系统的存储节点存在可用性不高的问题,随着分布式存储系统的发展和普遍应用,这种隐患带来的数据可靠性问题就越来越严重,如何保证数据的可靠性成为发展分布式存储系统的“当务之急”。保证数据的可靠性主要依赖于数据容错技术,而进行有效的数据修复则是解决数据容错技术的关键,也就是说,在存储系统中发生节点故障之后,有效节点尽可能少地消耗系统资源来完成失效节点的修复。基于网络编码的再生码因其较少的冗余存储量、高可靠性以及低修复带宽被广泛研究。但是,当前所研究的分布式存储再生码存在以下缺点:各种基于分布式存储系统的再生码由于自身结构等原因对存储节点的容忍度大小不一,容忍度越小,存储系统的数据可靠性和安全性就越低,一部分再生码的容忍度低导致可修复的节点数少;尽管有些现有的再生码容忍度大,但是需要高存储容量、高修复带宽或者高计算复杂度的存储系统才得以满足,代价过高。因此,我们需要设计一种高容忍度的再生码,同时有着较低的修复带宽、较低的存储容量以及较低的计算复杂度。针对以上提出的问题,本文在部分复制再生码的基础上,提出了一种多节点修复部分复制再生码MFRRC(Multi-repair Fractional Repetition Regenerating Codes)和一种异构部分复制码HFRRC(Heterogeneous Fractional Repetition Regenerating Codes)。本文的主要工作和创新点概括如下:针对之前的部分复制再生码仅允许存在一个存储节点失效的问题,本文提出了一种多节点修复部分复制再生码MFRRC,其中的研究主要包括编码的构造、数据精确修复过程分析、修复过程中节点选择的优先级的建立以及性能分析。在该编码方法中我们引入了父代存储节点和子代存储节点的概念,即为了保证多个存储节点失效后的精确修复,对原有的存储节点增加了相应的子节点来存储副本,我们通过理论分析得出了这种编码方式不仅提高了容忍度,并且保持了原来部分复制码的优点,同时我们通过设置相关参数对这种编码方式进行了仿真和数值分析,仿真结果表明提出的MFRRC能够大大提高容忍度,同时有效降低了总修复带宽和总修复时间。针对之前的部分复制再生码存在帮助节点数多以及只能允许一个存储节点失效的问题,在异构的分布式存储系统的情况下(即在修复过程中从有效帮助节点所下载的数据量不一样),提出了一种异构部分复制再生码HFRRC,其中的研究内容主要包括编码的构造、性能分析以及存在的问题,同时为了优化这种编码方法提出了扩展结构。在这种编码方式中,我们首先采用了修复带宽异构的编码构造,使得参与数据精确修复过程的帮助节点数减少;其次在异构部分复制再生码HFRRC的扩展结构中,再次引入父代存储节点和子代存储节点的概念,有效提高了容忍度。另外,我们对这种编码方式和其它典型的编码方式在容忍度等性能上进行仿真,仿真结果表明提出的HFRRC不仅大大减少帮助节点数和提高了容忍度,而且总修复带宽较小,数据修复过程快速高效。
【图文】：

原理图,纠删码,原理图

删码逡逑码起源于通信传输领域，最开始是为了保证有损信道中通信容错能纠删码的使用可以使通信系统忍受多个数据帧的丢失，，之后被运用到，实现对存储系统的数据检错与纠错，保证系统的数据可靠性［２８］。例１所示，将一个大小为Ｍ的数据对象Ｎ在存储时分为ｋ个大小相等的Ｎｉ，犯，…，Ｎｋ，每个数据块的大小为Ｍ／ｋ，利用将其编码为ｎ个编码块，记为Ｘ！，邋Ｘ２，邋？？？，Ｘｎ，ｎ＞ｋ，并将其交叉存储（Ｃｒｏｓｓ邋Ｓｔｏｒａ节点中。当存储系统出现故障，一些编码块丢失，利用任意ｋ个编码原始数据，这种编码称为最大距离可分纠删码（Ｍａｘｉｍｕｍ邋Ｄｉｓｔａｎｃｅ邋Ｓｅｐａｒｔ２９］。这种ＭＤＳ特性使得纠删码在冗余消耗的存储空间方面远远优于每个大小为Ｍ／ｋ的ｋ个编码块可以提供恢复大小为Ｍ的文件的最小数比较受关注的的最大距离可分纠删码是ＲＳ邋（Ｒｅｅｓ－Ｓｏｌｏｍｏｎ）码［３Ｑ］、Ｌｄｅｎｓｉｔｙ邋Ｐａｒｉｔｙ－ｃｈｅｃｋ邋Ｃｏｄｅ）纠删码［３１］。逡逑

信息流图,节点

山东大学硕士学位论文逡逑数据对象完成。逡逑在节点信息流图的模型下，一般用参数（ｎ，ｋ，ｄ）表示ＭＤＳ码。图２－２是节点逡逑信息流图的举例，表示为（４，２，３）邋ＭＤＳ码的信息流图。图中将原始数据对象分为逡逑ｋ个数据块，存储ｎ邋＝邋４个存储节点中，每个存储节点对应的存储容量为ａ邋＝１，数逡逑Ｃｕｔ逡逑v|逡逑图２－２邋（４，２，３）ＭＤＳ码的节点信息流图＜；逡逑据收集节点只需要连接ｋ邋＝邋２个节点就可以恢复原始数据对象，当第４个存储节点逡逑失效时，新加入一个节点５，通过连接Rp余节点的ｄ邋＝邋３个帮助节点并从每个存储逡逑节点获得Ｐ邋＝邋０．５数据信息的方式，来完成失效节点的数据修复过程，总修复带宽逡逑为Ｙ邋＝邋１．５。逡逑２．２．２修复类型逡逑基于上述信息流图的网络编码方案数据修复后的存储节点存储的数据并不一逡逑定和失效的存储节点完全一样，原因是新加入的存储节点在信息流图只是作为中逡逑继节点
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP333

【相似文献】