向量时钟算法简介
向量时钟算法简介
一、使用背景
先说一下需要用到向量时钟的场景。我们在写数据时候,经常希望数据不要存储在单点。如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、 冲突纠错时,矫正方有很多:有的放在后台服务端矫正,有的交给客户端来矫正,譬如客户端仲裁后,写回服务端。纠错时机也有很多,有点在读数据是发现数据不一致进行纠正,有的是同步时候发现不一致纠正。实际实现大家自己选择。

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

最近幾天,Ice Universe 不斷披露有關 Galaxy S25 Ultra 的詳細信息,人們普遍認為這款手機將是三星的下一款旗艦智慧型手機。除此之外,洩密者聲稱三星只計劃升級一台相機

OnLeaks 現在與 Android Headlines 合作,首次展示了 Galaxy S25 Ultra,幾天前,他試圖從他的 X(以前的 Twitter)粉絲那裡籌集到 4,000 美元以上的資金,但失敗了。對於上下文,嵌入在 h 下面的渲染圖像

除了發布兩款新智慧型手機外,TCL 還發布了一款名為 NXTPAPER 14 的新 Android 平板電腦,其大螢幕尺寸是其賣點之一。 NXTPAPER 14 採用 TCL 標誌性品牌霧面液晶面板 3.0 版本

Vivo Y300 Pro剛剛全面亮相,它是最薄的中階Android手機之一,配備大電池。準確來說,這款智慧型手機厚度僅為 7.69 毫米,但配備 6,500 mAh 電池。這與最近推出的容量相同

三星尚未就何時更新其 Fan Edition (FE) 智慧型手機系列提供任何提示。目前來看,Galaxy S23 FE 仍然是該公司的最新版本,於 2023 年 10 月年初推出。

最近幾天,Ice Universe 不斷披露有關 Galaxy S25 Ultra 的詳細信息,人們普遍認為這款手機將是三星的下一款旗艦智慧型手機。除此之外,洩密者聲稱三星只計劃升級一台相機

Redmi Note 14 Pro Plus 現已正式成為去年 Redmi Note 13 Pro Plus 的直接後繼產品(亞馬遜售價 375 美元)。正如預期的那樣,Redmi Note 14 Pro Plus與Redmi Note 14和Redmi Note 14 Pro一起成為Redmi Note 14系列的主角。李

摩托羅拉今年發布了無數設備,儘管其中只有兩款是可折疊的。就上下文而言,雖然世界上大多數地區都收到了 Razr 50 和 Razr 50 Ultra,但摩托羅拉在北美提供了 Razr 2024 和 Razr 2
