分散式系列：Vector clock

Lamport邏輯時鐘的問題

Lamport邏輯時鐘的第一個問題在於，它的全序關係不是唯一確定的。因為當邏輯時鐘的值一致的時候，需要選擇進程的全序關係R，而選擇的R具有任意性，比如可以比較進程編號，也可以比較進程運行伺服器的ip地址。這樣意味著R的不同，會導致事件順序的不同。

Lamport邏輯時鐘的第二個問題在於，它的大小無法準確描述事件先後順序。假設已知C(a) C(b)，也無法得到任何結論。例如下圖中57時刻的事件，儘管其邏輯時間小於61，但是實際上它是在61事件之後發生的。

Lamport邏輯時鐘的第三個問題在於，它丟失了一些依賴細節。例如下圖中，當進程p2接收到消息，把時鐘改成3的時候，其實這個3是由p1的2產生的，這一依賴細節就完全消失了。

Vector clock的實現

在Lamport邏輯時鐘的基礎上，人們又研究出了vector clock，vector clock本質上可以認為是Lamport邏輯時鐘的數組，即Lamport邏輯時鐘的向量，因此得名。

按照維基百科的說法，vector clock是在以下兩篇文章中各自獨立出現的：

《Timestamps in Message-Passing Systems That Preserve the Partial Ordering》

《Virtual Time and Global States of Distributed Systems》

Vector clock定義了一種happen before關係，當且僅當兩個兩個事件在所有的可能性中都具有因果關係時，它們才具有這種關係。假設VC(a)和VC(b)分別是a和b事件的vector clock值，如果VC(a) VC(b)，那麼a happen before b。

假設一共n個進程，則每個進程i維護n維向量(長度為n的數組)VCi，VCi初始值都為0。其中VCi[j]代表進程i知道的進程j的最新時間。

關於vector clock的實現，很多資料眾說紛紜，這裡我們只參考上述兩篇文章。

《Virtual Time and Global States of Distributed Systems》

VC的更新規則如下：

進程i執行任何事件之前，將VCi[i]的值 1

進程i發送消息m時，將m的時間戳設置為VCi

進程i接收消息m時，取得m的時間戳t，對VCi中的每個分量k，執行VCi[k]=max(VCi[k],t[k])

文中示意圖如下

這個和維基百科上的圖片效果是一樣的

這種情況下，對於VC(a)和VC(b)，如果同時滿足：

對於每個分量x，都有VC(a)[x] = VC(b)[x]

存在分量y，使得VC(a)[y] VC(b)[y]

那麼VC(a) VC(b)。

《Timestamps in Message-Passing Systems That Preserve the Partial Ordering》中的非同步模型

VC的更新規則有所不同，主要體現在發送消息的進程所在的分量也要遞增。例如下面的文章示意圖中，發送事件a發生在[1,0,0]，接收事件m發生在[2,2,0]，注意向量的第一個分量也加1了。

這種情況下，假設事件a和b分別發生在進程i和j中，如果VC(a)[i] VC(b)[i]，則說明a happen before b

《Timestamps in Message-Passing Systems That Preserve the Partial Ordering》中的同步模型

這時網路通信變成同步模型了，發送事件的時間和接收事件的時間變成一樣了，文中圖示如下：

這種情況下，假設事件a和b分別發生在進程i和j中，如果VC(a)[i] = VC(b)[i] 並且VC(a)[j] = VC(b)[j]，則說明a happen before b

同步模型我還沒有理解，歡迎知道的同學請補充一下

Vector clock的應用

Dynamo中使用vector clock來進行衝突解決，由於Dynamo是多master結構，可以在多個節點進行寫入操作，因此需要解決寫入的衝突問題。通過vector clock，系統可以找到衝突的數據，進而讓用戶進行修正。

在後續文章中有可能進一步介紹Dynamo的相關知識

Vector clock還有一種應用是獲得系統的global state，合法的系統狀態是系統的consistent cut，這個cut中的事件應該有並發上的要求。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！