Lamport Logical Clock 学习
1，導論
①如何在分布式環境下定義系統中所有事件的發生順序？②分布式環境下多個進程競爭資源時如何互斥？③什么是偏序，偏序的作用是什么，有什么不足？④什么是全序，全序的作用是什么，有什么不足？⑤為什么需要物理時鐘，物理時鐘如何同步？下面來進行介紹。
?
2，偏序的定義、發生在先(happened before)關系
考慮單一的進程A，在某時刻發生了事件E1，經過一段時間后，發生事件E2，可以說：E1發生在E2前面。考慮多個進程，進程A向進程B發送消息，進程A發送消息時記為事件E1，進程B接收到進程A發送的消息記為E2，可以說：E1發生在E2前面。以上兩個例子表明了E1與E2是一種偏序的關系。之所以說明這兩個例子所代表的關系是偏序的，是因為：當需要判斷下圖中的 a 和 e 這兩個事件誰先誰后時，在偏序關系下是無法判斷的。
偏序的定義：（1）若a，b 是同一進程中的兩個事件，且 a 發生在 b 之前，則 a ---> b? （---> 符號 表示 發生在先 關系， !---> 符號 表示 非發生在先 關系）
（2）若 a 是 "一個進程發送消息 "事件，b 是一個進程接收消息事件，則 a ---> b
(3)若 a !--->b and b!---> a ，則稱 a、b是并發的。如上圖中 事件a 與 事件e 就是并發的。
發生在先關系即偏序的代名詞。
?
3，全序
在 2 中，由于偏序不能表示 圖中事件a 和 事件e 的先后關系，而在分布式系統中對所有的事件排序又是必須的，因此就需要另一種方法來定義所有事件的順序，即用Lamport 邏輯時鐘來定義分布式系統中所有事件的全序。
“引用自網絡” Logical Clock解決的問題是找到一種方法，給分布式系統中所有時間定一個序， 這個序能夠正確地排列出具有因果關系的事件（注意，是不能保證并發事件的真實順序的） ，使得分布式系統在邏輯上不會發生因果倒置的錯誤。Lamport 邏輯時鐘如下：
首先定義一個Clock Condition:如果 a ---> b ，則 C(a) < C(b)(C(a)可以理解成事件a的"發生時刻")。再給出兩個條件C1和C2，C1定義：若 a，b是同一進程i中的兩個事件且 a---> b，則 Ci(a)<Ci(b)
C2定義：若事件a代表發送消息的進程i 發送消息，事件b代表接收進程j接收該消息，則Ci(a) < Cj(b)。顯然，當條件C1與C2成立時，Clock Condition是成立的。
在C1 和 C2 的基礎上，再定義兩個處理操作：IR1 和 IR2 (參考論文中的描述)。IR1、IR2 的本質就是，在同一進程中，a 在 b 之前發生 ，則需要設置 b 的時間戳大于 a的時間戳；在不同進程之間發送消息時，設置接收消息的事件的時間戳要 大于 發送消息這一事件的時間戳。
全序的定義：
各個進程間發生的事件的全序定義，可采用不同的方式。即論文中提到的 arbitrary total ordering.
理解如下：比如，可以把各個進程之間標序號。如1，2，3，4……當進程之間有并發的事件時，規定序號小的進程相應的事件 發生得早。比如上圖：設進程P的序號為1，進程Q的序號為2，對于事件e和事件a而言，就認為 事件e “早于” 事件a 發生。
這樣，由IR1 和 IR2 這兩個操作，再加上 將各進程標序號這種方式?就可以對所有的事件定義一個全序了，這樣就解決了在分布式系統中如何對所有事件排序這一問題。上圖的一個全序如下：
(1:1,e)---(1:2,f)---(2:1,a)---(2,2,b)??? 格式解釋：(進程序號：事件順序號，事件名稱)
在這里出現了一個小小的問題：(1:2,f)---(2:1,a)？？？----可能是向量時鐘需要解決的吧？？？
?
4，分布式環境下，多個進程之間競爭資源如何互斥？
現有一臨界資源，對它的訪問要求如下：
?占有資源的進程，在它將該資源授權其其他資源時，必須先釋放該資源
?對資源的授權必須按照 提出資源請求的順序 進行。即，若進程A先于進程B申請資源(有全序關系的保證，當然就知道請求的先后順序了)，那么在分配資源時，應該將資源先分配給A用。
?對任何已獲得資源的進程，最終會釋放資源；也即，任何進程發生的 申請資源的請求最終會被響應。換句話說，占有資源的進程最終會使用完該資源并釋放（不會死鎖），這樣就保證了任何資源請求最終會被響應。
如何解決該問題呢？
Lamport 大師提出了一個算法如下：
?若要請求資源，進程Pi需要發送一個格式為 Tm:pi 的請求消息給系統中的其他所有進程，并將該消息放入自己的請求隊列中。（Tm表示消息的時間戳）
?當其他進程如Pj收到 Tm:pi請求后，將它放到自己的請求隊列中，并發送一個帶有時間戳的確認給pi。
?釋放資源時，pi從自己的消息隊列中刪除所有的?Tm:pi請求，并向其他所有的進程發送帶有時間戳的 pi資源釋放消息。
?當其他進程，如pj收到pi的資源釋放消息時，pj從自己的消息隊列中刪除所有的?Tm:pi請求消息。
?若同時滿足如下兩個條件，則將資源分配給進程pi：
a)按照 全序 關系 排序后，?Tm:pi請求?排在它的請求隊列的最前面---即，在進程pi中，?Tm:pi資源請求消息是最先 發生的。
b)pi 收到了所有其他進程發給它的時間戳大于Tm的消息
根據算法的?????能夠證明???是成立的。
部分證明的理解如下：
?證明?的成立：反證法。
假設?不成立，則意味著在資源分配給某進程后，假設該進程為Pm，還有其他進程未釋放該資源，假設為Pn，那么對于這個進程來說，意味著它還未釋放資源，根據??，也就意味著它還未將該請求從自己的隊列中刪除，同時，由?可知，pm中還存儲著pn請求資源的消息。而進程Pm之所以能獲取資源，說明它滿足了?的兩個條件，但是根據?的條件a）說明進程Pm的資源請求是最早的，但是實際上Pn的請求要更早，因為它比Pm更早獲得授權，但是該請求還未從Pm的隊列中刪除，因此?的條件a)就不可能滿足，這樣就找到了矛盾的地方。
證明?的成立：
根據?的a)可知，資源的分配是按照 發生資源請求的 全序關系排序的，單獨考慮pi進程發出的資源請求而言，由全序關系 ，排在隊列前面的請求先得到滿足。再由?的b)，pi收到所有的其它進程發過來的請求，意味著pi知道了其他進程的事件請求操作情況，因此，它就知道了當前它的Tm:pi 請求在整個系統中是不是最早的，而?的b)中：pi 收到了所有其他進程發給它的時間戳大于Tm的消息，這樣它就確定Tm是最早的資源申請請求了，就會給Pi的Tm:pi 請求分配資源。
因此?成立
證明?的成立：
根據???可請證明?成立。假設pi已經擁有的資源，它發送一個帶時間戳的資源釋放請求給其他所有進程，其它進程就把當初進程pi請求資源時發送給它們的消息從隊列中刪除（參考?），這樣使得其它進程(非pi進程）的請求隊列中資源請求消息變成最早的了（因為，最最早的pi資源請求消息已經被刪除了），這樣就使得任何進程發出的資源請求消息最終能夠被響應。
?
5，邏輯時鐘存在的問題（Anomalous Behaviour）以及引入物理時鐘的原因
采用上述討論的邏輯時鐘還不能完成給事件排序。考慮下面一個情況：小A 在 A市 的計算機A上發送了一個請求A，然后打電話告訴 住在B市的小B，讓小B 在計算機B上產生一個請求B。在現實的物理世界中看出是請求A導致了請求B的發生，即A是因，B是果。但在邏輯時鐘系統下，可能會出現A的時間戳排在B的時間戳的后面。為啥？因為“打電話”這一手段可以理解為是在邏輯時鐘系統外部發生的。比如請求A在標號為2的進程上發生，而請求B在標號為1的進程上發生，排全序時，請求B的時間戳會小于請求A的時間戳。
如何解決這樣的情況？一種解決思路是把“打電話”這一事件也加入到系統中來考慮。這時，單純地用Lamport 邏輯時鐘就不能對所有的事件進行全排序了。因此，就引入了物理時鐘來解決該問題。
其次，對于邏輯時鐘而言，是沒有錯誤概念這一說的。failure這個概念只有在物理時間上下文中才有意義，如果沒有物理時間，就沒有辦法去區分進程是出錯了還是只是處于事件之間的間隔之中。用戶只能通過系統很長時間都沒有響應來判斷系統出了問題。
引入物理時鐘之后，物理時鐘的正確工作是需要一定的條件的，即各個計算機使用的物理時鐘值不能偏差太大。因此，又提出了物理時鐘同步。物理時鐘的同步主要有兩種方式：1）有一個標準的時間服務器，各個Client都去連接該時間服務器同步時鐘，從而達到各個Client的時鐘是同步的。2）Berkeley算法：時鐘服務器主動地詢問各個Client的當前的時鐘值，各個Client就會告訴時鐘服務器它們各自的時鐘是多少，時鐘服務器把收集到的這些值，再加上自己的時鐘值，得出一個平均值。并計算出各個Client的時鐘值與該平均值的差值，時鐘服務器把該差值分別發送給各個Client，讓它們進行調整。
如：Client A 比平均值少5秒，則Client A 需要加快自己的時鐘計數（并不是把自己的時鐘值倒退5秒），其實相當于物理學中的將加速度增大了。
?
6，Lamport邏輯時鐘的局限性
a)使用邏輯時鐘的方法給所有的事件排序時，必須保證所有的進程都參與其中（參考上面的算法描述），即不容許進程失敗。而這在現實的分布式系統中幾乎是不可能的。b)該算法假設消息是按序到達的，且一定會傳遞成功。這可以通過消息序號和確認機制來保證（TCP協議）。
?
總結：在分布式系統中，討論各個事件的發生順序時，一般講的都是偏序！！
7，參考文獻
《time clocks and the ordering of events in a distributed system》論文
Time Clocks and the Ordering of Events in a Distributed System(譯文)??
全序, 分布式一致性的本質
我對Lamport Logical Clock的理解
總結
以上是生活随笔為你收集整理的Lamport Logical Clock 学习的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： ElasticSearch index
- 下一篇： Maven内置属性及使用