分布式系统理论之Quorum机制

一，Quorum机制介绍

对于数据存储而言，为了提高可用性（Availability），采用了副本备份，比如对于HDFS，默认每块数据存三份。某数据块所在的机器宕机了，就去该数据块副本所在的机器上读取（从这可以看出，数据分布方式是按“数据块”为单位分布的）

但是，问题来了，当需要修改数据时，就需要更新所有的副本数据，这样才能保证数据的一致性（Consistency）。因此，就需要在 C(Consistency) 和 A(Availability) 之间权衡。

而Quorum机制，就是这样的一种权衡机制，一种将“读写转化”的模型。

在介绍Quorum之前，先看一个极端的情况：WARO机制

 WARO(Write All Read one)是一种简单的副本控制协议，当Client请求向某副本写数据时(更新数据)，只有当所有的副本都更新成功之后，这次写操作才算成功，否则视为失败。

从这里可以看出两点：①写操作很脆弱，因为只要有一个副本更新失败，此次写操作就视为失败了。②读操作很简单，因为，所有的副本更新成功，才视为更新成功，从而保证所有的副本一致。这样，只需要读任何一个副本上的数据即可。假设有N个副本，N-1个都宕机了，剩下的那个副本仍能提供读服务；但是只要有一个副本宕机了，写服务就不会成功。

 WARO牺牲了更新服务的可用性，最大程度地增强了读服务的可用性。而Quorum就是更新服务和读服务之间进行一个折衷。

Quorum机制是“抽屉原理”的一个应用。定义如下：假设有N个副本，更新操作wi 在W个副本中更新成功之后，才认为此次更新操作wi 成功。称成功提交的更新操作对应的数据为：“成功提交的数据”。对于读操作而言，至少需要读R个副本才能读到此次更新的数据。其中，W+R>N ，即W和R有重叠。一般，W+R=N+1

假设系统中有5个副本，W=3，R=3。初始时数据为(V1，V1，V1，V1，V1）--成功提交的版本号为1

当某次更新操作在3个副本上成功后，就认为此次更新操作成功。数据变成：(V2，V2，V2，V1，V1）--成功提交后，版本号变成2

因此，最多只需要读3个副本，一定能够读到V2(此次更新成功的数据)。而在后台，可对剩余的V1 同步到V2，而不需要让Client知道。

R表示Quorum中read节点的数量

W表示Quorum中writes/updates节点的数量

N表示系统中的节点数量

如果R=1, W=1, 也就是R+W=N=2, 客户端在A节点进行写入, 从B节点完成读取, 这种情况下客户端可能无法得到一致性的数据;

如果R=2, W=1, 也就是R+W>N, 客户端可以在任意的A或者B节点进行写入, 但是客户端需要同时读取节点A和B的数据, 这种情况是可以保证客户端得到最新的数据状态, 这也就是一些NOSQL DB通常说的双读(read repair);

如果W=2, R=1, 也就是R+W>N, 显而易见这种情况下客户端同时写入节点A和B, 读取任意一份数据即可满足一致性结果要求.

R+W>N, 这就是Quorum一致性协议.

 Quorum机制。每次写入的机器数目达到大多数(W)时，就认为本次写操作成功了。