分布式容错检查点算法研究与软件设计

摘要

计算机网络技术的迅猛发展，分布式系统应用的不断拓展，分布式应用对高可靠性和可用性的要求越来越迫切。一个高可用性的系统要求在任何情况下服务不会被中断并且能够提供正确的服务，因此，分布式系统的容错问题是目前分布式系统研究的热点和难点，同时也是一个富有挑战性的课题。由于分布式系统在地理区域分布的广泛性，使得整个系统无法获得一个统一的时钟，而这又是直接影响分布式系统性能的关键因素，这就给分布式系统的容错问题带来了巨大的挑战。本文以2008年申请的山东省自然科学基金项目为背景，以分布式系统容错检查点算法作为出发点，针对丰富的检查点设置策略和提高资源利用率和系统效率为目的，对分布式系统容错问题和检查点算法进行了深入的探索和研究。
　　 本文研究了分布式系统容错检查点的设置和恢复算法，容错检查点间隔设置的理论，方法和技术，探索将所研究的分布式容错检查点算法与实际的分布式容错软件相结合，提高分布式系统的可用性和算法的实用性，本文主要完成了如下工作：
　　 1.构造分布容错系统的层次结构模型并列举了该模型的主要特点，容错的概念和相关的定理,分析了分布式系统性能特性，并结合该性能提出分布式系统进程模型。根据进程通信模型进一步指出，分布式容错系统由于时钟自适应特性而出现的检查点通信问题，如孤儿报文、中途消息等。提出了如何消除这些非全局一致的检查点状态的条件和定理，给出了评价检查点算法性能优劣的指标，即算法的时间开销和空间开销。
　　 2.根据分布式容错检查点算法的原理，分析了同步检查点算法的设置，异步检查点设置和消息日志检查点算法的各自特点，深入理解了影响检查点算法性能的瓶颈因素，即算法设计较复杂，实用性较差，时空开销较大，对分布式系统性能的影响大。在此基础上，参与研究了一种改进的分布式容错检查的算法，矩阵一致检查点算法，该算法从容错的基本要素即进程间通信出发，以进程间通信的数目作为设计算法的核心思想，降低了算法的时空开销，提高了系统的整体性能，经演绎推理证明和实验验证，该检查点算法简洁有效。
　　 3.通过研究检查点算法的性能瓶颈，我们发现检查点间隔的设置和选取对于检查点算法的性能同样产生着重要的影响。在检查点间隔的设置算法中，尽量减少检查点机制所产生的时空开销对提高计算效率具有重要意义。本文在已有的动态检查点间隔设置的基础上，提出了一种新的动态检查点间隔的设置方法一随机时间序列分析方法的Markov动态检查点间隔设置，该算法既可以减少回滚重复计算时间，又可以降低检查点保存进程状态所需的存储空间。经Spin仿真实验结果表明，该动态检查点间隔算法与固定检查点算法和一般的动态检查点算法相比，平均检查点间隔开销率R(t)比传统方法平均减少1.019％。
　　 4.分布式容错软件平台的设计技术。由于分布式系统的跨平台特性，本文分别设计了Windows和Linux操作系统平台下的容错软件模块的设计方式，前者主要采用了Detour Windows API技术，通过在系统的进程中插入具有容错功能的线程来实现在Windows系统下的容错功能，并能根据保存的文件进行容错的恢复。后者主要采用了Linux LKM模块技术，在Linux内核中插入一个具有容错功能的LKM模块，进行Linux系统下检查点设置和容错恢复，该容错软件为分布式系统的可用性提供了有效的支持，具有一定的实际应用价值。

目录

文摘

英文文摘

CONTENTS

第1章 绪论

1.1 论文的选题背景和研究意义

1.1.1 容错检查点研究背景

1.1.2 检查点容错存在的问题

1.2 国内外研究与发展概况

1.3 论文的主要工作

第2章 检查点容错研究的基本概念和研究现状概述

2.1 容错检查点技术

2.2 容错检查点系统模型和基本概念

2.2.1 分布式系统模型

2.2.2 检查点容错基本概念

2.3 检查点系统发展现状

2.4 小结

第3章 分布式容错检查点算法

3.1 检查点算法

3.1.1 同步检查点算法

3.1.2 异步检查点算法

3.1.3 准同步检查点算法

3.2 消息日志算法

3.2.1 乐观消息日志

3.2.2 悲观消息日志

3.3 矩阵同步检查点算法

3.3.1 分布式系统扩展模型

3.3.2 全局一致状态判别

3.3.3 同步协调矩阵检查点算法

3.4 小结

第4章 马尔可夫决策过程的动态容错检查点间隔算法

4.1 马尔可夫决策过程概述

4.1.1 马尔可夫模型定义

4.1.2 隐马尔可夫模型

4.1.3 HMM需解决的三个问题

4.2 容错检查点间隔的设置策略

4.2.1 静态检查点间隔

4.2.2 动态检查点间隔

4.3 MDCI算法的设计与实现

4.3.1 MDCI算法存储空间建模

4.3.2 隐马尔可夫过程模型的间隔算法

4.4 算法性能评估与验证

4.4.1 算法评估

4.4.2 结果验证

4.5 小结

第5章 分布式容错软件模型与设计

5.1 分布式系统容错软件模型

5.2 Windows环境下的检查点系统

5.2.1 Detours Windows API拦截

5.2.2 进程检查点设置与回卷恢复

5.3 基于Linux内核的检查点系统

5.3.1 Linux LKM容错机制

5.3.2 检查点容错软件模式

5.4 小结

第6章 总结与展望

6.1 全文总结

6.2 课题展望

参考文献

致谢

攻读学位期间发表的学术论文目录

攻读学位期间参与科研项目及获奖情况

学位论文评阅及答辩情况表