《Time, Clocks, and the Ordering of Events in a Distributed System》中文版

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

原文: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,大部分人可能会说 …

阅读全文…