学位论文 > 优秀研究生学位论文题录展示

面向数据密集型超级计算的基于纠删码的容错存储技术研究

作　者: 周松
导　师: 王意洁
学　校: 国防科学技术大学
专　业: 计算机科学与技术
关键词: 数据密集型超级计算容错存储纠删码中间数据数据放置
分类号: TP302.8
类　型: 硕士论文
年　份: 2010年
下　载: 60次
引　用: 0次
阅　读: 论文下载

内容摘要

数据密集型超级计算作为一种新兴的计算模式,在高能物理、生物信息技术、天文计算、地震预报以及商业计算等数据密集型应用领域发挥着极其重要的作用。数据密集型超级计算以数据为中心,由系统负责存储、维护和处理海量数据。海量数据的存储和处理需求使得系统规模不断增长。随着存储规模的扩大,由于硬件故障、人员操作失误、病毒攻击、断电及火灾等各种原因,存储结点失效而导致整个系统发生故障的机率显著提高。因此,系统应具有较强的容错能力,保证数据的高可靠性和可用性。纠删码技术以其较强的容错能力和高空间利用率,为构造面向数据密集型超级计算的高可靠性和高容错性的大规模存储系统提供了一种有效的容错机制。然而,在数据密集型超级计算背景下,纠删码过高的修复成本易导致修复过程耗费大量的系统带宽,频繁的结点失效易导致大规模数据处理过程中产生的海量中间数据丢失而致使作业运行失败,数据放置不均易导致系统内结点利用率过低而使系统能耗过大。针对上述问题,本文对高容错低修复成本的纠删码编码技术、基于纠删码的中间数据容错存储管理方法以及功耗敏感的数据放置方法进行了深入的研究。取得的主要研究进展如下:纠删码过高的修复成本易导致修复过程占用大量系统带宽而降低系统性能。针对已有纠删码技术存在的不足,本文提出一种基于阵列结构的高容错低修复成本的纠删码EXPyramid。在EXPyramid码的基础上,针对多点失效和单点失效情况,本文分别提出了以最低修复成本为目标的多点失效修复算法RMFA和单点失效修复算法RSFA。EXPyramid采用阵列结构提高容错能力,将大数据集分组编码降低原始数据和冗余数据的关联程度,降低修复成本。在多点失效情况下,RMFA采用迭代的方法保证每次修复过程均具有最小成本,以使整体修复成本最低化;在单点失效情况下,RSFA采用广度优先搜索提高遍历效率,寻找最短修复路径,从而获得最低修复成本。理论分析表明,相对于已有纠删码,EXPyramid具有较强的容错能力和较低的修复成本。对大规模数据进行分布并行处理的过程中产生的中间数据是一类关键数据,中间数据丢失或损坏易导致后续任务的失败。已有的中间数据容错管理方法中,任务重执行方法易导致级联效应从而耗费大量计算资源,复制方法存储空间开销过高。针对当前中间数据容错管理方法存在的不足,本文提出一种基于EXPyamid码的中间数据容错存储管理方法EBIDS。EBIDS采用基于XOR运算的EXPyamid码对中间数据进行容错存储管理。XOR运算速度快,对中间数据短暂性的适应能力强;通过冗余编码,可有效降低存储开销;采用流式通信方式进行计算和传输冗余信息,能够有效降低单结点上的计算负载和带宽负载。实验结果表明,在正常情况下,EBIDS对系统的干扰很小。在单点失效情况下,EBIDS能有效防止级联效应的产生,降低失效对作业和系统的影响。和基于复制技术的中间容错存储管理方法相比,在提供相同容错保障的同时,EBIDS方法可有效降低冗余中间数据量,减小存储开销。在面向数据密集型应用的基于纠删码技术的存储系统内,合理地放置数据,有利于均衡存储负载和结点利用率。同时,可通过挂起部分闲置结点达到节省能耗的目的。已有的动态数据放置技术易造成大量数据迁移,从而占用系统带宽,降低系统性能。静态数据放置技术未考虑数据的访问特性,易造成结点利用率不均等问题。针对上述问题,本文提出了基于时间相关性的功耗敏感的数据放置方法TRBDPM。TRBDPM考虑数据密集型应用中数据访问模式的统计特性,引入时间相关性的概念,通过把无时间相关性的数据块和冗余块交叉放置,避开任务之间的相关性,从而使得在较长的一段时间内各结点的利用率保持均衡。同时,可通过挂起部分闲置结点以达到节省能耗的目的。实验结果表明,TRBDPM能够均匀地散布数据,保持存储负载均衡,在较长的时间内平衡结点利用率,部分结点有充足的时间进入低功耗模式从而被挂起,达到节省能耗的目的。

全文目录

摘要  9-11
Abstract  11-13
第一章绪论  13-30
  1.1 研究背景与意义  13-15
  1.2 数据密集型超级计算  15-16
  1.3 纠删码技术  16-22
    1.3.1 Reed-Solomon码  17-18
    1.3.2 奇偶阵列码  18-20
    1.3.3 奇偶校验码  20-21
    1.3.4 低密度奇偶校验码  21-22
  1.4 中间数据容错存储管理  22-26
    1.4.1 分布式并行处理框架  22-24
    1.4.2 中间数据  24-26
  1.5 节能技术  26-28
    1.5.1 基于硬件方法的节能技术  26-27
    1.5.2 基于软件方法的节能技术  27-28
  1.6 主要研究内容  28-29
  1.7 论文组织结构  29-30
第二章相关研究  30-41
  2.1 低修复成本的纠删码技术  30-34
    2.1.1 基于度数限制方法的纠删码技术  30-32
    2.1.2 基于网络编码方法的纠删码技术  32-34
  2.2 中间数据容错存储管理方法  34-38
    2.2.1 任务重执行方法  34-35
    2.2.2 分布式副本方法  35-36
    2.2.3 选择性异步复制  36-38
  2.3 功耗敏感的数据放置技术  38-40
    2.3.1 动态数据放置技术  38-39
    2.3.2 静态数据放置技术  39-40
  2.4 本章小结  40-41
第三章高容错低修复成本的纠删码研究  41-54
  3.1 基于阵列结构的高容错低修复成本的纠删码  41-47
    3.1.1 编码算法  41-44
    3.1.2 解码算法  44-47
  3.2 特性分析  47-48
  3.3 性能对比与分析  48-53
    3.3.1 修复能力  51
    3.3.2 平均多点修复成本  51-52
    3.3.3 平均单点修复成本  52-53
  3.4 本章小结  53-54
第四章基于纠删码的中间数据容错存储管理技术研究  54-65
  4.1 中间数据的特点  54-55
  4.2 基于 EXPyramid 码的中间数据容错存储管理方法  55-58
  4.3 实验结果与分析  58-64
    4.3.1 正常情况下作业运行情况对比  59-61
    4.3.2 单点失效情况下作业运行情况对比  61-63
    4.3.3 冗余中间数据量对比  63-64
  4.4 本章小结  64-65
第五章功耗敏感的数据放置技术研究  65-74
  5.1 结点挂起对系统性能的影响  65-68
  5.2 基于时间相关性的功耗敏感的数据放置算法  68-71
  5.3 实验结果与分析  71-73
  5.4 本章小结  73-74
第六章结束语  74-76
  6.1 研究工作总结  74-75
  6.2 未来工作展望  75-76
致谢  76-78
参考文献  78-83
作者在学期间取得的学术成果  83-84
作者在学期间参加的主要科研工作  84

面向数据密集型超级计算的基于纠删码的容错存储技术研究

内容摘要

全文目录

相似论文