大规模分布式纠删码存储系统中的高效数据传输技术研究

发布时间：2020-07-31 14:45

【摘要】：数字信息量的快速增长对大规模数据存储技术提出新的挑战,商业化低成本设备的大量应用使得数据可靠性问题日益突出。分布式存储通过维护额外的冗余数据以备容错来提供数据可靠性保证,其中纠删码存储通过编码生成冗余数据,大大优化了存储空间利用率,成为当前最受认可的分布式存储可靠性方案之一。分布式纠删码存储系统通常作为大规模集群底层存储提供数据归档和备份服务,其数据编码、访问和重构过程中产生大量数据传输。这些数据传输一方面占据宝贵的带宽从而影响整个集群的网络性能,另一方面引发拥塞造成时间延迟,同时还产生很大能耗。因此,大规模分布式纠删码存储系统中的高效数据传输技术研究是十分具有意义的。现有的大规模分布式纠删码存储系统研究存在一系列难点和挑战。首先,在纠删码存储系统中,可靠性、存储空间利用率和重构开销是三个非常重要又相互制约的指标。在同等可靠性前提下,提高存储空间利用率意味着压缩冗余数据量,这将导致数据重构更加复杂、开销更大。反之,简化数据重构则需要存储更多的冗余数据以达到同等可靠性。因此,在权衡中提高可靠性、存储空间利用率和重构开销是纠删码存储系统研究中的一个难点。第二,时间延迟和带宽开销是纠删码存储数据编码、访问和重构中最关心的两个性能指标。直观上,减少数据传输量可以间接减少拥塞,但有些情况下,减少数据传输量的同时可能增加传输跳数,进而增加时间延迟。因此,权衡数据传输开销和时间延迟是一个研究难点。第三,大规模分布式纠删码存储系统是纠删码算法和集群网络拓扑的有机结合。当前研究往往针对纠删码算法中的理想全联通拓扑,而忽略了底层集群的实际网络拓扑,导致算法的研究成果在实际系统网络拓扑中不能理想地发挥效果。尤其,数据传输开销受网络拓扑和传输路由的影响很大,因此在研究中如何妥善结合考虑上层算法和底层拓扑也是一个挑战。针对上述难点和挑战,本文对大规模分布式纠删码存储系统中的数据编码、放置和重构这几个重要处理环节展开研究。纠删码存储首先对原始数据进行编码,然后通过数据放置将编码数据存储到集群各节点上,当数据失效发生后,对失效数据的访问和修复则需要通过数据重构来达成。本文针对这几个重要环节中的高效数据传输技术进行了以下研究。数据重构是纠删码存储中最为重要的环节,因此本文首先对最为常见的单点数据重构中的数据传输开销问题进行研究。本文结合纠删码算法与集群网络拓扑,提出一种聚合解码方法,利用纠删码的信息聚合特性,在数据传输的过程中进行解码,从而减少了总带宽消耗量。聚合解码的效果与数据在网络拓扑中的传输路径有很大关系,于是本文将路径选择问题建模和归约为斯坦纳树问题,提出一种基于蚁群加权的最短路径启发式算法加以解决。实验证明聚合解码可以有效降低单点数据重构中的传输开销。在单点数据重构研究的基础上,本文进一步针对多点数据重构中的数据传输开销问题进行研究。本文首先分析阐明了多点数据重构的重要意义,并基于马尔科夫过程提出一个多点失效模型。然后提出面向多点重构的协同聚合解码方法Redu,将纠删解码中的冗余数据传输分为内容重复和信息冗余,并针对两种情况分别提出内容重删和信息聚合,协同减少整体数据传输开销。为了最大化协同去冗余解码的效果,本文还提出了相应的路径选择方法。实验证明Redu可以有效降低多点数据重构中的传输开销。随后,本文研究了纠删码存储系统数据放置环节中的冗余布局问题。纠删码中冗余数据与原始数据的对应称为冗余关系,纠删码算法的冗余关系与集群拓扑节点之间的映射称为冗余布局。冗余布局决定了各原始数据和冗余数据具体放置在哪些存储节点。当前研究大多考虑理想的均衡失效模型,即各存储节点失效概率相同。本文针对实际异构失效模型下的冗余布局问题,分析了冗余关系和异构失效模型对数据重构的影响,提出一种基于异构失效模型的纠删码存储系统冗余布局策略He Match,优化纠删码冗余关系在集群拓扑上的放置来优化数据重构开销。实验证明He Match可以有效减少数据传输开销,同时增加系统可靠性。在对数据重构和放置的研究的基础上,本文接下来针对数据编码环节中的传输开销问题进行研究。本文分析了纠删编码过程,发现该过程不仅具有类似纠删解码的信息聚合特性,同时还具有将编码数据块分散存储到不同节点的数据分布特性。基于这两个特性,本文提出一种基于树的协同去冗余编码方法,将纠删编码过程中的数据传输分为干路和支路,分别提出基于干路的去重传输和基于支路的聚合编码来消减冗余传输开销,并提出优化的路径树构造方法。实验证明协同去冗余编码方法可以有效减少数据编码环节中的传输开销。综上所述,本文对大规模分布式纠删码存储系统中的高效数据传输技术进行了一系列研究,对于推动纠删码存储技术的发展和提升分布式存储集群网络性能具有一定的理论意义和应用价值。
【学位授予单位】：国防科学技术大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP333
【图文】：

纠删码,存储系统

纠删码存储系统模型纠删码存储系统的结构由上层纠删码算法逻辑视图和下层集群网络拓扑物理视图两部分结合而成，如图1.6。逻辑视图中，每个纠删编码组中的n个数据块放置在全连通的n个节点上。而在物理拓扑中，纠删码存储系统坐落于集群上，集群的网络拓扑可能为树形、环形等，逻辑视图中的n个节点对应的是物理集群网络拓扑中n个物理存储节点。分布式纠删码存储系统中最基本的环节是数据编码、放置和重构。首先对原始数据进行编码，然后通过数据放置将编码数据存储到物第5页

模型图,马尔科夫过程,模型,纠删码

MTTMF的定义为：一个分布式纠删码存储系统从初始化到出现多点失效的平均时间。图4.2阐述了我们提出的基于马尔科夫过程的多点失效模型。图4.2基于马尔科夫过程的多点失效模型对于(n, k) 系统 RS 纠删码存储系统的基于马尔科夫过程的多点失效模型，系统共有N个存储节点，每个纠删编码组有三个状态如下，1.状态0纠删编码组中的全部n个编码数据块均有效可用。第48页

分布过程,编码数据

n k 个冗余数据块）发送到n个不同的存储节点上，这就是数据分布特性。图6.1展现了纠删码存储系统中的纠删编码数据分布，其中图的下半部分为逻辑上的数据分布视图，图的上半部分为实际系统集群中的数据分布传输。编码过程中传输的编码数据块都是由几个原始数据块进行信息聚合而成的，因此数据分布实际上是对这几个原始数据块的信息进行广播。基于4.3.1中对传输冗余的研究，信息广播过程中也存在内容重复。但由于传统纠删编码采用先计算、后传输的思路，重复数据在源节点就变成了编码数据块，从而不能在传输中直接通过基于合并的去重传输来消除冗余。图6.1纠删编码数据分布过程6.3 基于树的协同去冗余编码方法基于编码的信息聚合与数据分布特性，原始数据块信息冗余地存在于编码数据块中，造成了传输冗余。为了减少纠删编码过程中传输冗余消耗的额外带宽，我们提出一种基于树的协同去冗余编码方法

【相似文献】