向量時鐘算法簡介

向量時鐘算法簡介

一、使用背景

先說一下需要用到向量時鐘的場景。我們在寫數據時候，經常希望數據不要存儲在單點。如db1，db2都可以同時提供寫服務，並且都存有全量數據。而client不管是寫哪一個db都不用擔心數據寫亂問題。但是現實場景中往往會碰到並行同時修改。導致db1和db2數據不一致。於是乎就有人想出一些解決策略。向量時鐘算是其中一種。簡單易懂。但是並沒有徹底解決沖突問題，現實分布式存儲補充了很多額外技巧。

這裡反向敘述方式,介紹向量時鐘。先舉實際例子讓讀者有個感性認識，然後再說算法規則。

二、舉個例子

向量時鐘實際是一組版本號（版本號=邏輯時鐘)，假設數據需要存放3份，需要3台db存儲（用A，B，C表示），那麼向量維度就是3，每個db有一個版本號，從0開始，這樣就形成了一個向量版本 [A:0, B:0, C:0];
Step1： 初始狀態下，所有機器都是 [A:0,B:0, C:0]；

DB_A——> [A:0, B:0, C:0]

DB_B——> [A:0, B:0, C:0]

DB_C——> [A:0, B:0, C:0]

Step 2: 假設現在應用是一個商場，現在錄入一個腎6的價格 iphone6 price 5888； 客戶端隨機選擇一個db機器寫入。現假設選擇了A。,數據大概是這樣 ：
{key=iphone_price; value=5888; vclk=[A:1,B:0,C:0]}

Step 3: 接下來A會把數據同步給B和C；於是最終同步結果如下

DB_A——> {key=iphone_price; value=5888; vclk=[ A:1,B:0,C:0]}

DB_B——> {key=iphone_price; value=6888; vclk=[ A:1, B:0,C:0]}

DB_C——> {key=iphone_price; value=5888; vclk=[ A:1,B:0,C:0]}

Step 4：過了分鐘，價格出現波動，升值到6888；於是某個業務員更新價格。這時候系統隨機選擇了B做為寫入存儲，於是結果看起來是這樣：

DB_A——> {key=iphone_price; value=5888; vclk=[A:1,B:0,C:0]}

DB_B——> {key=iphone_price; value=6888; vclk=[A:1,B:1,C:0]}

DB_C——> {key=iphone_price; value=5888; vclk=[A:1,B:0,C:0]}

Step 5：於是B就把更新同步給其他幾個存儲

DB_A——> {key=iphone_price; value=6888; vclk=[A:1, B:1,C:0]}

DB_B——> {key=iphone_price; value=6888; vclk=[A:1,B:1,C:0]}

DB_C——> {key=iphone_price; value=6888; vclk=[A:1, B:1,C:0]}

到目前為止都是正常同步，下面開始演示一下不正常的情況。

Step 6：價格再次發生波動，變成4000，這次選擇C寫入：

DB_A——> {key=iphone_price; value=6888; vclk=[A:1,B:1,C:0]}

DB_B——> {key=iphone_price; value=6888; vclk=[A:1,B:1,C:0]}

DB_C——> {key=iphone_price; value=4000; vclk=[A:1,B:1,C:1]}

Step 7: C把更新同步給A和B，因為某些問題，只同步到A，結果如下：

DB_A——> {key=iphone_price; value=4000; vclk=[A:1,B:1, C:1]}

DB_B——> {key=iphone_price; value=6888; vclk=[A:1,B:1,C:0]}

DB_C——> {key=iphone_price; value=4000; vclk=[A:1,B:1,C:1]}

Step 8：價格再次波動，變成6000元，系統選擇B寫入

DB_A——> {key=iphone_price; value=6888; vclk=[A:1,B:1, C:1]}

DB_B——> {key=iphone_price; value=6000; vclk=[A:1,B:2, C:0]}

DB_C——> {key=iphone_price; value=4000; vclk=[A:1,B:1,C:1]}

Step 9： 當B同步更新給A和C時候就出現問題了，A自己的向量時鐘是 [A:1, B:1, C:1]， 而收到更新消息攜帶過來的向量時鐘是 [A:1,B:2, C:0], B:2 比 B:1新，但是C:0卻比C1舊。這時候發生不一致沖突。不一致問題如何解決？向量時鐘策略並沒有給出解決版本，留給用戶自己去解決，只是告訴你目前數據存在沖突。

三、規則介紹

版本號變更規則其實就2條，比較簡單

1、每次修改數據，本節點的版本號 加1，例如上述 step 8中 向B寫入，於是從B:1 變成 B:2, 其他節點的版本號不發生變更。

2、每次同步數據(這裡需要注意，同步和修改是不一樣的寫操作哦), 會有三種情況：

a： 本節點的向量版本都要比消息攜帶過來的向量版本低（小於或等於）如本節點為 [A:1, B:2,C:3]}， 消息攜帶過來為 [A:1, B:2,C:4] 或 [A:2, B:3,C:4]等。 這時候合並規則取每個分量的最大值。

b:本節點的向量版本都要比比消息攜帶過來的向量版本高，這時候可以認為本地數據比同步過來的數據要新，直接丟棄要同步的版本。

c:出現沖突，如上述step 9中，有的分量版本大，有的分量版本小，無法判斷出來到底誰是最新版本。就要進行沖突仲裁。

四、沖突解決

其實沒有一個比較好的解決沖突的版本：就筆者目前所了解，加上時間戳算是一個策略。具體方法是再加一個維度信息：數據更新的時間戳（timestamp）。[A:1, B:2,C:4，ts:123434354] ，如果發生沖突，再比較一下兩個數據的ts，大的數值說明比較後更新，選擇它作為最終數據。並對向量時鐘進行訂正。

五、其他問題

1、向量時鐘的維數和存放數據備份數目相等，如果備份數目太多。會導致向量太長。不過目前好像不會存在這個問題，一般備份數目=3就足夠。即使再多幾份，也不會太長。
2、 沖突糾錯時，矯正方有很多：有的放在後台服務端矯正，有的交給客戶端來矯正，譬如客戶端仲裁後，寫回服務端。糾錯時機也有很多，有點在讀數據是發現數據不一致進行糾正，有的是同步時候發現不一致糾正。實際實現大家自己選擇。