在上一篇文章 分布式系統：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，向量時鐘算法實作如下：
- 對于程序 i 來說，Ti[i] 是程序 i 本地的邏輯時間
- 當程序 i 當有新的事件發生時，Ti[i] = Ti[i] + 1
- 當程序 i 發送消息時将它的向量時間戳(MT=Ti)附帶在消息中。
- 接受消息的程序 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）來檢測資料沖突，下面我們來看看算法的實作。
- client 端寫入資料，該請求被 Sx 處理并建立相應的 vector ([Sx, 1])，記為資料 D1
- 第 2 次請求也被 Sx 處理，資料修改為 D2，vector 修改為([Sx, 2])
- 第 3、4 次請求分别被 Sy、Sz 處理，client 端先讀取到 D2，然後 D3、D4 被寫入 Sy、Sz
- 第 5 次更新時 client 端讀取到 D2、D3 和 D4 3個資料版本，通過類似向量時鐘判斷同時發生關系的方法可判斷 D3、D4 是同時發生的事件，是以存在資料沖突，最終通過一定方法解決資料沖突并寫入 D5
注意，向量時鐘和版本向量并不是同一個東西，版本向量借鑒了向量時鐘中利用向量來判斷事件的因果關系的思想，用于檢測資料沖突。向量時鐘還有其他的應用，例如強制因果通信（Enforcing Causal Communication），這裡不展開了，有興趣的讀者自行谷歌。
總結
向量時鐘算法利用了向量這種資料結構将全局各個程序的邏輯時間戳廣播給各個程序，通過向量時間戳就能夠比較任意兩個事件的因果關系（先後關系或者同時發生關系）。向量時鐘被用于解決資料沖突檢測、強制因果通信等需要判斷事件因果關系的問題。