Quorum机制学习笔记

原理

鸽巢原理

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

鸽巢原理证明

使用反证法证明： 假设n个鸽笼，每个鸽笼只有一只鸽子，那么最多只有n个鸽子,n<n+1，故不可能。

描述

术语

N: 存储数据副本的节点的数量 W: 写操作至少要写入的节点数量 R: 读操作至少要访问的节点数量

约束

# 须符合
R+W>N
W>N/2

分析

算法的关键在于使用鸽巢原理在节点中产生交集，使得在全局的视角下形成锁。

读

则保证R+W>N时，R和W的节点必然存在相交，因此必然能读到最新的数据。

写

通常写事务RW同时存在，因此R=W && R+W>N.所以广播的节点数至少是N/2+1。

多数派

不小于N/2+1节点的集合被称为多数派,多个多数派间必然存在相交的节点。

存在的缺陷

Quorum并不能实现强一致性。如果在写入副本的过程中失败，会导致脏数据产生。

问题

集群节点数必须是奇数么？

网上有文章说ZK，ETCD之类的服务，必须是奇数。因为要有多数派。这是错误的观点，如果节点挂了一个，奇数依然会变成偶数。 我认为并非强制要求，但不建议使用偶数组成集群。因为偶数集群的可用性和去掉一个节点后端奇数集群的容错能力相等。

证明

1. 容灾能力的关键在于可靠节点数是多数派。
2. 偶数可以表示为2n,去掉一台则是2n-1。
3. 二者的多数派，2n/2+1=n+1,(2n-1)/2+1=n+1是一样的。
4. 2n-1>2n,奇数个更节省资源。

所以建议使用奇数个节点组成集群。