Time, Clocks, and the Ordering of Events in a Distributed System 论文阅读
本文最后更新于：3 年前
背景
这篇论文是 Leslie Lamport 于 1978 年发表的，并在 2007 年被选入 SOSP 的名人堂，被誉为第一篇真正的”分布式系统”论文，该论文曾一度成为计算机科学史上被引用最多的论文（截止 2022 年 3 月 6 日已达到 13071 次）。论文的作者 Lamport 享有分布式计算原理之父的美誉，并且因其对分布式系统研究作出的卓越贡献，于 2013 年被授予了图灵奖。
这篇论文之所以经典，是因为它揭示了分布式系统的某些深层本质，深深地影响了人们对于分布式系统的思考方式。
当然，这篇论文除了理论意义和历史价值之外，它与业界一些重要的分布式系统实践也都有紧密的联系。比如，在大规模的分布式环境下产生单调递增的时间戳，是个很难的问题，而谷歌的全球级分布式数据库 Spanner 就解决了这个问题，甚至能够在跨越遍布全球的多个数据中心之间高效地产生单调递增的时间戳。做到这一点，靠的是一种称为 TrueTime 的机制，而这种机制的理论基础就是 Lamport 这篇论文中的物理时钟算法（两者之间有千丝万缕的联系）。再比如，这篇论文中定义的「Happened Before」关系，不仅在分布式系统设计中成为考虑不同事件之间关系的基础，而且在多线程编程模型中也是重要的概念。另外，还有让很多人忽视的一点是，利用分布式状态机来实现数据复制的通用方法（Replicated State Machine，简称 RSM），其实也是这篇论文首创的。
总之，如果在整个分布式的技术领域中，你只有精力阅读一篇论文，那一定要选这一篇了。只有理解了这篇论文中揭示的这些涉及时间、时钟和排序的概念，我们才能真正在面对分布式系统的设计问题时游刃有余。
内容
本来想写点什么，但是又感觉写的都是垃圾。因此只能强推这篇 博客，将这篇论文讲的十分透彻，我跪了。
总结
这篇论文首先介绍了应该如何认识时间，时钟和排序，接着引入了偏序关系，全序关系，逻辑时钟，物理时钟等概念，最后给出了现实世界中一种可行的为所有事件排序的方案。
对于为分布式系统中的所有事件进行排序这个问题，Lamport 首先指出简单的物理时钟是不可行的，因为一方面物理时钟很难绝对准确，另一方面不同进程的物理时钟也一定会有误差，因此需要先从逻辑时钟入手。
为此，Lamport 利用逻辑时钟定义了偏序关系：偏序关系能够为进程内部的事件和进程之间的因果事件排序，对于进程之间的独立事件无法排序。其实从系统内部的视角来看，对进程之间的独立事件进行排序本无意义。
因此，Lamport 在偏序关系的基础上又定义了全序关系：即通过一些人为规定的方式，可以把进程之间的独立事件进行排序，这样再结合偏序关系即可达到排序所有事件的理想效果，复制状态机的思想便起源于这里。
然而，这样人为规定的全序方案在现实世界来看可能违背因果一致性，产生这个现象的根本原因是逻辑时钟没有和真实的物理时钟绑定。即对于两个进程间的独立事件，系统无法感知到这两个事件在现实世界中有先后关系，所以可能给时间上发生更晚的事件指定更小的逻辑时间。因此我们得出结论：要想为分布式系统的所有事件排序，仅仅使用逻辑时钟是不行的，还是需要使用物理时钟才行。
在牛顿的物理体系下，时间是绝对的。在爱因斯坦的物理体系下，时间是相对的。根据相对论，任何信息传递的速度，最快就是光速。而一个事件要想对另一个事件产生影响，至少要在那个事件发生之前传递一定的信息到达所在的空间位置。举个最简单的例子，太阳光从太阳表面射出后大约需要 8.3 分钟才能到达地球，那么即使太阳发生了大爆炸，至少也需要 8.3 分钟才能对地球产生实质影响。
基于此，Lamport 结合相对论的知识介绍了我们所在的现实世界就是一种偏序时空，并进一步证明：如果物理时钟的误差能够限定到一个范围内，则违反因果一致性的现象就不会出现，即我们便可以为分布式系统中的所有事件排序。简单来讲：对于两个进程间的独立事件，如果他们在物理世界中存在时空偏序关系，那信息的传递也需要一定的时间。只要系统能够保证：系统内部的时间误差不会超过两个外部事件产生因果关系的时间，则就能够正确的为所有事件排序。这也是 Google TrueTime 正确性的理论支撑。
一个分布式系统自成宇宙，它是对现实世界的一种刻画。分布式系统由不同的进程组成，而不同的进程分布在不同的空间，每个进程可以看成一个单独的参照系。当我们按照这样的观点重新审视这个世界的时候，会产生一些很有意思的想法。
分布式系统是一个模拟系统。如果仅仅使用逻辑时钟，就相当于在使用一种系统内部自洽的方式对时间进行了模拟。由于逻辑时钟跟物理时间无关，因此我们站在系统内是不能感知到现实世界的时间流逝的。系统之所以会发现违反了因果一致性，是因为存在一种系统外的信息传递方式。
假设我们生活在模拟系统内部，我们会发现，有人在一个较早的逻辑时刻（对应较小的时间戳）接收到了其他人在较晚的逻辑时刻（对应较大的时间戳）的信息，相当于接收到了来自未来的信息，而且这个信息是通过不在这个系统内的某种机制传递的。据此，我们也许不需要特意“向外看”，就能推断出在这个系统外部，还有一个世界（我们的这个现实世界）。
同理，在我们当前生活的这个现实世界中，信息传递的速度受限于光速，而且时间永远向前流逝。也许某一天，我们发现了某种超越光速的信息传递手段，或者我们接收到了来自未来的信息（意味着我们可以预知未来了），那么，也许就说明，在我们这个世界的底层，还有一个更大的未知世界存在在那里。
在诺兰的《星际穿越》中，爱是我们唯一能感知到穿越时空维度的东西作为主旨贯穿了整部电影。主角在黑洞内用爱穿越了时空维度的限制，向女儿传递了缺少的关键数据，女儿也正是意识到这一点才带领人类走出了绝境。光不能逃逸黑洞，但爱可以，这是多么浪漫的主旨呀。
感想
说起来有些感慨，这篇学术论文不仅深入到了分布式系统的基础层面，还延伸到了宇宙的本质，引起了我们对世界的无限遐想。
在我的内心深处，毫无疑问这篇论文是我读过的最佳论文，没有之一。