Quorum机制和边界问题

在分布式的多副本复制中，一个简单的做法是单主节点+多副本，另一种是多主节点，此时需要处理主节点冲突问题。在无主节点的写入一致性上，经常会用到Quorum机制（类似鸽笼原理），在Raft里面也有类似的机制（joint consensus），用来在多个节点变更的时候达成共识选出master

Quorum

n个节点要获取最新的值，一种方案是只有一个主节点，其他的都是副本。读取的时候只读主节点。这样对主节点压力很大，而且容错性低，主节点一旦故障就无法读取了。

所以有了一些多主节点和无主节点的方案。

先看比较简单的无主节点的情况，假设有n个节点，客户端向节点发送写请求w，读请求r。类似鸽巢原理，当$w+r>n$的时候，读取到的节点包含最新值。

这样一个好处是容错，如果有少量节点故障依然可以正常工作。另一个好处是不必等写入全部完成后再进行读取，只要等到满足$w+r>n$就可以读到新值。

那么如何找到最新的节点？可以用时间戳或者递增id等方式，从所有读取中找到一个最新的。

实际上关键问题是我们只要找到一个最新的就可以了，于是我们其实可以不用严格的$w+r>n$，比如elasticsearch的consistency的quorum选项，区分了primary和replicas，quroum = int( (primary + number_of_replicas) / 2 ) + 1。这样区分了主从之后基本上只要从主节点读就可以了。考虑最简单最常用的主从备份，一个主节点一个从节点，只要从主节点读到就可以了（或者主从节点都读到）

再比如etcd的joint consensus，要选出leader，同时变更多个节点的时候要达成共识（不然有可能同时选出两个leader）
变更之前是C_old, 变更之后是C_new, 中间状态是C_old,new, 也需要用鸽巢原理选出majority认可的leader。（注意中间达成共识是需要时间的，不能从C_old直接跳到C_new, 在边界条件从C_old,new才能避免）。通过一个中间状态保证了要么是C_old,new的leader，要么是C_new的leader，这样就不会选出两个。

在类似elasticsearch的系统中w和r的参数可以配置，读多写少的场景下就将w设置的大一点。一种很简单的复制方法是WARO（Write All Read One），其实这就是w=n, r=1情况下的一种特例。这个时候容错很低，只要有1个节点出问题，就会出现写入失败的情况，此时读就没法读到新值。

边界条件

读写都是随机均匀的，有节点不可用的情况:

n=3, w=2, r=2时可以容忍一个副本节点故障
n=5, w=3, r=3时可以容忍2个
一般设置w和r都是$\frac{n}{2}$ ，可以容忍$\frac{n}{2}$个问题副本（读写都在$\frac{n}{2}$个剩余节点上）

当对读到新值的要求不那么高时，可以设置$w+r<n$, 此时有概率不满足一致性，有可能读到旧数据。不过这样可以提供更高的可用性，只有当可用节点低于$min(w,r)$时，才会无法读写（不可用）。这个一般被称为sloppy quorum

Quorum的问题

TLDR, Quorum无法保证强一致性。

没有返回最新的值的情况：

1.并发写入，解决并发写冲突的一种办法是丢弃早的（覆盖掉，会产生新的问题）
2.同时读写，但一部分节点还没写完（如果对时效要求不是很高那这个没关系）
3.之前新值大于w,但是某个节点故障了，恢复的时候恢复了一个旧值，此时新值为w-1，此时读不到新值

那有什么办法来保证强一致性呢，当然是Paxos和Raft啦（逃

那么如何判断并发写呢，下一篇再说吧（逃