分布式一致之 Paxos

之前看了很多次 Paxos 的原理分析,一直都是一知半解的状态,在对 Raft 在实际项目中的落地有比较深的理解后,重新整理了 Paxos 的一些细节实现。

本文适合对 Paxos 已经有一定了解,但总是看了又忘对某些细节有所困惑的朋友阅读:)

基础

首先明确一个问题:Paxos 解决的是什么问题?

paxos 解决的是在多节点下在各个节点提出的 value 里只有一个 value 会被选中,并且这个被选中之后不可更改,所有的节点最终都接受这个 value 达成共识。在没完全理解 paxos 之前,建议不要考虑状态机或者 kv-db 的设计问题,简单把 paxos 当作是解决一个 value 被超过半数的节点接受之后不可继续更改的共识算法。

单 acceptor

先考虑系统由单个 acceptor 和多个 proposer 组成,通过互斥锁的机制来管理并发的 proposer 运行。proposer 首先向 acceptor 申请 acceptor 的互斥锁访问权,然后才能 acceptor 接受自己的值。

acceptor 保存变量 var 和一个互斥锁 lock,提供三个接口:

  1. Acceptor::prepare(): 加互斥锁,给予变量 var 的访问权,并返回 var 当前的取值 f。
  2. Acceptor::relase(): 解互斥锁,收回 var 的互斥访问权。
  3. Acceptor::accpet(var, v): 如果已经加锁,并且 var 没有取值,则设置 var 为 v,并且释放锁。

propse(var, v) 分为两阶段执行:

  1. 第一阶段:通过 acceptor::prepare 获取互斥访问权和当前 var 的取值。如果不能返回 error,此时互斥锁可能被别人占用。
  2. 第二阶段:根据返回的 var 的值 f,选择执行:如果 f 为 null,则通过 Acceptor::accept(var, v) 提交 v;如果 f 不为 null,则通过 Acceptor::relase() 释放权,返回

上面这样一种实现有一个问题,Proposer 在释放互斥访问权之前发生故障,会导致系统陷入死锁。

为了解决死锁问题可引入抢占式访问,proposer 向 acceptor 申请访问权指定 epoch,acceptor 一旦接收到更大的新 epoch 的申请,马上让旧的 epoch 访问权失效,然后给新 epoch 发放互斥锁访问权。

新 epoch 抢占旧 epoch 的访问权,会让旧的访问权失效。同时不同 epoch 的 proposer 之间采用后者让同前者的原则,根据上面两阶段的原则,如果旧的 epoch 没有生成确定的值,新 epoch 将会使用自己的 value。而一旦旧 epoch 已经生成确定的值,新 epoch 将会在 prepare 阶段得到这个值,并且认同这个值不会发生冲突。

修改后的 acceptor 的实现如下:

  1. Acceptor 保存的状态:当前 var 的取值 <accepted_epoch, accepted_value> 以及最新发放访问权的 epoch latest_prepare_epoch
  2. Acceptor::prepare(epoch): 只接收比 lastest_prepared_epoch 更大的 epoch,并给予访问权,记录 latest_prepared_epoch = epoch,返回当前 var 的取值。
  3. Acceptor::accept(var, prepared_epoch, v): 验证 lastest_prepared_epoch==prepared_epoch,并设置 var 的取值 <accepted_epoch, accepted_value> = <prepared_epoch, v>

多 acceptor

单个 acceptor 有可能存在故障,引入多个 acceptor。一旦某 epoch 的取值被半数以上的 f 被半数以上的 acceptor 接受,则认为此 var 取值被确定为 f 不可被更改。

  1. Propose(var, v) 一阶段: 选取 epoch,获取 epoch 的访问权和对应 var 取值。acceptor 回复 proposer 的原则和上边一样。只接收比 lastest_prepared_epoch 更大的 epoch,并给予访问权,记录 latest_prepared_epoch = epoch,返回当前 var 的取值。之前没有接受过值则返回 null。
  2. Propose(var, v) 二阶段:如果获得半数以上的访问权和对应的 var 取值:
    • 如果获取的 var 值都为空,则旧的 epoch 无法形成确定性取值,此时努力使(epoch, v)成为确定性取值:向所有的 acceptor 提交取值(epoch, v),如果收到半数以上成功返回 (ok, v),否则返回 error(被新的 epoch 抢占或者 acceptor 发生故障)。
    • 如果 var 的取值存在,认同最大 accepted_epoch 对应的取值 f。如果 f 已经是确定性取值,直接返回 (ok, f),否则所有 acceptor 提交 (epoch, f),如果收到半数以上成功返回 (ok, f),否则返回 error(被新的 epoch 抢占或者 acceptor 发生故障)。

learner

为了获取一个已经被选中的 value,learner 必须要确定已经有一个 proposal 被 majority acceptor accpet 了。最简单的做法就是让每个 acceptor 在 accpet 了一个 proposal 之后向所有的 learner 发送这个 proposal。这能让 learner 尽快地找到被选中的 value,但这需要 acceptor 对每个 learner 进行回复——回复的数量为 acceptor 和 learner 数量的乘积。

我们可以让 acceptor 把它们的接受情况都发送给一个 distinguished learner,这个 learner 再转而通知其他的 learner 有个 value 被接受了。这种方法需要额外的一个 round 来让所有的 learner 发现被选中的 value。同时这样也是非常不可靠的,因为这个 distinguished learner 可能故障,但它只需要 acceptor 和 leaner 和的通信数。

活锁

两个 proposer 持续发送比对方的 epoch 高的 proposal,并且最终它们两者没有一个被选中。Proposer p 通过 epoch n1完成了 phase 1。另一个 proposer q 接着通过 epoch n2 > n1完成了 phase 1。proposer p 在 phase 2 的以 n1 标记的 accept request 会被所有 acceptor 拒绝,因为它们已经承诺不接受任何 number 小于 n2 的 proposal。因此 proposer p 开始用新的 proposal number n3 > n2 来开始并完成 phase 1,而这又导致了 proposer q 在 phase 2 的 accept 被忽略。

为了保证流程的执行,必须选出一个 distinguished proposer 来作为 leader。如果 distinguished proposer 能和 majority 进行通信,并且使用了一个比所有已经使用的 epoch 都大的 number,那么它就能成功发送一个已经被接受的 proposal。通过拒绝已有的 proposal 并且通过更高的 epoch 重试,distinguished proposer 最终会选择到一个足够大的 epoch。

Raft、Muti-Paxos、ZAB 等都是这样解决的,选出一个唯一的 leader。为了解决 leader 容量问题可以引入数据分区,比如 tidb 的 raft-group,下次再总结一下。

总结

Paxos 算法整体分两阶段执行:

  1. prepare:
    1. proposer 向 acceptor 发送 epoch 为 n 的 prepare request。
    2. 如果一个 acceptor 接受了一个 epoch 为 n 的 prepare request,并且 n 大于任何它已经回复的 epoch,那么它将承诺不再接受任何 epoch 小于 n 的 proposal,并且回复已经接受的最高 epoch 的 proposal value。
  2. accpet:
    1. 如果 proposer 接受了来自 majority acceptor 对它的 prepare request 的回复,那么接下来它将给这些 acceptor 发送一个 epoch 为n,value 为 v 的 proposal 作为 accept request。其中 v 是收到的回复中最高 epoch 的 proposal 的 value,或者如果回复中没有 proposal 的话,就可以是它自己选的值。
    2. 如果 acceptor 收到一个 epoch 为 n 的 accept request,如果它没有对 number 大于 n 的 prepare request 进行过回复,那么就接受该 accept request。