在上一篇文章分散式系統：Lamport 邏輯時鐘中我們知道Lamport 邏輯時鐘幫助我們得到了分散式系統中的事件全序關係，但是對於同時發生的關係卻不能很好的描述，導致無法描述事件的因果關係。向量時鐘是在 Lamport 時間戳基礎上演進的另一種邏輯時鐘方法，它通過向量結構不但記錄本節點的 Lamport 時間戳，同時也記錄了其他節點的 Lamport 時間戳，因此能夠很好描述同時發生關係以及事件的因果關係。

注意：

  • 本文中的因果關係指的是時序關係，即時間的前後，並不是邏輯上的原因和結果
  • 本文中提及的時間戳如無特別說明，都指的是邏輯時鐘的時間戳，不是物理時鐘的時間戳

為什麼需要向量時鐘

首先我們來回顧一下 Lamport 邏輯時鐘演算法，它提供了一種判斷分散式系統中事件全序關係的方法：如果 a -> b，那麼 C(a) < C(b)，但是 C(a) < C(b) 並不能說明 a -> b。也就是說C(a) < C(b) 是 a -> b 的必要不充分條件，我們不能通過 Lamport 時間戳對事件 a、b 的因果關係進行判斷。下面我們舉一個例子來說明。

假設有三個進程在發消息，Ts(mi)表示消息mi的發送時間戳，Tr(mi)表示消息mi的接受時間戳，顯然 Ts(mi) < Tr(mi)，但是這個能說明什麼呢？

我們可以發現在進程 P2 中，Tr(m1) < Ts(m3)，說明 m3 是在 m1 被接收之後發送的，也就是說 m3 的發送跟 m1 的接收有關係。難道通過 Lamport 時間戳就能區分事件的因果的關係了嗎？答案是 No，我們仔細看可以發現，雖然 Tr(m1) < Ts(m2)，但實際上 m2 的發送跟 m1 並沒有關係。

綜上所述，我們可以發現 Lamport 邏輯時鐘演算法中每個進程只擁有自己的本地時間，沒有其他進程的時間，導致無法描述事件的因果關係。如果每個進程都能夠知道其他所有進程的時間，是否就能夠得到事件的因果關係了呢？為此，有人提出了向量時鐘演算法，在 Lamport 邏輯時鐘的基礎上進行了改良，提出了一種在分散式系統中描述事件因果關係的演算法。

可能有人會有疑問：向量時鐘到底有什麼用呢？舉一個常見的工程應用：數據衝突檢測。分散式系統中數據一般存在多個副本，多個副本可能被同時更新，這會引起副本間數據不一致，此時衝突檢測就非常重要。基於向量時鐘我們可以獲得任意兩個事件的順序關係，結果要麼是有因果關係（先後順序），要麼是沒有因果關係（同時發生）。通過向量時鐘，我們能夠識別到如果兩個數據更新操作是同時發生的關係，那麼說明出現了數據衝突。後面我們會詳細說明相關的實現。

什麼是向量時鐘

通過上面的分析我們知道向量時鐘演算法是在 Lamport 邏輯時鐘的基礎上進行了改良，用於在分散式系統中描述事件因果關係的演算法。那麼為什麼叫向量時鐘呢？前面我們知道如果每個進程都能夠知道其他所有進程的時間，就能夠通過計算得到事件的因果關係。向量時鐘演算法利用了向量這種數據結構將全局各個進程的邏輯時間戳廣播給各個進程：每個進程發送事件時都會將當前進程已知的所有進程時間寫入到一個向量中，附帶在消息中。這就是向量時鐘命名的由來。

如何實現向量時鐘

假設分散式系統中有 N 個進程，每個進程都有一個本地的向量時間戳 Ti，向量時鐘演算法實現如下：

  1. 對於進程 i 來說，Ti[i] 是進程 i 本地的邏輯時間
  2. 當進程 i 當有新的事件發生時，Ti[i] = Ti[i] + 1
  3. 當進程 i 發送消息時將它的向量時間戳(MT=Ti)附帶在消息中。
  4. 接受消息的進程 j 更新本地的向量時間戳：Tj[k] = max(Tj[k], MT[k]) for k = 1 to N。（MT即消息中附帶的向量時間戳）

下圖是向量時鐘的示例：

那麼如何利用向量時鐘判斷事件的因果關係呢？我們知道分散式系統中的事件要麼是有因果關係（先後順序），要麼是沒有因果關係（同時發生），下面我們來看一下如何利用向量時鐘判斷時間的因果關係。

假設有事件 a、b 分別在節點 P、Q 上發生，向量時鐘分別為 Ta、Tb，如果 Tb[Q] > Ta[Q] 並且 Tb[P] >= Ta[P]，則a發生於b之前，記作 a -> b，此時說明事件 a、b 有因果關係； 反之，如果 Tb[Q] > Ta[Q] 並且 Tb[P] < Ta[P]，則認為a、b同時發生，記作 a <-> b。例如上圖中節點 B 上的第 4 個事件 (A:2，B:4，C:1) 與節點 C 上的第 2 個事件 (B:3，C:2) 沒有因果關係，屬於同時發生事件。

向量時鐘的實際應用

前面我們提到向量時鐘可以用來檢測分散式系統中多副本更新的數據衝突問題，注意是檢測（發現問題），它並不能解決問題。數據衝突的解決是另一個課題，這裡不展開了。

亞馬遜的 Dynamo 是一個分散式Key/Value存儲系統，為了高可用，即使在出現網路分區或者機器宕機時依然可讀可寫。當網路分區恢復之後，多個副本同步數據一定會出現數據不一致的情況，那麼如何檢測數據衝突呢？參考向量時鐘（Vector clock）的思想，Dynamo 中使用了版本向量（Version vector）來檢測數據衝突，下面我們來看看演算法的實現。

  1. client 端寫入數據，該請求被 Sx 處理並創建相應的 vector ([Sx, 1])，記為數據 D1
  2. 第 2 次請求也被 Sx 處理，數據修改為 D2，vector 修改為([Sx, 2])
  3. 第 3、4 次請求分別被 Sy、Sz 處理，client 端先讀取到 D2，然後 D3、D4 被寫入 Sy、Sz
  4. 第 5 次更新時 client 端讀取到 D2、D3 和 D4 3個數據版本，通過類似向量時鐘判斷同時發生關係的方法可判斷 D3、D4 是同時發生的事件，因此存在數據衝突，最終通過一定方法解決數據衝突並寫入 D5

注意，向量時鐘和版本向量並不是同一個東西，版本向量借鑒了向量時鐘中利用向量來判斷事件的因果關係的思想，用於檢測數據衝突。向量時鐘還有其他的應用，例如強制因果通信（Enforcing Causal Communication），這裡不展開了，有興趣的讀者自行谷歌。

總結

向量時鐘演算法利用了向量這種數據結構將全局各個進程的邏輯時間戳廣播給各個進程，通過向量時間戳就能夠比較任意兩個事件的因果關係（先後關係或者同時發生關係）。向量時鐘被用於解決數據衝突檢測、強制因果通信等需要判斷事件因果關係的問題。

參考資料

  • 分散式系統理論基礎 - 時間、時鐘和事件順序
  • Lamport Clocks And Vector Clocks
  • Vector Clock/Version Clock
  • Dynamo: Amazon』s Highly Available Key-value Store
  • Why Vector Clocks Are Hard

推薦閱讀：

相關文章