基于纠删码的分布式容错存储技术研究

发布时间：2020-10-23 13:56

　　 随着网络与信息技术的飞速发展,分布式存储系统在成本、性能、可扩展性以及存储容量等方面已取得了快速进步,但同时在容错性方面也面临着巨大的挑战:随着节点规模的不断扩大,分布式存储系统中节点出现失效的概率会大大增加,而节点失效导致的数据丢失会造成灾难性的后果。因此,如何设计高效、可靠的分布式容错存储技术是当前亟需解决的关键问题。相比于副本技术,基于纠删码的数据冗余技术能够在保证相同容错能力的基础上,极大地降低存储开销,成为了当前分布式存储领域研究的热点。基于纠删码的分布式容错存储技术面临的主要挑战在于:(1)现有的纠删码数据写入方法将数据分块、编码与传输等任务集中于同一节点,存在较为严重的瓶颈问题。随着数据量的不断增大,瓶颈问题更加突出。(2)节点规模的不断增加使得多点失效的概率明显增大,在多点修复过程中现有的纠删码数据修复方法修复效率较低,修复开销较大。(3)纠删码更新过程中涉及较多的数据传输与复杂的数据计算,现有的纠删码更新方法需要消耗较大的网络开销,导致了较低的更新效率。为此,本文围绕实现基于纠删码的高效低成本存储服务这一目标,分别针对基于纠删码的数据写入、数据修复和数据更新技术展开深入研究。针对已有的纠删码数据写入方法因单点瓶颈而导致写入效率较低的问题,本文研究提出了一种基于分组的分布式流水线数据写入方法D2CP。D2CP采用一种基于分组的分布式框架以维护源节点、数据节点与编码节点之间的邻居关系。通过一种基于一致性哈希的数据放置算法,D2CP将节点位置与数据存储位置进行哈希计算以提高数据放置效率。为了降低写入开销,D2CP采用一种基于分组的数据发送调度算法以动态调度源节点的数据发送。为了提高编码计算效率,D2CP采用一种基于协作的编码数据生成算法以协作方式组织编码节点之间的计算。基于HDFS-RAID平台的测试结果表明,与目前已有的纠删码数据写入方法相比,在多种不同参数设置情况下,D2CP的数据写入时间平均减少了26%,网络开销平均降低了24.5%,显著提升了纠删码数据写入效率并降低了网络开销。在多点失效场景中,集中式修复方法存在单点瓶颈的问题,而分布式修复方法存在修复开销大的问题。两种方法的修复效率随着数据量的增大而显著下降。为此,本文研究提出了一种基于协作的自适应数据修复方法DARS。DARS采用一种星型结构与树型结构结合的自适应数据修复模型以同时支持单点失效和多点失效的修复。通过一种带宽感知的节点选择算法,DARS选择具有更高可用带宽的节点以保证节点之间的高可用带宽。通过一种线型结构的数据传输算法,DARS有效组织提供者节点与中继节点之间的数据传输。通过一种基于中心节点的数据分发算法,DARS有效组织协调者节点与新生节点之间的数据交互,进而保证节点之间的数据传输效率。为了最小化网络代价,DARS通过条带内的懒惰修复算法自适应地调整失效数据的修复时机,并动态调整提供者节点的数目从而保证负载的均衡性。基于HDFS-RAID平台的测试结果表明,与目前已有的纠删码数据修复方法TSR和CORE相比,在多种不同参数设置情况下,DARS的数据修复时间平均减少了29%和55%,显著提升了纠删码数据修复效率。更新过程中复杂的数据传输与计算使得已有的纠删码单点更新方法效率随着数据规模的增长而显著下降。为此,本文研究提出了一种基于树型结构的单点数据更新方法TA-Update。TA-Update采用一种编码参数无关的更新树结构维护节点之间的连接关系,以支持不同参数的编码算法。通过一种机架感知的树型构建算法,TA-Update构建了一颗最优更新树,以保证节点之间数据传输的高效性。通过一种自顶向下的流水线数据处理算法,TA-Update将节点之间的数据传输流水线化并将更新计算任务分布在多个不同的节点中。TA-Update通过一种基于缓存的失效处理算法高效修复失效数据并恢复暂停的更新过程,以提高方法的适应性。基于HDFS-RAID平台的测试结果表明,与目前已有的纠删码数据单点更新方法相比,TA-Update在无节点失效情况下的更新时间平均减少了33%,在单点失效情况下的更新时间平均减少了44%,显著提升了纠删码单点更新效率。多点更新过程中,顺序更新的方式导致已有的更新方法更新开销较大,更新效率随着数据量的增大而显著下降。为此,本文研究提出了一种基于分组结构的多点更新方法Group-U。Group-U采用基于分组的更新框架以有效组织节点之间的邻居关系。通过一种负载感知的分组算法,Group-U依据更新负载自适应地为多个待更新节点选择合理的分组方式与分组大小。通过一种混合更新算法,Group-U依据时间间隔阈值有效组织多个更新节点的更新时机,从而保证数据节点的数据一致性和编码节点的更新效率。通过一种基于缓存的失效处理算法,Group-U有效处理更新过程中出现的节点失效并保证更新过程的顺利进行。基于HDFS-RAID平台的测试结果表明,与目前已有的纠删码数据多点更新方法相比,在多种不同参数设置情况下,Group-U的数据更新时间平均减少了44%,更新开销平均降低了12%,显著提升了纠删码多点更新效率。
【学位单位】：国防科学技术大学
【学位级别】：博士
【学位年份】：2016
【中图分类】：TP333
【部分图文】：

多点更新方法更新的方式导致已有的更著下降。为此，本文研究roup-U 采用基于分组的更感知的分组算法，Group-的分组方式与分组大小。有效组织多个更新节点的点的更新效率。通过一种中出现的节点失效并保证果表明，与目前已有的况下，Group-U 显著提升1.4 论文结构织结构如图 1.4 所示。

采用的随机放置方法。完成编码任务，数据以编码的形式写入系写入方式，直接编码方式无需同时维护副写入系统时完成编码即可。直接编码主要数据上传。其中，数据分块是指数据对象；数据编码是指编码节点将分割的数据块上传是指编码节点将完成编码的数据块和过程中原始数据对象被分割为 k 个数据算产生 r 个编码块。最后，k 个数据块和依据数据写入过程中三个步骤的执行情式和分布式数据写入方法。12分布式存储系统

我们通过一个条带中的编码过程来了解整个数据对般性，我们将 k 个数据块表示为1{ , , }ko o。在一个分组码点参与：存储原始数据块的存储节点，存储局部编码块的局编码块的全局编码节点。其中，局部编码块是由一组数编码块则由所有的数据块编码生成。我们可以用参数(k,g,l其中，k 表示原始数据块的总数目，g 表示组数，l 表示局示全局编码块数目。在编码过程中，k 个数据块1{ , , }ko o被1, / ,1 , /, ), ,( , , ))k g g g k g o o o。 其 中 ， 第 i 组 的 局 部 编 码 /)l g，o 个全局编码块表示为1( , , )op p。第 i 组的第 j 个局部3.1 生成，全局编码块ip 通过公式 3.2 生成。/, , , ,1* ,1 ,1 /k gi j i j x i xx o i g j l g (3.1)/*, , , , ,1 1 1* * ,1g k g gj j i x j x i j i ji x i o p j o (3.2)

本文编号：2853126