可靠分布式系统- Paxos 的直观解释

vlambda
2022-05-14

可靠分布式系统- Paxos 的直观解释

前言

paxos 是什么？

在分布式系统中保证多副本数据强一致的算法。

paxos 有啥用？

没有 paxos 的一堆机器, 叫做分布式；
有 paxos 协同的一堆机器, 叫分布式系统。

Google Chubby 的作者 Mike Burrows 说过：

这个世界上只有一种一致性算法，那就是Paxos …

其他一致性算法, 都可以看做 paxos 在实现中的变体和扩展。

另外一个经常被提及的分布式算法是【raft】，raft 的贡献在于把一致性算法落地。因为【Leslie Lamport】的理论很抽象，要想把他的理论应用到现实中，还需要工程师完全掌握他的理论再添加工程必要的环节才能跑起来。

经常有人问起 raft 和 paxos 的区别，或在实现中应该选择哪个，在不了解 paxos 之前可能会有这种疑问。对于这个问题, 就像是被问及四则运算和算盘有什么区别，小店老板应该使用四则运算还是用算盘结账一样。

记得 Leslie Lamport 2015 年时来了一次北京，那时会场上有人也问了老爷子 paxos 和 raft 有啥区别。

老爷子当时给出的回答是：没听过 raft…

raft 的核心可以认为是 multi paxos 的一个应用，对于要掌握一致性算法的核心内容，从 paxos 入手，更容易去掉无关干扰，直达问题本质。所以我们选择 paxos 作为了解一致性算法的入口，聊开了聊透了。

网络上 raft 比 paxos 流行，因为 raft 的描述更直白一些，实际上 raft比 paxos 更复杂。raft 详细的解释了“HOW”，缺少“WHY”的解释。paxos 从根本上解释清楚了“WHY”，但一直缺少一份通俗易懂的教程，以至于没有被更广泛的接受。所以就有了本文，一篇 paxos 入门教程，从基本的分布式中的复制的问题出发，通过逐步解决和完善这几个问题，最后推导出 paxos 的算法。

本文分为 2 个部分:

前 1 部分是分布式一致性问题的讨论和解决方案的逐步完善，用人话得出 paxos 算法的过程。如果只希望理解 paxos 而不打算花太多时间深入细节，只阅读这 1 部分就可以啦。
第 2 部分是 paxos 算法和协议的严格描述。这部分可以作为 paxos 原 paper 的实现部分的概括。如果你打算实现自己的 paxos 或类似协议。需要仔细了解协议细节，希望这部分内容可以帮你节省阅读原 paper 的时间。

图片是 xp 之前做过的 paxos 分享使用的 slides，在此基础上加入了更多口头解释的内容。

分布式系统要解决的问题

slide-01

paxos 的工作，就是把一堆运行的机器协同起来，让多个机器成为一个整体系统。在这个系统中，每个机器都必须让系统中的状态达成一致，例如三副本集群如果一个机器上上传了一张图片，那么另外 2 台机器上也必须复制这张图片过来。整个系统才处于一个一致的状态。

slide-02
我是无需解释的目录页。可靠分布式系统- Paxos 的直观解释

slide-03
分布式系统的一致性问题最终都归结为分布式存储的一致性。像 aws 的对象存储可靠性要求是 9 ~ 13 个 9。而这么高的可靠性都是建立在可靠性没那么高的硬件上的。

slide-04
几乎所有的分布式存储（甚至单机系统），参考【EC 第一篇：原理】，【EC 第二篇：实现】，【EC第三篇：极限】都必须用某种冗余的方式在廉价硬件的基础上搭建高可靠的存储。而冗余的基础就是多副本策略，一份数据存多份。多副本保证了可靠性，而副本之间的一致，就需要 paxos 这类分布式一致性算法来保证。

slide-05
在早些年各种各样的复制策略都被提出来来解决各种场景下的需要。除了复制的份数之外，各种各样的算法实际上都是在尝试解决一致的问题。从下一页开始简单回顾下各种复制策略，看看他们的优缺点以及 paxos 如何解决副本之间一致性的问题。

不太完美的复制策略

slide-06
无需解释的目录页可靠分布式系统- Paxos 的直观解释

slide-07
主从异步复制是最简单的策略之一，它很容易实现，但存在一个问题：客户端收到一个数据已经安全（OK）的信息，跟数据真正安全（数据复制到全部的机器上）在时间上有一个空隙，这段时间负责接收客户端请求的那个机器（master）如果被闪电击中或被陨石砸到或被打扫卫生的大姐踢断了电源，那数据就可能会丢失。因此它不是一个可靠的复制策略（使用主从异步复制要求你必须相信宇宙中不存在闪电陨石和扫地大姐）。

slide-08
跟主从异步复制相比，主从同步复制提供了完整的可靠性：直到数据真的安全的复制到全部的机器上之后，master 才告知客户端数据已经安全。

但主从同步复制有个致命的缺点就是整个系统中有任何一个机器宕机，写入就进行不下去了。相当于系统的可用性随着副本数量指数降低。

slide-09
然鹅，在同步和异步之间，做一个折中，看起来是一个不错的方案。这就是半同步复制。它要求 master 在应答客户端之前必须把数据复制到足够多的机器上，但不需要是全部。这样副本数够多可以提供比较高的可靠性；1台机器宕机也不会让整个系统停止写入。

但是它还是不完美，例如数据 a 复制到 slave-1，但没有到达 slave-2；数据 b 复制达到了 slave-2 但没有到达 slave-1，这时如果 master 挂掉了需要从某个 slave 恢复出数据，任何一个 slave 都不能提供完整的数据。所以在整个系统中，数据存在某种不一致。

slide-10
为了解决半同步复制中数据不一致的问题，可以将这个复制策略再做一改进：多数派读写：每条数据必须写入到半数以上的机器上。每次读取数据都必须检查半数以上的机器上是否有这条数据。

在这种策略下，数据可靠性足够，宕机容忍足够，任一机器故障也能读到全部数据。

slide-11
然鹅多数派读写的策略也有个但是，就是对于一条数据的更新时，会产生不一致的状态。例如：

node-1，node-2 都写入了 a=x
下一次更新时 node-2，node-3 写入了 a=y

这时，一个要进行读取 a 的客户端如果联系到了 node- 1和 node-2，它将看到 2 条不同的数据。

为了不产生歧义，多数派读写还必须给每笔写入增加一个全局递增的时间戳。更大时间戳的记录如果被看见，就应该忽略小时间戳的记录。这样在读取过程中，客户端就会看到 a=x₁，a=y₂ 这 2 条数据，通过比较时间戳 1 和 2 发现 y 是更新的数据，所以忽略 a=x₁ 这样保证多次更新一条数据不产生歧义。

slide-12
是的，但是又来了。这种带时间戳的多数派读写依然有问题。就是在客户端没有完成一次完整的多数派写的时候：例如，上面的例子中写入 a=x₁ 写入了 node-1 和 node-2，a=y₂ 时只有 node-3 写成功了，然后客户端进程就挂掉了，留下系统中的状态如下：

 
   
   
 
  
    
    
  node-1: a=x₁
node-2: a=x₁
node-3: a=y₂

这时另一个读取的客户端来了：

如果它联系到 node-1 和 node-2，那它得到的结果是 a=x₁
如果它联系到 node-2 和 node-3，那它得到的结果是 a=y₂

整个系统对外部提供的信息仍然是不一致的

slide-13
现在我们已经非常接近最终奥义了，paxos 可以认为是多数派读写的进一步升级，paxos 中通过 2 次原本并不严谨的多数派读写，实现了严谨的强一致 consensus 算法。

从多数派读写到 paxos 的推导

slide-14
首先为了清晰的呈现出分布式系统中的核心问题：一致性问题, 我们先设定一个假象的存储系统，在这个系统上，我们来逐步实现一个强一致的存储，就得到了 paxos 对一致性问题的解决方法。

slide-15
在实现中，set 命令直接实现为一个多数派写，这一步非常简单。而 inc 操作逻辑上也很简单，读取一个变量的值 i₁，给它加上一个数字得到 i₂，再通过多数派把 i₂ 写回到系统中。

slide-16
冰雪如你一定已经看到了这种实现方式中的问题：如果有 2 个并发的客户端进程同时做这个 inc 的操作，在多数派读写的实现中，必然会产生一个 Y 客户端覆盖 X 客户端的问题，从而产生了数据更新点的丢失。

而 paxos 就是为了解决这类问题提出的，它需要让 Y 能检测到这种并发冲突，进而采取措施避免更新丢失。

slide-17
提取一下上面提到的问题：让 Y 去更新的时候不能直接更新 i₂ 而是应该能检测到 i₂ 的存在，进而将自己的结果保存在下一个版本 i₃ 中，再写回系统中。

而这个问题可以转化成：i 的每个版本只能被写入一次，不允许修改。如果系统设计能满足这个要求，那么 X 和 Y 的 inc 操作就都可以正确被执行了。

slide-18
于是我们的问题就转化成一个更简单，更基础的问题：如何确定一个值（例如 iⱼ）已经被写入了。

直观来看，解决方法也很简单，在 X 或 Y 写之前先做一次多数派读，以便确认是否有其他客户端进程已经在写了，如果有，则放弃。

slide-19
但是！这里还有个并发问题，X 和 Y 可能同时做这个写前读取的操作，并且同时得出一个结论：还没有其他进程在写入，我可以写。这样还是会造成更新丢失的问题。

slide-20
为了解决上面的问题，存储节点还需要增加一个功能，就是它必须记住谁最后一个做过写前读取的操作。并且只允许最后一个完成写前读取的进程可以进行后续写入，同时拒绝之前做过写前读取的进程写入的权限。

可以看到，如果每个节点都记得谁读过，那么当 Y 最后完成了写前读取的操作后，整个系统就可以阻止过期的 X 的写入。

这个方法之所以能工作也是因为多数派写中，一个系统最多只能允许一个多数派写成功。paxos 也是通过 2 次多数派读写来实现的强一致。

slide-21
以上就是 paxos 算法的全部核心思想了，是不是很简单？剩下的就是如何实现的简单问题了：如何标识一个客户端如 X 和 Y，如何确认谁是最后一个完成写前读写的进程，等等。

slide-22
【Leslie Lamport】就这么把这么简单的一个算法写了个 paper 就获得了图领奖！骚年，改变世界就这么容易！

paxos 算法描述

接下来的篇幅中我们将用计算机的语言准确的描述整个 paxos 运行的过程。

slide-23
首先明确要解决的问题：

slide-24
我们要介绍的 paxos 实际上是最朴实的 classic paxos，在这之后我们顺提下几个老爷子对 paxos 的优化，multi paxso 和 fast paxos，它们都是针对 paxos 的理论层面的优化。

slide-25
paxos 算法中解决了如何在不可靠硬件基础上构建一个可靠的分布式系统的方法。但 paxos 核心算法中只解决网络延迟/乱序的问题，它不试图解决存储不可靠和消息错误的问题，因为这两类问题本质上跟分布式关系不大，属于数据校验层面的事情。

有兴趣可以参考【Byzantine Paxos】的介绍。

slide-26
本文尽量按照【Classic Paxos】的术语来描述。

老爷子后面的一篇【Fast Paxos】实现了 fast-paxos，同时包含了 classic-paxos，但使用了一些不同的术语表示。

Proposer 可以理解为客户端。
Acceptor 可以理解为存储节点。
Quorum 在 99% 的场景里都是指多数派，也就是半数以上的 Acceptor。
Round 用来标识一次 paxos 算法实例，每个 round 是 2 次多数派读写：算法描述里分别用 phase-1 和 phase-2 标识。同时为了简单和明确，算法中也规定了每个 Proposer 都必须生成全局单调递增的 round，这样 round既能用来区分先后也能用来区分不同的 Proposer（客户端）。

slide-27
在存储端（Acceptor）也有几个概念：

last_rnd 是 Acceptor 记住的最后一次进行写前读取的 Proposer（客户端）是谁，以此来决定谁可以在后面真正把一个值写到存储中。
v 是最后被写入的值。
vrnd 跟 v 是一对，它记录了在哪个 Round 中 v 被写入了。

v 和 vrnd 是用于恢复一次未完成的 paxos 用的。一次未完成的 paxos 算法运行可能留下一些没有达到多数派的值的写（就像原生的多数派写的脏读的问题）， paxos 中通过 vrnd 来决定哪些值是最后写入的，并决定恢复哪个未完成的 paxos 运行。后面我们会通过几个例子来描述 vrnd 的作用。

slide-28
首先是 paxos 的 phase-1，它相当于之前提到的写前读取过程。它用来在存储节点（Acceptor）上记录一个标识：我后面要写入；并从 Acceptor 上读出是否有之前未完成的 paxos 运行。如果有则尝试恢复它；如果没有则继续做自己想做的事情.

我们用类似 yaml 的格式来描述 phase-1 的请求/应答的格式：

 
   
   
 
  
    
    
  request:
 rnd: int

response:
 last_rnd: int
 v: "xxx",
 vrnd: int

phase-1 成功后，acceptor 应该记录 X 的 rnd=1，并返回自己之前保存的 v 和 vrnd。

slide-29
Proposer X 收到多数（quorum）个应答，就认为是可以继续运行的。如果没有联系到多于半数的 acceptor，整个系统就 hang 住了，这也是 paxos 声称的只能运行少于半数的节点失效。

这时 Proposer 面临 2 种情况：

所有应答中都没有任何非空的 v，这表示系统之前是干净的，没有任何值已经被其他 paxos 客户端完成了写入（因为一个多数派读一定会看到一个多数派写的结果），这时 Proposer X 继续将它要写的值在 phase-2 中真正写入到多于半数的 Acceptor 中。
如果收到了某个应答包含被写入的 v 和 vrnd，这时，Proposer X 必须假设有其他客户端（Proposer）正在运行，虽然 X 不知道对方是否已经成功结束，但任何已经写入的值都不能被修改！所以 X 必须保持原有的值。于是 X 将看到的最大 vrnd 对应的 v 作为 X 的 phase-2 将要写入的值。

这时实际上可以认为 X 执行了一次（不知是否已经中断的）其他客户端（Proposer）的修复。

slide-30
在第 2 阶段 phase-2，Proposer X 将它选定的值写入到 Acceptor ，这个值可能是它自己要写入的值，或者是它从某个 Acceptor 上读到的 v（修复）。

同样用类似 yaml 的方式描述请求应答：

 
   
   
 
  
    
    
  request:
 v: "xxx",
 rnd: int

reponse:
 ok: bool

slide-31
当然这时（在 X 收到 phase-1 应答，到发送 phase-2 请求的这段时间），可能已经有其他 Proposer 又完成了一个 rnd 更大的 phase-1，所以这时 X 不一定能成功运行完 phase-2。

Acceptor 通过比较 phase-2 请求中的 rnd，和自己本地记录的 rnd，来确定 X 是否还有权写入。如果请求中的 rnd 和 Acceptor 本地记录的 rnd 一样，那么这次写入就是被允许的, Acceptor 将 v 写入本地，并将 phase-2 请求中的 rnd 记录到本地的 vrnd 中。

用例子看 paxos 运行

好了 paxos 的算法描述也介绍完了。这些抽象的算法描述，其中的规则覆盖了实际所有可能遇到的情况的处理方式。一次不太容易看清楚它们的作用，所以我们接下来通过几个例子来看看 paxos 如何处理各种不同状态并最终使整个系统的状态达成一致。

slide-32
没冲突的例子不解释了可靠分布式系统- Paxos 的直观解释

slide-33
X 和 Y 同时运行 paxos，Y 迫使 X 中断的例子：

X 成功完成了写前读取（phase-1），将 rnd=1 写入到左边 2 个 Acceptor。
Y 用更大的 rnd=2，覆盖了 X 的 rnd，将 rnd=2 写入到右边 2 个Acceptor。
X 以为自己还能运行 phase-2，但已经不行了，X 只能对最左边的 Acceptor 成功运行 phase-2，而中间的 Acceptor 拒绝了 X 的 phase-2。
Y 对右边 2 个 Acceptor 成功运行了 phase-2，完成写入 v=y，vrnd=2。

slide-34
继续上面的例子，看 X 如何处理被抢走写入权的情况：

这时 X 的 phase-2 没成功，它需要重新来一遍，用更大的 rnd=3。

X 成功在左边 2 个 Acceptor 上运行 phase-1 之后，X 发现了 2 个被写入的值：v=x，vrnd=1 和 v=y，vrnd=2；这时 X 就不能再写入自己想要写入的值了。它这次 paxos 运行必须不能修改已存在的值，这次 X 的 paxos 的运行唯一能做的就是，修复（可能）已经中断的其他 proposer 的运行。
这里 v=y，vrnd=2 是可能在 phase-2 达到多数派的值。v=x，vrnd=1 不可能是，因为其他 proposer 也必须遵守算法约定，如果 v=x，vrnd=1 在某个 phase-2 达到多数派了，Y 一定能在 phase-1 中看到它，从而不会写入 v=y, vrnd=2。

因此这是 X 选择 v=y，并使用 rnd=3 继续运行，最终把 v=y，vrnd=3 写入到所有 Acceptor 中。

slide-35
Paxos 还有一个不太重要的角色 Learner，是为了让系统完整加入的，但并不是整个算法执行的关键角色，只有在最后在被通知一下。

Paxos 优化

slide-36
第一个优化 multi-paxos：

paxos 诞生之初为人诟病的一个方面就是每写入一个值就需要 2 轮 rpc：phase-1 和 phase-2。因此一个寻常的优化就是用一次 rpc 为多个 paxos 实例运行 phase-1。

例如，Proposer X 可以一次性为 i₁~i₁₀ 这 10 个值，运行 phase-1，例如为这 10 个 paxos 实例选择 rnd 为 1001，1002…1010，这样就可以节省下 9 次 rpc，而所有的写入平均下来只需要 1 个 rpc 就可以完成了。

这么看起来就有点像 raft 了：

再加上 commit 概念（commit可以理解为: 值v送达到多数派这件事情是否送达到多数派了）
和组成员变更（将 quorum 的定义从“多于半数”扩展到“任意2个quourm必须有交集”）

slide-37
第二个优化 fast-paxos：

fast-paxos 通过增加 quorum 的数量来达到一次 rpc 就能达成一致的目的。如果 fast-paxos 没能在一次 rpc 达成一致，则要退化到 classic paxos。

slide-38
fast-paxos 为了能在退化成 classic paxos 时不会选择不同的值, 就必须扩大 quorum 的值。也就是说 fast-round 时，quorum 的大小跟 classic paxos 的大小不一样。同样我们先来看看为什么 fast-quorum 不能跟 classic-quorum 一样，这样的配置会引起 classic 阶段回复时选择错误的值 y₀：

slide-39
要解决这个问题，最粗暴的方法是把 fast-quorum 设置为 n，也就是全部的 acceptor 都写入成功才认为 fast-round 成功（实际上是退化到了主从同步复制）。这样，如果 X 和 Y 两个 proposer 并发写入，谁也不会成功，因此 X 和 Y 都退化到 classic paxos 进行修复，选任何值去修复都没问题。因为之前没有 Proposer 认为自己成功写入了。.

如果再把问题深入下，可以得出，如果 classic paxos 的 quorum 是 n/2+1，那么 fast-round 的 quorum 应该是大于 ¾n，¾ 的由来可以简单理解为：在最差情况下，达到 fast-quorum 的 acceptor 在 classic-quorum 中必须大于半数，才不会导致修复进程选择一个跟 fast-round 不同的值。.

slide-40
下面是一个 fast-round 中 X 成功，Y 失败的冲突的例子：

X 已经成功写入到 4（fast-quorum>¾n）个 acceptor，Y 只写入 1 个，这时 Y 进入 classic-round 进行修复，可以看到，不论 Y 选择哪 3（classic quorum）个 acceptor，都可以看到至少 2 个 x₀，因此 Y 总会选择跟 X 一样的值，保证了写入的值就不会被修改的条件。

slide-41
再来看一个 X 和 Y 都没有达到 fast-quorum 的冲突：

这时 X 和 Y 都不会认为自己的 fast-round 成功了，因此修复过程选择任何值都是可以的。最终选择哪个值，就回归到 X 和 Y 两个 classic-paxos 进程的竞争问题了。最终会选择 x₀ 或 y₀ 中的一个。

其他

slide-42
一个很容易验证的优化，各种情况下都能得到一致的结果。

参考链接

[raft]：https://raft.github.io/
[Leslie Lamport]：http://www.lamport.org/
[Byzantine Paxos]：https://en.wikipedia.org/wiki/Paxos_(computer_science)#Byzantine_Paxos
[Classic Paxos]：http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple
[Fast Paxos]：http://lamport.azurewebsites.net/pubs/pubs.html#fast-paxos
[EC第一篇：原理]：https://blog.openacid.com/storage/ec-1
[EC第二篇：实现]：https://blog.openacid.com/storage/ec-2
[EC第三篇：极限]：https://blog.openacid.com/storage/ec-3