分布式系统,程序语言,算法设计

Paxos Made Simple 论文导读

引子

Paxos 是分布式系统中绕不过去的一个算法,但出了名的难以理解。因此我看到 Paxos 也是一直绕着走,但是绕的多了总感觉有些遗憾。于是过去一周闲暇时间搜集了很多资料,尝试了很多打开方式,总算初窥门径。便趁着新鲜,将脑中的理解赶到纸上,做个小结,以备后日不时之需。

Paxos 算法的发明人 Leslie Lamport 是分布式系统的奠基人之一,轶事颇多,从 Paxos 这个名字也能窥得一斑:Paxos 是 Lamport 为了引出分布式系统共识问题,所虚拟的一个古希腊城邦。在最初的相关论文 The Part-Time Parliament 发表于 1998 年后,很多人都表示理解不能。于是 Lamport 在 2001 年,又使用相对简练的语言和逻辑,将其主干思想重新阐述了一遍,便有了 Paxos made simple

Lamport 在 Paxos made simple 论文的摘要只有一句话:

The Paxos algorithm, when presented in plain English, is very simple

然而,我却无法理解这种 simple。

作者:木鸟杂记 https://www.qtmuniao.com/2021/06/14/paxos/zhixing, 转载请注明出处

建模

按我的一贯理论,如果你理解不了一个简单的东西,一定是打开方式(建模方式)不对。既然作者说该理论很 simple,那么只要能找到契合我上下文的解析,一定能知道他在干什么。

于是我搜索了很多资料,在看了知行学社——paxos和分布式系统视频后,茅塞顿开。该视频用了程序员熟悉的 Client-Server + 锁的模型来层层递进地讲解了 Paxos 的一些概念和约束条件,让我在感性上对 Paxos 要解决的问题和解决的思路有个初步的把握,之后再去读论文,很多地方便通了。

那么知行学社是如何拆解这个共识算法的呢?下面依照我对论文的理解,来简要梳理下视频内容,部分内容有改动。没看过视频的,强烈推荐先去看看视频。

:本文没有涉及到 Learner,也没有对原论文进行详细解读,更没有对 Paxos 工程化进行探讨。本来想将他们写到一篇文章中,但后来发现实在是太长了,于是拆成一个系列吧。

基本概念

作为一个程序员来理解 Paxos,肯定会有两个疑问:Paxos 是用来解决什么问题的?Paxos 在工程中如何应用到分布式系统?

Paxos 算法是用来确定一个不可变量的取值的。不可变的、单个取值,貌似对分布式系统用处不大。但我们通过一个桥梁——写前日志(WAL),也可以叫操作日志,来构建一个对外表现的像单机一样的分布式系统。

一方面,操作日志可以视为一组不可变的操作记录组成的序列,对于不可变的单个操作记录来说,多机达成共识正是 Paxos 所解决的问题。只要稍加扩展,便能让多机就确定操作的序列达成共识。另一方面,如果我们有一份全局唯一的操作序列,每个副本便可以按相同顺序执行此操作序列,构建相同的状态机,而状态机的表达能力是很强的,可以解决一大类系统问题。

问题抽象

下面,回到对 Paxos 算法本身的理解。视频首先抽象出一个实际工程问题,并逐步给出更好的解决方案,来拆解 Paxos 算法约束。

问题描述:设计一个系统,存储名称为 var 的变量。

系统角色

  1. 系统内部由多个 Acceptor 组成,负责存储和管理 var 变量。
  2. 系统外部有多个 Proposer 并发的调用系统 API,向系统提交不同的 var 取值。

系统 APIpropose(var, V) → <OK, f> or <Error> 其中 f 是 Acceptor 中 var 保存的值。

系统要求

  1. 一旦 var 的值确定,便不能更改,之后可以一直读到该值
  2. 可以容忍任意 Proposer 出现故障
  3. 可以容忍半数以下的 Acceptor 出现故障

跟算法题一样,可以先简化问题,理出基本思路。然后泛化,逐步得到原问题的解。

方案一

假设系统由单个 Acceptor 组成。

为了处理多个 Proposer 的并发调用,最简单的做法,可以在 Acceptor 上使用一把互斥锁,并且通过两阶段来进行 Propose:

Prepare 阶段:

某 Proposer 通过 Acceptor::prepare 获取 Acceptor 的锁和当前 var 的值 f。如果发现锁被占用,则 abort。

Accept 阶段

如果 f 为 null,则通过 Acceptor::accept(var, V),接受该 Proposer 的数据 V。

如果 f 不为 null,则通过 Acceptor::release() 释放锁。

该方案存在的问题:不能容忍 Proposer 机器故障。当 Proposer 调用 Acceptor::prepare 获取锁之后,挂掉了,就会一直占用锁,使得 Acceptor 不可用。

方案二

解决 Proposer 故障问题。

Proposer 比较多,单个 Proposer 挂掉再所难免。既然我们不能决定 Proposer 的生死,就只能在锁上做文章了。比如给锁引入超时,再比如让锁可抢占。对于前者,超时阈值不太好控制:太长性能不行,太短有可能频繁重试。后者就好一些,只有有新的 Proposer 请求时才会让原来的锁失效。

下面展开下可抢占锁的设计。

可抢占必然会引入优先级问题:高优先级 Proposer 可以抢占低优先级 Proposer 的锁。我们使用一种最简单的优先级规则:每个 Proposer 在要锁的时候,需要首先申请一个号码 n,号码大 Proposer 优先级高。这里没有采用视频中的 epoch 叫法。而使用了论文中的叫法 n,但意思是一样的。该号码可以由一个全局发号器来分配,保证单调递增;也可以直接用时间戳,但会有多机器间戳的同步问题。

视频中还提到另外一个问题,即 Proposer2 抢占了 Proposer1 的锁后发现,Acceptor 的值 var 已经被设置,此时,Proposer2 能不能修改呢?但我觉得在单个 Acceptor 中这不是问题,只要任何时候都遵循 Acceptor 的 var 被设置了不能再被修改即可。

方案二和方案一大体相同,Acceptor 只需要多保存一个状态:当前授予锁的 Proposer 的号码 latest-n。并且在两个阶段都首先比对 Proposer 的标号 proposer-n 和当前保存的标号 latest-n,来决定拒绝请求还是接纳请求。此外,每次不需要调用接口显式的释放锁。

该方案存在的问题:单个 Acceptor 宕机会导致系统无法提供服务。

方案三

在方案二基础上引入多个 Acceptor。

这里假设 Acceptor 集群数量固定。该情况下,扩展方案二时会遇到几个问题:

  1. Acceptor 集群如何确定一个值?过半 Acceptor 的 var 被设置成同一值;那么对于单个 Acceptor 来说,就要求能多次 accept 值。
  2. Proposer 在 prepare 阶段发现某些 Acceptor 有值,是否可以直接释放锁?不一定,因为现在有多个 Acceptor ,且过半的 Acceptor 认定同一个值才算结束。因此在该值数量没有过半时, Proposer 需要继续 accept 阶段,但此时选取什么值就需要考虑一下了:是从阶段一种获取到的值集合中随机选一个,还是按照某种规则选一个。为了快速收敛,我们选择具有最大标号的值。
  3. Proposer 如何在 prepare 阶段获取 Acceptor 集群的“锁”?获取过半的 Acceptor 的锁。根据鸽巢原理,某个标号 n 最多有一个 Proposer 获取到锁。

解决了上述几个问题,则最终方案呼之欲出:

对于 Proposer:

prepare 阶段:获取标号 n,向 Acceptor 集群发起 prepare(n) 请求,未收到过半 OK 回复则终止。收到过半 OK 回复时,若回复中存在非 null 的值,则选取标号最大的值 v;若回复中不存在任何值,则可以选择任意值 v 发起 accept 请求。

accept 阶段:使用上阶段选定的值 v,向 Acceptor 集群发起 accept(n, v) 请求。如果收到半数以上 OK,则说明集群接受 v 成功。否则,说明可能被更高标号的 Proposer 抢占了或者某些 Acceptor 故障。

:两个阶段并不用向集群中所有 Acceptor 逐一发起请求,只要选择一个过半的集合就可。并且阶段一和阶段二选择的 Acceptor 集合也不必相同。

对于 Acceptor:

需要维护的状态:当前 accept 的值和对应标号 <accepted-n, accepted-v>,以及当前授权的锁的最大标号:latest-n

prepare 阶段:收到 Proposer 的 prepare(n) 请求,如果 latest-n > n,则返回 Error。否则返回 <OK, accepted-n, accepted-v>。并更新 latest-n 为 n。

accept 阶段:收到 Proposer 的 accept(n, v) 请求,如果 latest-n > n,则返回 Error。否则接受请求,更新 latest-n 、 accepted-n、accepted-v,并返回 OK

小结

看了知行学社视频,结合上面的梳理,再去读 Paxos made simple 论文,应该能有个比较好的理解。后来我想,直接读论文难以理解原因是什么?一方面,论文没有太多铺垫,上来就开始推理,而我们脑中并没有一个合适的模型来理解论文中提到的各种概念;另一方面,论文是一个逆向组织的过程,即从结论逐步推出需要满足的条件,最后再将所有条件组合起来。这些都造成了直接拿起论文就读的困难。

最后,再次总结下 Paxos 的理解要点:

  1. 弄明白原始 Paxos 的目的,就是多个 Acceptor 对单个不可变值达成共识。
  2. 使用工程中 Client-Server + 锁的模型辅助理解。
  3. 将算法分为两阶段可以快速失败。
  4. 标号 n 的引入是为了解决死锁以及抢占顺序问题。
  5. 阶段二选取最大标号的值,可以使得 accept 过程快速收敛。

参考资料

  1. 论文:http://www.scs.stanford.edu/20sp-cs244b/sched/readings/paxos_made_simple.pdf
  2. 翻译:https://www.cnblogs.com/yaodd/p/6150498.html
  3. 知行学社——paxos和分布式系统:https://www.bilibili.com/video/BV1Lt411m7cW

我是青藤木鸟,一个喜欢摄影的程序员,欢迎关注我的公众号:“木鸟杂记”。

wx-distributed-system-muniao-s.jpg