分布式系统中的时间，时钟，以及事件顺序

原文：Time, Clocks, and the Ordering of Events in a Distributed System
作者：Leslie Lamport
发表日期：1978 年 07 月
译者：ou@https://ouonline.net/

摘要

本文研究了“分布式系统中一个事件在另一个事件之前发生”这个概念，并用它来定义事件的偏序关系。给出了用于同步逻辑时钟系统的分布式算法，该算法可以用来确定事件的全序关系。用解决同步问题的方法来说明全序的使用。这个算法被专门用来同步物理时钟，并得出时钟同步的最大偏离范围。

引言

时间的概念是我们思维的基础。它源自一个更基础的概念，即事件发生的顺序。如果某事发生在我们的时钟读数为 3:15 之后并且在其读数变为 3:16 之前，我们就说 3:15 发生了某事。事件的时间顺序概念充斥着我们对系统的思考。例如，在航空公司的预定系统中，我们指定如果在航班满员之前提出预定请求，那么应该允许该请求。然而，我们会看到，在考虑分布式系统中的事件时，必须仔细重新检查这个概念。

一个分布式系统由空间上分离的不同进程的集合组成，这些进程通过交换消息来互相通信。一个互相连接的计算机的网络，例如 ARPA，就是一个分布式系统。单个计算机也可以被看作是一个分布式系统，其中的中央控制单元，存储单元和输入输出通道都是独立的进程。如果消息传输延迟与单个进程中事件发生的间隔相比不能忽略，则这个系统就是分布式的。

我们将主要关注空间上分离的计算机系统。但是，我们的许多结论将会更通用。特别地，单台计算机上的多进程系统会遇到与分布式系统类似的问题，因为某些事件的发生顺序不可预测。

在分布式系统中，有时候无法决定两个事件中的哪一个先发生。因此，“先发生”关系只是系统中事件的偏序关系。我们发现这个问题经常出现，是因为人们没有完全意识到这个事实以及它的含义。

在本文中，我们讨论了由“先发生”关系定义的偏序，并给出了一种分布式算法，用于将偏序扩展为所有事件的一致全序。这个算法可以为实现分布式系统提供有用的机制。我们通过一个解决同步问题的简单方法来说明它的用法。如果由这个算法得到的顺序和用户感知的顺序不同，则可能会发生意外的异常行为。通过引入真实的物理时钟可以避免这种情况。我们介绍了一种用来同步这些时钟的简单的方法，并推导出它们漂移的不同步程度的上限。

偏序

如果事件 a 发生的时间早于事件 b，大部分人可能会说 …

阅读全文…