前言

本文是讀完P(guān)aper（本文中Paper特指《Time, Clocks and the Ordering of Events in a Distributed System》，下同）后的一些感想涨颜，不是譯文（推薦閱讀原文），感想也純屬一家之言宣肚，歡迎指正。
本文按照以下結(jié)構(gòu)組織：首先簡(jiǎn)單總結(jié)下本次閱讀的Paper的背景喻鳄、主要內(nèi)容和影響；其后介紹下本人讀完paper后的一些感想。感想部分主要包含了

1. 分布式系統(tǒng)中的因果序和相依相對(duì)論中因果序的異同
2. Spanner中的True Time和本文的Physical Clocks的差別唆貌，以及Spanner的一個(gè)理論缺陷
3. Logical Clocks和Physical Clocks的本質(zhì)區(qū)別

讀過(guò)paper的可以直接跳到感想部分。

總結(jié)

本Paper是Leslie Lamport老爺子在1978年的時(shí)候?qū)懙墓敢遥m然已經(jīng)是41年前的Paper了锨咙，但是Paper挖掘了分布式系統(tǒng)中的時(shí)間的本質(zhì)，并結(jié)合狹義相對(duì)論進(jìn)行深入的分析追逮，給人一種醍醐灌頂?shù)母杏X(jué)酪刀。Paper中提出的"happened before"，Logical Clocks钮孵，The Partial Ordering骂倘，Replicated State Machine等是目前整個(gè)分布式理論的基礎(chǔ)。本Paper對(duì)于現(xiàn)代分布式理論的意義不亞于狹義相對(duì)論之于現(xiàn)代物理學(xué)巴席。

本Paper在Google Scholar中的引用數(shù)為11231历涝，最早發(fā)表于“Communication of ACM”，后分別獲得了“2000 PODC Influential Paper Award”以及“ACM SIGOPS Hall of Fame Award in 2007” [1]

本Paper的幾項(xiàng)重要貢獻(xiàn)

1. 指出了分布式系統(tǒng)中時(shí)間的本質(zhì)漾唉，探索了分布式理論的本質(zhì)
2. 提出了Logical Clock算法荧库，是后續(xù)Vector Clock，HLC等的基礎(chǔ)
3. 提出了Replicated State Machine的理念赵刑，是后續(xù)Paxos及其應(yīng)用的基礎(chǔ)
4. 設(shè)計(jì)了無(wú)中心的分布式臨界資源算法分衫，是后續(xù)多種無(wú)中心分布式算法的鼻祖
5. 設(shè)計(jì)了時(shí)間同步的雛形算法，后續(xù)NTP等的基礎(chǔ)

本Paper大致分為如下幾部分：

1. Happened Before & Partial Ordering

這部分提出了分布式系統(tǒng)中的時(shí)間問(wèn)題般此。我們生活中感知的事件（Event）發(fā)生的先后是依賴于時(shí)鐘的蚪战，而分布式系統(tǒng) “A distributed system consists of a collection of distinct processes which are spatially separated, and which communicate with one another by exchanging messages.” 中很難包含一個(gè)實(shí)際的時(shí)鐘（Wall Clock），同時(shí)在多個(gè)不同process中的時(shí)鐘往往不夠精確铐懊，因此在分布式系統(tǒng)中必須有一套獨(dú)立的算法來(lái)解決時(shí)間問(wèn)題邀桑。

分布式系統(tǒng)中如果沒(méi)有實(shí)際的時(shí)鐘，那么我們能依賴的就只有Happened Before了科乎，即在某些條件下概漱，我們可以確定event A一定在event B之前發(fā)生。這里有一個(gè)非常重要的理念：在分布式系統(tǒng)中喜喂，我們能依賴的只有這種部分事件之間的Happened Before關(guān)系，也就是Partial Ordering竿裂。在分布式系統(tǒng)中有2種情況是可以建立起Happened Before關(guān)系的：

• 同一個(gè)process先后發(fā)生的event A和event B

• 同一個(gè)message從event A發(fā)送玉吁，由event B接收

  
  
  分布式系統(tǒng)的時(shí)空?qǐng)D

Figure 1中由下往上是時(shí)間的流逝，自左往右是不同的空間中的process腻异。Figure 1中的有些event之間是有直接（p1 -> q2）或者間接（p1 -> r3）的happened before關(guān)系的进副；而有些event之間是沒(méi)有的（p3和q3），因此我們無(wú)法確定p3和q3之間的順序，所以我們說(shuō)p3和q3是并發(fā)的影斑。

Happened Before的理論和狹義相對(duì)論中的物理世界中的觀念十分的類(lèi)似给赞，即event的先后是相對(duì)的，在實(shí)際世界中的不同慣性坐標(biāo)系下矫户，2個(gè)event的先后關(guān)系可能發(fā)生變化片迅。不過(guò)Paper中沒(méi)有深入的對(duì)比，我會(huì)在感想部分中深入討論下

2. Logical Clocks

其實(shí)對(duì)Happened Before和Partial Ordering的理解才是最重要和最難的皆辽，有了Partial Ordering的概念柑蛇，我們很容易理解Logical Clocks。即我們指定一個(gè)全局的邏輯的時(shí)鐘規(guī)則C(x)驱闷，以保證

Clock Condition. For any events a, b: if a -> b then C(a) < C(b).

這個(gè)時(shí)鐘的規(guī)則也相對(duì)比較簡(jiǎn)單

IR1. 同一個(gè)process的前后2個(gè)event的時(shí)間+1
IR2. 當(dāng)一個(gè)process收到另外一個(gè)process的message的時(shí)候耻台，將本地時(shí)鐘設(shè)置為本地時(shí)鐘當(dāng)前值和發(fā)送message時(shí)間+1的max值

以上規(guī)則分別體現(xiàn)了2個(gè)Happened Before關(guān)系。

3. Total Ordering & Case Study

既然知道了我們唯一能確定的就是Happened Before關(guān)系空另，但是我們?cè)诮鉀Q現(xiàn)實(shí)問(wèn)題的時(shí)候盆耽，往往會(huì)用到全局序（Total Ordering）。那么我們可以預(yù)定義一個(gè)process之間的順序扼菠，假設(shè)當(dāng)event的邏輯時(shí)間相等時(shí)摄杂，process1的event永遠(yuǎn)先于process2的，那么我們就可以確定一個(gè)全局序娇豫。這里要強(qiáng)調(diào)的是Partial Ordering是唯一的匙姜，而Total Ordering是不唯一的。
本章舉了一個(gè)在沒(méi)有Coordinator的情況下的冯痢，分布式臨界資源算法氮昧。注意這里的分布式臨界資源是指沒(méi)有統(tǒng)一協(xié)調(diào)者，沒(méi)有統(tǒng)一等待隊(duì)列的浦楣，需要多個(gè)process互相協(xié)商的算法袖肥。這個(gè)算法非常重要，因?yàn)檫@是一個(gè)無(wú)中心的分布式算法（2PC是有中心的振劳，才有block問(wèn)題）椎组。幾乎所有的無(wú)中心分布式算法都是從這個(gè)算法演化而來(lái)的。同時(shí)我們可以通過(guò)狀態(tài)機(jī)（State Machine）的思想历恐，將該算法演變成一個(gè)完整的分布式系統(tǒng)寸癌。Lamport在這里提出的State Machine方案是一個(gè)被后人忽視的，但是卻十分重要的貢獻(xiàn)弱贼，甚至在很長(zhǎng)時(shí)間內(nèi)大家都沒(méi)意識(shí)到paper中有這方面的貢獻(xiàn)蒸苇，老爺子后來(lái)的自述中也提到：

This is my most often cited paper. Many computer scientists claim to have read it. But I have rarely encountered anyone who was aware that the paper said anything about state machines. People seem to think that it is about either the causality relation on events in a distributed system, or the distributed mutual exclusion problem. People have insisted that there is nothing about state machines in the paper. I’ve even had to go back and reread it to convince myself that I really did remember what I had written.

篇幅原因，這個(gè)分布式臨界資源算法的細(xì)節(jié)大家參考原文的吮旅，有問(wèn)題可以討論溪烤。

4. Physical Clocks

上面定義的Logical Clocks有一些反常的行為，例如我們定義的Total Ordering是process 1 < process 2的，那么event a(from process 1)和event b(from process 2)的邏輯時(shí)間雖然相等檬嘀，但是在Total Ordering中是C(a) < C(b)槽驶。但是現(xiàn)實(shí)生活中event a和event b可能是人操作產(chǎn)生的，而event b的操作員操作完成后打電話給event a的操作員操作的鸳兽。那么Logical Clocks就顯著違背了事實(shí)掂铐。其主要原因是b happened before a這個(gè)關(guān)系是在非本系統(tǒng)的外部系統(tǒng)中產(chǎn)生的，本系統(tǒng)不掌握這個(gè)情況贸铜，所以導(dǎo)致了反常堡纬。
為避免這種反常，有2中解法：

• 將外部的happened before關(guān)系手動(dòng)的引入到系統(tǒng)內(nèi)（event b產(chǎn)生是強(qiáng)調(diào)依賴 event a）
• 引入實(shí)際物理時(shí)鐘

Paper中基于Logical Clock的整體理論蒿秦，將邏輯時(shí)鐘的產(chǎn)生替換為了物理時(shí)鐘烤镐，并處理了2個(gè)主要時(shí)鐘誤差和其矯正方法：

• 同一個(gè)process的clock在不同時(shí)間的流逝誤差
• 不同process的clock的流逝誤差
  上文中的Logical Clock的規(guī)則變?yōu)橐韵伦冃危?/li>

IR1' . 如果某一時(shí)刻t，process沒(méi)有收到消息棍鳖，那么它的本地時(shí)鐘是可微分的炮叶，并且其微分值>0 (即時(shí)鐘正向流逝)
IR2'. 當(dāng)一個(gè)process收到另外一個(gè)process的message的時(shí)候，將本地時(shí)鐘設(shè)置為略大于本地時(shí)鐘當(dāng)前值和發(fā)送message時(shí)間+最小傳輸時(shí)間的max值

感想

1. 關(guān)于偏序（因果序）和狹義相對(duì)論

從Lamport總結(jié)的分布式系統(tǒng)的時(shí)空觀和狹義相對(duì)論中物理世界的時(shí)空觀有著驚人的相似渡处。

狹義相對(duì)論中關(guān)于因果關(guān)系的一些結(jié)論

1. 在任何慣性坐標(biāo)系中镜悉，有因果關(guān)系的2個(gè)事件的順序都不會(huì)顛倒
2. 如果2個(gè)事件在空間上的距離大到光不可能在2個(gè)事件的空間位置上發(fā)生一次傳播，那么這兩個(gè)事件沒(méi)有因果序（也就說(shuō)這種情況下不同的觀察者可能看到2個(gè)事件不通的先后順序医瘫，這種情況等價(jià)于分布式系統(tǒng)的并發(fā)事件）

• 直觀的理解就是說(shuō)2個(gè)事件發(fā)生的距離大到光不可能發(fā)生一次通信侣肄，那么這兩個(gè)事件沒(méi)有因果關(guān)系

以上理論在所有的洛倫茲變換的慣性坐標(biāo)系中都是成立的，我們可以以一下的方式直觀的理解下：

• 只要event2在發(fā)生的時(shí)候醇份，已經(jīng)看到event1發(fā)生了稼锅，那么他們之間就有因果序
• 如果event2在發(fā)生的時(shí)候，event1發(fā)生的光還沒(méi)有射到event2的地點(diǎn)僚纷，那么他們就沒(méi)有因果序
• 也就是說(shuō)因?yàn)楣鈧鞑サ谋容^慢矩距，那么只要event1和event2發(fā)生的絕對(duì)時(shí)間間隔（假設(shè)存在）小于光在2地傳播的時(shí)間，那么離event1近的就會(huì)看到event1先發(fā)生怖竭，event2后發(fā)生锥债，反之亦然。
• 但是如果event1和event2發(fā)生的絕對(duì)時(shí)間間隔大于光在2地傳播的時(shí)間痊臭，那么在任何地方肯定是先看到event1

分布式系統(tǒng)中的logic clock和狹義相對(duì)論的對(duì)應(yīng)關(guān)系

1. 光是時(shí)時(shí)刻刻在傳播的哮肚，而分布式系統(tǒng)中的消息則不是，所以分布式系統(tǒng)更容易出現(xiàn)并發(fā)問(wèn)題广匙。

• 如果每個(gè)process都時(shí)時(shí)刻刻在向所有其他process發(fā)送消息的話绽左，那么分布式系統(tǒng)就是狹義相對(duì)論的時(shí)空了

2. 沒(méi)有happened before關(guān)系的2個(gè)event，可以認(rèn)為是并發(fā)的艇潭，因?yàn)榫秃拖嘁老鄬?duì)論一樣，event1和event2（假設(shè)在不同的process，如果是在相同的process那就是dx為0蹋凝，一定存在因果關(guān)系）event2在發(fā)生之前鲁纠，看不到event1（沒(méi)有任何直接/間接的從event1所在的process發(fā)出的消息到達(dá)event2所在的process），那么event1和event2沒(méi)有因果關(guān)系鳍寂，他們是并發(fā)的改含。

• paper中定義了一種任意的兩個(gè)process的happened before關(guān)系來(lái)產(chǎn)生一種total order，但是這種total order是不確定的
• paper最后還是借助了物理時(shí)鐘（Wall Clock）來(lái)強(qiáng)化關(guān)系迄汛，但是Wall Clock也需要遵循狹義相對(duì)論捍壤，所以本質(zhì)上也是偏序，只是在伽利略變換中近似于全局序

3. 因此整個(gè)宇宙只有偏序（因果序/partial ordering）沒(méi)有全序(total ordering/invariant total ordering of events)

• 如果要獲得全序鞍爱，那么要保證整個(gè)系統(tǒng)在有限的物理空間范圍內(nèi)（例如地球上）鹃觉，同時(shí)每個(gè)process的2個(gè)event保證有足夠的時(shí)間間隔，以保證整個(gè)系統(tǒng)的物理空間范圍內(nèi)都先看到了前面的event（產(chǎn)生了因果序）睹逃，而這種全序本質(zhì)上也是因果序

2. 關(guān)于Spanner中的True Time和本文的Physical Clocks

Spanner中的True Time和本Paper中最后的Physical Clocks非常的相似盗扇。但是本文中的Physical Clocks是有一些限制的例如時(shí)鐘不能倒退，同時(shí)通過(guò)系統(tǒng)內(nèi)的message進(jìn)行時(shí)鐘修正沉填，這也是在當(dāng)時(shí)的硬件條件下的理想方案疗隶，而True Time通過(guò)系統(tǒng)外的消息進(jìn)行修正（GPS），同時(shí)優(yōu)化了協(xié)議翼闹。

1. True Time引入了物理硬件（原子鐘和GPS）來(lái)限制最大誤差（Paper
   中的微分誤差k和process間誤差e）
2. True Time引入了Commit Wait來(lái)解決沒(méi)有系統(tǒng)內(nèi)消息同步以后斑鼻，帶來(lái)的process間誤差。

同時(shí)根據(jù)狹義相對(duì)論猎荠，因?yàn)槲锢淼臅r(shí)鐘也是偏序的坚弱，只有可能在限制物理范圍，并且保證event間間隔的情況下才有可能變成全局法牲。因此完整的True Time理論嚴(yán)格來(lái)說(shuō)應(yīng)該有這部分的論證史汗。

由此想到的很多經(jīng)典論文中的方案，可能當(dāng)時(shí)來(lái)看是難以實(shí)現(xiàn)的拒垃，但是隨著硬件的發(fā)展停撞，稍加優(yōu)化以后，可能會(huì)帶來(lái)系統(tǒng)性的突破悼瓮。

3. Paper中Logical Clocks和Physical Clocks的本質(zhì)

從本質(zhì)上來(lái)說(shuō)文章的Logical Clocks和Physical Clocks本質(zhì)上是一樣的都是通過(guò)消息來(lái)產(chǎn)生Happened Before的偏序戈毒，再依賴這個(gè)偏序確定整個(gè)系統(tǒng)的因果序/全序。雖然我們從狹義相對(duì)論中知道横堡，“當(dāng)2個(gè)事件只要在光可到達(dá)的時(shí)間差外先后發(fā)生埋市，那么它們就有因果關(guān)系”，但是2個(gè)物理時(shí)鐘并不能因此產(chǎn)生同步命贴，還是需要有外部機(jī)制來(lái)產(chǎn)生同步道宅，例如：NTP食听，GPS∥垡穑可惜的是在1978年 NTP（1988年）和GPS（1989年商用）都還沒(méi)發(fā)用樱报，所以Lamport設(shè)計(jì)了這個(gè)時(shí)鐘同步的雛形算法。
2者的不同是：

• Logical Clocks是通過(guò)系統(tǒng)內(nèi)的消息建立因果序泞当，并且其時(shí)間戳是邏輯的
• Physical Clocks是通過(guò)系統(tǒng)內(nèi)外的消息建立全序（本質(zhì)也是因果序）迹蛤，并且其時(shí)間戳是物理的

說(shuō)到這里必須要提HLC了，HLC本質(zhì)上是Logical Clocks而非Physical Clocks襟士，這個(gè)下篇文章詳細(xì)說(shuō)吧

參考

1. Time, Clocks and the Ordering of Events in a Distributed System
2. https://www.microsoft.com/en-us/research/publication/time-clocks-ordering-events-distributed-system/
3. https://en.wikipedia.org/wiki/Special_relativity
4. Spanner: Google’s Globally Distributed Database
5. Logical physical clocks