分布式系統理論基礎3： 時間、時鐘和事件順序

轉自：https://www.cnblogs.com/bangerlee/p/5448766.html

本系列文章将整理到我在GitHub上的《Java面試指南》倉庫，更多精彩内容請到我的倉庫裡檢視

https://github.com/h2pl/Java-Tutorial

喜歡的話麻煩點下Star哈

文章首發于我的個人部落格：

www.how2playlife.com

該系列博文會告訴你什麼是分布式系統，這對後端工程師來說是很重要的一門學問，我們會逐漸了解分布式理論中的基本概念，常見算法、以及一些較為複雜的分布式原理，同時也需要進一步了解zookeeper的實作，以及CAP、一緻性原理等一些常見的分布式理論基礎，以便讓你更完整地了解分布式理論的基礎，為後續學習分布式技術内容做好準備。

如果對本系列文章有什麼建議，或者是有什麼疑問的話，也可以關注公衆号【Java技術江湖】聯系作者，歡迎你參與本系列博文的創作和修訂。

<!-- more -->

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

    —— 《阿飛正傳》

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

實體時鐘 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上發生，P_i、Q_j分别表示我們給P、Q的編号，如果 C(a) = C(b) 并且 P_i<Q_j，同樣定義為a發生在b之前，記作 a => b。假如我們對圖1的A、B、C分别編号A_i = 1、B_j = 2、C_k = 3，因 C(B4) = C(C3) 并且 B_j < C_k，則 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分别為T_a、T_b，如果 T_b[Q] > T_a[Q] 并且 T_b[P] >= T_a[P]，則a發生于b之前，記作 a -> b。到目前為止還和Lamport時間戳差别不大，那Vector clock怎麼判别同時發生關系呢？

如果 T_b[Q] > T_a[Q] 并且 T_b[P] < T_a[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端寫入資料，該請求被S_x處理并建立相應的vector ([S_x, 1])，記為資料D1
• 第2次請求也被S_x處理，資料修改為D2，vector修改為([S_x, 2])
• 第3、第4次請求分别被S_y、S_z處理，client端先讀取到D2，然後D3、D4被寫入S_y、S_z
• 第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