Quorum NWR：通过仲裁实现数据一致性
楔子
数据同步相关的协议有 Paxos, Raft, ZAB 等等（我们以后会聊），但这些协议都有一个相同之处，就是要求集群当中要有一个领导者。客户端只向领导者发送写请求，领导者再将数据同步给追随者。领导者决定写入的顺序，而追随者则按相同顺序来同步领导者的写入。
但也有一些数据存储系统采用了不同的方法，其放弃了领导者的概念，并允许任何副本都能接受来自客户端的写入。最早的一些系统是无领导者的（leaderless），但是在关系数据库主导的时代，这个想法几乎已被忘却。
不过在亚马逊将其用于内部的 Dynamo 系统之后，它再一次成为数据存储的一种时尚架构。Riak, Cassandra 和 Voldemort 都是由 Dynamo 启发的无领导复制模型的开源数据存储，所以这类数据库也被称为 Dynamo 风格。
但是问题来了，在无领导者的实现中，客户端将写入发送到任何一个节点都可以，那么该节点的数据要如何同步给其它节点呢？以及客户端在读取的时候读取到旧数据该怎么办呢？
此时就需要 Quorum NWR 算法，客户端写数据不止写入一个节点，而是写入多个节点；同理当客户端读取的时候，也会读取多个节点。关于这背后的原理，我们来慢慢讲解。
仲裁读
假设你有一个带有三个副本的分布式系统，而其中一个副本目前不可用，如果是基于领导者的复制，那么可能要执行故障切换。但在无领导者配置中，故障切换不存在。
比如下图显示的那样：客户端（用户 satori）将写入并行发送到所有的副本中，并且两个可用副本接受写入，但是不可用副本错过了它。所以现在的结果就是，三个副本中有两个写入成功（返回了响应），而此时客户端整体写入成功，因此客户简单地忽略了其中一个副本错过了写入的事实。
然后客户端开始读取，显然 Replica 3 返回的是之前的旧数据，因为在写入新数据的时候它下线了。所以为了解决这个问题，客户端在读数据的时候不仅仅只读一个副本，正如写请求会并行地写入多个副本，读请求也会从多个副本读取。这样就会获取多个响应，然后通过版本号选择最新的值。
比如当前从 Replica 3 中读取到的虽然是旧值，但 1 和 2 返回的是新值，基于版本号可以选择出最新的那一个。
所以原理还是不难理解的，就是每次写的时候，会写入多个副本；读的时候，也会读多个副本，基于版本号选择最新的那一个。这样也能保证客户端看到的是新数据，从而实现数据一致性。
但这就产生了一个问题，客户端每次写的时候到底要写多少个副本，读的时候又要读多少个副本呢？我们一直说多个副本，显然这是很模糊的，因为说不清楚究竟多少才叫多。
读取的法定人数
还是上面那张图，三个副本有两个写入成功，我们就认为客户端写入成功了。但如果只有一个副本写入成功了呢？
首先当成功写入两个时，这意味着至多有一个副本可能是陈旧的，因此在读取的时候至少要读取两个副本，才可以确保至少有一个是最新的。但如果只成功写入一个，那么在读取的时候就要读三个副本。
注：这里我们一个节点上只有一个副本
更一般地说，如果有 n 个节点，写入的时候至少成功写入 w 个节点才能被认为是成功，并且读取的时候至少读取 r 个节点。那么只要
比如 3 个节点，成功写入了 2 个，那么读的时候至少要读 2 个，才能拿到最新的值；如果只成功写入了 1 个，那么就至少要读 3 个，才能拿到最新的值。同理 5 个节点，成功写入 2 个，还剩下 3 个没写，那么读的时候至少要读 4 个，才能保证拿到最新的值。
这些 r 值和 w 值就被称为读写的法定人数（quorum），你可以认为，r 和 w 是有效读写所需的最低票数。而在大部分使用 Quorum 的系统中，r, w, n 都是可配置的，通过使 r + w > n 便可实现强一致性。
比如你开发了一个有 5 个节点的分布式系统，一开始的要求是实现最终一致性，用户写完数据之后不一定会立刻看到变化，经过一段时间的数据同步之后，这个变化才会看到。但最新需求变了，让你支持强一致性，用户一旦写完数据，就要立刻看到变化。
此时便可以通过 Quorum 自定义一致性，既然要求强一致性，那么只要保证 r + w 大于 n 即可。这里 n 是 5，那么就让 r 和 w 都为 3。
因为 𝑤 + 𝑟 > 𝑛，读取 r 个副本，至少有一个副本必然包含了最近的成功写入。但是问题来了，剩余的两个节点的数据该怎么办呢？虽然目前可以实现强一致性，但节点之间的数据还是不一致的。
在 Dynamo 风格的数据存储中经常使用两种机制：
1）读修复（Read repair）
当客户端并行读取多个节点时，它可以检测到所有陈旧的响应。如果发现某个节点的值是旧值，那么会将新值写回。因此这种方法适用于频繁读取的值。
2）反熵过程（Anti-entropy process）
关于反熵我们在介绍 gossip 的时候已经说过了，数据存储系统的后台进程会不断查找副本之间的数据差异（随机挑选两个副本），并将缺少的数据从一个副本复制到另一个副本。与基于领导者的复制不同，反熵不会以任何特定的顺序复制写入（但我们在设计的时候可以适当调整），并且在复制数据之前可能会有显著的延迟。
r 和 w 应该怎么设置
如果你有 n 个副本，并且使得 𝑤+𝑟 > 𝑛，那么读取的节点中至少有一个具有最新值的节点，因为写的节点集合和读的节点集合一定会有重叠。但当满足 𝑤+𝑟 > 𝑛 时，有很多种组合，那么 r 和 w 到底应该怎么设置呢？
r 和 w 的设置方式，取决于我们想要优化哪一方面的性能。如果 w = n，那么每次写数据时所有节点都要写，然后读的时候只要读一个就行，显然这是为了优化读性能；如果 r = n，那么每次读数据时要读所有的节点，然后写的时候只需要写一个就行，显然这是为了优化写性能；如果 r 和 w 接近，等于 (n + 1) / 2，那么容错能力比较好，能容忍 (n - 1) / 2 个点发生故障。
如果读写频率相差不大的话，那么建议将 r 和 w 设置为第三种，总之只要保证读写使用的节点做交集之后至少包含一个节点即可。因此法定人数的配置是很自由的，这使得分布式算法的设计有一定的灵活性。
所以 Quorum NWR 是非常实用的一个算法，能有效弥补 AP 型系统缺乏强一致性的痛点，给业务提供了按需选择一致性级别的灵活度。
当然啦，我们这里是让 r + w > n，为了实现强一致性。但也可以让 r + w <= n，实现最终一致性，在这种情况下，由于法定条件不满足，读取的时候可能会读不到包含最新值的节点。然后经过一段时间的同步，才会读到新数据。
另外 r+w <= n 这种配置允许更低的延迟和更高的可用性，比如网络中断，并且许多副本变得无法访问，可以继续处理读取和写入的机会更大（因为 w 和 r 更小）。只有当可达副本的数量低于 w 或 r 时，系统才分别变得不可用于写入或读取。
本文参考自分布式神书《DDIA》