向量時鐘的本質

　　分布式系統中有兩大問題：一沒有全局時鐘，二沒有共享記憶體。很多時候我們都需要引入時間的概念，譬如來确定事件之間的順序和因果關系。那分布式系統中既然沒有全局的時鐘，我們又該如何确定事件的順序呢?

　　PS：不需要背景介紹的讀者可以直接跳到後面講因果曆史的部分。

　　1

　　邏輯時間與Lamport Timestamp

　　Leslie Lamport在其1978年著名的論文《Time, clocks, and the ordering of events in a distributed system》中提出了邏輯時間，即用一個整數來表示一個事件的邏輯時間，以及happened-before 順序。可以總結如下：

　　簡而言之，每個線程都用一個integer來simulate它自己的時間，對于本地事件或者消息的發送和接收按照以下規則來更新時間。

　　每一次發生本地事件，該線程的時間+=1

　　每一次發送消息，發送的線程的時間先+=1，然後再發送。發送的消息中會包含它的時間

　　每一次接收消息，接收的線程先擷取消息中帶有的時間，再和它自己的local時間對比，取最大值後，再+=1作為自己新的local時間

　　這種更新時間的方式稱為Lamport timestamp或者Lamport clock。它的确為整個系統定義了一個全序(total order)，但是它沒有說明事件是否concurrent，根據Lamport的論文，concurrent的定義是：

　　即事件a和b的時間戳沒有happened-before關系，無法比較。這就是一個偏序(partial order)，但是上述的Lamport timestamp算法沒有辦法表示偏序，即(引用維基百科一段話)

　　即，根據C(a) < C(b)，我們并不能完全infer出a和b的happened-before關系。

　　2

　　向量時鐘

　　向量時鐘(Vector Clock)其實是Lamport clock的一種很自然的extension了，其定義的是偏序而不是全序，于是可以表示concurrent的關系，據考證類似概念最早由Rivka

Ladin和Babara Liskov于1986年提出，vector clock由Colin Fidge和Friedemann

Mattern于1988年左右首次使用。Vector Clock可以總結如下：

　　Vector clock的更新方法和Lamport clock類似，差別在于現在每個線程需要維護一個vector來記錄它眼中每一個線程(包括它自己)的時間。然後發送消息的時候，整個vector都要包含在消息裡。接收消息的時候，把自己的local時間+=1，然後對于vector中的其他每一個項都需要用上述max的辦法更新，以擷取其他線程最新的時間。

　　這裡的重點在于上面圖檔中的等價符号<=>，=>的部分是顯然的(根據VC更新的規則)，但是<=的部分是如何證明的呢?即，是否存在當V(e) < V(f)的時候，e和f之間并沒有happened-before關系?

　　這個證明我個人覺得并沒有那麼顯然，需要一番思考，但是假如我們從Causal history的角度來看就明顯多了。

　　3​​鄭州無痛人流醫院​​​​http://sg.zztj120.com/​​

　　因果曆史(Causal History)

　　因果曆史是檢查因果關系的一個直覺的方法。每個線程維護一個集合，然後每次碰到local event，給這個event一個名字，然後加入到集合中。每次發送消息則發送自己的集合，每次接收消息則合并消息的集合。下圖是一個例子：

　　此時，要知道兩個event之間的因果關系或者happened-before關系，隻需要看他們對應的集合是否一個包含另一個，即set inclusion test。