逻辑时间和兰波特时钟（第一部分）

在本系列文章中，我们已经看到很多事情远比表面看起来复杂得多。我们从失败中看到了这一点，也从复制中看到了这一点。最近，我们发现就连时间的概念也比我们最初想象的要复杂得多。

然而，当你发现自己原本以为了解的事情比以往任何时候都更加复杂时，有时答案反而是化繁为简。换句话说，我们可以通过剔除令人困惑的部分，将其简化为最本质的要素，从而简化问题。事实上，这正是上世纪70年代末一位计算机科学家所采用的方法。当时，他和我们一样，正试图弄清如何在分布式系统中理解时间的概念。

前两篇关于时钟和分布式系统中事件排序的文章，都是在为我们即将揭晓的主题——逻辑时间和Lamport时钟——做铺垫！内容很多，所以我们会分两篇文章来讲解。让我们直接进入第一部分吧！

因果关系和“先发生”

逻辑时钟的故事始于1978年，当时一篇发表在ACM通讯期刊上的论文载入史册。麻省计算机协会的计算机科学家莱斯利·兰波特（Leslie Lamport）撰写了这篇关于分布式系统中事件排序的研究论文。这篇题为《分布式系统中的时间、时钟和事件排序》的论文后来成为计算机科学领域被引用次数最多的论文之一，并在20多年后荣获分布式计算原理最具影响力论文奖。

在论文中，兰波特概述了我们人类如何看待时间，以及为什么在面对分布式系统和偏序概念时，我们需要转变范式。他解释说：“在分布式系统中，有时无法确定两个事件哪个先发生。”

正如兰波特在他的论文中所述，我们之所以关注时间，是为了弄清楚事件发生的顺序。虽然在分布式系统中这无疑更加困难（有时甚至不可能！），但我们想要了解系统中某些事件顺序的原因都源于同一个愿望：我们关心事件的顺序，以便确定这些事件之间的联系。在处理任何系统中的事件时，我们之所以想要对它们进行排序，实际上是为了了解系统内部的事件链。尤其是在分布式系统中，这意味着我们经常试图确定一个节点上的事件是否会影响或导致另一个节点上的事件。

但是，正如我们在分布式系统的研究中看到的那样，这项任务绝非易事。当系统是分布式的，就没有全局时钟，这意味着我们无法依赖任何中心时间源。这也意味着系统中的事件并非完全有序，也就是说我们无法确定系统中每个事件发生的确切时间。Lamport 的论文承认了所有这些限制，并深切体会到这个问题确实非常棘手！

兰波特的解决方案是转变我们的思维方式。他提出了一个新颖的观点：我们实际上无需一开始就从整体顺序的角度来思考因果关系。相反，他认为我们可以从事件的部分顺序入手，然后只需弄清楚哪些事件发生在其他事件之前。一旦我们确定了部分顺序，就可以将其转化为一致的整体顺序。

那么我们该如何做到这一点呢？首先，我们需要转变思路，从思考事件何时发生转变为思考事件发生之前发生了什么。

从“何时”到“之前”的转变

兰波特的论文核心思想是“一个事件发生在另一个事件之前”。他使用“ →”简写符号来表示“发生于”关系，即一个事件发生在另一个事件之前。例如，如果我们知道事件a发生在事件b之前，那么我们可以说a → b，或者说a发生在b之前。

“先于”关系也可以传递。换句话说，我们可以构建一个事件链，其中一个事件发生在另一个事件之前。如果我们说a → b且b → c，那么利用传递性，我们可以说a → c，或者说a发生在c 之前。我们可以想象，我们可以很容易地将一系列事件串联起来，其中一个事件发生在另一个事件之前，而后者又发生在下一个事件之前，以此类推。

等等——我们一直在讨论系统中的各种事件，但却一直没有真正弄清楚事件究竟是什么！事实上，分布式系统中的事件可以采取不同的形式。我们知道，分布式系统中可以有许多不同的节点。每个节点都有自己的本地系统时钟，并且能够处理自己的任务。此外，节点之间还可以相互通信，互相发送消息。

事件涵盖了系统中节点内部和节点之间可能发生的所有不同情况。事件可以是单个进程或节点上发生的事件。事件还包括发送事件，即节点向另一个节点或进程发送消息的事件。反之，我们也必须考虑接收事件，即节点从系统其他位置接收传入消息的事件。

在上面的例子中，我们可以看到这三种事件的示例。我们有两个进程 P 和 Q。进程 Q 上发生一个事件 Q3，该事件与发送或接收任何消息无关。这是我们的基本事件，表明进程 Q 的节点上发生了某些事情。此外，我们还有几个发送事件：P1、Q1 和 Q4。这些事件都表明我们正在从一个节点向系统中的其他节点发送消息。另一方面，P2、P3 和 Q2 都是接收事件，它们表明我们已经从系统中的另一个节点接收到了消息。

既然我们已经理解了系统中的事件是什么，就可以回到“先发生”关系上来讨论。当我们说事件a → b时，我们是在断言事件a发生在事件b之前，因为a的确发生在b之前。我们可以说这两个事件是因果顺序的，事件的先后顺序取决于一个事件导致另一个事件的发生。

因果关系有一些重要的规则需要我们理解。要使a → b成为因果关系，以下三种情况之一必须成立：

1. 事件a和b必须发生在同一 进程上，并且a必须在b发生之前发生。
2. 只要a是与 b 对应的发送事件，并且 b 必须是其接收事件，这些事件就可以发生在不同的 进程中。
3. 这些事件与系统中的另一个事件有传递关系，但a仍然发生在b之前。例如，如果a发生在c之前，而c发生在b之前，那么我们知道a → b。

当信息在时间和空间中从一个进程传递到另一个进程时，我们可以开始构建因果事件链（也称为因果路径），并观察不同进程中的事件是如何相互关联的。例如，在进程 P 和 Q 中，Q1 → P3（通过事件 P2），以及 P1 → Q4（通过事件 Q2 和 Q3）。

最后值得一提的是，如果事件a和b并非先后发生，那么我们可以说a ≠ > b且b ≠ > a，这两个事件是同时发生的。我们将在本文的第二部分更深入地探讨这一点，但现在我们只需记住，同时发生的事件之间不存在因果关系。

舞台上的逻辑时钟

除了“先发生”的概念之外，兰波特在论文中引入的另一个核心概念是逻辑时钟。我们已经知道，分布式系统中的每个节点或进程都有自己的时间概念，或者说自己的本地时钟。然而，兰波特对本地时钟的理解与我们之前所见的有所不同。

Lamport建议使用与我们通常所想到的物理时钟不同的方法。与其使用每个进程的物理时钟来跟踪事件顺序，不如使用计数器。计数器可以从初始时间（例如0）开始，我们可以将该计数器视为进程自身的本地时钟。

Lamport 进一步提出，分布式系统中的每个进程不仅应该有自己的时钟，而且进程记录的每个事件也应该在该进程的本地时钟上有一个值。此外，每个事件在时钟上的值必须反映任何先于事件发生的关系。例如，如果事件a → b ，那么事件a发生的时钟时间必须小于事件b发生的时钟时间；换句话说，clock( a ) < clock( b )。

通过使用基本计数器而非物理时钟，兰波特简化了时钟系统，使其更易于处理。这些计数器时钟被称为逻辑时钟。逻辑时钟与物理时钟截然不同，它没有中心时间概念，而仅仅是一个根据系统中的事件递增的计数器。

分布式系统中的每个进程都可以使用逻辑时钟来对所有与其相关的事件进行因果排序。当进程中发生事件（无论是发送事件还是接收事件）时，进程的时钟计数器都会递增一个任意值。我们将在本文的第二部分详细了解其实际工作原理。我们还将介绍 Lamport 的计数器递增算法，以及如何在进程间遵循因果关系。有很多有趣的内容值得学习；幸运的是，我们有更多的时间，并且还有另一篇文章来涵盖所有内容！

资源

兰波特关于逻辑时钟和因果顺序的研究成果颇丰，相关教材和文献也相当丰富。有很多优秀的资源介绍了这些主题，难度各异。如果您想深入阅读，不妨看看我下面列出的一些我最喜欢的资源！

1. 分布式系统中的时间、时钟和事件排序，莱斯利·兰波特
2. 分布式系统中的时间、时钟和事件顺序，丹·鲁宾斯坦
3. 时间和排序：兰波特时间戳，Indranil Gupta
4. 兰波特的逻辑时钟，迈克尔·惠特克
5. 逻辑时钟，保罗·克日扎诺夫斯基教授