前言

在一個(gè)分布式系統(tǒng)中存在著各種各樣的并發(fā)事件，對(duì)于某些存在內(nèi)在因果關(guān)系的事件需要知道事件的先后順序，并且能夠按照正確的順序處理這些事件，區(qū)分事件的先后順序在單機(jī)系統(tǒng)中可以靠本地時(shí)鐘來(lái)做到，但在分布式系統(tǒng)中如何做到呢，這就是分布式系統(tǒng)中的logical time問(wèn)題。

本文為大家介紹logical time算法的鼻祖Lamport Clock。

為了形象地描述logical time問(wèn)題，我們舉個(gè)簡(jiǎn)單的例子，假設(shè)客戶A下單購(gòu)買了一本書(shū)，這時(shí)系統(tǒng)向訂單系統(tǒng)提交a請(qǐng)求(客戶買書(shū)的訂單)，然后購(gòu)買該書(shū)還有個(gè)優(yōu)惠活動(dòng)，能夠獲得一本贈(zèng)書(shū)，這時(shí)系統(tǒng)需要向優(yōu)惠活動(dòng)管理系統(tǒng)發(fā)送b請(qǐng)求(客戶要求贈(zèng)書(shū)x)，優(yōu)惠活動(dòng)管理系統(tǒng)檢查準(zhǔn)許客戶的贈(zèng)書(shū)請(qǐng)求，于是將b請(qǐng)求轉(zhuǎn)發(fā)給訂單系統(tǒng)，在該例子中顯然訂單系統(tǒng)應(yīng)該先收到買書(shū)的訂單，然后是贈(zèng)書(shū)的訂單，但是由于網(wǎng)絡(luò)延時(shí)的原因，可能存在贈(zèng)書(shū)請(qǐng)求先于買書(shū)請(qǐng)求到達(dá)訂單系統(tǒng)的情況，那么這種情況需要如何處理?

我們用簡(jiǎn)單的圖來(lái)描述上面的過(guò)程，圖中P0代表訂單系統(tǒng)，P1代表客戶，P2代表優(yōu)惠活動(dòng)管理系統(tǒng)，a請(qǐng)求就是買書(shū)請(qǐng)求，b請(qǐng)求就是贈(zèng)書(shū)請(qǐng)求。

為了解決該問(wèn)題比較容易想到的做法就是同步通信，發(fā)送a請(qǐng)求后等待P0處理完成并回復(fù)后再開(kāi)始發(fā)送b請(qǐng)求，該方法簡(jiǎn)單易實(shí)現(xiàn)但是并不能發(fā)揮分布式系統(tǒng)的并發(fā)性能，效率低下，也不能簡(jiǎn)單地用給時(shí)間a和b打上本地時(shí)間戳的方式來(lái)處理，因?yàn)榉植际较到y(tǒng)中本地時(shí)鐘是無(wú)法做到完全同步的，所以需要一種適用于分布式系統(tǒng)的能將事件的先后順序信息也被稱為“ happened before”信息識(shí)別出來(lái)的算法，本文主要介紹logical time算法的鼻祖Lamport clock。

Lamport clock算法

Lamport clock算法的思想很簡(jiǎn)單，主要有以下兩個(gè)規(guī)則：

• 每個(gè)process在成功完成一個(gè)事件后都增加自己的時(shí)間戳，通常是加1;
• 如果process Pi通過(guò)消息m發(fā)送了事件a，那么該消息m中包含了當(dāng)前pi的時(shí)間戳Ci(a);process Pj收到消息m后，取消息m中帶的時(shí)間戳和Pj當(dāng)前的時(shí)間戳Cj中的較大值然后加1;

例如一個(gè)較為復(fù)雜的例子，已經(jīng)用Lamport clock算法為每個(gè)事件加了時(shí)間戳，如下圖：

通過(guò)該例子可以發(fā)現(xiàn)存在一些并沒(méi)有明確的先后關(guān)系的并發(fā)事件，比如p1上的時(shí)間戳為3的事件和p2上的時(shí)間戳為4的事件，這些事件可以是任意先后或者同時(shí)發(fā)生，但在Lamport clock算法中這些事件卻有了明確的時(shí)間戳，該時(shí)間戳的大小并不代表事件的先后順序。

重要屬性

用簡(jiǎn)單的公式來(lái)描述logical time算法的Clock Condition，C表示時(shí)間戳，ei 和 ej表示兩個(gè)事件，假設(shè)ei先于ej發(fā)生，并用->表示該“happened before”關(guān)系，那么存在以下兩個(gè)Clock Condition：

1) ei -> ej => C(ei) < C(ej)

表示如果ei先于ej發(fā)生，那么ei的時(shí)間戳C(ei)必定小于C(ej)。

2) ei -> ej <=> C(ei) < C(ej)

表示如果ei先于ej發(fā)生，那么ei的時(shí)間戳C(ei)必定小于C(ej)，如果C(ei)小于C(ej)，那么ei必定先于ej發(fā)生。

根據(jù)算法是否滿足以上Clock Condition來(lái)區(qū)分其所具備的屬性，如果一個(gè)算法滿足Clock Conditon 2，那么該算法具備strongly consistent屬性，本篇文章介紹的Lamport clock算法只滿足Clock Condition 1，所以不具備strongly consistent屬性，但后續(xù)介紹的vector clock算法具備strongly consitent屬性。

strongly consistent屬性的意義在于是否可以通過(guò)C時(shí)間戳來(lái)判斷出事件ei與ej的順序關(guān)系，具備該屬性的算法，當(dāng)時(shí)間戳C(ei) > C(ej)時(shí)，可以確定ei先于ej發(fā)生，否則可以認(rèn)為ei與ej是沖突的(這里的沖突表示ei與ej可以是任意的先后關(guān)系)，所以可以用來(lái)檢測(cè)事件的沖突。

案例分析

使用Lamport clock對(duì)之前的例子做排序，如下圖：

P1發(fā)送a消息和b消息，因?yàn)镻1的初始時(shí)間戳為0，所以按照Lamport clock算法事件a和b的發(fā)送時(shí)間戳為1和2。

P0收到P1的消息a，取兩者時(shí)間戳的較大值max(0，1)并+1得到時(shí)間戳為2。

P2收到b消息后，取兩者時(shí)間戳的較大值max(0，2)并+1得到時(shí)間戳為3。

P0收到P2轉(zhuǎn)發(fā)的事件b后，取兩者時(shí)間戳的較大值max(2，3)并+1得到時(shí)間戳為4。

所以在P0端可以得到事件a是先于事件b的。

但在實(shí)際的應(yīng)用中由于存在網(wǎng)絡(luò)延時(shí)，會(huì)出現(xiàn)以下情況：

因?yàn)榫W(wǎng)絡(luò)延時(shí)導(dǎo)致P0先收到P2轉(zhuǎn)發(fā)的b事件，再收到P1的a事件，然后根據(jù)Lamport clock算法計(jì)算出來(lái)的時(shí)間戳也變成了b事件先于a事件了，這顯然是錯(cuò)誤的，那么要如何避免出現(xiàn)這個(gè)情況，為了關(guān)注解決該問(wèn)題的實(shí)際算法，假定系統(tǒng)已經(jīng)滿足以下條件：

• 消息的接受順序與發(fā)送順序一致;
• 所有的消息最終都會(huì)被收到;

每個(gè)process都有自己的請(qǐng)求隊(duì)列，并且對(duì)其他process不可見(jiàn)，請(qǐng)求隊(duì)列中的初始時(shí)間戳為0，算法由以下5條規(guī)則組成：

1) 請(qǐng)求資源時(shí)，process Pi發(fā)送消息Tm，給其他所有process，并且將消息Tm置于它的請(qǐng)求隊(duì)列中

2) prcocess Pj收到Pi的資源請(qǐng)求消息Tm后，將該消息置于自己的請(qǐng)求隊(duì)列中并發(fā)送一個(gè)帶有時(shí)間戳的回復(fù)給Pi

3) 釋放資源時(shí)，Pi將消息Tm從請(qǐng)求隊(duì)列中移除，并發(fā)送資源釋放消息給所有其他process

4) process Pj收到Pi的資源釋放消息后將之前的資源請(qǐng)求消息Tm從請(qǐng)求隊(duì)列中移除

5) 當(dāng)滿足以下2個(gè)條件時(shí)認(rèn)為Pi獲取了資源

• Pi的請(qǐng)求隊(duì)列中有請(qǐng)求消息Tm，并且按照順序排列好的，這里以消息的發(fā)送順序?yàn)闇?zhǔn);
• Pi收到了任意一個(gè)時(shí)間戳比Tm要大的消息;

把這個(gè)算法帶入到上面的例子中，相當(dāng)于P1發(fā)起了兩個(gè)事件a和b來(lái)請(qǐng)求資源，a比b要先發(fā)生，那么也期望a比b要先被P0處理(這里處理可以理解為獲取了P0的資源)，那么當(dāng)出現(xiàn)上述例子中的情況，事件b先被P0收到，按照算法，P0發(fā)送Tm給所有其他process，然后等待回復(fù)，當(dāng)收到P1的回復(fù)時(shí)a事件也必然被收到了(按照系統(tǒng)假定滿足的條件1)消息的接受順序與發(fā)送順序一致)，這時(shí)按照規(guī)則5的(i)條件，會(huì)根據(jù)事件a和b的發(fā)送端的時(shí)間戳比較，重新排序?yàn)閍事件先于b事件，這樣就解決了因?yàn)榫W(wǎng)絡(luò)延時(shí)導(dǎo)致的消息亂序問(wèn)題。

總結(jié)

Lamport clock雖然作為分布式系統(tǒng)中解決logical time問(wèn)題的鼻祖，為后續(xù)其他算法提供了思路，但其不具備strongly consistent，無(wú)法滿足分布式數(shù)據(jù)庫(kù)場(chǎng)景中寫(xiě)沖突的檢測(cè)，所以實(shí)際場(chǎng)景中更多是使用后來(lái)的vector clock，后面我們將會(huì)給大家介紹vector clock。

【本文是51CTO專欄機(jī)構(gòu)作者“大U的技術(shù)課堂”的原創(chuàng)文章，轉(zhuǎn)載請(qǐng)通過(guò)微信公眾號(hào)(ucloud2012)聯(lián)系作者】

 戳這里，看該作者更多好文