简单的Vector Clock

上一篇文章中说过Dynamo为了解决数据一致性问题使用了Vector Clock。基本思想就是对同一份数据的每一次修改都加上<修改者,版本号>的标签。在搜索相关资料的时候发现了另一个有意思的项目,Riak。Riak可以说是一个类Dynamo的Erlang实现,更多相关介绍可以参考下边链接。本文来自Riak主页上的一篇blog,简单介绍Vector Clock以及在Riak中的使用。虽然名为“简单的Vector Click”,仅仅是介绍的简单。后续还有一篇“复杂的Vector Click”

Vector clock确实很简单,以至于你第一次见到它时甚至不确定能不能给你带来好处。不过只要你认真遵循vector clock的几条准则,它就一定能有效的解决你所遇到的问题。这几条简单的准则就是:1)为每一个要操纵数据的人分配一个ID;2)然后在任何时候,只要修改了数据,就一定带上自己的ID和数据原有的Vector clock。接下来先以生活中的一件事情为例解释一下这两条规则,然后我们再看看Riak中要怎么做。
假设有如下场景:

Alice,Ben,Catby,Dave四人约定下周要一起聚餐,首先四个人通过邮件商量聚餐的时间。  
Alice首先建议,周三。  
之后Deve和Catby商量觉得周四更合适。
后来Deve又和Ben商量之后觉得周二也行。
最后Alice要汇总大家的意见,得到的反馈如下:
Catby说,他和Deve商量的时间周四。  
Ben说,他和Deve商量的时间是周三。  
此时恰好联系不上Deve,而且不知道Catby和Ben分别与Deve确定时间的先后顺序。
Alice就不能确定到底该定在哪一天了。  

事情大概就是这样,而且类似的事情经常发生。当你向两个或几个人问一些消息的时候,返回的内容不一样,而且你不知道哪个是最新的。Vector Clock就是为了解决这种问题设计的,简单来说,就是为每一个商议结果附上一个时间戳,当结果改变时,更新时间戳。再一次描述这个过程如下。

当Alice第一次提议将时间定为周三时,可以这样描述这个信息:

data = Wednesday  
vclock = Alice:1  

vclock就是这条消息的Vector Clock,表示这是从Alice发出的第一个版本。接着,Dave和Ben商量将时间改为周二,Ben发给Deve的的消息如下:

data = Tuesday  
vclock = Alice:1, Ben:1  

注意Ben这条消息保留了Alice的记录,同时加上了自己的记录。1代表这是Ben第一次修改的记录。接着Deve收到Ben的消息,并同意将时间改为周二,他回给Ben的消息如下:

data = Tuesday  
vclock = Alice:1, Ben:1, Deve:1  

这条消息同样保留了原来的vclock记录,同时加上自己的记录。

另一方面,Catby收到Alice的消息,打算与Deve商量将时间改为周四,于是他发送如下消息给Deve:

data = Thursday  
vclock = Alice:1, Catby:1  

这里你可能会奇怪,为什么这里的vclock中没有了之前的Ben和Deve的记录了?这是因为Ben和Deve商量的时候Catby并不知道这个情况。Catby手中的信息还是Alice最初发送的那份。这样当Deve收到来自Catby的消息的时候就发现有冲突了。Deve手中的两份信息如下:

date = Tuesday  
vclock = Alice:1, Ben:1, Dave:1  
date = Thursday  
vclock = Alice:1, Catby:1  

Dave通过比对两份消息的vclock可以发现冲突。这是因为上边两个版本的vclock都不是对方的“祖先”。其中vector clock对祖先的定义是这样的:当我们说vclock A是vclock B的祖先时,当且仅当A中的每一个标记ID都存在于B中,同时A中对应的标记版本号要小于等于B。对于标记ID不存在的情况,可以认为标记版本号为0。
Dave通过对比vclock的方式发现了版本冲突,于是尝试解决冲突。两个版本中只能选择一个,于是他选择了时间为周四的,那么这条消息可以表示为:

date = Thursday  
vclock = Alice:1, Ben:1, Catby:1, Dave:2  

Dave在vclock中加上了两个消息中的全部标记ID(Alice,Ben,Catby,Dave),同时将自己对应的版本号加1。然后将这条消息发送给Catby。

最后当Alice从Catby和Ben收集反馈消息的时候(此时Dave联系不上),收到如下消息: 来自Ben的:

data = Thursday  
vclock = Alice:1, Ben:1, Dave:1  

来自Catby的:

data = Thursday  
vclock = Alice:1, Catby:1, Ben:1, Dave:2  

这时Alice从Catby的消息就可看出,Dave已经改变主意了。

Riak中是如何做的

上边的流程已经清楚了,现在看看Riak中怎么做?Riak中使用vector clock一样非常方便,下边将会使用HTTP接口来描述。

首先无论什么时候你要保存一条消息的时候,都要在HTTP头中包含“X-Riak-ClientID”字段,来作为你的标记ID。首先我们来看Alice的第一条消息:

curl -X PUT -H "X-Riak-ClientId: Alice" -H "content-type: text/plain" \  
http://localhost:8098/raw/plans/dinner --data "Wednesday"  

接着,Ben,Catby和Dave通过GET方式取得Alice的消息,他们将会得到同一份消息:

curl -i http://localhost:8098/raw/plans/dinner  
HTTP/1.1 200 OK  
X-Riak-Vclock: a85hYGBgzGDKBVIsrLnh3BlMiYx5rAzLJpw7wpcFAA==  
Content-Type: text/plain  
Content-Length: 9

Wednesday  

“X-Riak-Vclock”字段中记录了经过编码之后的vector clock。代表的意思和上边的描述的一致。

现在Ben将时间修改之后,将修改的消息发送个Dave。消息中要包含取得消息时的vclock,同时附上他自己的“X-Riak-Client-Id”

curl -X PUT -H "X-Riak-ClientId: Ben" -H "content-type: text/plain" \  
-H "X-Riak-Vclock: a85hYGBgzGDKBVIsrLnh3BlMiYx5rAzLJpw7wpcFAA==" \
http://localhost:8098/raw/plans/dinner --data "Tuesday"  

之后Dave通过GET方式取回一份新的版本,也就是被Ben修改过的。然后同意Ben的时间,再将这个消息重新提交。

curl -i http://localhost:8098/raw/plans/dinner  
...
X-Riak-Vclock: a85hYGBgymDKBVIsrLnh3BlMiYx5rAymfeeO8EGFWRLl30GF/00ACmcBAA==  
...
curl -X PUT -H "X-Riak-ClientId: Dave" -H "content-type: text/plain" \  
-H "X-Riak-Vclock: a85hYGBgymDKBVIsrLnh3BlMiYx5rAymfeeO8EGFWRLl30GF/00ACmcBAA==" \
http://localhost:8098/raw/plans/dinner --data "Tuesday"  

与此同时,Catby拿到的消息还是最开始GET到的,所以并不是最新的。所以当他提交建议时使用的vclock还是原来的。

curl -X PUT -H "X-Riak-ClientId: Cathy" -H "content-type: text/plain" \  
-H "X-Riak-Vclock: a85hYGBgzGDKBVIsrLnh3BlMiYx5rAzLJpw7wpcFAA==" \
http://localhost:8098/raw/plans/dinner --data "Thursday"  

这时候Dave再次GET这份消息时,会得到两份版本不同的消息(前提是Riak的allowmult属性设置为了false,否则他只能看见Catby的版本。如果allowmult设置为true,他就会得到一份他最后修改的版本和Catby的版本。我们这里假设allow_mutl = true)。

curl -i -H "Accept: multipart/mixed" http://localhost:8098/raw/plans/dinner  
HTTP/1.1 300 Multiple Choices  
X-Riak-Vclock: a85hYGBgzWDKBVIsrLnh3BlMiYx5rAymfeeO8EGFWRLl30GF1fsRwsypF59BhT0mIoTZ/1SYQIUrEcJszUksu9R6kCWyAA==  
Content-Type: multipart/mixed; boundary=ZZ3eyjUllBi7GXRRMJsUublFxjn  
Content-Length: 368

--ZZ3eyjUllBi7GXRRMJsUublFxjn
Content-Type: text/plain

Tuesday  
--ZZ3eyjUllBi7GXRRMJsUublFxjn
Content-Type: text/plain

Thursday  
--ZZ3eyjUllBi7GXRRMJsUublFxjn--

Dave这时候得到了两个版本的消息,因为这两条消息均不是对方的祖先。当Raik不能解决冲突时,就返回全部版本,这种做法和Dynamo是一致的,这时候只能是应用方自己解决。

Dave最终决定将日期定在周四,同时更新这条消息。因为在Dave取消息的时候,Riak应经附上了vclock,所以Dave在提交的时候同样附上这个vclock就可以了。

curl -X PUT -H "X-Riak-ClientId: Dave" -H "content-type: text/plain" \  
-H "X-Riak-Vclock: a85hYGBgzWDKBVIsrLnh3BlMiYx5rAymfeeO8EGFWRLl30GF1fsRwsypF59BhT0mIoTZ/1SYQIUrEcJszUksu9R6kCWyAA==" \
http://localhost:8098/raw/plans/dinner --data "Thursday"  

这个时候,Alice检查最新版本的消息时,Riak就会只返回最后Dave更新的版本了。

curl -i http://localhost:8098/raw/plans/dinner  
HTTP/1.1 200 OK  
X-Riak-Vclock: a85hYGBgzWDKBVIsrLnh3BlMiYx5rAymfeeO8EGFWRLl30GF1fvhwmzNSSy71HqgEpUTEerZ/1SYYBFmTr34DCjMBBTOnQwUzgIA  
Content-Type: text/plain  
Content-Length: 7

Thursday  

Reference

http://basho.com/blog/technical/2010/01/29/why-vector-clocks-are-easy/
http://wiki.basho.com/Riak.html

comments powered by Disqus