前言

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

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

讀過paper的可以直接跳到感想部分。

總結(jié)

本Paper是Leslie Lamport老爺子在1978年的時候?qū)懙?，雖然已經(jīng)是41年前的Paper了，但是Paper挖掘了分布式系統(tǒng)中的時間的本質(zhì)，并結(jié)合狹義相對論進行深入的分析，給人一種醍醐灌頂?shù)母杏X。Paper中提出的"happened before"，Logical Clocks，The Partial Ordering，Replicated State Machine等是目前整個分布式理論的基礎(chǔ)。本Paper對于現(xiàn)代分布式理論的意義不亞于狹義相對論之于現(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的幾項重要貢獻

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

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

1. Happened Before & Partial Ordering

這部分提出了分布式系統(tǒng)中的時間問題。我們生活中感知的事件（Event）發(fā)生的先后是依賴于時鐘的，而分布式系統(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.” 中很難包含一個實際的時鐘（Wall Clock），同時在多個不同process中的時鐘往往不夠精確，因此在分布式系統(tǒng)中必須有一套獨立的算法來解決時間問題。

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

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

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

  
  
  分布式系統(tǒng)的時空圖

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

Happened Before的理論和狹義相對論中的物理世界中的觀念十分的類似，即event的先后是相對的，在實際世界中的不同慣性坐標(biāo)系下，2個event的先后關(guān)系可能發(fā)生變化。不過Paper中沒有深入的對比，我會在感想部分中深入討論下

2. Logical Clocks

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

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

這個時鐘的規(guī)則也相對比較簡單

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

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

3. Total Ordering & Case Study

既然知道了我們唯一能確定的就是Happened Before關(guān)系，但是我們在解決現(xiàn)實問題的時候，往往會用到全局序（Total Ordering）。那么我們可以預(yù)定義一個process之間的順序，假設(shè)當(dāng)event的邏輯時間相等時，process1的event永遠先于process2的，那么我們就可以確定一個全局序。這里要強調(diào)的是Partial Ordering是唯一的，而Total Ordering是不唯一的。
本章舉了一個在沒有Coordinator的情況下的，分布式臨界資源算法。注意這里的分布式臨界資源是指沒有統(tǒng)一協(xié)調(diào)者，沒有統(tǒng)一等待隊列的，需要多個process互相協(xié)商的算法。這個算法非常重要，因為這是一個無中心的分布式算法（2PC是有中心的，才有block問題）。幾乎所有的無中心分布式算法都是從這個算法演化而來的。同時我們可以通過狀態(tài)機（State Machine）的思想，將該算法演變成一個完整的分布式系統(tǒng)。Lamport在這里提出的State Machine方案是一個被后人忽視的，但是卻十分重要的貢獻，甚至在很長時間內(nèi)大家都沒意識到paper中有這方面的貢獻，老爺子后來的自述中也提到：

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.

篇幅原因，這個分布式臨界資源算法的細節(jié)大家參考原文的，有問題可以討論。

4. Physical Clocks

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

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

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

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

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

感想

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

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

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

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

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

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

• 只要event2在發(fā)生的時候，已經(jīng)看到event1發(fā)生了，那么他們之間就有因果序
• 如果event2在發(fā)生的時候，event1發(fā)生的光還沒有射到event2的地點，那么他們就沒有因果序
• 也就是說因為光傳播的比較慢，那么只要event1和event2發(fā)生的絕對時間間隔（假設(shè)存在）小于光在2地傳播的時間，那么離event1近的就會看到event1先發(fā)生，event2后發(fā)生，反之亦然。
• 但是如果event1和event2發(fā)生的絕對時間間隔大于光在2地傳播的時間，那么在任何地方肯定是先看到event1

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

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

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

2. 沒有happened before關(guān)系的2個event，可以認為是并發(fā)的，因為就和相依相對論一樣，event1和event2（假設(shè)在不同的process，如果是在相同的process那就是dx為0，一定存在因果關(guān)系）event2在發(fā)生之前，看不到event1（沒有任何直接/間接的從event1所在的process發(fā)出的消息到達event2所在的process），那么event1和event2沒有因果關(guān)系，他們是并發(fā)的。

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

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

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

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

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

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

同時根據(jù)狹義相對論，因為物理的時鐘也是偏序的，只有可能在限制物理范圍，并且保證event間間隔的情況下才有可能變成全局。因此完整的True Time理論嚴格來說應(yīng)該有這部分的論證。

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

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

從本質(zhì)上來說文章的Logical Clocks和Physical Clocks本質(zhì)上是一樣的都是通過消息來產(chǎn)生Happened Before的偏序，再依賴這個偏序確定整個系統(tǒng)的因果序/全序。雖然我們從狹義相對論中知道，“當(dāng)2個事件只要在光可到達的時間差外先后發(fā)生，那么它們就有因果關(guān)系”，但是2個物理時鐘并不能因此產(chǎn)生同步，還是需要有外部機制來產(chǎn)生同步，例如：NTP，GPS?？上У氖窃?978年 NTP（1988年）和GPS（1989年商用）都還沒發(fā)用，所以Lamport設(shè)計了這個時鐘同步的雛形算法。
2者的不同是：

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

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

參考

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