加载中…
正文 字体大小:

分布式数据库的数据版本合并

(2011-11-03 22:37:49)
标签:

vector

clock

分类: 分布式

大家知道,在分布式数据库系统中,为了避免硬盘的随机IO读写,对于数据的更新操作使用插入一个新的数据来代替的。同时,为了使数据库有很好得容错性,往往在一致性哈希环上进行N台备份的办法,那么这就导致了数据在不同的备份服务器中都存在。那么在不同的时刻由于一致性哈希环中可能有宕机节点,同一客户端的数据往往在不同时刻也会被分配到不同的服务器中去存取数据,或者不同的客户端请求会被hash到不同的服务器上去去进行处理,那么在不同服务器上对同一键值数据的更改就会造成冲突。为了始终保持用户能够随时随地得写入数据,不能简单得在所有备份服务器数据完成同步之前拒绝任何可能会造成文件冲突的写入操作。因此服务器同一键值的数据记录会有多个版本。

要理解这个问题,首先要明白QNW模型。所谓QNW模型中,N指的是如果对同一数据有N台服务器进行备份,R指的是至少同步得读取R台服务上的数据之后才能决定读取的数据是多少,W指的是写入该数据时要同步得写入W台服务器才认为数据的写入是成功的。需要注意的是R和w都是同步操作,R是同步读R台服务器,W是同步写W台服务器。当R+W>N时,这才能保证数据的一致性。这个公式很好理解。需要注意的当W<N时,那么写入的数据会以异步的方式被备份到剩下的N-W台服务器上,当W=N,备份则是同步完成的。这个QNW需要考虑2个问题:

image

                                        图1

备份同步冲突

举个例子,如下图:

1,2,3,4这四台服务器构成了一致性哈希圆环,圆环方向为顺时针。Count=1作为原始数据存放在2,3,4上。假设我们定义N=3,也就是3台服务器备份数据。选择不同R和W决定了服务器的读写特点,比如R=1,W=3,那么读可用最大化,如果W=1,R=3,那么写可用最大化。如果R=2,W=2,则读写可用性相对平衡。

假设我们取R=2,W=2,数据会被异步得同步到3台服务器上(W<N)。有一个用户x(用户x在哈希圆环上的位置如图)对数据D进行自加更新(count++,需要注意的是自加更新分为两个步骤,第一步先读取count的值,然后运行count=count+1计算并写入服务器,一个是读,一个是写),他首先读取了数据D,得到了count=1,然后自加产生了数据D1(count=2),那么服务器就开始准备把D1(count=2)写入到服务器3,4中,然后数据D1会被异步得同步到服务器1上去。在用户x完成读取和计算但还没实际将数据写入到服务器上时,用户y紧接着也对数据D进行了一个自加更新(count++),由于此时用户x的D1尚未真正写入(下划线就表示数据还未写入),那么此时y连续读取两台服务器2,3(需要连续读取两次,R=2,由于服务器1此时没有任何count的数据,因此对服务器1的读取不能算在R的统计次数当中)取出自加前的count值,发现数据D(count=1),它就会把数据自加得到D2(count=2),然后也准备把它写入并同步到1,2,3这三台服务器上。但在y准备写入的时侯,此时用户x的数据的写入和同步已经完成了,服务器1上的数据发生了变化,用户x产生的count=2已经到达了服务器1。这样在服务器上就产生了同一数据D的不同版本上造成的写入操作冲突(原来我的自加操作是在count=1的版本基础上进行的,现在自加操作基础怎么又变成了count=2?)我该义无反顾的把我的数据写入,还是抛弃这次写入(因为我的自加操作的基础已经发生变化了,操作似乎涉嫌非法)?在理想的语义上,我们应该是希望y更新的数据是count=3,因为y的行为是发生在x之后的。

这种情况的冲突发生在数据在异步地进行同步的过程中发生的冲突,所以称之为备份同步冲突

冗余读取冲突

这是在写入数据时发生了冲突。那么读取数据时不同版本的冗余备份也会有冲突。假设上面的写入冲突不存在,y进行自加操作之前,x的数据已经更新到1上去了,那么用户y读取数据D时,从两台服务器1,2得到了2个版本的数据(所有的历史数据都没删除,更新和添加数据在实际数据库中都是增加数据记录):count=1(原始的数据),count=2(x的更改)。那么哪个数据D是正确的呢?

在同一台机器上也会发生冗余读取冲突,在同一机器上的对同一数据的修改,为了避免随机磁盘IO开销,通常用追加来代替修改,这也造成了冲突。

问题的解决

思路1 Lamport时间戳

对于冗余读取冲突,一个很自然的想法就是为同一数据的不同记录版本打上一个时间戳,然后对比一下看看哪条记录是最新的。针对上面的问题,用户y读取数据D时,它发现了两个版本:count=1(原始的数据),count=2(x的更改)。此时count=1的时间戳是系统创建时间,count=2的时间戳是x创建D1时的时间,显然count=2新于count=1,于是读取D时认为count=2。这么做似乎没有问题。

对于备份同步冲突,时间戳似乎也能工作。用户y准备写入count=2时,发现count=2的数据已经被同步到服务器1上了,而且时间戳比较新(是x写入2时的时间),而自己自加之前读取count=1的时间戳比较老(系统创建之初时的时间戳),那么抛弃自己这次做的更新,抛出更新异常通知调用者。这么做不仅解决了写入冲突,语义上的结果似乎也很理想(y写的时间比x新,因此不应该在老的数据基础进行更新,而应该在x的基础上更新,系统抛出异常通知调用者,一旦跑出了异常用户获得了通知,用户就可以了解状态并作出合适的处理,要么调用者再重新执行这次操作,要么调用者可以根据自己合理的逻辑进行,)。

一切都很完美,但仔细想想,上面的思路还有待斟酌。

这里的时间戳,我们想当然的认为它应该是一个绝对时间,比如我们利用的GMT时间。但实际上绝对时间是很难100%完全同步,在服务器1上的绝对时间不可能100%和服务器2的相等,因为服务器的CPU频率,线程负载都不完全相同,你总能在某个合适的时间粒度上发现他们的绝对时间戳不相等。那么,依据绝对时间戳来判定记录是否新还是旧就不可靠了。怎么办呢?

于是就有了Lamport时间戳算法。Lamport时间戳算法使用的是一个相对时间戳,每台服务器维护自己的时间戳,该时间戳就是一个计数器(初始化为0),每发生一件事情或者需要检查一件事情,该计数器自加1(这就是说每个checkpoint计数器都加1,checkpoint可以是任何事件,只要有一件事情需要被打上Lamport时间戳用来衡量相对时间,那么这个事件就是checkpoint,并且会被打上Lamport时间戳)。Lamport时间戳之间的间隔只是一个相对时间,在同一台机器上,它可以很长,也可以很短,依据checkpoint之间的实际时间。不同服务器上的时间戳没有可比性,同一台服务器上的时间戳才能标定checkpoint的先后。当服务器1向服务器2发送数据时,需要把服务器1此时的时间戳附在消息上一起发送过去,如果服务器1此时的Lamport时间戳小于服务器2时,那么服务2会为该数据打上一个服务器2的Lamport时间戳(其值为服务器2上的现有最大计数值加1)。如果服务器上1的时间戳大于服务器2上,那么服务器1的时间戳+1就可以作为服务器2的时间戳。也就是说服务器2上的Lamport时间戳等于max(消息上的时间戳[表示发送消息时服务器1的时间戳],服务器2现有的最大时间戳)+1。看下图:

image

                                           图2

上面这个图2表示了前面举的备份同步的例子,冒号右边的数字就是Lamport时间戳,左边是服务器1上一个自加更新操作(自加分为a,b,c,d四个步骤,先读取,再自加,再写入,再同步给别人),右边是服务器2上的一个自加更新操作。蓝色的节点表示冲突发生的节点。在h事件中,服务器2开始准备写入数据D了,可是它面对这么几个数据:e:count=1(原始数据);g:count=2(服务器1同步的数据)。而g的Lamport时间戳为5,e的时间戳为1,似乎认为count=2是最新的数据(因为5>1),我们应该基于count=2进行自加。但实际上并不能这么认为,看下图图3。e发生在a之前,我们应该给予count=1自加。因此基于同一台机器内Lamport时间戳,我们能够得到该机器上所有事件的全序,但对于不同机器,Lamport时间戳不能用于比较时间的先后顺序,只能得出所谓的“部分顺序”:如果C(a)>=C(b),那么a不可能决定影响b(所谓决定影响指的是a,b处于一条箭头单向可达的顺序链,a的位置先于b,比如图2,b影响c,影响g,但不能说b影响f,因为两者无法通过箭头单向可达),其它什么都说明不了。比如图2中的i,i>g,i发生的时间先于g,而g>d,g的时间又晚于d,所以不要奢望能够据此能够决定数据的新和旧。

但有人也许就会问,那这个Lamport时间戳对于同步备份冲突有什么帮助呢?实际上这个时间戳只是检测出数据版本发生了变化,但只要能检测出变化我们就知道数据发生了冲突(但尽管我们不知道这个发生冲突的数据谁应该留下)。对于冗余读取冲突,如果是同一台机器的数据发生了冲突,我们自然能够进行合并(这种能力称之为部分顺序能力),但如何发生冲突的数据有一方是另外一台机器的备份,那么我们也只能是检测出这个冲突,剩下的交由用户处理。Lamport能检测冲突,但对大部分冲突没有合并能力。

image

                                             图3

思路2:Vector clock

针对Lamport算法能否改进呢?能否有一种方法能够一定程度对不同服务器之间的数据进行比较新旧的合并呢?答案是vector clock。

Vector clock本质上也是一个时间戳,只不过这个时间戳是个向量,向量中的每个分量代表一台服务器,每台服务器中的checkpoint只能自加向量中代表自己这台服务器的那一位,每台服务器前后相邻的事件的vector clock只会在代表本服务器的那一位上有区别。vector具体的介绍和解释 请参考文献[2],[9],文献讲得很清楚。

每个事件有了vector clock,那么事件之间就可以比较了。如果事件1的向量时钟中的任何一个分量都小于或等于事件2的向量之中对应的分量,那么事件1的时间就旧于事件2,这种关系我们称之为“小于”。如果两个向量时钟中有一部分是向量1的大,另一部分是向量2的大,如果是这种情况那么这两个事件就发生了冲突,需要用户来决策做出出合并。

回过头来针对上面的备份合并冲突:

image

                                             图4

针对上图出现的例子,g事件合并[4,-],[-.3],这两个向量并不存在小于的关系,因此两个事件发生了冲突,因此必须用户人为做出决定处理冲突,冲突解决后就可以合并向量得到[4,3]。针对这个例子,你可能认为向量时钟没什么效果。但是如果在服务器很多,同步比较复杂的情况下,更常出现的情况是当发生备份合并时,两个向量是一个“小于”的关系,这两者直接可以合并,并没有发生冲突,系统可以直接将两者合并。

对于冗余读取冲突,系统也可以合并不同机器上的时钟向量之间是“小于”关系的事件,对于同一台机器的事件,依据算法,他们之间一定是“小于”的关系,因此他们也可以合并。

因此我们可以看到,向量时钟相对于Lamport时间戳,它能够解决部分涉及多台机器的事件的合并问题,对于另外一部分确实发生冲突的事件,它无法自动合并,但它能够检测出来。Lamport时间戳除了能够合并同一台机器上的事件之外,对于任何涉及多台机器的事件合并,它都无能为力,它可以检测出备份合并冲突。从这个角度来看,向量时钟是大大优于Lamports时间戳的。

本质上,时钟向量表达了这么一个思想:这个事件是我在依据其它服务器事件的基础上做出的,我做出这个事件依据的逻辑环境背景都在向量中体现出来,如果时钟向量1“小于”时钟向量2,那就说明事件1的依据比较老,那么自然而然也就会被依据比较新的环境做出的事件2所替换。这就是时钟向量背后蕴含的思想。

参考文献:

[1]:《why vector clocks are more powerful than Lamport timestamp》http://skipperkongen.dk/2011/07/26/vector-clocks-vs-lamport-timestamps/

[2]:Lamport时间戳维基http://en.wikipedia.org/wiki/Lamport_timestamps

[3]:维基 http://en.wikipedia.org/wiki/Happened-before

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

[5]:http://basho.com/blog/technical/2010/01/29/why-vector-clocks-are-easy/

[6]:详细解析Dynamo存储引擎

http://www.google.com.hk/url?sa=t&rct=j&q=vector+clock&source=web&cd=3&ved=0CEQQFjAC&url=http://storage.it168.com/a2009/1013/757/000000757579_all.shtml&ei=js-nToP_KIXLhAeZ7o38DQ&usg=AFQjCNGD2aywzSIB6fplWncHvuNYLwIXFg&cad=rjt

[7]:NoSql数据库笔谈

http://sebug.net/paper/databases/nosql/Nosql.html#I_O_9886723485627446_373115905_5228612841633498

[8] http://skipperkongen.dk/2011/07/26/vector-clocks-vs-lamport-timestamps/

[9]《Fundamentals of Distribute Computing: A practical Tour of Vector Clock Systems》 http://net.pku.edu.cn/~course/cs501/2008/reading/a_tour_vc.html#sidebar1

0

阅读 评论 收藏 转载 喜欢 打印举报
已投稿到:
  • 评论加载中,请稍候...
发评论

       

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有