分散式資料庫中為什麼要使用 Vector Clock？
在一些分散式資料庫中，如Dynamo，Project Voldemort，為了控制同一record的不同版本，常常會使用Vector Clock這樣的概念。我想問問如果僅僅需要知道不同版本的同一record之間的先後順序，是否可以簡單地使用timestamp（也就是該版本創建的時間）來進行相應的控制。同時在分散式系統中使用時間戳是否是一個好的選擇（在不同的節點中時間是否可以精確地同步？這樣的方式的效率如何？）
Vector Clock是邏輯時鐘的一種實現方式，最早這個概念由Leslie Lamport (神一般的存在，最近一次圖靈獎得主)在1978年發表的一篇論文《Time, Clocks, and the Ordering of Events in a Distributed System》（http://research.microsoft.com/en-us/um/people/lamport/pubs/time-clocks.pdf）提出的，目的是在不依賴於物理時鐘確定在離散系統中各個events的發生次序（文中稱為happen-before），並且基於這種兩兩event之間的先後次序推導出多個process上發生的各個event的整體次序關係（Total Ordering）。所以這種邏輯時鐘實現同步的方式也叫Lamport Timestamp，區別於物理timestamp。
比如說，在分散式系統中的一個process上的event B和另外一個process上的event A有數據交換（如果兩個event不用communicate那就可以不用管了。。。），那麼如果B需要A的信息，則稱A happened-before B， 以此類推根據這樣兩兩關係可以得出相關events的所有次序甚至是整個系統中這些events的總次序（Total Order）。
當然，這樣的總次序未必是唯一的，因為系統中總有各種並發的事件，不過對於這種不存在數據交換的event，次序不一樣也不會有什麼影響。
2015年11月22日更新:關於Vector Clock的話題，專門寫了篇blog
Vector Clock/Version Clock
=======================================================
首先Vector Clock在Dynamo中是為了解決衝突的，為了解決last write win導致的寫丟失問題。具體 @fleuria 已經說了。
然後說說問題中的record之間的先後順序問題
對於一個資料庫系統來說，需要有一種機制來界定事務或者操作的先後順序。
1. 如果是單機資料庫，事務提交的時候獲取時間戳作為事務ID，誰先提交誰的時間戳就小。Oracle就是這麼乾的。
2. 如果是一個分散式資料庫呢，由於1.0版本之前的OceanBase實際上是單點寫，也就是說事務ID是在同一個節點上獲得，和第1點類似。所以本質上，如果一個資料庫需要Vector Clock，那麼這個數據一定是一個支持多點寫的資料庫，Dynamo就是這樣。
既然多點寫，那麼機器和機器之間必然存在時鐘誤差。事務時間戳從不同的機器上獲得，那麼必然會存在在wall time上先提交的事務最後得到的事務ID(時間戳)反而更小! 如何解決這個問題?Spanner提供TrueTime API，你可以認為這個就是一個全局時鐘，就是從一台機器上獲得的，只不是這個API的返回值不是一個具體的值，而是一個區間，保證真實的wall time在這個區間中。有了這個API加上一些wait機制，就可以給所有的事務進行定序。Spanner的這個做法沒有利用任何的happens-before關係，和純粹的Vector Clock是兩個極端。
and Consistent Snapshots in Globally Distributed Databases 這篇文章將邏輯時鐘和物理時鐘結合起來，將誤差控制在NTP誤差內。
請閱讀Riak開發者所寫一下文檔
Why Vector Clocks are Easy
Why Vector Clocks Are Hard
Vector Clocks Revisited
分散式系統的本地操作和數據交換當做事件，則理想系統中，事件時間上的先後關係和因果關係如果是全序，則系統中的進程按照全序關係執行處理事件，很容易達成一致。實際的情況是， 進程存在空間隔離、時鐘漂移、網路延遲等原因導致事件的全序關係(注意，不能採用中央協調的方式)難以確定，其他答主提及Lamport的論文Time, Clocks and the Ordering of Events in a Distributed System，對此進行詳細對確定事件的順序進行了詳細的表述，可以細心研讀。
實際上我們可以通過Lamport clock和Vector clock獲得事件的偏序關係， 不存在偏序關係的兩個事件為並發。其實，dynamo，Riak用到的演算法為version vector。 如果多個用戶並發地修改存儲在多節點上的需要保持某種約束的一組數值，而且只能有一個成功，怎麼處理這種問題? 需要檢查寫寫衝突！ version vector就是一種檢測寫寫衝突的演算法，如果並發事務存在寫寫衝突，可以按照一定的策略只讓一個事務commit，其他事務rollback。 我貼出的三篇文檔已經給出了詳細的實例，此處不在贅述了。 建議看看分散式事務，STM， spanner等相關知識。似乎 riak 和 cassandra 應用 vector clock 的效果並不是很好。甚至，cassandra 後來乾脆用上了 ntp 同步的物理時間： Why Cassandra doesn』t need vector clocks
- vector clock 要求每次請求前先向對方拿一次版本，這個性能不大好接受；
- 只能幫助發現衝突，但對解衝突沒有幫助，如果並發地修改了兩個不同的欄位，vector clock 只能告訴你整個紀錄有衝突，不能精確到欄位；
- riak 那個人工合併衝突的 siblings 機制比較殘，解衝突的速度一旦跟不上並發更新的速度（這是肯定的事），就炸了...
這樣反過來看，ntp 同步的系統時間也沒有那麼差：
- 多數時間裡都是好的；
- 足夠拿來發現衝突，不準的 last write wins 也是 last write wins；
- cassandra 的並發控制以列為單位，相比以整個記錄為單位，衝突更容易合併；
- 對於有 linearizability 需求的場景，請一律使用 lightweight transaction 走一個 paxos 協調做 CAS 的樂觀並發控制；
這意味著如果不用 lightweight transaction，cassandra 是不能保證 linearizability 的，也就是會丟寫，如果一個節點的時鐘不同步，慢了幾秒，這個節點跟人衝突時就永遠寫不進東西了。
前面的回答說得已經很明白了。補充一下，dynamo paper是七、八年前寫的了，現在的amazon dynamo早已摒棄了version vector，而採用了synchronous replication（類似paxos的protocol）,每一個partition會有一個leader負責寫入。其實version vector並不scale，因為對於一個key來說，隨著writer數量的增加，version vector數量成指數級的增長。
像vector clock這類logic clock都是為了解決分散式系統中因為multi-master引入的同步問題.只要一個系統存在多點寫入就會需要考慮這類問題(一個反例是DNS系統,屬於典型的single -master).
首先先回答,物理時鐘是否可以?答案是不行,因為無法做到絕對的同步,依賴NTP在區域網可以做到微妙級別的lag,在廣域網可能在毫秒級別,這個級別的時鐘差異依然會帶來對衝突的誤判.所以大牛們引入了logic clock的概念.
vector clock是其中的一種,並且是目前被證明的能精確進行衝突檢測的最有效的數據結構(有沒有更有效的?答案是有,後面會介紹,但是精確度會下降).它的原理就是所有允許寫入的節點維護一個counter,每次本地提交的動作會導致value+1並把這個值由本次操作攜帶,同步到其他節點去.遠端節點在收到請求後也會為該操作分配一個本節點最新的counter.所以某個操作會在N-master集群中得到一個N個值的數組,只有當所有節點上的操作A的counter都小於對應節點上操作B的counter的時候才認為他們具有明確的happen-before,否則視為衝突.
而我們所說的Lamport clock是一種scalar clock,可以決定時序,但是任何的scalar clock並不能檢測衝突.因為counter(A)&
沒那麼複雜。。
其實這裡有個關鍵的問題就是讀寫順序問題。
對於一份共享的數據，我們對他能做的操作就兩個，第一個是寫，第二個是讀。 這兩個操作有四種組合，寫寫，讀讀，讀寫，寫讀。
如何能夠在保證語義不變的前提下，讓用戶看起來是有正確的讀寫順序關係的？ 這就是所有一致性演算法要解決的共性問題。
包含vector clock . 你可以嘗試把上面的內容帶入進去看看？：）
詳細內容可以見我的博客中的一致性專題 沈詢所有資源的索引（會不斷更新）一般對於普通的分散式系統來說，時間戳是可用的，通過NTP等協議可以保證一個機房內的集群時鐘是同步的，誤差在幾百個ns，這樣對於大部分應用而言定序也夠了。但對於dynamo系列的分散式資料庫而言，它最大的特點就是解決跨機房的分區問題，重點就是「跨機房」寫事務的高可用性，目前還沒有什麼措施來控制多機房時鐘同步誤差。利用GPS原子鐘是一個可行的方法，Google的最新分散式存儲Spanner里用到了。
當然可以，但是不適合在分散式資料庫裡面。為什麼呢？ 首先，需要先確定你這個時間戳取自哪裡。1、所有的時間戳都取自一個中心點節點，這樣讓時間戳得到一個全序關係，這是最簡單的實現，如果你的分散式資料庫只是部署在一個數據中心的話，但是這樣就增加了一個中心節點，影響資料庫的擴展性，而且任何一個取時間戳的動作都要增加上網路延遲的開銷。如果分散式資料庫部署需要跨數據中心，這種方案變的不可行，跨數據中心網路時延太大。從而影響整體性能2、所有的時間戳取自已所在的節點。這就涉及到時鐘同步的問題，就像Dongdong說的，如果取的物理時間那麼這些節點並沒有一個一致的時間，總會有一點誤差，這種解決方案就有兩種思路：
一、就是現在以Leslie Lamport 提出的邏輯時鐘的方法，重新定義了一種分散式的全序關係。vector clock就是以邏輯時鐘為基礎上發展而來的。
二、使用物理時鐘，就是google spanner使用gps 加原子鐘進行時間同步，不同節點之間的時間是不能精確同步的，只能把不同節點之間的時間同步到一個範圍之內，spanner一個節點上獲得一個時間戳，不是一個時間值，而是一個時間值加上一個誤差範圍，也就是一個時間窗，如果兩個時間窗有重合，就無法比較大小，從而無法比較出來時間窗代表的事件的先後關係。而時間同步演算法就是讓分散式各節點之間的時間的誤差盡量的小，這樣取時間戳這個動作效率是最高的，只在本節點取一下物理時間即可，但是為了同步時間，各個節點肯定在周期與其它節點進行通訊來同步物理時間（google時間同步的演算法好像沒有開源）。時間同步演算法只能讓時間盡量的精確。分散式資料庫裡面是不能直接使用NTP來同步時間的，因為NTP時間同步協議裡面允許節點的時間能夠回退，而資料庫裡面要求本地的時鐘必須是遞增的。
and Consistent Snapshots in Globally Distributed Databases這篇論文
很簡單，既然是分散式系統，你無法保證集群中的每台機器的時間都是一樣的（有的快幾分鐘，有的慢幾分鐘），所以，如果你想通過時間戳來區分一條record的先後順序，顯然不是很精確的。
點一下vector clock跟其他方案的核心區別
vector clock核心是講是非同步網路下的方案，而且偏重理論，並不是很好的工程化方案，其他方案（Timestamp、原子鐘）都是同步網路下的解決方案，而且比較好工程化。
真實的無約束的網路是非同步網路，我們可以添加一些約束使是變成同步網路。現在多數實踐也是這麼做的，比如機器上安裝原子鐘，上ntp校時等。
就像你中學物理學到的那些知識都是理想情況下的理論，真正到了工程實踐（蓋房，造車）還是有很多變通的。標量邏輯時鐘就是你說的timestamp或者單調遞增的邏輯時鐘，只能保證事件在分散式系統中的半序，所以實際上它能區分有因果關聯的事件的序，但是不能確定沒有因果關係的事件間的序。
而向量邏輯時鐘是全序的。
缺點是向量邏輯時鐘消息體量大，開銷大，沒有和本地時間的對照關係等
hlc很好的解決這個問題
推薦閱讀：