分布式系统下时钟同步及事件因果一致性问题研究

摘要

时钟同步是分布式系统中经典的问题，是分布式计算中的核心技术之一。随着计算机技术和网络通讯技术的迅猛发展，人们对该问题给予了更多的关注和研究。分布式系统内事件因果顺序的确定是时钟同步问题的目标之一，对于该问题的研究产生了很多新算法，提出了使用逻辑时钟(如向量时钟)的时间戳方法，将时钟同步问题发展到一个新的领域。本文首先介绍了当前该问题的背景和研究现状，然后介绍了分布式系统的概念和特点，这是研究该问题的理论基础。
　　要实现分布的各节点间的时钟同步，面临着许多困难。首先，由于计算机硬件中对时钟的实现通常是采用对晶振体的震动频率来计量时间的，但是由于该硬件设备存在的固有的漂移特性，使得每个计算机终端都有不同的时钟速率，这也是产生时钟同步问题的来由。第二，实现时钟同步必然要通过网络交换信息，但是由于网络延迟的存在及不确定性，很难获得准确的其他节点的时钟信息。第三，还要注意对网络产生的负担。第四，是节点发生故障时的处理问题，如何知道节点是否发生故障以及如何使其恢复正常也是主要考虑的问题。最后，就是要实现高精度的时钟同步，这是对时钟同步算法评价的最主要的标准。
　　本论文详细讨论了时钟同步问题的概念和相关定义。并按照不同的分类方法介绍了不同的时钟同步算法对以上各问题的实现情况，它们由于有不同的侧重，所以适用于不同的分布式环境，并有不同的实现效果。然后介绍一种经典的具有容错和恢复能力的时钟同步算法。时钟同步问题的一个实现目标是要确定分布式系统内数据的一致和事件发生顺序的先后关系。但是，由于我们很难得到一个高精度的同步时钟，因此，提出了使用逻辑时钟的方法，逻辑时钟不再表示时间上的一致性，而只是表示事件发生的顺序在逻辑上一致，通常逻辑时钟采用一维的数组(如向量时钟、障碍-锁时间戳等)实现，本文详细介绍了向量时钟的实现方法和它的改进算法，并对它们的缺陷和效果做了讨论。
　　论文提出了一种时钟同步模型，它适用于一个封闭的分布式系统。采用主动式同步方式，通过获得各节点的平均运行时间来调整各节点的时钟，它类似于平

目录

摘要

ABSTRACT

第1章 绪论

1.1 背景

1.2 国内外研究现状

1.3 论文内容、成果和意义

1.4 论文的结构

第2章 时钟同步问题概述

2.1 分布式系统简述

2.1.1 分布式系统概念和特点

2.1.2 接口和协议

2.2 时间的计量

2.3 时钟同步的定义

2.4 时钟同步要解决的问题

2.5 时钟同步方式和模型

2.5.1 时钟同步方式

2.5.2 内部时钟同步

2.5.3 外部时钟同步

2.6 本章小结

第3章 时钟同步算法与事件因果一致性研究

3.1 时钟同步算法介绍

3.1.1 相关概念

3.1.2 算法前提条件

3.1.3 算法设计目标

3.1.4 算法的实现

3.1.5 故障恢复

3.2 事件因果一致性研究

3.2.1 问题定义

3.2.2 算法的实现

3.2.3 改进的算法

3.2.4 讨论

3.3 本章小结

第4章 时钟同步模型的设计与实现

4.1 算法概述

4.2 前提条件

4.3 算法的实现

4.3.1 获得校正时钟差

4.3.2 同步周期调整

4.4 故障处理

4.5 模拟实验与结果分析

4.6 本章小结

第5章 结束语

参考文献

致谢

攻读学位期间发表的学术论文和参加的工作

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