Riak?是以 Erlang 編寫的一個高度可擴展的分布式數據存儲，Riak的實現是基于Amazon的Dynamo論文，Riak的設計目標之一就是高可用。Riak支持多節點構建的系統，每次讀寫請求不需要集群內所有節點參與也能勝任。像這樣的系統，我們需要版本機制來確定哪個值是最新的。所以就引入了向量時鐘（Vector Clock）

?

當存儲一個對象到Riak時，都被打上向量時鐘標簽。通過向量空間祖先繼承的關系比較，Riak可以自動的修復不同步的值，使數據保持最終一致性。

向量時鐘的作用

有個比較經典的例子，說明向量時鐘的作用。假設有如下場景：

Alice、Ben、Catby和Dave四人約定下周一起聚餐，四個人通過郵件商量聚餐的時間。 Alice首先建議周三聚餐。 之后Dave和Catby商量覺得周四更合適。 后來Dave又和Ben商量之后覺得周二也行。 最后Alice要匯總大家的意見，得到的反饋如下： Cathy說，他和Dave商量的時間是周四 Ben說，他和Dave商量的時間是周三此時恰好聯系不上Dave，而且不知道Cathy和Ben分別與Dave確定時間的先后順序，Alice就不能確定到底該定在哪天了。

Vector Clock就是為了解決這種問題而設計的，簡單來說，就是為每個商議結果加上一個時間戳，當結果改變時，更新時間戳。所以加上時間戳之后，我們再一次描述上面的場景，如下：

當Alice第一次提議將時間定為周三時，可以這樣描述信息 date = Wednesday vclock = Alice:1其他三個人都收到了信息，Dave和Ben開始交流，Ben建議改成周二，把Alice的初試向量加進去標識Ben看到Alice的消息了 date = Tuesday vclock = Alice:1, Ben:1Dave回復Ben，確定周二可以 date = Tuesday vclock = Alice:1, Ben:1, Dave:1然后Cathy開始說話，也和Dave說建議周四，此時在Dave看來就收到了兩個數據如下： date = Tuesday vclock = Alice:1, Ben:1, Dave:1date = Thursday vclock = Alice:1, Cathy:1 這兩份數據，各自都不是互相的祖先，所以就產生了沖突，Dave要自動解決這個沖突，他選擇了周四，然后將消息改成如下，繼承來自Dave現在收到的兩條消息，這個消息發回給Cathy date = Thursday vclock = Alice:1, Ben:1, Cathy:1, Dave:2最后來了，Alice只問Ben和Cathy最后的決定： Ben說 date = Tuesday vclock = Alice:1, Ben:1, Dave:1Cathy說 date = Thursday vclock = Alice:1, Ben:1, Cathy:1, Dave:2Alice就明白了，因為第二個Cathy說的是完全繼承于Ben說的，所以最后采納Cathy說的決定，周四去。

以上這個決策用到了向量時鐘，有個圖還比較清晰了說明整個過程：

?

?

向量時鐘的空間無限增長問題

以上的做法還比較完美的解決了問題，這里只列舉了四個決策者的向量時鐘，不過在現實生活中，如果有很多的決策者，相當于有很多的客戶端，整個向量時鐘的長度就無限制增長了，這對于存儲系統來說，不是一個好消息。我們需要想辦法解決。

一個直接的想法是，不要用client來標識向量空間，用server來標識向量空間，因為server的數量是可控的，這里用X，Y兩臺server來重現以上決策的過程，只是標簽不再用客戶端，而是用server標識，決策過程如下

此時Dave收到兩個消息

Tue X:2,Y:1 ?with Ben

Thu X:1,Y1 ? from Cathy （這個消息比較新）

發現后者是前者的祖先，所以自然拋棄祖先，最終最新的，這樣就悄無聲息的把Cathy給他的消息給丟了。

所以嘗試用server來做標識，以期減少向量時鐘的空間是不可取的，因為會丟數據。實際情況還是需要用客戶端的標識來做向量時鐘。

?

向量時鐘的剪枝

所以為了解決向量時鐘空間的無限增長問題，引入了向量時鐘的剪枝。

Riak用四個參數來避免向量時鐘空間的無限增長：

• small_vclock
• big_vclock
• young_vclock
• old_vclock

small_vclock和big_vclock參數標識向量時鐘的長度，如果長度小于small_vclock就不會被剪枝掉，如果長度大于big_vclock就會被剪枝掉

young_vclock和old_vclock參數標識存儲這個向量時鐘時的時間戳，剪枝策略同理，大于old_vclock的才會被剪枝掉，剪枝策略如下圖

?這樣只會丟掉一些向量時鐘的信息，即數據更新過程的信息，但是不會丟掉實實在在的數據。只有當一種情況會有問題，就是一個客戶端保持了一個很久之前的向量時鐘，然后繼承于這個向量時鐘提交了一個數據，此時就會有沖突，因為服務器這邊已經沒有這個很久之前的向量時鐘信息了，已經被剪枝掉了可能，所以客戶端提交的此次數據，在服務端無法找到一個祖先，此時就會創建一個sibling。

所以這個剪枝的策略是一個權衡tradeoff，一方面是無限增長的向量時鐘的空間，另一方面是偶爾的會有"false merge"，對，但肯定的是，不會悄無聲息的丟數據。綜上，為了防止向量時鐘空間的無限增長，剪枝還是比用server標識向量時鐘工作的更好。

?

?

參考：

http://docs.basho.com/riak/latest/theory/concepts/Vector-Clocks/

http://basho.com/why-vector-clocks-are-easy/

http://basho.com/why-vector-clocks-are-hard/

《大型網站系統與Java中間件實踐》

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的向量时钟Vector Clock in Riak的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。