分佈式系統：向量時鐘
- 2019 年 10 月 3 日
- 筆記
Lamport時鐘存在的問題
使用Lamport時間戳，只是比較事件(a)和(b)各自的時鐘值(C{a})和(C{b})，無法說明它們之間的關係。也就是說，(C{a}<C{b})不能說明事件(a)在事件(b)之前發生。比如下面的事件(C4)與(A3)，(C{A3}<C{C4})，但是在時間上事件(A3)在(C4)之後發生。
所以，Lamport時間戳的問題在於它不能捕獲事件的因果關係，為了解決這個問題，有大神提出了向量時鐘。
向量時鐘
Vector clock是在Lamport時間戳基礎上演進的另一種邏輯時鐘方法，它通過vector結構不但記錄本節點的Lamport時間戳，同時也記錄了其他節點的Lamport時間戳。即，當系統有(N)個進程時，則存在(N)個邏輯時鐘向量，一個進程對應一個時鐘。具體如下：
- 初始時所有時鐘都為0；
- 每一次處理內完內部事件，將本進程對應的邏輯時鐘+1；
- 每一次發送一個消息的時候，需要將自己的向量時鐘和消息一起發送；
- 每一次接收到一個消息，需要將自己的邏輯時鐘+1，同時更新每一個邏輯時鐘，更新規則為取本地邏輯時鐘和收到的邏輯時鐘的最大值。
假設分佈式系統有A、B和C這3個進程，根據上述規則其各自對應的邏輯時鐘隨着時間演化情況如圖所示，其數值變化規則遵循上述規則，時間線之間的邊代表進程間發送的消息。標為cause的陰影部分代表導致［A:2,B:4,C:1]事件的原因，標為effect的陰影部分則代表［A:2,B:4,C:1]事件影響到的後續事件，而無陰影部分覆蓋的事件則是和［ A:2,B:4,C:1]事件無邏輯上因果關係的事件。
事件關係判斷方法：
- 正常情況下，向量時鐘V1上的各個時間分量如果全部都小於等於V2上各個時間分量，則認為V1比V2早。舉個例子說明，比如事件［A:1,B:2,C:1］以及［A:4,B:5,C5]，通過和［A:2,B:4,C:1］對應位置比較可知其因果關係為：[A:1,B:2,C:1]為［A:2,B:4,C:1]之因，[A:4,B:5,C5］ 為[A:2,B:4,C:1］之果。
- 向量時鐘V1上的各個時間分量有的比V2上的時間分量大，有的比其小，則認為是同時發生。比如事件[A:2,B:4,C:1]與事件[ ,B:3,C:3]。
向量時鐘的應用——衝突檢測
可能有人會有疑問：向量時鐘到底有什麼用呢？舉一個常見的工程應用：數據衝突檢測。分佈式系統中數據一般存在多個副本，多個副本可能被同時更新，這會引起副本間數據不一致，此時衝突檢測就非常重要。基於向量時鐘我們可以獲得任意兩個事件的順序關係，結果要麼是有因果關係（先後順序），要麼是沒有因果關係（同時發生）。通過向量時鐘，我們能夠識別到如果兩個數據更新操作是同時發生的關係，那麼說明出現了數據衝突。注意是檢測（發現問題），它並不能解決數據衝突。
下面我們舉個向量時鐘應用的例子，以一個例子來說明如何使用時鐘向量，來維護一個分佈式系統的一致性。
Alice, Ben, Cathy, Dave四個人準備下周聚餐，在時間安排上協調出現了問題。首先，Alice提出Wednesday聚餐，那麼對提出這個提議的Alice來說，此時她的時鐘向量就是這樣的：
date = Wednesday vclock = Alice:1她將這個消息廣播給其他三個人：
Ben在收到提議之後，提出自己的提議Tuesday，此時ben的時鐘向量就是：
date = Tuesday vclock = Alice:1, Ben:1然後將消息發送給Dave:
Dave收到之後，回復Ben表示同意Tuesday，此時Dave的時鐘向量是：
date = Tuesday vclock = Alice:1, Ben:1, Dave:1現在Cathy參與進來，建議Thursday，此時Cathy的時鐘向量是：
date = Thursday vclock = Alice:1, Cathy:1然後將提議發送給了Dave：
Dave此時就有了兩份有衝突的數據（衝突的原因是Ben和Cathy「同時」修改了最初Alice的數據）：
date = Tuesday vclock = Alice:1, Ben:1, Dave:1和
date = Thursday vclock = Alice:1, Cathy:1根據時鐘向量的關係判斷規則，Dave發現了衝突，因為當前的向量時鐘和新接收到的向量時鐘上的各個邏輯時鐘並不是全部小於或大於。幸運的是，Dave是個有理性的人，選擇了Thursday（前面是發現衝突，這裡相當於解決衝突，實際系統中解決衝突的方法不同，解決衝突不是向量時鐘的內容）。Dave解決衝突並回復給Cathy，此時Dave的向量時鐘為：
date = Thursday vclock = Alice:1, Ben:1, Cathy:1, Dave:2至此，當Alice問Ben和Cathy最新的決定，會收到來自Ben的：
date = Tuesday vclock = Alice:1, Ben:1, Dave:1和來自Cathy的：
date = Thursday vclock = Alice:1, Ben:1, Cathy:1, Dave:2這樣，Alice她可以說Dava與Cathy一致修改了自己和Ben的提議，並將Cathy的消息給Ben，Ben就知道它的提議已經被修改。
現在，它們愉快的達成了一致。對於整個協商的過程，可以看到衝突的根源在於Ben和Cathy都「同時」修改了Alice的數據，Dave解決了數據衝突（不同問題，解決數據衝突的方法不同），最後它們達成一致。
參考文檔：
Vector clock
Dynamo: Amazon』s Highly Available Key-value Store
分佈式系統：向量時鐘(部分內容翻譯自上文)
Why Vector Clocks Are Hard
時鐘向量在一致性問題中的應用(部分內容翻譯自上文)
Timestamps in Message-Passing Systems That Preserve the Partial Ordering
公眾號：
