前言
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
我是无需解释的目录页。
slide-03
分布式系统的一致性问题最终都归结为分布式存储的一致性。像 aws 的对象存储可靠性要求是 9 ~ 13 个 9。
而这么高的可靠性都是建设在可靠性没那么高的硬件上的。
slide-04
简直所有的分布式存储（甚至单机零碎），参考【EC 第一篇：原理】，【EC 第二篇：实现】，【EC 第三篇：极限】都必须用某种冗余的形式在便宜硬件的根底上搭建高牢靠的存储。而冗余的根底就是多正本策略，一份数据存多份。多正本保障了可靠性，而正本之间的统一，就须要 paxos 这类分布式一致性算法来保障。
slide-05
在早些年各种各样的复制策略都被提出来来解决各种场景下的须要。除了复制的份数之外，各种各样的算法实际上都是在尝试解决统一的问题。从下一页开始简略回顾下各种复制策略，看看他们的优缺点以及 paxos 如何解决正本之间一致性的问题。
不太完满的复制策略 不太完满的复制策略
slide-06
无需解释的目录页
slide-07
主从异步复制 是最简略的策略之一，它很容易实现，但存在一个问题：客户端收到一个 数据曾经平安（OK）的信息，跟 数据真正平安（数据复制到全副的机器上）在工夫上有一个空隙，这段时间负责接管客户端申请的那个机器（master）如果被闪电击中或被陨石砸到或被打扫卫生的大姐踢断了电源，那数据就可能会失落。因而它不是一个牢靠的复制策略（应用主从异步复制要求你必须置信宇宙中不存在闪电陨石和扫地大姐）。
slide-08
跟主从异步复制相比，主从同步复制 提供了残缺的可靠性：直到数据真的平安的复制到全副的机器上之后，master 才告知客户端 数据曾经平安。但主从同步复制有个致命的毛病就是整个零碎中有任何一个机器宕机，写入就进行不上来了。相当于零碎的可用性随着正本数量指数升高。
slide-09
然鹅，在同步和异步之间，做一个折中，看起来是一个不错的计划。这就是 半同步复制 。它要求 master 在应答客户端之前必须把数据复制到 足够多 的机器上，但不须要是全副。这样正本数够多能够提供比拟高的可靠性；1 台机器宕机也不会让整个零碎进行写入 。然而它还是不完满，例如数据 a 复制到 slave-1，但没有达到 slave-2；数据 b 复制达到了 slave-2 但没有达到 slave-1，这时如果 master 挂掉了须要从某个 slave 复原出数据，任何一个 slave 都不能提供残缺的数据。所以在整个零碎中，数据存在某种 不统一。![9.jpg]
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 和 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 的申请 / 应答的格局：
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 的形式形容申请应答：
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
没抵触的例子不解释了
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…(computer_science)#Byzantine_Paxos
- [Classic Paxos]：http://lamport.azurewebsites….
- [Fast Paxos]：http://lamport.azurewebsites….
- [EC 第一篇：原理]：https://blog.openacid.com/sto…
- [EC 第二篇：实现]：https://blog.openacid.com/sto…
- [EC 第三篇：极限]：https://blog.openacid.com/sto…
对于 Databend
Databend 是一款开源、弹性、低成本，基于对象存储也能够做实时剖析的旧式数仓。期待您的关注，一起摸索云原生数仓解决方案，打造新一代开源 Data Cloud。
- Databend 文档：https://databend.rs/
- Twitter：https://twitter.com/Datafuse_…
- Slack：https://datafusecloud.slack.com/
- Wechat：Databend
- GitHub：https://github.com/datafusela…