今天的文章來聊聊向量時鐘，在前文介紹分布式系統一致性的時候，曾經介紹過，在弱一致性模型當中會有一個因果性的問題。向量時鐘算法正是設計出來解決因果關系問題的。
我們來回顧一下因果問題，在實際日常的網頁行為當中，部分行為存在因果關系。比方說知乎里面回答問題，顯然得先有一個同學提出問題，然后才能有各路大V謝邀解答問題。但是由于是分布式系統，有可能問題和回答并不是存放在同一臺機器，導致有可能它們更新的順序不一致，所以就有可能會出現用戶在訪問知乎的時候，發現自己關注的大V回答了某個問題，但是點進去問題卻是空的。這種幽靈情況不是靈異事件，只是單純的分布式系統設計沒過關，沒有考慮因果問題。
有的同學可以會說，這個不難啊，我們加入時間戳啊。時間戳的確可以解決一部分問題，但是并不能解決所有問題。有了時間戳之后，我們可以獲得事件發生的時間，但是仍然不知道不同的數據之間的因果關系。由于分布式系統存在延遲，也不能簡單地通過時間戳來做過濾或者篩選。不過，雖然單純的時間戳不行，但已經非常接近了。
我們日常生活當中用事件發生的時間來反應事物發生的順序，我們說的先后順序，其實是以客觀上的時間作為參考系參考得到的結果。問題來了，我們能不能找到或者構造出其他的參考系來反應事物發生的順序呢？
當然是可以的，不然也沒有這篇文章了，這就是大名鼎鼎的邏輯時鐘算法。多說一句，邏輯時鐘算法和許多其他分布式算法一樣，同樣源于大神Lamport的發明。
邏輯時鐘
我們還用之前的例子來思考一下，一個人在知乎提交了問題，另一個人回答了問題，這是兩個事件。我們第一反應自然是通過兩個事件發生的時間來反應因果順序，但我們仔細分析一下這個場景。后面那個人既然能回答問題，說明他一定是看到了問題。也就是說回答問題和看到問題之間發生了交互，所以很自然地可以想到，我們是不是可以用兩個系統或者是兩個事件之間有沒有發生過信息交互來反應因果順序呢？
于是基于這個思想，Lamport大神提出了邏輯時鐘的概念。邏輯時鐘概念的核心就是剛才我們說的，兩個事件之間建立因果關系的前提是，兩個事件之間發生過信息傳遞。
我們梳理一下可能發生的事件的種類，可以分成三種。第一種是發生在某個節點內部，也就是說沒有和其他任何節點發生聯系。第二種是發送事件，是事件的發送方。第三種是接收事件，和第二種對應，是事件的接收方。明確了這三點之后，我們就可以用時間戳來表示這三種情況了。首先，我們假設每個節點內部都會維護一個時間戳，記錄當下節點的狀態。
針對上面說是三種時序關系呢，我們設定三種策略。
首先是內部事件，對于節點內部發生事件呢，很簡單，我們只需要將它的時間戳增大1，表示發生過了某件事情。
其次是發送事件，節點內部的時間戳自增1，并且在發送消息當中加上這個時間戳。
最后是接收事件，由于會額外接收到一個時間戳，所以我們需要利用這個時間戳來更新節點內部的時間戳。更新的方法也很簡單，假設節點內部的時間戳是t，跟著消息傳遞而來的時間戳是t', 那么: t_new = max(t + 1, t') 。
我們分析一下上面這個關系，假設當下有事件A和B，如果事件A是事件B發生的前提。那么顯然事件A的時間戳小于事件B。如果反過來，事件A的時間戳小于B，能說明事件A是事件B的前提嗎？并不能，所以時間戳較小是因果關系的必要條件，但不是充分條件。
由于會存在多個節點或者進程時間戳相等的情況，所以我們把進程id也作為比較的銀子。我們用C表示一個事件的時間戳，P表示事件的進程pid。如果事件A排在事件B前面，只有兩種可能：
- C(A) < C(B)
- C(A) = C(B) and P(A) < P(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的前面。也就是說我們通過比較 C(A) 和 C(B)無法得出真實的發生順序。
為了解決這個問題，大神們在Lamport的邏輯時鐘上做了改進，提出了向量時鐘算法。
向量時鐘和邏輯時鐘的原理幾乎一樣，只不過對于每個節點或者進程而言，它維護的不再是一個單個的時間戳，而是一個時間戳構成的向量。向量的維度就等于進程的數量，也就是說每個進程不止記錄自己的時間戳，而且還會記錄其他進程的時間戳，這些時間戳組合在一起，就構成了一個時間向量。
在事件的處理上，向量時鐘算法和邏輯時鐘基本一致。
- 在進程i發生事件（接收、發送或者是內部事件）的時候，，這時候C是一個時間戳向量，i是進程i的下標。
- 當進程i發送消息的時候，會將消息和自己的時鐘向量一同發出。
- 當進程i收到進程j發送來的消息時，會根據一起發送來的時鐘向量更新自己的時鐘向量：
同樣，由于單個時間戳換成了向量時鐘，所以我們判斷因果順序的方式也需要變化。在向量時鐘算法當中，我們定義如果事件A在事件B之前，那么需要滿足兩個條件：
- 對于所有的下標K，都有
- 存在下標，使得
也就是說至少需要一個維度存在嚴格小于，其他維度全部小于等于，才可以看做是因果關系。原因也很簡單，因為如果存在消息傳遞，那么至少有一個維度會帶來增加。如果兩個事件的向量時鐘相等，說明兩者是沒有發生過信息傳遞的，自然也就不符合我們定義的因果關系。
我們回顧一下之前的例子，將節點改寫成向量時鐘之后，得到的結果如下圖：
將邏輯時鐘優化成向量時鐘之后，就可以嚴格判斷因果關系了。如果兩個節點的時鐘向量沒有大小關系，那么可以說明這兩個事件之間沒有聯系。
實際應用
和我們之前介紹的一樣，向量時鐘算法主要用在分布式系統的因果關系的檢測上。而因果關系之所以需要檢測，往往是因為我們面臨多個副本同時更新，我們需要檢測這些副本的沖突。
我們來一起看一個例子，這個例子是亞馬遜的Dynamo系統， 它是一個KV的存儲系統，類似于redis，可以簡單理解成緩存。為了高可用，Dynamo保證即使在出現網絡分區或者機器宕機的時候，仍然可讀可寫。但是這會導致一個問題，當網絡分區恢復之后，多個副本的數據可能會出現不一致的情況，這個時候我們就需要通過向量時鐘算法來檢測沖突了。
假設一開始的時候客戶端W創建了一個記錄X，這個記錄是由機器 Sx 來負責的。那么則形成了數據 D1
和它對應的向量時鐘 [Sx, 1]。
之后，客戶端繼續更新記錄X，同樣由機器 Sx 執行，形成了新數據 D2，它的向量時鐘變成 [Sx, 2]，它和 D1 存在因果關系。所以我們可以知道 D2 是最新的數據。
再之后，客戶端繼續更新X，這次由 Sy 執行，產生了D3，同樣，可以知道操作結束之后它的向量時鐘為 [Sx, 2], [Sy, 1]。
與此同時，另一個客戶端讀入了 D2 之后，在機器 Sz 上更新產生了 D4 ，此時的向量時鐘是 [Sx, 2], [Sz, 1]。
我們來分析一下，如果這時候有客戶端同時讀到 D2 和 D3 ，那么通過向量時鐘可以判斷出來，D3 是最新的數據。如果同時讀到 D3 和 D4 ，由于這兩者的向量時鐘并沒有因果關系，所以無法判斷誰是最新的數據，這就產生了沖突。
但是必須要說明的是，向量時鐘算法只能檢測沖突，并不能解決沖突，沖突需要客戶端自己解決。如果客戶端判斷，決定應該以 Sx 的節點為準，那么最后的數據就會變成 D5 ，此時的向量時鐘為[Sx, 3], [Sy, 1], [Sz, 1]。
除了知乎之外，其實還有很多場景下的一致性問題都需要考慮因果關系。因此向量時鐘算法在分布式領域可以說是鼎鼎大名，使用非常廣泛。在剛聽到這個名字的時候，往往會覺得它非?；逎y懂，但實際深入了解之后，會發現其實并不困難，反而非常有趣，這也算是學習的樂趣之一吧。
今天的文章就到這里，如果覺得有所收獲，請順手點關注或轉發個吧，你們的支持是我最大的動力。
