Paxos 算法那些事

何言 2021年09月02日 181次浏览

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 。