Paxos 算法那些事

paxos 云原生 数据一致
1163

Paxos 是 Lamport 提出的最著名的基于消息传递的一致性算法，在 2006 年 Google 将其运用于 Chubby 锁服务器上后便受到了巨大的关注。

1998 年，Lamport 在其发表的论文 《The Part-Time Parliament》中虚构了一个古希腊诚邦，并通过寓言的方式讲解了如何在城邦中形成一个确定性的提案。论文提出后，许多人表示难以理解，于是 Lamport 在 2001 年又发表了第二篇论文 《Paxos made simple》。

在学习过程中我发现该算法不是很好理解，特别是很难与分布式系统结合起来。不过在观看了 知行学社 的有关视频后，豁然开朗。

本文主要为该视频学习后的一些记录。

Paxos 想要解决什么问题

Paxos 算法是用来确定一个不可变量的取值的 。

在分布式系统中，为了具有分区容错，我们需要将数据的副本存储到多个节点中，如果不作任何处理，则在此过程中可能会出现网络延迟等问题导致节点中的数据不一致。而 Paxos 算法允许我们在一个分布式系统中确定一个不可变变量的取值。

这里取值可以是任意二进制数据，并且一旦该值确定，则不可更改，并且可以被获取。

这里的不可更改主要是描述在并发修改的过程中，只有一个请求可以修改成功，之后都不能修改。

可以被获取则主要描述一旦该值确定之后，即使在有少量节点宕机的情况下，分布式系统外部也能获取到该确定的值。

那么确定一个不可变变量的取值有什么作用呢？

例如在分布式存储系统中应用 Paxos，我们可以把每个节点看做一个状态机，其当前状态由两方面决定，一是初始状态，二是操作序列 [Op1, Op2, Op3 …, Opn] 。

初始状态可以由程序写死，而操作序列中的每一个操作可以看成一个不可变变量（不允许撤销）。我们只需要使用 Multi-Paxos (多次使用 朴素 Paxos 算法确定多个值) 确定这个操作序列，则整个分布式系统可对外表现为一个单机的状态机，进而提供数据存储等功能。

提出问题

为了便于理解，视频提出了一个工程问题，并通过不断优化来最终引出 Paxos 算法。

设计一个系统，来存储名为 var 的变量。

负责存储的系统由多个 Acceptor 组成 。外部有多个 Proposer 及其任意并发调用 Api，向系统提交不同的 var 取值或读取 var 的取值 。

这里的 API 接口为 ：Acceptor::propose(var, V) => <ok, f> or <error, null>

这里读取该值不存在问题，因此不做分析，Acceptor 直接将自己设备中存储的值返回即可。

要求：

  1. 一旦 var 的值被确定，便不能更改，之后可以一只获取到该值
  2. 可以容忍任意 Proposer 故障
  3. 可以容忍半数以下的 Acceptor 故障

方案一

假设系统只有一个 Acceptor，则只需要解决 Proposer 的并发调用。这里可以采用一种互斥锁的方式解决，并 propose 操作分为两个阶段：

  • Prepare ：首先调用 Acceptor::prepare 获取 Acceptor 的锁和当前 var 的值 f，如果发现锁被占用，则停止 propose 操作。
  • Acceppt ：
    • 如果 f 为 null，则调用 Acceptor::accept(var, v)，将 Acceptor 的 var 值设置为 v 。
    • 否则，则调用 Acceptor::release() 释放锁

该方案会出现死锁的问题，当 Proposer 调用 Acceptor::prepare 获取锁后宕机，则会一直占用锁，整个系统将不可用。因此不能容忍 Proposer 故障 ，需要改进。

方案二

为了解决方案一的死锁问题，我们引入一个可抢占锁机制：

Proposer 向 Acceptor 申请访问权时指定编号 epoch，获得访问权之后才能向 acceptor 提交取值。

对于 Acceptor ，采用 喜新厌旧 原则，其需要记录自己授权的最大的编号 last_epoch，对于任何请求，如果其附带的 epoch 小于 last_epoch ，则不接受其请求，返回 <error>。

对于 Proposer 来说，采用 后者认同前者 原则：

  • 在肯定旧的 epoch 没有形成确定性取值时，新的 epoch 会提交自己的 value
  • 一旦旧的 epoch 形成了确定性取值，则新的 epoch 会认同此取值。

最终实现：

acceptor 保存的状态：

  • 当前 var 的取值 var
  • 当前 var 的值赋值时的 epoch 编号 accepted_epoch
  • 最新授予的 epoch 编号 lastest_epoch

接口 API：

Acceptor::preprare(epoch)

  • 如果 epoch大于 lastest_epoch，则给予访问权，同时返回 accepted_epoch 与 var

  • 记录 last_epoch = epoch

Acceptor::accept(var, prepared_epoch, V)

  • 当 lastest_epoch == prepared_epoch 时，将 var 设置为 V，accepted_epoch 设置为 prepared_epoch
  • 否则，返回 error

Proposer 两阶段：

  • 选取当前时间戳作为 epoch，通过 Acceptor::prepare 获取访问权，如果能获取则同时获得当前 var 的取值，如果不能获取则直接停止。
  • 第二阶段需要根据第一阶段获取到的当前 var 取值来进行处理
    • 如果 var 的取值为空，则调用 Acceptor::accept(var, prepared_epoch, V) 将数据 V 提交，因为存在并发，因此这里可能会失败。
    • 如果 var 的取值不为空，则说明已经有确定性取值，因此不调用任何 acceptor 的接口，直接将 var 作为获取到的值返回 。

在该方案中，只要 Acceptor 不宕机，则该系统一定能成功运行，包括某些极端情况 （例如 两个 Proposer 同时经过阶段一后同时执行阶段二），同时 因为 只有一个 Acceptor，所有异步请求在进入 Acceptor 后都会变为 串行请求 。

但该方案的前提 只有一个 Acceptor 决定了该方案中 Acceptor 存在单点故障。

方案三

方案三在方案二的基础上引入多个 Acceptor，实际上该方案也就是 Paxos 算法最终的模式 。

Acceptor 的实现保持不变，仍然采用 喜新厌旧 的 原则 。

同时因为引入了多个 Acceptor，因此不定值的确定需要引入新的原则。也就是 Paxos 中的半数以上确定原则，即：

一旦某 epoch 的取值 f 被半数以上的 acceptor 接受，则认为该值已经确定为 f 。

这里的半数是法定半数，为所有节点数量的半数，不是当前正常工作的设备的半数，即宕机的节点也要被计算在内。

因此 Proposer 的实现需要进行一些改变：

  • 选定时间戳作为 epoch，调用所有 acceptor 中的 Acceptor::prepare 获取访问权，同时也会得到一组取值。如果能不能获取半数以上 Acceptor 的访问权，则直接停止。否则进入第二阶段。
  • 在方案一获取到的所有取值中
    • 如果获取到的 var 取值都为空，则调用 所有Acceptor::accept(var, prepared_epoch, V) 将数据 V 提交，如果能收到半数以上 Acceptor 成功，则返回成功，否则返回失败。这里失败后会重新进行阶段一 。
    • 如果获取到的 var 取值不为空，则认同 最大 accepted_epoch 对应的 f，调用所有 Acceptor::accept(var, prepared_epoch, f) 将 f 作为新值提交修改，同时如果能收到半数以上 Acceptor 成功，则返回成功，否则返回失败。

Liveness 问题

方案三中，如果初始状态 var 没有取值，而两个 profoser 交替进行阶段一和阶段二，每次都将对方的访问权抢占，则可能会导致活锁。称为 Paxos 算法的 Liveness 问题。目前对于该问题，一般是限定 Proposer 为一个解决。当然在真正的工程中，为了防止 Proposer 单点故障，一般采用投票选举的方式选出 Proposer，在 之后 zab 或 raft 协议中会提及。

总结

  1. 不可变变量包括两个信息，其取值，与其接受对应的 epoch
  2. Acceptor 采用 喜新厌旧 原则，只接受 epoch 大的请求
  3. Profoser 采用 后者认同前者 原则 与 半数以上接受 原则
  4. 在实际应用中，需要对该算法作进一步建模，例如实际上 Profoser 与 Acceptor 都作为分布式系统内部的节点。而外部的读请求则直接返回，写请求则通过重定向等方式转发给 Profoser 执行。
  5. 在实际应用中，使用朴素 Paxos 确定单个不变量取值的场景较少，一般为使用 Multi-Paxos 确定多个取值作为一组操作序列（日志）。
  6. 在实际应用中，为了避免活锁问题，一般需要确保只有一个 Profoser，而该算法本身没有确定该方面，因此在具体的协议中一般会另外规定选举的算法。
  7. 关于 Multi-Paxos 的定义和范围，网上的资料参差不齐，存在争议，因此之后将避开这个名词，直接讲解具体的一致性协议 zab 与 raft 。