复杂的Vector Clcok

之前一篇文章简单介绍了使用Vector Clock解决消息副本不一致问题的方法。虽然文章题目叫做“简单的Vector Clock”,但是说的都是从使用者角度看的,对于使用者而言确实比较简单。所以如果系统中提供了这个机制,那不妨就直接用好了。现在我们换个角度来看这个机制,从实现者角度来看,恐怕这个系统就不是那么容易了。

从实现者角度来看,其中最难的两个问题是:1)确定谁作为消息更新的Actor(actor,在vclock中有自己独立的域,同时负责版本解析和递增);2)保证vclock能过随着时间延续,无限地递增。

在上一篇文章所用的例子中,将提出对消息修改的客户端(即Alice等人)当做vclock中的actor。当然vclock就是为这种模型设计的,并且能很好的工作。但是这种模型仍有不足之处,一个显著的缺点就是,vclock的长度将会随着客户端的增加而增加。当客户端规模较小时,这不是问题。但是在一个大型分布式系统中,客户端的规模可能会非常大,此时不仅存储vclock要耗费大量的内存,而且对其解析也要花费不少时间。同样使用上一篇文章中的例子来看。

首先Alice发出第一条消息,“提议将时间定为周三”。图中vclock的actor做了简写,Alice用A代表。

date = Wednesday  
vclock = Alice:1  

接着Ben建议改为周二:

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

Dave收到Ben的提议并回应,同意定在周二:

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

另一方面,Cathy建议将时间定在周四:

date = Thursday  
vclock = Alice:1, Cathy:1  

Dave收到Cathy的消息后发现与自己之前的不一致。两份消息如下:

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

Dave之所以能分辨出这两份消息产生冲突了,是因为这两份消息均不是对方的”后裔”,关于后裔的概念可以参考上一遍文章。Dave发现了冲突,就要解决冲突。最终他选择了周四,并将结果回应给Cathy。

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

最后当Alice收集大家的意见时(此时Dave刚好不在),分别从Ben和Cathy拿到的消息如下:

date = Tuesday  
vclock = Alice:1, Ben:1, Dave:1  
date = Thursday  
vclock = Alice:1, Ben:1, Cathy:1, Dave:2  

Alice从两分消息中携带的Vclock中就能知道,Dave最终是将时间定在了周四,而他之前与Ben商量好的计划被覆盖了。Alice将这份消息发给Ben看的时候,Ben也能明白自己的消息被覆盖了。
上边值得注意的是,即使很简单的一个例子也导致了vclock包含了所有的参与者信息。在实际应用中也是如此,每一份数据都会附着上对其做过修改的客户端信息。这些信息对于存储和计算来说都是很大的消耗。所以最好考虑如何优化一下。

一个直观的想法就是把处理客户端请求的服务器作为vclock中的actor。因为几乎每个系统中都会有数目差不多固定的服务器组成,而且通常服务器的数量要远远少于客户端的数量。据我所知(原文作者)至少有两个实际的系统是这么干的。另外除了能够控制vclock在一定范围内增长外,这种方法还能够将vclock的使用隐藏在服务端,而不至于暴露给客户端。

同样使用上述的例子来看,我们假定这个分布式系统由两个服务器组成,客户端均匀的分配到两台服务器上,这样每个客户端都同固定的一台服务器通信。Alice和Dave使用Server X,Ben和Cathy使用Server Y。为了简化说明,下图忽略了服务器之间的通信。最开始的几步如下图:

与之前的过程唯一一点不同就是,这里的vclock更新时采用的是服务器作为一个actor。 之后Cathy对消息更新之后,问题产生了。

按照之前的流程,在Dave拿到Cathy的更新之后,会发现数据产生冲突了,进而解决冲突。但是在我们采用新的策略时,事情就不一样了。Ben和Cathy都更改了消息内容,而且这里采用是处理他们请求的服务器来标示这个修改,所以Cathy修改的消息携带的vclock和Ben的vclock是一样的!!这样Dave之前回复给Ben的消息正好是Cathy消息的后裔。然后Cathy的消息就悄无声息的丢失了。。。很显然,这个策略目前是不能正常工作的。还记得上边说的采用这个策略的系统啊,当他们意识到这个策略会丢失更新时都果断放弃了。。。

所以如果想要通过使用vclock方法达到想要的结果,那么vclock中的域必须是实际参与数据修改的客户端。在上述的例子中就是必须采用客户端ID而不是服务器ID。 对vclock进行修剪

现在我们回到在开始,继续使用客户端ID作为vclock的actor。随着越来越多的客户端加入到系统中,vclock的长度会越来越长。这时大部分都会采用的策略是对vclock进行”修剪“。一种办法是对vclock中每一个域都加入一个时间戳,每次更新这个域的时候,都更新时间戳,但是在对vclock进行比较的时候忽略这个时间戳,因为时间戳只在对vclock修剪的时候才用到。 当一个给定的vclock增长到了一个设定的临界值时,你就可以把那些最长时间都没更新的域删掉。你肯定会想,这样一来不就丢了一部分信息?确实是这样的!但是不会带来你数据的损失。只有在一种情况下,这种修剪会带来影响,当一个客户端使用一个包含非常老的域的vclock(也就是没经过修剪的vclock)来更新消息时会产生一个冲突。但是如果服务器端保存了完整的未经过修剪的vclock的话,这个冲突就很容易自动解决。所以当你对vclcok做修剪时需要权衡:是要保证vclock在可控的范围内增长,还是允许某些时候出现这种”假的冲突“,但是不会丢失数据。

总结

综上,Vector Clock确实很很复杂的,在一个无限增长的系统中,即使是实现的非常完美,依然不能保留全部的因果信息。要意识到这点,并且要针对性的设计。不过这些只是针对要设计新的分布式系统或是改进现有系统的人的一点建议,使用系统提供的vector clock依然是很简单的。

Reference

http://basho.com/blog/technical/2010/04/05/why-vector-clocks-are-hard/

comments powered by Disqus