Time, Clock, and the Ordering of Events in a Distributed System
時間時鐘和分布式系統(tǒng)中事件的順序
背景
當(dāng)消息傳遞的延遲是不能夠被忽視的時候（相較于單機中進程的消息交換的延遲），我們就認為該系統(tǒng)是一個分布式系統(tǒng)。
在一個分布式系統(tǒng)中，有時候不太可能說兩個事件中其中一個發(fā)生在另一個之前。這個“happen before”關(guān)系在事件中因此成了部分事件的順序。
之前定義事件a發(fā)生在事件b之前使用的是時鐘的概念，即物理時間的概念。但是即使這個系統(tǒng)中存在這樣的物理時鐘，但是由于時鐘的精度和精確性問題，還是存在問題。（比如，a和b發(fā)生的時候，其物理時鐘處在統(tǒng)一時刻，此時便不能分辨出兩個事件的發(fā)生先后，精確性的問題在于分布式環(huán)境中存在時鐘同步和跳變問題）
鑒于以上原因此時便不能再依賴于物理時鐘。
邏輯時鐘
我們定義一個 Clock Condition. 對于任意事件a, b:
if a -> b then C<a> < C<b>
可以很明確的發(fā)現(xiàn)，要想滿足Clock Condition，需要滿足以下兩個條件：
- 如果a,b是在同一個進程Pi里的兩個事件，并且a 在 b 之前，那么Ci<a> < Ci<b>
- 如果a是進程Pi發(fā)送出去的消息，而b是Pj接收到消息，那么Ci<a> < Cj<b>
若想保證系統(tǒng)的時鐘滿足Clock Condition，我們需要確保系統(tǒng)的時鐘滿足C1和C2.
C1比較簡單，進程只需要滿足以下的規(guī)則即可：
IR1. 每個進程Pi，在任意兩個成功的事件之間自增自己的時鐘Ci即可。
IR2.
a>. 如果事件a是一個消息發(fā)送事件是由進程Pi發(fā)起的，發(fā)送的消息為m，m中需要包含一個時間戳， Tm = Ci<a>
b>. 當(dāng)Pj收到消息m，Pj設(shè)置自己的時鐘大于或等于當(dāng)前的值并且要大于Tm。
Lamport提出的邏輯時鐘可以用來對分布式系統(tǒng)中的所有事件進行全序排列。這是一個很難得的進步。
當(dāng)在排序的時候遇到時鐘相等的事件的時候，可以按照預(yù)先指定的進程優(yōu)先級順序，打破平局。即優(yōu)先級較高的進程，可以排序在與其邏輯時鐘相同的事件前面。這樣就能全部排序了。
使用這種全序關(guān)系實現(xiàn)的一個分布式鎖?？紤]一個系統(tǒng)由固定的進程數(shù)量組成，共享一個資源，每次只有一個進程可以使用該資源。所以進程必須同步他們自己狀態(tài)，來保證沒有沖突。我們希望存在一個算法，每次只給某一個進程賦予訪問資源的權(quán)限。需要滿足以下3個條件：
- 每個獲取到資源的進程要授予其它進程訪問資源權(quán)限時，必須先自己釋放對資源的授權(quán)。
- 不同的授權(quán)請求，必須按照它們發(fā)起的順序給于授權(quán)。
- 如果每個授權(quán)資源的進程最終釋放了資源，那么它們最終都授權(quán)過。
我們假設(shè)資源最開始授權(quán)給了某一個進程。
必須意識到，通過一個中央的授權(quán)進程按照它收到的授權(quán)順序進行授權(quán)是不夠的。因為網(wǎng)絡(luò)包可能并不是按照請求發(fā)起的順序到達中央授權(quán)進程的。為了解決這個問題，我們實現(xiàn)一個系統(tǒng)的時鐘，滿足IR1和IR2。并且用它們來給所有的事件定義一個全局的順序=>。這樣就給所有的申請資源請求和釋放資源請求都可以排序了。那么問題就在于只要確保了每個進程學(xué)習(xí)到了所有其它進程的請求了。
我們假設(shè)任意兩個進程Pi和Pj，消息從Pi到Pj是按照發(fā)送的順序到達的。更進一步，我們假設(shè)每個消息最終是送達的。我們同樣假設(shè)進程可以直接給其它所有進程發(fā)送消息。
每個進程維護自己的一個發(fā)送隊列，其不能被其它進程看到。并且假設(shè)請求隊列里面初始化時存在一條消息，T0:P0請求，意味著，一開始資源是授權(quán)給了P0進程的。并且T0是小于所有進程的時鐘的。我們定義一下5條規(guī)則：
- 要獲取資源，進程Pi需要發(fā)送一個 Tm:Pi的請求到其它進程，發(fā)送之后將這條消息放置到自己的請求隊列中。Tm是這條消息的是時間戳。
- 當(dāng)進程Pj收到 Tm:Pi請求資源的消息后，它將其放置到自己的請求隊列中，并且回復(fù)一個帶時間戳的ACK消息給Pi。
- 當(dāng)需要釋放資源的時候，進程Pi從自己的隊列中移除任何的 Tm:Pi請求，并且發(fā)送一個帶時間戳的Pi釋放資源請求給其它進程。
- 當(dāng)Pj收到一個Pi釋放資源的消息之后，它從自己的請求隊列中移除任何的 Tm:Pi 請求。
- 進程Pi最終可以授權(quán)資源取決于如下兩個條件滿足：
a>. Tm:Pi 排在所有請求資源隊列的隊頭（通過=>規(guī)則排序）
b>. Pi已經(jīng)收到所有其它進程的大于Tm時間戳的消息。
（筆者：這就保證了其它進程已經(jīng)學(xué)習(xí)到了Pi進程Tm:Pi的請求資源，不會去爭搶）
這是一個分布式的算法，每個進程都是獨立地運行這些規(guī)則，沒有一個中央的節(jié)點或者存儲來做同步。
這個算法的實現(xiàn)可以用來實現(xiàn)任何分布式多進程系統(tǒng)的期望的同步。
這個同步算法依托于一個狀態(tài)機，由一個可能的命令集合 C，和一個可能得狀態(tài)集合 S。
以及一個函數(shù)：e: C X S -> S?？梢缘玫揭粋€關(guān)系即：
e(C,S) = S'。這個關(guān)系意味著，在機器處于S狀態(tài)的時候，可以執(zhí)行命令C，進而使得狀態(tài)機進入 S' 狀態(tài)。
在我們的例子中，C 即是由所有的 Pi 的請求資源命令和釋放資源命令組成。
狀態(tài)由等待請求命令的隊列組成，其中隊列頭部的請求是當(dāng)前授予的請求。
執(zhí)行請求命令將請求添加到隊列的尾部（筆者：這里的尾部個人認為，應(yīng)該是放在排序后合適的位置），執(zhí)行釋放命令將命令從隊列中刪除。
每個進程獨立地模擬狀態(tài)機的執(zhí)行。同步是可以滿足的。因為所有的進程對收到的請求中的時間戳都通過 => 關(guān)系進行排序。所以每個進程都會執(zhí)行相同的順序的命令。
一個進程可以執(zhí)行時間戳為T的命令，當(dāng)他已經(jīng)學(xué)習(xí)到了所有的其它進程的小于等于T的命令。
這個方法允許在所有的分布式環(huán)境下實現(xiàn)任意一種形式的多進程間的同步。不過缺點也是很明顯的，即，一個進程必須知道所有其它進程發(fā)起的命令。也就意味著每個參與者進程必須是活躍的。任何單個進程出問題，都會導(dǎo)致整個狀態(tài)機無法向前推進。從而導(dǎo)致整個系統(tǒng)停滯。
（筆者：這是分布式中Liveness的保證，不在此篇的討論范圍內(nèi)）。
系統(tǒng)要想理解（意識到）某個進程出現(xiàn)問題，必須引入物理時間的概念，因為只能通過長時間收不到請求來發(fā)現(xiàn)某個進程出現(xiàn)了failure。或者使用者從外部告訴系統(tǒng)。
（筆者：有了這種全序關(guān)系的之后，我們就可以實現(xiàn)我們自己的分布式復(fù)制狀態(tài)機，即在每個邏輯時鐘上達成分布式共識。新的較大的邏輯時鐘ID，將基于小于其的ID對應(yīng)的所有共識的狀態(tài)基礎(chǔ)上進行狀態(tài)的疊加。（State Machine Replication））
異常行為（以下為簡略總結(jié)）：
當(dāng)僅僅使用邏輯時鐘時，會出現(xiàn)一些異常行為。當(dāng)外部系統(tǒng)（現(xiàn)實世界，即物理時間）干預(yù)到僅僅使用邏輯時鐘的系統(tǒng)時，會出現(xiàn)一些異常現(xiàn)象，舉例（注：這里的舉例是筆者自己舉的例子）：
進程Pi，對 變量 X的賦值序列如下：
C1: X = 1;
C2: X = 2;
C3: X = 3;
此時，外部系統(tǒng)看到了 X = 3，告知進程Pj，去查看一下X的值，對于外部系統(tǒng)來說，此時無論哪個進程去讀取X的值，都應(yīng)該得到 X = 3 這個事實。
Pj的邏輯時鐘目前還是1，系統(tǒng)內(nèi)部沒有其它進程和Pj有過通信。所以其只能按照自己當(dāng)前的邏輯時鐘去讀取X的值。
C1 只能讀取到 X = 1 的狀態(tài)。
此時對于外部系統(tǒng)（比如用戶）而言，不能理解這個現(xiàn)象了。明明外部系統(tǒng)已經(jīng)看到了Pi將 X 的值更新成 3。但 Pj 進程讀取到的還是1。
這里L(fēng)amport使用狹義相對論的概念來進行解釋了。（以下是筆者理解的）
對于系統(tǒng)內(nèi)部的進程而言，Pj讀取到 X 的值是1是再合理不過的，之所以系統(tǒng)外部的用戶感到疑惑，是因為，外部系統(tǒng)所在的時空是物理世界，物理時空，可以想象他有一個隱形的單調(diào)遞增的全局時鐘。但是這個外部世界的時鐘，系統(tǒng)內(nèi)部是無法感知的。所以這個問題，僅憑系統(tǒng)內(nèi)部的機制是無法解決的。既然引入了外部系統(tǒng)，則是視角變換了，系統(tǒng)內(nèi)部必須引入外部世界的因素，來進行度量內(nèi)部系統(tǒng)的行為。
在系統(tǒng)內(nèi)部，Pi對X的修改之所以對于Pj無法感知，原因就是Pi和Pj之間沒有發(fā)生任何的消息通信，即根據(jù)狹義相對論描述，Pj如果想要感知到Pi的變化，Pi必須傳遞點信息過去，并且，Pj發(fā)生讀取的時刻，要處在Pi發(fā)送消息的未來光錐之內(nèi)，Pj才能感知到Pi做的一些變化。如果Pj在消息還沒有傳遞到它的時候已經(jīng)發(fā)生了讀取，則也是無效的。
所以，要解決上述問題，需要引入觀察者系統(tǒng)的度量因素，重新對于事件進行排序。才能達到觀察者想要的目的和效果。
因此需要引入現(xiàn)實世界的物理時間。
物理時間的引入，就需要解決時鐘偏移和漂移的問題。漂移是單機的行為，可以通過硬件設(shè)計控制其只向大漂移。
偏移是多臺機器之間的時鐘不同步問題，要想將所有的事件按照現(xiàn)實世界的物理時間排序，就必須要做到系統(tǒng)中的時鐘必須是強制同步的，只允許一個極小的誤差 E，即同一時刻，不同進程的時鐘必須將誤差縮小在E之內(nèi)。在引申一下也就是說，如果兩個相關(guān)的事件A,B分別發(fā)生在不同的機器的進程Pi和Pj中，即使Pi向Pj傳遞消息的速度就是光速，也要保證兩邊的時鐘不能出現(xiàn)相同的值。
上述的要求，對于分布式時鐘的同步提出了相當(dāng)嚴格的要求。Google的Spanner就根據(jù)Lamport的論文中的同步算法實現(xiàn)了全球范圍內(nèi)的物理時間同步。保證了線性一致性。
代價也是非常大的，需要銫原子鐘級別的晶振誤差。
Lamport的算法，對時鐘同步的最小延時做出了明確的計算和規(guī)定。對于網(wǎng)絡(luò)延遲的誤差范圍也給出了規(guī)定。對于時鐘的晶振誤差也給出了范圍。
IR1和IR2的定義：
盡管規(guī)則是根據(jù)物理時間參數(shù)正式指定的，但是進程只需要知道它自己的時鐘讀數(shù)以及收到的消息的時間戳。為了數(shù)學(xué)上的方便，我們假設(shè)每個事件都在物理時間的精確時刻發(fā)生，這樣相同進程中的不同事件在不同的時間發(fā)生。這些規(guī)則就是規(guī)則 IR1 和 IR2 的特化，因此我們的時鐘系統(tǒng)滿足時鐘條件。真實事件具有有限的持續(xù)時間這個事實不會給算法的實現(xiàn)帶來任何困難。在實現(xiàn)過程中，唯一真正關(guān)心的是確保離散的時鐘“嘀嗒”足夠頻繁，以便保證滿足 C1。
Um -> 最小延遲
U -> 實際最小延遲
E -> 不同節(jié)點間的時鐘偏移的最大值
E' -> 表示不可預(yù)測延遲
T -> 表示每T秒發(fā)送一個消息
d -> 表示弧的長度
k -> 表示晶振的頻率
最終的定理的結(jié)果即：
E 約等于 d(2kT + E') 其含義大致理解如下：
括號展開：E 約等于 2kTd + E'd
不同節(jié)點間能容忍的時鐘最大偏移 約等于
每T秒鐘一次消息所產(chǎn)生的時鐘的誤差 在 長度d的弧上的積 的兩倍 與
不可預(yù)測延遲 在 長度d上的積 的 和。
（具體含義還是不太清楚，不過暫時也不打緊）
意味著，只要兩個時鐘在同一時刻的漂移差值 小于 上述結(jié)果，幾滿足了物理時鐘的誤差內(nèi)同步，即可滿足能夠區(qū)分出相關(guān)因果事件在物理事件上的單調(diào)性。
結(jié)論
我們已經(jīng)看到“先發(fā)生”這個概念定義了分布式多進程系統(tǒng)中事件的不變偏序關(guān)系。我們描述了一種用來將偏序擴展為有些隨意的全序的算法，并展示了怎樣使用全序來解決簡單的同步問題。未來的論文將展示如果擴展這種方法來解決任意的同步問題。
該算法定義的全序有些隨意。如果它與系統(tǒng)用戶所感知的順序不一致，則可能會產(chǎn)生異常行為。這可以通過正確使用同步的物理時鐘來避免。我們的定義表明了時鐘可以同步的誤差程度。
在分布式系統(tǒng)中，重要的是意識到事件發(fā)生的順序只是偏序關(guān)系。我們認為這種想法對理解任何多進程系統(tǒng)很有幫助。它可以幫助人們獨立地理解多進程的基本問題以及用來解決它們的機制。
The End;
