在前一篇文章中，我们谈到了分布式系统里进程彼此的物理时间是如何进行同步的，并介绍了一些经典的时间同步算法。但静下心来仔细想想，我们希望进行时间同步，很多时候是希望不同的进程，对系统内事件的顺序达成一致。至于是否是使用真实世界的那个时间来排序，往往并不是那么重要。

那么，如何在一个分布式系统中，对发生在众多节点上的事件进行定序呢？目前已知的做法包括以下几种：

1. 使用物理时间同步的方法，确保众多节点的时间偏差在某个范围内(参考前一篇文章)。而后记录事件的发生时间及理论误差范围，比如将每个事件的发生时间登记为\((t \pm \Delta)\), 如果两个事件的时间范围没有overlap，那么就自然的可以排序判断；否则，则需要引入一个新的排序规则(比如以节点id)，对这两个事件约定一个排序。spanner中采用了这种方式。
2. 采用Lamport Timestamp及其引申算法进行定序，确保事件满足causality consistency的性质，成为后续更高层次的分布式算法设计的基础。本文后面主要将展开这类算法，并引出分布式系统中一些基础概念。这些基础概念是理解分布式共识问题(consensus problem)的基础。

为明确这个问题，我们首先需要先对事件的序(happen-before)做出一个定义。在Lamport的体系中，事件的先后关系是按照如下原则设定的：

• 规则一：如果A、B两个事件都发生在同一个进程内，那么，A、B之间的序自然可以由这个进程给出。假如进程先执行了A后执行了B，那么可以说A在B之前发生，记为\(A \prec B\)；
• 规则二：如果进程x往进程y发送了一条消息M；设在进程x的消息发送事件为A，进程y收到消息的事件为B，则显然我们应当认为A在B之前发生，同样记为\(A \prec B\)。

这两个规则是非常自然的，因为它体现了事物的“因果关系”(causality)。比如，张三买了张电影票后(事件A)，走进了电影院(事件B); 在路边李四的眼里，也应该是按照这个顺序进行的（规则一），否则会让人以为张三无票进场了。但假如还有个王五，也先买票(事件C)后进电影院(事件D)。那么，从观察者的角度来看，只需要保证\(A \prec B\)和\(C \prec D\)即可。AB和CD是并发的两组独立事件，无论是怎么相互传插着到达第三者眼中的，这个第三者都不会觉察出有什么异样；但如果王五不是从售票窗口买的电影票，而是从张三那里买的，即二者之间发生了通讯、交换了信息，那我们就必需要满足\(A \prec C\)和\(C \prec D\)，否则旁观者就会觉察出王五凭空从口袋里变出了一张电影票，是”不合逻辑”的。我们希望设计一种算法，能够对一个分布式系统间的所有事件打上一个逻辑上的时间戳(timestamp)，使其排序结果不违背上面的两个规则，以符合人对事件因果关系的理解。

由此引出了Lamport timestamp的算法，这个算法就是一种给事件打上逻辑时间戳、确保其满足causality的基本属性。这个算法的基本过程为：

• 每个进程都记录自己的一个当前时间戳，初始的时候，大家都是0
• 如果进程内部发生了一个新的事件，那么将当前时间戳记为\(t'=t+1\)，并认为事件发生于\(t'\)时刻
• 如果进程A向进程B通讯，则发送消息的时候，进程A的时间戳\(t'_A = t_A + 1\)，并随消息发送到B，B更新自己的时间戳为\(t'_B = max(t'_B, t'_A) + 1\)

// TODO: 补充一个图，说明lamport的计算过程

至此，系统中事件都被打上了时间戳，彼此满足Causality的属性。我们可以据此比较系统中的两个事件发生的先后顺序。如果\(A \prec B\)和\(B \prec A\)同时为false的时候，我们可以认为事件A和B同时发生，即是”并发”(concurrency)的，可以简单记为\(A == B\)。我们能否直接以这个timestamp来对事件作排序呢？

答案显然是不行的，因为有并发事件。我们无法判断并发的事件，谁发生在谁的前面。在Lamport的算法中，这个问题可以通过引入node-id，即进程的标识来实现：当两个事件的时间戳一致的时候，则通过比较node-id的大小，来对这些事件进行排序。至此我们就可以给出一个序，它是满足causality的，并且能够被大多数人理解。对分布式系统中的事件进行”排序”，以满足Causality性质的过程，被称为Total ordering。

但至此是否解决了开头所提出的时序的问题了呢？其实没有。比如在现实的系统中，我们需要所有的进程，对系统中发生的事件的顺序达成一致。比如某个对象的状态变化，如果所有的进程，对于这个object起始状态，以及对这个object的操作顺序达成了一致，那么我们很自然的就能确保这个object的当前状态在所有进程的理解中是一致的¹。在这个场景中，一个发生了的事件需要被广播(broadcast)出去、被系统中的其他进程“观察”到，且观察者对于观察到的事件的顺序要彼此达成一致(Total order broadcast)。这个场景是无法简单的用Lamport timestamp的方法解决的。比如下图中：进程x先后发生了两个事件，即\(A \prec B\)。这个过程需要被进程m和n观察到，即有消息被广播发送给m和n进程。但由于网络通讯的原因，A事件被延后了很久才被n观察到。此时，在m、n两个观察者的眼里，A、B事件发生的顺序就是相反的。

换句话说，Total order虽然给出了事件的一个”有意义的序”，但这个序是假定有个上帝视角的进程，收集到所有信息后所给出的；但在现实的多进程系统中，Lamport timestamp还是没办法让所有的”观察者”观察到的顺序保持一致。大家所熟知的一些分布式算法，比如zookeeper内的zab、近几年开始流行的raft，还有让人十分费解的经典的paxos协议，都是为了一定程度的解决这个问题，后面有机会会展开介绍。