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

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

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

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

Vr?+ Vw?> V
Vw?> V/2

Vw +Vr > V ：说明Vw 和 Vr 有交集地方

Vw? ?> V/2

第一条规则保证了一个数据不会被同时读写。

? ? ? ?当一个写操作请求过来的时候，它必须要获得Vw个冗余拷贝的许可。而剩下的数量是V-Vw?不够Vr，因此不能再有读请求过来了。

? ? ? ?同理，当读请求已经获得了Vr个冗余拷贝的许可时，写请求就无法获得许可了。

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

算法的好处

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

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

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

参考文献

^?Gifford, David K.?SOSP '79: Proceedings of the seventh ACM symposium on Operating systems principles. Pacific Grove, California, United States: ACM: 150–162. 1979.?doi:10.1145/800215.806583.?|contribution=被忽略 (帮助)

鸽巢原理

鸽巢原理，又名狄利克雷抽屉原理、鸽笼原理。

其中一种简单的表述法为：

若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少2只鸽子。

另一种为：

若有n个笼子和kn+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一个笼子有至少k+1只鸽子。

集合论的表述如下：

若A是n+1元集，B是n元集，则不存在从A到B的单射。

拉姆齐定理是此原理的推广。

例子

虽然鸽巢原理看起来很容易理解，但有时使用鸽巢原理会得到一些有趣的结论：

比如：北京至少有两个人头发数一样多。
证明：常人的头发数目在15万左右，可以假定没有人有超过100万根头发，但北京人口大于100万。如果把每个鸽巢定义为“头发的数量”，便共有100万个鸽巢。打一个比方，一根头发的人就会被编排在一根头发属于的巢、两根就在两根头发属于的巢，如此类推。鸽子则对应于人，那就变成了有大于100万只鸽子要进到100万个巢中（另一种说法是把多于100万个人编排到他们身上头发所属的鸽巢，比如有一个人有三根头发，他便会进了属于有三根头发的人的鸽巢）。因为北京人口多于100万，如果受访的前100万人头发数目刚好不同，第100万零一个的北京市民就必定会进了一个已经有一人在内的鸽巢。因此，我们便可以得到“北京至少有两个人头发数一样多”的结论。

另一个例子：

盒子里有10只黑袜子、12只蓝袜子，你需要拿一对同色的出来，最多需要拿出几只？假设总共只能拿一次，只要3只就无法回避会拿到两只相同颜色的袜子，因为颜色只有两种（鸽巢只有两个），而有三只袜子（三只鸽子），从而得到“拿3只袜子出来，就能保证有一双同色”的结论。

另一个例子：

某男性先后有过4位妻子，合共生有2子3女，则至少有2位子女有同一位母亲，且至少1位妻子没有女儿，至少2位妻子没有儿子。
至少有2位子女有同一位母亲 → 若非如此，即任何2位子女都没有相同的母亲，则该男性至少要有5位妻子，矛盾。
至少1位妻子没有女儿 → 若非如此，即每位妻子都有女儿，则该男性至少要有4位女儿，矛盾。
至少2位妻子没有儿子 → 若非如此，即最多1位妻子没有儿子，则该男性至少要有3位儿子，矛盾。

更不直观一点的例子：

有n个人（至少2人）互相握手（随意找人握），必有两人握过手的人数相同。
这里，鸽巢对应于握过手人数，鸽子对应于人，每个人都可以与[0,n-1]人握过手（但0和n-1不能同时存在，因为如果一个人不和任何人握手，那就不会存在一个和所有其他人都握过手的人），所以鸽巢是n-1个。但有n个人（n只鸽子），因此证明了命题正确。

鸽巢原理经常在计算机领域得到真正的应用。比如：哈希表的重复问题（冲突）是不可避免的，因为Keys的数目总是比Indices的数目多，不管是多么高明的算法都不可能解决这个问题。这个原理，还证明任何无损压缩算法，在把一些输入变小的同时，作为代价一定有其他的输入增大，否则对于长度为L的输入集合，该压缩算法总能将其映射到一个更小的长度小于L的输出集合，而这与鸽巢理论相悖。

推广

一种表达是这样的：如果要把n个对象分配到m个容器中，必有至少一个容器容纳至少 $\left\lceil {\frac {n}{m}}\right\rceil$ 个对象。

数学证明

反证法

设把n+1个元素分为n个集合 $A_{1},A_{2},\cdots ,A_{n}$ ，记 $a_{i}=|A_{i}|(i=1,2,\cdots ,n)$ 表示这n个集合里相应的元素个数。

假设 $\forall a_{i}<2(i=1,2,\cdots ,n)$

因为 $a_{i}\in \mathbb {N}$

所以 $a_{i}\leq 1$

所以 $a_{1}+a_{2}+\cdots +a_{n}\leq 1+1+\cdots +1=n<n+1$

这与题设矛盾，因此结论得证。

概率方法

将m个元素随机放入n个集合 $A_{k}$ 中(m > n)。规定 $\left\lceil {\frac {m}{n}}\right\rceil ={\frac {m}{n}}$ 如果n整除m。随机选择一个集合，它的大小的期望值是：? $\sum _{k=1}^{n}|A_{k}|{\frac {1}{n}}={\frac {|A_{1}|+|A_{2}|+\cdots +|A_{n}|}{n}}={\frac {m}{n}}$ ?由于 $|A_{k}|$ 只能是整数，所以必有一个m，使得 $|A_{m}|\geq \left\lceil {\frac {m}{n}}\right\rceil$

更强的形式

设?q1,?q2, ...,?qn?皆是正整数，现有

$q_{1}+q_{2}+\cdots +q_{n}-n+1$

个对象要分配在n个箱子中，那么以下叙述至少一者成立：

第1个箱子包含至少q1个对象；
第2个箱子包含至少q2个对象；
......
第n个箱子包含至少qn个对象。[1]

这个原理一样可以使用反证法证明，即假设上述所有叙述为假并得出矛盾，方法与前述简单情况类似。

无穷集中的情况

借由康托的无穷基数可将鸽巢原理推广到无穷集中：如果集合A的势大于集合B的势，那么不存在由A到B的单射。

参见

其他组合原理，如：
容斥原理
乘法原理

来源

Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998.?ISBN 0-201-19912-2. pp. 244–248.
Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Electronic document, retrieved 11 November 2006.
抽屉原理[永久失效链接]

外部链接

鸽笼原理?（页面存档备份，存于互联网档案馆）；谢聪智对鸽巢原理的介绍。
"The strange case of The Pigeon-hole Principle?（页面存档备份，存于互联网档案馆）";?Edsger Dijkstra?investigates interpretations and reformulations of the principle.
"The Pigeon Hole Principle?（页面存档备份，存于互联网档案馆）"; Elementary examples of the principle in use by Larry Cusick.
"Pigeonhole Principle from Interactive Mathematics Miscellany and Puzzles?（页面存档备份，存于互联网档案馆）"; basic Pigeonhole Principle analysis and examples by?Cut-the-Knot.
"The Puzzlers' Pigeonhole";?Cut-the-Knot?on the importance of the principle in the field of puzzle solving and analysis.

^?Brualdi 2010，第74 Theorem 3.2.1页