Quorum

Quorum(['kwɔ:rəm])字面意思是选举法定人数,在西方资本主义社会在举行选举时,通常要求参与人数必须达到额定的数量,才能成为一个法定有效的选举。这个额定的人数就是Quorum,这是原始的涵义。而在计算机的世界里,Quorum机制是一种容错技术,常常出现在分布式系统设计中。微信后台也用这个算法。

这个技术不是新东西,而依据的数学理论就更早了,鸽笼原理,相关的论文好像是1979年发表的。鸽笼原理很简单:若有n+1只鸽子关在n个笼子里,那么至少有一个笼子有至少2只鸽子。

分布式系统通常支持多副本,副本存放在不同节点上,读写时需要对多个副本进行操作。按照自然而然的想法,一个写操作会需要写多个副本,但是读只要读到一个副本即可。这种思路猛听起来很合理,有一个学名叫“读一写全协议”(read only write all,ROWA)但若真依此实现,每一次写都必须刷新所有副本,才能避免产生一致性问题,如此写操作就显得太“重”了,尤其是和读操作相比较,一头轻一头重,负载明显不平衡,更加显得不协调。而且写的respond time变长其实也会间接影响到读,因为不写好没法读嘛,最终拖慢整体性能。在实际的系统中,通常Quorum指的就是一次有效读或写操作所需要完成的有效副本数。采用Quorum机制后,写操作需要即刻完成的副本数减少,读操作需要成功读取的副本数增加,负载被间接转移了过去,一定程度上平衡了读写两种操作,系统整体性能会得到提升。

1. 基于Quorum投票的冗余控制算法

在有冗余数据的分布式存储系统当中,冗余数据对象会在不同的机器之间存放多份拷贝。但是同一时刻一个数据对象的多份拷贝只能用于读或者用于写。该算法可以保证同一份数据对象的多份拷贝不会被超过两个访问对象读写。

算法来源于[Gifford, 1979]。 分布式系统中的每一份数据拷贝对象都被赋予一票。每一个操作必须要获得最小的读票数(Vr)或者最小的写票数(Vw)才能读或者写。如果一个系统有V票(意味着一个数据对象有V份冗余拷贝),那么这最小读写票必须满足:

  1. Vr + Vw > V

  2. Vw > V/2

第一条规则保证了一个数据不会被同时读写。当一个写操作请求过来的时候,它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V-Vw 不够Vr,因此不能再有读请求过来了。同理,当读请求已经获得了Vr个冗余拷贝的许可时,写请求就无法获得许可了。

第二条规则保证了数据的串行化修改。一份数据的冗余拷贝不可能同时被两个写请求修改。

1.1. 如何应用

如在分布式系统中,冗余数据是保证可靠性的手段,因此冗余数据的一致性维护就非常重要。一般而言,一个写操作必须要对所有的冗余数据都更新完成了,才能称为成功结束。比如一份数据在5台设备上有冗余,因为不知道读数据会落在哪一台设备上,那么一次写操作,必须5台设备都更新完成,写操作才能返回。

对于写操作比较频繁的系统,这个操作的瓶颈非常大。Quorum算法可以让写操作只要写完3台就返回。剩下的由系统内部缓慢同步完成。而读操作,则需要也至少读3台,才能保证至少可以读到一个最新的数据。

Quorum的读写最小票数可以用来做为系统在读、写性能方面的一个可调节参数。写票数Vw越大,则读票数Vr越小,这时候系统读的开销就小。反之则写的开销就小。

2. Reference


CategoryAlgorithm

MainWiki: Quorum (last edited 2015-04-24 15:47:56 by twotwo)