分散式初探——判斷因果關係的向量時鐘演算法

2020 年 3 月 5 日
筆記

點擊上方藍字，和我一起學技術。

今天的文章來聊聊向量時鐘，在前文介紹分散式系統一致性的時候，曾經介紹過，在弱一致性模型當中會有一個因果性的問題。向量時鐘演算法正是設計出來解決因果關係問題的。

我們來回顧一下因果問題，在實際日常的網頁行為當中，部分行為存在因果關係。比方說知乎裡面回答問題，顯然得先有一個同學提出問題，然後才能有各路大V謝邀解答問題。但是由於是分散式系統，有可能問題和回答並不是存放在同一台機器，導致有可能它們更新的順序不一致，所以就有可能會出現用戶在訪問知乎的時候，發現自己關注的大V回答了某個問題，但是點進去問題卻是空的。這種幽靈情況不是靈異事件，只是單純的分散式系統設計沒過關，沒有考慮因果問題。

有的同學可以會說，這個不難啊，我們加入時間戳啊。時間戳的確可以解決一部分問題，但是並不能解決所有問題。有了時間戳之後，我們可以獲得事件發生的時間，但是仍然不知道不同的數據之間的因果關係。由於分散式系統存在延遲，也不能簡單地通過時間戳來做過濾或者篩選。不過，雖然單純的時間戳不行，但已經非常接近了。

我們日常生活當中用事件發生的時間來反應事物發生的順序，我們說的先後順序，其實是以客觀上的時間作為參考系參考得到的結果。問題來了，我們能不能找到或者構造出其他的參考系來反應事物發生的順序呢？

當然是可以的，不然也沒有這篇文章了，這就是大名鼎鼎的邏輯時鐘演算法。多說一句，邏輯時鐘演算法和許多其他分散式演算法一樣，同樣源於大神Lamport的發明。

邏輯時鐘

我們還用之前的例子來思考一下，一個人在知乎提交了問題，另一個人回答了問題，這是兩個事件。我們第一反應自然是通過兩個事件發生的時間來反應因果順序，但我們仔細分析一下這個場景。後面那個人既然能回答問題，說明他一定是看到了問題。也就是說回答問題和看到問題之間發生了交互，所以很自然地可以想到，我們是不是可以用兩個系統或者是兩個事件之間有沒有發生過資訊交互來反應因果順序呢？

於是基於這個思想，Lamport大神提出了邏輯時鐘的概念。邏輯時鐘概念的核心就是剛才我們說的，兩個事件之間建立因果關係的前提是，兩個事件之間發生過資訊傳遞。

我們梳理一下可能發生的事件的種類，可以分成三種。第一種是發生在某個節點內部，也就是說沒有和其他任何節點發生聯繫。第二種是發送事件，是事件的發送方。第三種是接收事件，和第二種對應，是事件的接收方。明確了這三點之後，我們就可以用時間戳來表示這三種情況了。首先，我們假設每個節點內部都會維護一個時間戳，記錄當下節點的狀態。

針對上面說是三種時序關係呢，我們設定三種策略。

首先是內部事件，對於節點內部發生事件呢，很簡單，我們只需要將它的時間戳增大1，表示發生過了某件事情。

其次是發送事件，節點內部的時間戳自增1，並且在發送消息當中加上這個時間戳。

最後是接收事件，由於會額外接收到一個時間戳，所以我們需要利用這個時間戳來更新節點內部的時間戳。更新的方法也很簡單，假設節點內部的時間戳是，跟著消息傳遞而來的時間戳是, 那麼: 。

我們分析一下上面這個關係，假設當下有事件A和B，如果事件A是事件B發生的前提。那麼顯然事件A的時間戳小於事件B。如果反過來，事件A的時間戳小於B，能說明事件A是事件B的前提嗎？並不能，所以時間戳較小是因果關係的必要條件，但不是充分條件。

由於會存在多個節點或者進程時間戳相等的情況，所以我們把進程id也作為比較的銀子。我們用C表示一個事件的時間戳，P表示事件的進程pid。如果事件A排在事件B前面，只有兩種可能：

我們來看一個例子：

上圖當中有A、B和C三個進程，其中P(A) < P(B) < P(C)。圖中每一個箭頭都代表傳遞的消息。

我們根據重新定義的時序關係，可以得到這些點的先後順序是：

C1⇒B1⇒B2⇒A1⇒B3⇒A2⇒C2⇒B4⇒C3⇒A3⇒B5⇒C4⇒C5⇒A4

如果仔細觀察這條鏈的話會發現它並不能真實反映事件發生的順序，會存在不公平的情況。但至少因果關係可以保證。

以上這個演算法被稱為是邏輯時鐘演算法，它相當於重新定義了一個邏輯上的時間來代替真實物理世界的時間。由於它是Lamport大神提出的，所以也被稱為是Lamport邏輯時鐘演算法。

向量時鐘

在上面的文章當中我們也分析了，邏輯時鐘演算法有一個問題是雖然保證了因果順序，但也犧牲了公平。比如上圖當中B3和A2發生在同一時間，但是B3排在A2的前面。也就是說我們通過比較和無法得出真實的發生順序。

為了解決這個問題，大神們在Lamport的邏輯時鐘上做了改進，提出了向量時鐘演算法。

向量時鐘和邏輯時鐘的原理幾乎一樣，只不過對於每個節點或者進程而言，它維護的不再是一個單個的時間戳，而是一個時間戳構成的向量。向量的維度就等於進程的數量，也就是說每個進程不止記錄自己的時間戳，而且還會記錄其他進程的時間戳，這些時間戳組合在一起，就構成了一個時間向量。

在事件的處理上，向量時鐘演算法和邏輯時鐘基本一致。

在進程i發生事件（接收、發送或者是內部事件）的時候，，這時候C是一個時間戳向量，i是進程i的下標。
當進程i發送消息的時候，會將消息和自己的時鐘向量一同發出。
當進程i收到進程j發送來的消息時，會根據一起發送來的時鐘向量更新自己的時鐘向量：

同樣，由於單個時間戳換成了向量時鐘，所以我們判斷因果順序的方式也需要變化。在向量時鐘演算法當中，我們定義如果事件A在事件B之前，那麼需要滿足兩個條件：

對於所有的下標K，都有
存在下標，使得

也就是說至少需要一個維度存在嚴格小於，其他維度全部小於等於，才可以看做是因果關係。原因也很簡單，因為如果存在消息傳遞，那麼至少有一個維度會帶來增加。如果兩個事件的向量時鐘相等，說明兩者是沒有發生過資訊傳遞的，自然也就不符合我們定義的因果關係。

我們回顧一下之前的例子，將節點改寫成向量時鐘之後，得到的結果如下圖：

將邏輯時鐘優化成向量時鐘之後，就可以嚴格判斷因果關係了。如果兩個節點的時鐘向量沒有大小關係，那麼可以說明這兩個事件之間沒有聯繫。

實際應用

和我們之前介紹的一樣，向量時鐘演算法主要用在分散式系統的因果關係的檢測上。而因果關係之所以需要檢測，往往是因為我們面臨多個副本同時更新，我們需要檢測這些副本的衝突。

我們來一起看一個例子，這個例子是亞馬遜的Dynamo系統，它是一個KV的存儲系統，類似於redis，可以簡單理解成快取。為了高可用，Dynamo保證即使在出現網路分區或者機器宕機的時候，仍然可讀可寫。但是這會導致一個問題，當網路分區恢復之後，多個副本的數據可能會出現不一致的情況，這個時候我們就需要通過向量時鐘演算法來檢測衝突了。

假設一開始的時候客戶端W創建了一個記錄X，這個記錄是由機器來負責的。那麼則形成了數據和它對應的向量時鐘。

之後，客戶端繼續更新記錄X，同樣由機器執行，形成了新數據，它的向量時鐘變成，它和存在因果關係。所以我們可以知道是最新的數據。

再之後，客戶端繼續更新X，這次由執行，同樣，可以知道操作結束之後它的向量時鐘為。

與此同時，另一個客戶端讀入了之後，在機器上更新產生了，此時的向量時鐘是。

我們來分析一下，如果這時候有客戶端同時讀到和，那麼通過向量時鐘可以判斷出來，是最新的數據。如果同時讀到和，由於這兩者的向量時鐘並沒有因果關係，所以無法判斷誰是最新的數據，這就產生了衝突。

但是必須要說明的是，向量時鐘演算法只能檢測衝突，並不能解決衝突，衝突需要客戶端自己解決。如果客戶端判斷，決定應該以的節點為準，那麼最後的數據就會變成，此時的向量時鐘為。

除了知乎之外，其實還有很多場景下的一致性問題都需要考慮因果關係。因此向量時鐘演算法在分散式領域可以說是鼎鼎大名，使用非常廣泛。在剛聽到這個名字的時候，往往會覺得它非常晦澀難懂，但實際深入了解之後，會發現其實並不困難，反而非常有趣，這也算是學習的樂趣之一吧。

今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支援是我最大的動力。