作者：振荡Qi 

授权转自：原理

哲学园鸣谢

在现实世界里，想要知道此时是几分几秒好像并不是什么难事儿。可是对电脑来说，事情却并没有那么简单。

现代计算机系统中，对于时间流逝的感知和量度，大部分来自石英晶体振荡器。这是利用石英晶片的压电效应制造的电子元件。当晶片在交变电压的作用下产生谐振时，振荡器可以输出稳定度较高的振荡频率。之所以说稳定度较高，是因为它并不是以绝对恒定的频率在振动。在各方面的影响下，总会出现振荡频率比元件声称的频率稍高或者稍低的状况。这种偏差反映到系统时钟上，就是系统时钟比标准时间稍快或者稍慢。

单机系统

如果所有的任务和作业都是在单个计算机上完成的，似乎系统时钟稍快稍慢并不是很严重的事情。我们可以设想这个稍快或者稍慢的计算机就像是一个独立的世界。在这个世界中，因为时钟速率不同，带来的影响也只不过是各种事件发生得更快或者更慢。该发生的终究都会发生，事件的因果先后顺序也都还在。只要不需要和外部世界的时间作协调同步，那这里就像一个平行宇宙一样，冷暖自知。

分布式系统

但如果是分布式系统的话，情况就不一样了。所谓分布式系统，简单来看就是由多台计算机组成的系统，这些计算机通过网络相互通信，共同协作完成任务。现如今的互联网，各式的云服务，搜索引擎，以及微信微博等的社交软件，在它们的背后都是一个分布式系统。

理想情况下，我们当然是希望系统内的所有计算机对此时此刻是什么时间以及时间过得有多快都有一个共同的概念。如果拿“老狼老狼几点了”这个游戏来类比的话，就好像大家都觉得现在是12点了，该跑的跑该抓的抓，可是有个小朋友他偏偏觉得现在是11:58，每次都是他被抓；而且他当老狼的时候，每次他觉得12点的时候，其他所有小朋友都觉得已经12:02了，并且都跑出去二里地了，这游戏可还怎么玩儿？！

要同步系统内所有计算机的时钟，首先，自然的想法是让系统内的计算机都跟同一个更可靠的时钟源做校准。这种方法可行，但并不足够好。来自谷歌的一篇文章[1]提到说，他们自己数据中心的所有服务器会有200百万分率（ppm, parts per million）的时钟偏差。即，如果所有机器每30秒做一次校准的话，机器还是会有6毫秒的偏差；如果每天做一次的话，偏差则会有17秒之多。这个校准后的差值，部分来自于晶振本身的频率波动，其实还有一部分来自时钟校准的过程。时钟校准的过程包含了网络通信，待校准的计算机和拥有更可靠时间的计算机通过网络通信交换信息以实现校准。然而网络通讯是包含了通信延迟的，更可怕的是，我们对这个延迟并不能有一个很准确的测量（这个延迟取决于机器本身在收发信息时的繁忙程度，以及信息传递过程中通信信道的繁忙程度）。网络时间协议（NTP）是计算机之间进行时间校准的标准协议，它的工作原理大致如下：

○ NTP计算时钟偏差示意图。 | 图片来源：[2]

可靠时钟源会记录本地的时间T₁和T₂, 并通过回复信息返回给请求者，请求校准的计算机自己记录下T₀和T₃, 最终较可靠的时钟源跟本地时钟的偏差为：

（（T₁﹣T₀）﹢（T₂-T₃））/ 2

这个计算是带有一个假设的，就是请求的发送和回复的回传在网络通信上的延迟是相等的，这个计算希望通过分子中的两项相加来把这个通信延迟项给抵消掉。在不事先预知相关计算机和通信信道的繁忙程度以及通信延迟不可测的情况下，这种假设和计算似乎是对真实偏差的一个可以做到的最佳的近似了。

所以，在系统设计阶段，我们就不得不假定计算机之间的时钟会有至少10毫秒左右的偏差？就只有这样了么？

或许，需要换一个角度来思考这个问题。比如，我们真的需要知道准确的时刻么？

现实生活中，我们需要确认时间，大部分时候只是为了确认相关事件的顺序。在赛跑的终点线，我们记录各个运动员撞线的时刻，按照不同的时刻，来给他们排列次序。上班打卡，是为了确认你到公司这个事件，和公司规定的所有员工开始上班这个事件，谁先谁后。飞机航班预先告知起飞时刻，是为了让旅客考虑到赶往机场，值机/托运行李，安检，登机这些事件本身的时间长短，合理安排计划，确保它们可以有序地不重叠地依次发生。所以，如果在系统中我们不借助准确的时刻信息，就能确定在不同的计算机上所要发生的所有事件的顺序呢？是不是就可以不依赖这些个一点儿都不准的时间而照常运转了呢？

逻辑时钟

莱斯利·兰波特（Leslie Lamport）在他1978的一篇论文[3]中阐述了这一观点并提出了逻辑时钟这个概念。他的想法是，我们可以把时钟看作一个函数，函数的输入是系统中的事件，输出是一个数，是这个“逻辑时钟”赋予这个事件的“逻辑时刻”。这个“逻辑时刻”不必须和物理世界里的时间有任何关系，它可以只是一个计数器的值。像在现实世界中一样，我们通过比较这些“时刻”的大小来判断事件发生的次序。只是在实现这个特殊的“时钟函数”的时候，需要遵守两条规则：（一）在任意一台计算机（原文中使用的是“进程”）中，发生任意事件的同时，增加本地“逻辑时钟”的值，并把它的值作为“时刻”赋予这个事件；（二）当一个计算机发送信息（也被视为一个事件，对“时钟”的操作遵循前一条规则）进行通信的同时，要在信息中附加此时发送方本地“逻辑时钟”的“时刻”信息，在任何计算机收到信息（也被视为一个事件，对“时钟”的操作遵循前一条规则）的同时，比较信息中的“时刻”和本地“逻辑时钟”的值，取其中较大的一个作为本地新的“时刻”。

○ Leslie Lamport　| 图片来源：http://amturing.acm.org/photo/lamport_1205376.cfm

文中的论述表明，利用这两条规则，可以表达系统中所有可能存在因果关系事件的次序，无论事件是否发生在同一台计算机上。规则（一）确保发生在同一台计算机上的所有事件都有明确的先后顺序，这是任何试图对“时钟”的重新定义都必须保证的。因为从计算机系统顺序执行指令的模型来看，即使没有任何“时钟”或是“时间”的概念，事件发生的次序也都是明晰的。规则（二）则是抓住了不同计算机上的事件之间可能存在的因果关系。对发生在两台计算机之间的一条通讯信息而言，发送是接受的原因，任何发生在发送方发送事件之前的事件，都有可能成为发送信息这一事件的原因；同样地，所有接受方发生在接受信息事件之后的事件，也都有可能成为接受信息这一事件的结果。而通过在接受信息时调整本地“时钟”到一个两个时钟的较大者上，完美地表达了所有以上可能存在的因果先后关系：所有（可能的）原因的“时刻”都比（可能的）结果的“时刻”要小。

○ “逻辑时钟”的运行 | 图片来源：[2]

上图中，P1，P2，P3代表三台不同的计算机，a到f是发生的不同的事件。事件上方的箭头表示本地“逻辑时钟”按照两条规则对于事件所发生的响应。在开始时，所有的本地“时刻”都是0，箭头右边的数字代表了在“逻辑时钟”下事件发生的“时刻”。通过比较这些时刻，我们可以得出事件发生的次序。在图中还有一个问题被表现出来了：如何比较事件a和e的次序（“时刻”都是1）？在文章中兰波特的观点是，对于这种“时刻”相等的状况，我们可以制定任意的规则，来得出一个次序。无论是a在e之前，还是e在a之前，都是被允许的。原因在于事件a和e，并没有因果性地相互影响，在f发生以前，对于P3来说，并不知道事件a已经发生了，所以谁先谁后都不会影响系统的正确性。

从系统实现的角度，如果用简单的一个计数器来实现“逻辑时钟”的话，每次对“时钟”的增长只不过是对一个变量的加法运算和读写操作，在现代CPU上，这可以在纳秒的尺度上完成。这么看来的话，“逻辑时钟”所构造的体系要比通过各种校准试图紧跟物理时间的系统强大的多。

在文章中，兰波特使用了很多时空图来进行分析。显然他从物理的相对论里也汲取了不少灵感。他说：“在相对论中，事件的顺序是通过有可能被传递的信息来定义的。然而，我们采用了一种更加务实的方法，那就是只考虑那些真正被发出的信息。我们应该可以只通过系统中确实发送了的信息，而不是那些有可能被发送的信息，来断定这个系统是否在正确地运转”。[3] 

2013年，兰波特获得了图灵奖，为了表彰他在并发和分布式系统领域所做的基础性贡献[4]。本文中的“逻辑时钟”就是其中重要的一部分。

顺便，排版系统LaTex里的“La”也说的是他。：）

参考文献：

[1] James C. Corbett, Jeffrey Dean, Michael Epstein, el al.: “Spanner: Google’s Globally-Distributed Database”

[2] Dr Robert Watson http://www.cl.cam.ac.uk/teaching/1718/ConcDisSys/2017-CDS-1B-L12-handout.pdf

[3] Leslie Lamport: “Time, Clocks, and the Ordering of Events in a Distributed System”

[4] https://amturing.acm.org/award_winners/lamport_1205376.cfm

[5] Martin Kleppmann, Designing Data-Intensive Applications, O’Reilly Media, 2017.