分布式入门之2:Quorum机制

1.  全写读1(write all, read one)
全写读1是最直观的副本控制规则。写时,只有全部副本写成功,才算是写成功。这样,读取时只需要从其中一个副本上读数据,就能保证正确性。
这种规则需要解决一个问题:如果是一个kv系统,对某个key的第i次写如果只有部分成功,那么系统中既存在次i次写的结果,又存在着第i-1次写的结果。而根据规则,生效的仅仅是第i-1个版本。因此,需要全局性地记录某个key对应的数据目前的版本号i-1。这个元数据可能为是系统的瓶颈。
可用性:对于写操作,虽然有N个副本,但其实是不能容忍任意一个副本的异常,可用性不高。而读服务则是高可用的。
 
2. quorum机制则是上述内容的一个升级版,也很好理解。
对于可用性来说,可以适当作如下折衷。对于N副本的系统,如果写操作只成功了W个副本,那么如果读N-W+1个副本,那么读结果的集合中,一定包含着最新版本的数据。
 
用于读写:
这里隐含的关键问题是,如何判断读到的R个副本中,哪个是成功提交的数据?比如提交3次,只有第2次成功。那么,依quorum读时,一定会读到成功提交的第2版本的副本,同时可能会读到1,3版本的未最终成功提交的数据。
 
第一种思路,直接用某个元数据服务将成功提交的版本号记录下来,如果有版本号,则可以直接确定哪个版本的数据是应该读的。这方法不是很好。但实际上quorum本身并没有什么手段解决这个问题。读操作一定会读到已经提交成功的数据。这是强一致性。quorum为解决强一制性,还需要引入额外的限制:
限制quorum机制的提交,只有在前一版本成功的基础上,才能进行下一版本的提交。言下之义就是,提交不成功的版本,只可能是最后一个版本。
 
这样就好处理了。如果读R个副本中,最高版本号的副本数不足W个,则继续读第R+1个副本,判断最高版本的副本个数有没有达到W个。如果直到读完全部N个都没有达到,那说明这个最高版本不是成功提交的纪录,只能取次高版本的版本号作为最终成功提交记录(由限制条件保证)。
可以看出, 这方法虽然能解决问题,但读可能过多。而且,如果有副本异常时,可能出现没法判断当前最终提交成功的到底是哪个版本的问题。
一般来说,应该回避这种思路,而将quorum与主从机制结合在一起,读主。
 
用于选主:
在主从控制中,如果主节点失效,需要从其余的从节点中选一个主。quorum机制的选主分三步:第一,读R个节点,取其中的最高版本号的数据,这个数据一定时序上大于等于最新成功提交的数据(要么是最新提交成功,要么是最新提交尚未成功);第二,将数据同步至W份,使系统满足写W份的要求,确保数据成为最新提交数据;第三,作为新主节点。
 
 
 
应用:
GFS:GFS中,使用的是quorum的退化方式,即写全读一。为了解决写时副本损坏引起不可用,GFS在append副本失败时,会在没有异常的机器上新创建chunk, 在此chunk上append,提高可用性。
dynamo:去中心化的结构上,quorum的写每次可能由不同的副本引发,这会引起数据的不一致与冲突。dynamo没有处理这种情况,而是引用了一个clock vector,记录每次操作由谁发起,什么版本号。将clock vector一起返回给用户,由用户去处理。
如: N=3, W=R=2。初始为(1,1,1)。
1. 以A引发操作+1,A同步给C:
数据(2,1,2),clock vector记录[1,A][][1,A];
2. 以B引发操作+2,同步给C:
数据(2,3,3),clock vector记录[1,A][1,B][1,B];
3. 以A引发操作+3,同步给C:
数据(5,3,5),clock vector为[(1,A)(2,A)][1,B][(1,A)(2,A)];
此时,可见B上的记录与A、C有冲突,需要用户依据不同策略解决这冲突。可以合并,得到结果7。
 
Big Pipe:与GFS一样是WARO,解决写失败的副本不一致的方法是,所有副本将最后一条记录更新到zookeeper,作为标准。同样与GFS一样,更新失败后会新创建chunk用于后续写,提高可用性。
上一篇:Compilation err ororg.eclipse.jdt.internal.compiler.classfmt.ClassFormatException


下一篇:bzoj千题计划130:bzoj1305: [CQOI2009]dance跳舞