分布式系统中的事件排序问题

在本文中，我们将探讨如何分析分布式系统中事件的排序方式。众所周知，分布式系统是由多个进程组成的，这些进程在空间上是相互分离的，它们只能通过交换消息来相互通信。这种通信可以在不同的计算机上进行，或者甚至可以在同一台计算机上的多个进程中实现。

一个显著的特点是，与单个过程中事件之间的时间间隔相比，消息传输的延迟是不可忽视的。在分布式系统中，对事件的排序存在根本性的限制：有时候，如果考虑整个分布式系统中的所有事件，那么就无法判断某个事件是否真的发生在另一个事件之前。

我们最多只能在这些事件之间定义出一种部分排序关系。而对这些事件的排序顺序的理解，自然与这些事件发生的时机相关联。

然而，在分布式系统中，我们无法依赖物理时钟来进行精确的时间测量。因为，即使计算机本身拥有物理时钟，两个位于不同系统的时钟也永远无法完全同步。实际上，任何两个物理时钟之间总会存在一定的误差。

因此，在分布式系统中对事件进行排序时，通常可以忽略物理时间因素。因为，这些事件只在该系统内部才能被观察到。

现在，可以观察到的事件，主要就是信息的发送与接收过程。

我们假设，单个进程是完全顺序执行的。也就是说，我们可以把该进程中发生的所有事件进行排序。这样，我们就能得到这些事件在进程中发生的确切顺序了。

• 所谓“事件”，其实就是发送或接收消息的过程而已。
• 现在，事件的部分排序可以用“⇢”来表示。我们可以这样定义它：如果有两个事件，且它们属于同一个过程，那么当a发生在b之前时，就可以表示为a⇢b，即a发生在b之前。
• 现在，如果有两个进程在相互通信的话，那么“a”指的是一个进程发送消息的行为，而“b”则指的是另一个进程接收到该消息的行为。因此，我们可以认为“a”发生在“b”之前。
• 最后，我们还有传递性这一性质。它指出：如果事件a发生在事件b之前，而事件b又发生在事件c之前，那么事件a也必然发生在事件c之前。也就是说，如果a⇢b且b⇢c，那么a⇢c。
• 由于这是一种部分排序，因此有可能出现这样的情况：对于两个事件a和b来说，它们不会有一个先于另一个发生。在这种情况下，我们无法通过观察系统中发生的事件来判断它们哪个先发生了。因此，我们称a和b同时发生了。

• P、Q、R分别表示各个进程。线上的点则代表各个事件。曲线则表示各个进程之间传递的消息。从这种表示方式来看，我们可以看出p1发生在r4之前。因为p1向Q发送了一条消息，而这条消息又引发了事件q2。在进程Q中，我们向R发送了一条消息，这条消息在r3时被接收到了。因此，我们可以得出结论：p1确实发生在r4之前。而r2和q6是同时发生的，因为它们不会相互影响。
• “在关系建立之前发生的事件”实际上是一种非自反的部分序关系，它存在于所有在系统中发生的事件的集合上。也就是说，对于任意一个事件a来说，(a⇢ a)这一关系并不成立。
• 这其实与爱因斯坦的广义相对论有关。在广义相对论中，各种事件都是按照可能发送出的“信息”来进行排序的。

逻辑时钟：

逻辑时钟是一种为事件分配编号的方法。这个编号可以被看作是该事件发生的时间。这里使用的表示方式是Ci<a>，其中C表示“时钟”。这些数字纯粹是逻辑上的概念，与物理时间没有任何关系。

逻辑时钟的适用条件：

• 如果事件a发生在事件b之前，那么进程Pi中，事件a的逻辑执行时间应该小于事件b的逻辑执行时间。
  • 如果 a⇢ b，那么 C<a><C<b>
• 如果a是进程Pi发送的消息，而b则是进程Pj接收到该消息的情况的话……
  • Ci<a><Cj<b>。
• 逻辑时钟与时间戳相关联。

因此，在这些条件下，我们可以通过在进程内部增加其自身的时钟来定义时钟函数。也就是说，每个进程Pi会在任意两个连续事件之间增加其对应的时钟值。

现在，我们已经得到了分布式系统中各个事件的排序方式。同时，我们还有办法为这些事件分配数字，从而可以从中构建出逻辑时钟。