基于网络编码的分布式数据存储与故障修复策略

作     者：田志坚 

作者单位：浙江工业大学 

学位级别：硕士

导师姓名：朱艺华

授予年度：2013年

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：网络编码 分布式存储 重建时间 修复带宽 修复策略 

摘      要：如今,人类社会已经步入了信息化高速发展的时期,信息在社会生活中起举足轻重的地位。与此同时,海量信息数据的存储也越来越被人们所重视。尤其是近几年高清视频的广泛应用,大数据时代的来临,传统的集中式数据存储系统呈现出越来越多的弊端,比如安全性不高,可靠性也没有保证,可扩展性不强等。分布式数据存储系统则弥补了这方面的缺陷,它使得海量数据能以分布的形式存储,满足了大规模存储的需求,而且具有更高的稳定性。 但是分布式数据存储会面临存储节点故障的问题,因而如何修复故障节点保证系统的稳定运行成为分布式数据存储系统的重要课题。当前,修复故障节点的指标主要有节点存储容量,修复带宽,修复开销,重建时间等。如何在修复故障节点的同时使得相关指标尽可能地小成为了当前分布式数据存储的研究热点。本文研究了基于网络编码的分布式数据存储及故障修复策略,主要的工作和贡献如下： (1)本文将分布式数据存储系统的故障修复问题抽象化为基于网络编码的信息流图,以便于用图论的相关理论来简化分析数据传输过程。 (2)针对目前的故障修复策略没有对重建时间进行优化,本文从理论上分析了重建时间的下界,然后提出了最小化重建时间故障修复策略MTR (Minimum-Time Repair),该修复策略达到了重建时间的下界值,而且,在此基础上将修复带宽降到了最低值。分析数据表明,与现有的节点修复策略相比,MTR修复策略能大大降低重建时间,使得故障节点快速修复,这对那些需要快速修复的分布式数据存储系统有着非常重要的意义。 (3)考虑到实际应用中,重建时间受约束这个因素,本文提出了重建时间约束的带宽最优故障修复策略,建立了该策略的优化模型并显式给出最优解。该策略能在给定的重建时间阈内修复故障节点,且在该时间点上的修复带宽是最小的。同时,该策略具有较好的灵活性,在任何重建时间阈值(大于重建时间下界)内,都存在使修复带宽最小的故障修复策略。