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