事件和時間：Time, Clocks, and the Ordering of Events in a Distributed System 讀後感

01-29

前言

Lamport老爺子在這篇著名的論文中探討了分散式系統中事件和時間的關係，並且以數學家的最敏銳的嗅覺抓住了分散式系統中的本質問題，同時引入邏輯時鐘，為以後的分散式系統設計點亮了指路明燈。

事件

事件是驅動萬物演化的根本動力。事件包含其內在的一系列行為以及這些行為而產生的影響，而這些影響又可能觸發下一個事件。在這綿延不斷的事件鏈條中，周圍的世界處於一刻不停的變化之中。一件極其微小的事件可能產生巨大的連鎖反應，蝴蝶效應說的便是這個道理。

nnnn

時間

時間是什麼，沒幾個人真正理解。不妨將時間和事件聯繫起來，我們便會產生直觀而具體的感受。我們是無法感受時間的，也無法測量時間，我們感知的時間其實是事件的流逝，比如看到太陽升起我們知道是早晨，而落日則意味著傍晚。

時間有眾多的計量方法：比如古人的日晷，再到現在的原子時鐘。所有計時方法的本質在於記事。因此，時間和事件本就合二為一。

nn分散式系統nn

在我看來，這個世界就是一個分散式系統。區別的只是系統的規模。

搞計算機的眼裡幾台伺服器組成的系統就是分散式系統，生物學家眼裡某個種群構成了一個分散式系統，而在外眼裡，整個世界是一個分散式系統。

分散式系統最核心的問題是什麼？信息交互！為什麼在上面提到的不同的學者關注不同的分散式系統呢？這是因為這些系統之間難以存在信息流通。例如，目前階段一台計算機很難和一頭大象交流。而計算機之間則很容易信息交互。

信息又是什麼？信息是載體，它是事件綿延不斷傳播的源動力。沒有了信息，事件便成為孤單的粒子。因此，可以毫不誇張的說，信息是發展的源動力。

分散式系統的難點在於分散式。分散式帶來的頭疼問題是信息交互的延遲、丟失、亂序等一系列問題。受限於光速限制，任何信息的傳播都需要一定的時間，哪怕再短。

而信息交互的延遲、丟失、亂序等問題則進一步體現在事件的影響上。信息的延遲可能導致事件發生的延遲，信息的丟失導致事件根本不會被處罰、信息的亂序則可能導致事件錯亂。而這些看似偶然事件錯亂則可能會給大千世界的演化帶來極其深刻的影響。

nnnn

事件序列

其實文章的核心在於討論事件序列。事件序列指的是特定環境中的事件發生的先後順序。時間只不過是事件序列的一種定義方法。即使是用時間來定義，也存在物理時間、邏輯時間等等方法。

一個分散式系統由眾多獨立的個體組成，稱之為Process，每個個體的事件來源有兩類：

內部事件：此類事件由個體內部產生，可以認為與其他個體不產生關聯；
外部事件：此類事件由其他個體刺激本個體產生，這種刺激的表現形式是消息。

事件序列有兩種：偏序事件序列和全序事件序列。

偏序

所謂的偏序指的是只能為系統中的部分事件定義先後順序。這裡的部分其實是有因果關係的事件。

例如，發生在個體PA的一個事件E1，該事件的影響是產生了消息M，M傳播至個體B，進而導致事件E2的發生，即說明E1->E2：因為E1而導致了E2的產生。而對於兩個相互獨立的事件，我們無法從原理上判斷孰先孰後。

偏序的嚴格定義，偏序以符號->代替：

在同一個Process內部，如果事件a早於事件b發生，稱為a->b；

如果a和b是兩個不同Process的事件，且b是a發送的消息的接收者，同樣 a->b；

如果a->b，b->c，那麼a->c。

這個定義很容易理解。

Lamport在論文中提出了一種利用邏輯時間設計的一種偏序系統方法：

每個Process存在獨立的事件序列發生器，每次產生新的事件，該序列發生器自增1，並將結果賦予該事件；

如果Process的事件E需要向其他Process發送消息M，那麼在M中攜帶E的序列號；

如果Process收到外部消息M，獲取M中攜帶的序列號，與自身的事件序列發生器取最大值，然後自增1，賦給由於M而觸發的新的外部事件。

根據上面的定義，我們可以得到如下結論：

Process內部的事件均可以比較先後順序；

Process之間的因果事件可以確定先後順序，而Process之間的獨立事件則無法比較。

nnnn

例如：

n上圖中的p1->r4成立，因為有：p1->q2，q2->q3，q3->q4，q4->r3，r3->r4。

n而p3->q3則不成立。

真實世界其實是一個偏序系統，記住，物理時間是不準確的。

全序

全序是指所有的事件都可以區分先後順序。無論是真實或是虛擬世界，這都是受歡迎的。因為，所有的事件都有了一個統一的評判標準，我們一直歡迎統一而拒絕分裂。

在偏序的基礎上，Lamport定義了一種全序方案，在偏序的基礎上有所增強：

每個事件表示為一個三元組：<E, C, P>
n

其中：

E：代表事件；
C：代表事件所發生的Process賦予該事件的序列號(邏輯時間)；
P：代表事件所發生的Process的編號

有了該三元組後，定義事件先後的順序就變成了：

如果C(i, a) < C(j, b)
或者
n 如果C(i, a) = C(j, b)並且P(i) < P(j)

n

通過事件序解決特定問題

做著費盡心思定義了偏序和全序，接下來就看它如何幫助解決實際問題。例如，有這樣一個共享資源分配問題：

多個Process共享一個集中資源R，每個Process想使用R時必須申請，經過全部人同意後才可以使用，且使用完成後必須要釋放R以供他人使用。且需要滿足先申請先訪問原則，還不能存在死鎖的問題。
n

很容易想到的是使用協調者的解決方法：

存在一個至高無上的協調者管理資源分配；

協調者根據收到請求的先後順序分配資源的使用順序；

這個方案看起來一切正常，但是可能存在一個漏洞，假如：

Process 1向協調者發起資源分配請求R1；

Process 1向Process2發消息M；

M觸發Process 2產生事件，該事件也向協調者發起資源分配請求R2；

R2先於R1到達協調者

於是就不滿足上面的先申請先訪問的原則了。

Lamport提出的方案：

去掉協調者，改用分散式協調方案；

每個Process均有一個隊列維護資源申請的消息，成為RequestQueue

P申請資源時，向其他Process廣播該資源申請消息，該消息是一個三元組<T, P, Action>；

P收到其他Process的資源申請消息時，將該消息放置於RequestQueue的尾部，並給申請者回復ACK消息；

nnnn

而Pi判斷某個消息(其實代表了一個事件，因為一般是事件申請資源訪問，而消息只不過是代替事件去獲得訪問許可權)能否獲得資源的訪問許可權的條件：

該消息獲得了所有節點的ACK；

在本地的消息隊列中沒有比該消息更早的消息。

我們仔細品味下這兩個條件：

獲得所有節點的ACK這個比較容易理解，只有大家都同意了才可以訪問；

沒有比該消息更早的消息則表示該消息是最早的申請者，注意，本地的消息隊列中不僅有自己發出的資源申請訪問的請求消息，還存有其他節點的資源申請訪問請求；

如何判斷兩個消息先後順序就採用了我們上面的全序定義方案，先判斷T，相同時再判斷P。

需要注意的是，本地的Request Queue中保存的請求消息可能會亂序，並非說隊列頭部是就是就舊的，隊列尾部的就是最新的。因為多個節點之間存在消息傳遞上的延遲，先發出的請求有可能會後到達。因此，在判斷時需要遍歷隊列上的所有消息。

物理時鐘

論文的這部分未涉獵，因為涉及到很複雜的數學證明。

nnnn

總結

如果將這篇論文當作純技術論文來看，那就大錯特錯了，論文的背後其實包含了極其深刻的數學和哲學含義，作者看似在說分散式系統，其實可以將其推廣到整個世界乃至宇宙。至少，老爺子的這篇文章觸發了我重新審視時間和事件這兩個概念，特整理出來，與大家分享，希望能互相交流。