基于 Quorum 投票机制的 Replica Control 算法

在分布式系统中,一份数据可能有多份副本(冗余数据)。为了保证数据读写的正确性,同一时刻一份数据的多份副本只能用于读或用于写,而不能同时被超过两个访问对象并发读写。Quorum机制就可以保证这一点,我们来看一下它的思想。

一个分布式系统中,我们给每个数据副本都赋予一票。假设一共有 V 个数据副本,那么总共就有 V 个票数。每个操作必须要获得读票数(完成读操作所需要读取的最小副本数,read quorum, V(r) )或写票数(完成写操作所需要读取的最小副本数write quorum, V(w) )才能够对数据进行读或写。票数需要遵循以下规则:

  1. $V_{r} + V_{w} > V$
  2. $V_{w} > \frac{V}{2}$

第一条规则有两个作用:第一个作用是保证了一个数据不会被同时读写。当请求一个写操作时,它需要的得到 V(w) 读票数,而剩下的票数为 V - V(w) < V(r),因此不再允许读操作。请求读操作时也是同理;第二个作用是保证了强一致性。根据 鸽巢原理,写数据操作与读新数据操作之间是有重叠的,这就确保至少有一个读操作是可以读到最新数据的。

第二条规则保证了数据的串行化修改,同一个数据不能同时被两个写操作并发修改。

Quorum投票机制非常有用。比如一份数据在5个结点上存有副本,进行一次写操作的时候,必须等待五个结点的写操作都完成,整个写操作才返回(因为可以从任意结点读取)。这样会导致写操作负载太高,而有了Quorum机制以后,我们可以让写操作在至少3个结点上完成就可以返回,另外的结点可以等待后台同步,而读操作V(r)也需要大于 V-V(w) 才能确保至少一个读操作可以读到最新数据。


References

  • Weighted Voting for Replicated Data, David K. Gifford, Stanford University and Xerox Palo Alto Research Center
文章目录
  1. 1. References