Lamport時間戳論文筆記

2021 年 10 月 14 日
筆記
分散式系統

本文主要參考文獻^[1]完成。

聲明：本人僅在部落格園發表了本文章，筆名LightningStar，其他網站均為轉載。

筆記

私以為，論文中作者的核心工作是為分散式系統建立了一種數學模型，並基於這種數學模型提出了相應的分散式演算法。

論文依序論述了偏序關係和全序關係模型在分散式系統中的應用。作者通過一系列規則建立的全序關係模型系統地描述了如何在分散式系統中確定執行操作順序的方法，並通過這些規則提出了一種分散式的演算法。最後作者論述了系統外事件會導致分散式系統內的事件的發生會導致依據邏輯時鐘排序的結果違反因果律，因此提出了物理時鐘的概念。

在分析論文之前，我們首先要明晰作者為什麼要建立偏序關係和全序關係。作者的目標是提出一種分散式演算法，而其中的核心問題就是一致性問題。為了解決一致性問題，就必須明確分散式系統中各個進程中的各個事件發生的先後關係和並發關係，並為這些事件建立良好的順序。離散數學中的偏序關係和全序關係恰好就是一種排序模型。關於偏序關係和全序關係進一步的討論將在後文思考章節展開。

到目前為止，我們應當明確，論文的核心目標是對分散式系統中發生的所有事件進行排序，獲得一個確定的事件序列，這樣我們才能夠獲得系統之間一致性的保障。

偏序關係

偏序關係模型可以明確一個進程內部事件發生的先後關係以及具有資訊傳遞時兩個進程中的事件的先後關係（如A進程發送一個消息給B進程則A進程發消息以及發消息之前的事件一定先於B進程接收消息以及接收消息之後的事件）。作者定義了這麼一種二元關係→，→表示「happened before」，定義如下：

如果事件a、b在一個進程中，如果a發生在b之前則a→b
如果a是發送一條消息的時間，b是接收這條消息的事件，那麼a→b
如果a→b和b→c成立，那麼a→c成立。如果兩個事件a和b既不滿足a→b也不滿足b→a則認為兩個事件是並發的。
a→a是不成立的，即不滿足自反性

那麼如何來將這種偏序關係應用到系統中呢？最好的方法就是引入一個全局時鐘。而物理時鐘本身是有精確度等的問題，作者引入了一個邏輯時鐘。通過對系統中各個進程中的事件打上時間戳，就可以根據事件發生的先後順序進行排序。

顯然，這種排序是滿足『happened before』的定義的。下面我們看，為什麼說這種排序是偏序的。這是因為當兩個事件具有相同的時間戳的時候，這兩個事件就是不可比的，也即無法進行排序。而全序關係要求的是所有元素都是可比的，這種全局排序也是我們希望得到的。

偏序關係模型無法描述兩個進程之間的並發事件的順序關係，也就是說，無法對所有的進程的所有的事件按照某個順序進行排序。因此需要將偏序關係拓展到全序關係。

全序關係

在偏序關係的模型中，作者避開了對物理時鐘的描述，引入了邏輯時鐘。在引入了邏輯時鐘之後，我們就可以給每個事件都打上一個時間戳，通過這個時間戳我們就可以將happened before關係拓展到所有進程的所有事件。即，只需要在前文的偏序關係的基礎上，對無法描述happened before關係的並發事件根據邏輯時鐘的時間戳進行排序即可（當時間戳仍然相同時，我們需要進程的偏序關係做判斷）。這樣我們就得到了一個所有事件的排序。

全序關係定義如下：
定義二元關係=>:

如果事件a、b在一個進程中，如果a發生在b之前則a→b
如果a是發送一條消息的時間，b是接收這條消息的事件，那麼a→b
a→a是不成立的，即不滿足自反性
對於兩個進程中的事件a和b如果具有相同的事件戳，那麼通過全局進程ID進行判斷，如果\(C_i(a) > C_j(b)\)，則a=>b

物理時鐘

但是，邏輯時鐘會有一個難以解決的問題，這種問題導致無法正確建立全序關係。即：當有外部因素介入時，會使得兩個進程之間的事件在事實上建立了先後關係，如a在事實上先發生，b在事實上後發生，但是由於資訊傳遞等的原因，會認為b比a先發生。這就需要引入物理時鐘。使用物理時鐘替代邏輯時鐘。

但是物理時鐘有兩個問題，一是物理時鐘的滴答速率不是恆定的，二是物理時鐘需要進行同步校準。

物理時鐘變化率

如果將時鐘Ci作為一個真實的物理時鐘，那麼它必須以一個近似正確的速率來運行，即：

dCitdt-1<k

物理時鐘的變化率必須要儘可能保持恆定。

物理時鐘校準

隨著時間的流逝，物理時鐘會逐漸與真實時間產生偏差。因此每次進程間進行通訊時都要進行校準。且這種校準只能向前校準，不能向後校準。

當進程B收到進程A的消息之後，進程B就會對當前系統時間進行校正。校準後的時間是max(B進程當前時間，收到消息的時間戳+資訊傳輸時間)。

拓展

偏序關係和全序關係

偏序關係

給定集合S，\(\le\)是S上的二元關係，若滿足：

自反性： \(\forall a \in S, a \le a\)
反對稱性： \(\forall a,b \in S, a \le b 且 b \le a, 則 a = b\)
傳遞性： \(\forall a,b,c \in S, a \le b 且 b \le c, 則 a \le c\)
則稱\(\le\)是S上的偏序關係。
值得注意的是，不要求集合中的任何一對元素之間具有可比較性。

全序關係

給定集合S，\(\le\)是S上的二元關係，若滿足：

自反性： \(\forall a \in S, a \le a\)
反對稱性： \(\forall a,b \in S, a \le b 且 b \le a, 則 a = b\)
完全性： \(\forall a,b \in S, a \le b 或 b \le a\)
則稱\(\le\)是S上的全序關係。
值得注意的是，全序關係要求集合中的任何一對元素之間具有可比較性，這是與偏序關係最大的不同。

拓展閱讀

參考文獻

LAMPORT L. Time, clocks, and the ordering of events in a distributed system[J]. Communications of the ACM, 1978, 21(7): 558–565. DOI:10.1145/359545.359563. ↩︎