分散式系統理論基礎 - 時間、時鐘和事件順序

十六號…… 四月十六號。一九六零年四月十六號下午三點之前的一分鐘你和我在一起，因為你我會記住這一分鐘。從現在開始我們就是一分鐘的朋友，這是事實，你改變不了，因為已經過去了。我明天會再來。

—— 《阿飛正傳》

現實生活中時間是很重要的概念，時間可以記錄事情發生的時刻、比較事情發生的先後順序。分散式系統的一些場景也需要記錄和比較不同節點間事件發生的順序，但不同於日常生活使用物理時鐘記錄時間，分散式系統使用邏輯時鐘記錄事件順序關係，下面我們來看分散式系統中幾種常見的邏輯時鐘。

物理時鐘 vs 邏輯時鐘

可能有人會問，為什麼分散式系統不使用物理時鐘(physical clock)記錄事件？每個事件對應打上一個時間戳，當需要比較順序的時候比較相應時間戳就好了。

這是因為現實生活中物理時間有統一的標準，而分散式系統中每個節點記錄的時間並不一樣，即使設置了 NTP 時間同步節點間也存在毫秒級別的偏差[1][2]。因而分散式系統需要有另外的方法記錄事件順序關係，這就是邏輯時鐘(logical clock)。

Lamport timestamps

Leslie Lamport 在1978年提出邏輯時鐘的概念，並描述了一種邏輯時鐘的表示方法，這個方法被稱為Lamport時間戳(Lamport timestamps)[3]。

分散式系統中按是否存在節點交互可分為三類事件，一類發生於節點內部，二是發送事件，三是接收事件。Lamport時間戳原理如下：

圖1: Lamport timestamps space time (圖片來源: wikipedia)

1. 每個事件對應一個Lamport時間戳，初始值為0
2. 如果事件在節點內發生，時間戳加1
3. 如果事件屬於發送事件，時間戳加1並在消息中帶上該時間戳
4. 如果事件屬於接收事件，時間戳 = Max(本地時間戳，消息中的時間戳) + 1

假設有事件a、b，C(a)、C(b)分別表示事件a、b對應的Lamport時間戳，如果C(a) < C(b)，則有a發生在b之前(happened before)，記作 a -> b，例如圖1中有 C1 -> B1。通過該定義，事件集中Lamport時間戳不等的事件可進行比較，我們獲得事件的偏序關係(partial order)。

如果C(a) = C(b)，那a、b事件的順序又是怎樣的？假設a、b分別在節點P、Q上發生，Pi、Qj分別表示我們給P、Q的編號，如果 C(a) = C(b) 並且 Pi < Qj，同樣定義為a發生在b之前，記作 a => b。假如我們對圖1的A、B、C分別編號Ai = 1、Bj = 2、Ck = 3，因 C(B4) = C(C3) 並且 Bj < Ck，則 B4 => C3。

通過以上定義，我們可以對所有事件排序、獲得事件的全序關係(total order)。上圖例子，我們可以從C1到A4進行排序。

Vector clock

Lamport時間戳幫助我們得到事件順序關係，但還有一種順序關係不能用Lamport時間戳很好地表示出來，那就是同時發生關係(concurrent)[4]。例如圖1中事件B4和事件C3沒有因果關係，屬於同時發生事件，但Lamport時間戳定義兩者有先後順序。

Vector clock是在Lamport時間戳基礎上演進的另一種邏輯時鐘方法，它通過vector結構不但記錄本節點的Lamport時間戳，同時也記錄了其他節點的Lamport時間戳[5][6]。Vector clock的原理與Lamport時間戳類似，使用圖例如下：

圖2: Vector clock space time (圖片來源: wikipedia)

假設有事件a、b分別在節點P、Q上發生，Vector clock分別為Ta、Tb，如果 Tb[Q] > Ta[Q] 並且 Tb[P] >= Ta[P]，則a發生於b之前，記作 a -> b。到目前為止還和Lamport時間戳差別不大，那Vector clock怎麼判別同時發生關係呢？

如果 Tb[Q] > Ta[Q] 並且 Tb[P] < Ta[P]，則認為a、b同時發生，記作 a <-> b。例如圖2中節點B上的第4個事件 (A:2，B:4，C:1) 與節點C上的第2個事件 (B:3，C:2) 沒有因果關係、屬於同時發生事件。

Version vector

基於Vector clock我們可以獲得任意兩個事件的順序關係，結果或為先後順序或為同時發生，識別事件順序在工程實踐中有很重要的引申應用，最常見的應用是發現數據衝突(detect conflict)。

分散式系統中數據一般存在多個副本(replication)，多個副本可能被同時更新，這會引起副本間數據不一致[7]，Version vector的實現與Vector clock非常類似[8]，目的用於發現數據衝突[9]。下面通過一個例子說明Version vector的用法[10]：

圖3: 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個數據版本，通過類似Vector clock判斷同時發生關係的方法可判斷D3、D4存在數據衝突，最終通過一定方法解決數據衝突並寫入D5

Vector clock只用於發現數據衝突，不能解決數據衝突。如何解決數據衝突因場景而異，具體方法有以最後更新為準(last write win)，或將衝突的數據交給client由client端決定如何處理，或通過quorum決議事先避免數據衝突的情況發生[11]。

由於記錄了所有數據在所有節點上的邏輯時鐘信息，Vector clock和Version vector在實際應用中可能面臨的一個問題是vector過大，用於數據管理的元數據(meta data)甚至大於數據本[12]。

解決該問題的方法是使用server id取代client id創建vector (因為server的數量相對client穩定)，或設定最大的size、如果超過該size值則淘汰最舊的vector信息[10][13]。

小結

以上介紹了分散式系統里邏輯時鐘的表示方法，通過Lamport timestamps可以建立事件的全序關係，通過Vector clock可以比較任意兩個事件的順序關係並且能表示無因果關係的事件，將Vector clock的方法用於發現數據版本衝突，於是有了Version vector。

[1] Time is an illusion, George Neville-Neil, 2016

[2] There is No Now, Justin Sheehy, 2015

[3] Time, Clocks, and the Ordering of Events in a Distributed System, Leslie Lamport, 1978

[4] Timestamps in Message-Passing Systems That Preserve the Partial Ordering, Colin J. Fidge, 1988

[5] Virtual Time and Global States of Distributed Systems, Friedemann Mattern, 1988

[6] Why Vector Clocks are Easy, Bryan Fink, 2010

[7] Conflict Management, CouchDB

[8] Version Vectors are not Vector Clocks, Carlos Baquero, 2011

[9] Detection of Mutual Inconsistency in Distributed Systems, IEEE Transactions on Software Engineering , 1983

[10] Dynamo: Amazon』s Highly Available Key-value Store, Amazon, 2007

[11] Conflict Resolution, Jeff Darcy , 2010

[12] Why Vector Clocks Are Hard, Justin Sheehy, 2010

[13] Causality Is Expensive (and What To Do About It), Peter Bailis ,2014