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

描述（维基百科）

在有冗余数据的分布式存储系统当中，冗余数据对象会在不同的机器之间存放多份拷贝。但是同一时刻一个数据对象的多份拷贝只能用于读或者用于写。

该算法可以保证同一份数据对象的多份拷贝不会被超过两个访问对象读写。

算法来源于[Gifford, 1979][3][1]。 分布式系统中的每一份数据拷贝对象都被赋予一票。每一个读操作获得的票数必须大于最小读票数（read quorum）（Vr），每个写操作获得的票数必须大于最小写票数（write quorum）(Vw）才能读或者写。如果系统有V票（意味着一个数据对象有V份冗余拷贝），那么最小读写票数(quorum)应满足如下限制：

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

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

解释

这种逻辑来自于鸽巢原理，也是狄利克雷抽屉原理，简单的描述若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。
Vr + Vw > V
Vw > V/2
这两个公式的理解：

首先，这个算法讨论的是无主的模式，也就是允许静默同步，但是每个节点都可以提供读写服务，单次写操作不需要等待所有节点同步完成。在这种情况下,Vr和Vw指节点中可以进行读写需要的最少的票数。换句话说，Vr表示：至少要有Vr个节点提供读服务，Vw表示：至少要有Vw个节点可写，满足VrVw，集群之间的副本才可以认为具有一致性。

这两个最小票数是可以调整的，我们分析一下为什么必须满足这两个公式，集群之间的副本才具备一致性。

Vr + Vw > V，假设我们共有5个节点，{a,b,c,d,e},如果我们设置Vw=2,Vr=3，那么如果选择写入的节点是{a,b}，选择读取的节点刚好是{c,d,e}，都满足了读写的票数要求，此时读到的就是脏数据，不满足一致性了，注意我们这里选择的节点是随机的。每个节点其实都可以读写，只是需要判断当前能否投出足够的票，只要集群内能写的机器>=Vw,就可以在能写的机器上写。

但是如果我们设置Vw=3,Vr=3,此时如果可以进行操作，就满足Vr + Vw > V，那么读取的机器必定有一台就是写了最新数据的机器，那么从3台中我们一定可以读到最新数据。

Vw > V/2,这个更好理解，如果5个节点，我们让Vw=2，那么就可能出现{a,b},{c,d}同时在写，此时无论如何都读不到正确的数据，完全没有一致性可言。但是如果满足的话，假设A1，A2两个写操作进来写，我们会发现至少有一个节点，会被阻塞而依次写了A1和A2，也就是最新的数据。

所以一般都会保证Vw>V/2来保证写一致，适当调小Vr让Vr+Vw < V ,以一定概率读到旧数据为代价来减少读的规模。

但是这个如果一开始就规定好读写节点，也就是事先规定好部分节点只读和只写，那么就会简单很多，只需要保证提供读服务的节点数量大于提供写服务的节点数量，也就是第一条即可。