關於時間和事件定序

時間就是過去、現在、將來的一系列事件的集合，如果世界是靜止的，時間就沒有意義。如果我們將事件看成這個世界的本質，那麼[1]裡面提到的happen before就意義非凡，在這種場景下，時間並不重要，事件定序才是第一需求。

定序有兩種基本思路，一種是假設世界存在一個絕對的物理時間（這玩意是否存在我不確定，似乎只是人類賦予的一個符號），永遠以勻速向前推進，且所有發生事件的主體都可以獲得這個時間，這樣所有的事件也自然而然在時間軸上獲得了自己的位置，定序十分簡單。然而獲得或者模擬這樣一個抽象的物理時間是一件複雜的事情，在實際實現的時候可以做一定的弱化處理。

思路一，在一個小的系統裡面，自己定義一個時鐘源，所有主體在send/local/receive事件發生時都向這個時鐘源獲得時間，一些分散式系統採用了這種機制，簡單直接。這個時鐘源可以發出邏輯信號，比如1 2 3(Logical Clock, [1])，也可以同時考慮物理信號（Hybrid Logical Clock. [2]. 比起LC，HLC給時鐘賦予了一定的自然意義，其分配的時鐘跟物理時鐘的偏差被控制在一定範圍內，易於理解或者與外部系統對接）。這種架構中，單點帶來的性能、可用性、運維效率等問題，需要額外的機制解決（系統裡面特殊的角色越少越好，最終會不會演進到share nothing成為主流呢？也很難，在某一個層次上有一個或者多個協調者更符合一般認知）。

思路二，在基礎雄厚的大公司，可以直接模擬絕對時間，比如原子鐘以及在此基礎上形成的時間同步系統。這套機制建立起來後，可以承擔一個分布在廣泛地理區域的，龐大複雜的分散式系統的定序問題，為分散式系統的實現奠定基礎。目前似乎只有Spanner的TT公開發表過。

思路三，直接從本質出發，絕對時間是為了解決定序的，所以可以繞開絕對時間考慮其他思路，比如相對時間。在這個思路下，為每個事件主體分配獨立遞增的時鐘源，然後在相互作用的主體之間分享各自的時鐘源狀態，最終將能夠對所有相關事件進行排序。而那些不相關事件，可以通過對事件主體定序（比如ID排序）從而解決定序問題。通過這種思路，我們一樣能夠得到所有事件的序，那麼絕對時間就不是必要的了。在這個系統裡面，各個主體的獨立性是最強的（只有在需要的時候才跟其他主體發生作用），也意味著系統擴展性是最好的。不過必須認識到，如果系統裡面太多的主體之間發生相互作用，就會導致每個主體維護其他主體時鐘狀態的開銷十分可觀。Vector clock是這種思想的一個產物，其複雜性也反映了這種思路的複雜性[3]。對於這種複雜性，解決思路一般是想辦法減少參與主體的個數，或者想辦法丟棄一部分歷史狀態。但是反過來想，如果我們的某個系統要求高擴展性，且參與主體個數可控，歷史狀態簡單（比如線性），這種思路不失為一個好的備選項。

對分散式系統有了一點認識之後，回來再看一些說法，也很值得玩味。

A system is distributed if the time it takes to send a message from one process to another is significant compared to the time interval between events in a single process. [1]. 隨著網路越來越快，分散式系統是否可能出現新的特徵?

The term partial is used to indicate that it is not necessary for any two elements of the set to be related in some way. [1]. 偏序的抽象定義。具體一點可以說，存在兩個事件，其序不可比。全序就是在此基礎上加一個約束，所有的事件，其序都可比。

The causality rela- tionship captured (by LC), called happened-before (hb), is defined based on passing of information, rather than passing of time. [2]. 本質是事件。

The reason for seeing very low l - pt and c values in the WAN deployment is because the message communication delays across WAN are much larger than the e, the clock synchronization uncertainty. [2]. 試驗分析。隨著網路越來越快，這個試驗結果會變，可能導致c佔用更多的bit，雖然不影響正確性，可能影響可用性（等待新時鐘）。對於新系統，是否一開始就分離pt和c更好？

[1]. Time, Clocks, and the Ordering of Events in a Distributed System

[2]. Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases

[3]. http://basho.com/posts/technical/why-vector-clocks-are-hard/

[4]. 封面圖來自[1]

推薦閱讀：