Follow me on GitHub

基于 Quorum 的投票机制

quorum [ˈkwɔ:rəm],法定人数

Quorum 机制是一种投票算法,核心思想是:

执行某操作之前,必须先获取足够的票数。

在分布式系统中,Quorum 投票有两种常见用法:

  • 副本读写控制:保证同一数据的多个副本在每一时刻,只能用于读 or 写;
  • 事务提交协议:存在网络分区时,保证分布式事务的原子性;

副本读写控制

假设每份数据有 V 个副本,每个副本对应一票,读、写操作首先要请求副本以获取其票数,定义:

  • read quorum R
    • 最小读票数:读操作获取的票数必须大于该值才允许读;
  • write quorum W
    • 最小写票数:写操作获取的票数必须大于该值才允许写;

VRW 必须满足:

  1. R + W > V
    • 保证对于每份数据,不会 同时读和写
  2. W > V / 2
    • 保证对于每份数据,不会同时出现 两个写,即写操作是串行的

延伸一下:

  • 没有规定 R > V / 2,即 quorum 机制允许 多个读同时发生,即允许 并发读
  • 考虑 write -> read 序列,因为 R + W > V,因此 WV 之间至少有一个重叠(鸽巢原理),从而保证 write 之后,read 操作至少会获取一个 最新副本

两条规则一起能保证系统的一致性模型为 one-copy serializability(1SR)。

Quorum 投票对于分布式数据库很重要,为了保证可用性,分布式数据库对每份数据做复制冗余,考虑可用性,副本(replica)越多越好,但副本越多,对应的写操作、磁盘占用、响应时间都要翻倍,从而响应性能,因此副本数量需要综合权衡两者。

一般而言,3 个副本太少(只能容忍一个副本失败,可用性不足),5 个副本太多(性能太差),借助 Quorum 机制,5 个副本只需要完成 3 个写即可响应成功,大大提升了写操作的响应速度,又没有减弱可靠性,因此很好。

5 副本在保证高可靠性的同时,代价很大:

  • 5 倍磁盘占用
  • 5 倍贷款占用
  • 1/5 吞吐量

所以 Quorum 常用于存储集群 配置信息/元数据(如 Zookeeper),但较少用于真正的数据存储,一个例子是 HDFS,它使用 Quorum 实现高可用的 namenode,但真正的数据存储并没有使用 Quorum.

Quorum 投票本质上是把 写负载 转移到了 读负载,是一种设计权衡。

比如 5 副本时,写入成功需要 5 次写,读时仅需访问一个副本即可;但 5 次写入的开销太大,设计者认为用户无法接受,因此决定采用 Quorum 投票,并决定 W = 3,R = 3,所以此后 3 次写入即认为写成功,成功 减小了写入负载,但代价是读操作必须至少访问 3 个副本才能保证其中有最新副本,否则可能导致脏读。

只要保证 W + R > 5,且 W > 2.5 即可,具体选值反应了设计者的不同权衡,以下都是合法值:

  • W = 3,R = 3
  • W = 3,R = 4
  • W = 3,R = 5
  • W = 4,R = 2
  • W = 4,R = 3
  • W = 4,R = 4

比较如下 3 种典型选择:

  • W = 3,R = 3
  • W = 4,R = 2
  • W = 5,R = 1

第一种比较中庸,读写负载分配均匀,第二种减小了读负载,代价是更大的写负载,第三种是 Quorum 投票的极端场景,相当于最初未采用 Quorum 时的方案。

事务提交协议

在分布式系统中,事务也是分布式的,可能涉及多个不同节点,为保证原子性,事务必须在所有节点上同时 commit 或 abort,若系统发生网络故障(如网络分析),导致部分节点之间无法通信,则可借助 Quorum 机制保证事务的原子性。

每个节点对应一票,若系统共有 V 个节点,则总共 V 票,事务提交前(commit or abort),各个节点投票说明自己的行为,事务整体行为由 投票结果 决定,定义:

  • commit quorum C
    • 最小 commit 票数:事务 commit 前必须获取的最少票数;
  • abort quorum A
    • 最小 abort 票数:事务 abort 前必须获取的最少票数;

VCA 必须满足:

  • C + A > V

C + A > V 保证事务只能 commit 或 abort,两者不会 同时发生,是 commit 还是 abort 由各个节点的投票结果决定,因此可保证原子性。


参考: