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