论文部分内容阅读
当前,信息技术飞速发展,已从以计算设备为核心的时代进入到以存储设备为核心的时代,数据海量化成为一种趋势。分布式存储以其廉价和高扩展性等特点适用于数据的海量存储,得到越来越广泛的应用。分布式存储系统依靠冗余存储来维持整个系统的可靠性,并且需要一个良好的节点修复机制在发生节点故障时能快速有效的进行修复,维持系统的冗余度。基于网络编码的分布式存储系统编码冗余方式(再生码)相比于传统的冗余策略(复制、纠删码),降低了维持系统可靠性所需的存储开销和节点修复所需的带宽开销,因此有着良好的应用前景。我们希望对基于再生码的各种具体的编码方式及节点修复方式进行研究。分布式存储系统的另一个关键问题是系统扩容。对于相对较为复杂的基于再生码的分布式存储系统而言,如何高效的进行系统扩容,也是我们需要解决的问题。本文主要研究了基于网络编码的分布式存储系统中的节点修复问题和扩容问题,主要研究内容如下:(1)基于MSR(最小存储再生码)的单节点修复确定性算法良好的节点修复机制对分布式存储系统至关重要。本文研究了基于MSR编码的分布式存储系统的单节点修复问题。我们通过对节点修复过程中的两个编码步骤进行分析,给出了每个编码步骤所需满足的条件。并参考多播问题中中间节点进行数据编码的确定性算法,给出了一种实际的MSR编码单节点修复问题的确定性算法满足上述条件。与传统的随机性方法相比,我们的确定性算法能够百分之百保证修复性质,使得系统拥有更高的可靠性。同时只需要一个相对小得多的有限域,从而大大减少了编解码过程中的计算开销和内存开销。(2)多节点合作修复的E-MBR(确定性修复的最小带宽再生码)编码方法实际系统中,常常会遇到多个节点同时发生故障的情况。现有的E-MBCR编码方法仅基于r=n-k个节点修复的情况。对于r’<n-K个节点故障尽管也能修复,但带宽开销和存储开销都较高。本文中,我们证明了任意(n,K)系统中的任意r(2≤r≤n-K)个节点故障情况下达到节点修复带宽开销下界的E-MBCR编码的存在性,并给出了一种实际的编码方式以及相应的节点修复和还原原始文件的方法。我们的方法通过多节点合作修复降低了修复带宽开销。并通过确定性修复维持了系统中未编码的原始文件块的存在,从而提高了访问性能。同时,比起现有的基于r=n-k个节点故障的E-MBCR编码方法,我们的方法降低了系统存储开销和节点修复带宽开销。(3)基于E-MSR(确定性修复的最小存储再生码)的分布式存储系统的存储容量扩容问题分布式存储系统常常会遇到存储容量或访问性能不足的情况,从而产生系统扩容的需求。本文率先提出了基于再生码的分布式存储系统扩容问题,并研究了基于E-MSR编码的分布式存储系统的存储容量扩容问题。我们对该问题进行了建模分析,给出了其限制条件及优化目标,并主要针对扩容过程的带宽开销这一优化目标对问题进行了研究,指出减少带宽开销的关键点在于扩容前后系统的编码块部分有较大相关性。我们采用了利用较大规模系统的编码矩阵构造较小规模系统的编码矩阵的方法,使得系统在扩容前后编码块的编码矩阵有较大部分保持不变,冗余节点只需下载一小部分数据就能完成编码块更新,从而降低了整个扩容过程的带宽开销。