技術分享：Lamport邏輯時鐘

前言

《Time, Clocks, and the Ordering of Events in a Distributed System》是Lamport老哥的論文，這篇論文在1978年7月發表在《Communication of ACM》，於2000年獲得了首屆PODC最具影響力論文獎，於2007年獲得了「ACM SIGOPS Hall of Fame Award」。這篇論文被多次進行引用，裡面提出了分散式系統中的多個關鍵概念，例如：事件先後的happen-before，定義關聯事件順序的偏序關係，定義所有事件順序的全序關係，邏輯時鐘，物理時間的同步，分散式互斥演算法，state machine等等。

本文中我們只涉及邏輯時鐘相關部分。

狹義相對論

說出來你可能不信，計算機領域的論文里會出現相對論，但是實際上據說作者就是從物理學中獲得的靈感。在狹義相對論中，認為隨著參考系的變化，觀測到的事件發生順序有可能發生變化。比如下圖中，有一輛運動的車輛，t=0時，車輛的中心向兩邊發射一束光線。在車上的人看來，光速到底兩端的事件是同時的，在車下的人看來，光先到底車尾，後到達車頭。

但是如果事件之間發生了關聯，即兩個事件有因果關係，那麼因果關係會得到保留。

更多相關內容，請參考相對論相關文章。

在分散式的系統當中，很難取得精確的物理時間，作者提出了邏輯時鐘來判斷事件的因果關係，來決定事件的先後順序。

happen before偏序關係

首先作者定義了happen before的偏序關係。定義happen before關係-滿足如下條件：

事件a和b在同一個進程中發生，a在b之前發生，那麼a-b

事件a是發送信息，事件b是接收該信息，那麼a-b

a-b並且b-c，那麼a-c如果即不存在a-b，也不存在b-a，那麼a和b是並發的。

作者用上面這個圖片展示了時序關係，豎直方向代表時間，從下向上增長，圓點代表事件，波浪線代表發送消息。可以看出p1-r4，但是p3和q3是並發的。

邏輯時鐘

定義Ci作為進程Pi的時鐘，Ci(a)用來給事件a產生一個數字，代表事件的時間。

定義C作為系統的時鐘，如果事件b屬於進程Pi，那麼C(b)=Ci(b)

系統內時鐘條件如下：如果a-b,那麼C(a) C(b)。

注意反之則不然，因為那樣會推導出對於並發的兩個事件a和b，存在C(a)=C(b)。上圖中p2和p3都和q3並發，就意味著C(p2)=C(p3)，這顯然不合理。

從-的定義可以推出如下結論：

事件a和b在同一個進程Pi中發生，a在b之前發生，那麼Ci(a) Ci(b)

事件a是進程Pi發送信息，事件b是進程Pj接收該信息，那麼Ci(a) Cj(b)為了實現邏輯時鐘，假設每個進程i有個變數Ci，用來產生事件的時間。Ci按如下規則變化：

每個進程i在節點內事件發生時將Ci遞增

假設事件a是進程i發送消息m的事件，m需要攜帶時間戳t=Ci(a);進程j接收到m之後，將Cj設置為比t大並且不小於Cj當前值的值作為一個實現，我們設置Ci的初始值為0，並且：

每個進程i在節點內事件發生時將Ci加1

假設事件a是進程i發送消息m的事件，m需要攜帶時間戳t=Ci(a);進程j接收到m之後，將Cj設置為max(t,Cj) 1全序關係

有了邏輯時鐘，我們可以定義所有事件的全序關係了。注意，因為存在兩個事件的邏輯時鐘一致的情況，所以這裡在先任意的選擇一個進程全序關係-，例如我們可以將進程編號的大小關係作為-。

進程i中的事件a和進程j中的事件b的全序關係=定義為滿足如下任意條件時，a=b：

Ci(a) Cj(b)

Ci(a) = Cj(b) 並且 Pi-Pj值得注意的是，這個全序關係不是唯一的，和-的選擇有很大的關係。

後記

在論文的後面，作者還介紹了用事件全序關係和state machine實現的分散式互斥演算法和時鐘同步演算法，有興趣的讀者可以自行參閱。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！