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