可靠分布式系统- Paxos 的直观解释
在分布式系统中保证多副本数据强一致的算法。
没有 paxos 的一堆机器, 叫做分布式； 有 paxos 协同的一堆机器, 叫分布式系统。
这个世界上只有一种一致性算法，那就是Paxos …
前 1 部分是分布式一致性问题的讨论和解决方案的逐步完善，用人话得出 paxos 算法的过程。如果只希望理解 paxos 而不打算花太多时间深入细节， 只阅读这 1 部分就可以啦。 第 2 部分是 paxos 算法和协议的严格描述。这部分可以作为 paxos 原 paper 的实现部分的概括。如果你打算实现自己的 paxos 或类似协议。需要仔细了解协议细节，希望这部分内容可以帮你节省阅读原 paper 的时间。
slide-01
我是无需解释的目录页。
分布式系统的一致性问题最终都归结为分布式存储的一致性。像 aws 的对象存储可靠性要求是 9 ~ 13 个 9。而这么高的可靠性都是建立在可靠性没那么高的硬件上的。
几乎所有的分布式存储（甚至单机系统），参考【EC 第一篇：原理】，【EC 第二篇：实现】，【EC第三篇：极限】 都必须用某种冗余的方式在廉价硬件的基础上搭建高可靠的存储。而冗余的基础就是多副本策略，一份数据存多份。多副本保证了可靠性，而副本之间的一致，就需要 paxos 这类分布式一致性算法来保证。
在早些年各种各样的复制策略都被提出来来解决各种场景下的需要。除了复制的份数之外，各种各样的算法实际上都是在尝试解决一致的问题。从下一页开始简单回顾下各种复制策略，看看他们的优缺点以及 paxos 如何解决副本之间一致性的问题。
无需解释的目录页
主从异步复制是最简单的策略之一，它很容易实现，但存在一个问题：客户端收到一个数据已经安全（OK）的信息，跟数据真正安全（数据复制到全部的机器上）在时间上有一个空隙，这段时间负责接收客户端请求的那个机器（master）如果被闪电击中或被陨石砸到或被打扫卫生的大姐踢断了电源，那数据就可能会丢失。因此它不是一个可靠的复制策略（使用主从异步复制要求你必须相信宇宙中不存在闪电陨石和扫地大姐）。
跟主从异步复制相比，主从同步复制提供了完整的可靠性：直到数据真的安全的复制到全部的机器上之后，master 才告知客户端数据已经安全。
然鹅，在同步和异步之间，做一个折中，看起来是一个不错的方案。这就是半同步复制。它要求 master 在应答客户端之前必须把数据复制到足够多的机器上，但不需要是全部。这样副本数够多可以提供比较高的可靠性；1台机器宕机也不会让整个系统停止写入。
为了解决半同步复制中数据不一致的问题，可以将这个复制策略再做一改进：多数派读写：每条数据必须写入到半数以上的机器上。每次读取数据都必须检查半数以上的机器上是否有这条数据。
然鹅多数派读写的策略也有个但是，就是对于一条数据的更新时，会产生不一致的状态。例如：
node-1，node-2 都写入了 a=x 下一次更新时 node-2，node-3 写入了 a=y
是的，但是又来了。这种带时间戳的多数派读写依然有问题。就是在客户端没有完成一次完整的多数派写的时候：例如，上面的例子中写入 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₂
现在我们已经非常接近最终奥义了，paxos 可以认为是多数派读写的进一步升级，paxos 中通过 2 次原本并不严谨的多数派读写，实现了严谨的强一致 consensus 算法。
首先为了清晰的呈现出分布式系统中的核心问题：一致性问题, 我们先设定一个假象的存储系统，在这个系统上，我们来逐步实现一个强一致的存储，就得到了 paxos 对一致性问题的解决方法。
在实现中，set 命令直接实现为一个多数派写，这一步非常简单。而 inc 操作逻辑上也很简单，读取一个变量的值 i₁，给它加上一个数字得到 i₂，再通过多数派把 i₂ 写回到系统中。
冰雪如你一定已经看到了这种实现方式中的问题：如果有 2 个并发的客户端进程同时做这个 inc 的操作，在多数派读写的实现中，必然会产生一个 Y 客户端覆盖 X 客户端的问题，从而产生了数据更新点的丢失。
提取一下上面提到的问题：让 Y 去更新的时候不能直接更新 i₂ 而是应该能检测到 i₂ 的存在，进而将自己的结果保存在下一个版本 i₃ 中，再写回系统中。
于是我们的问题就转化成一个更简单，更基础的问题：如何确定一个值（例如 iⱼ）已经被写入了。
但是！ 这里还有个并发问题，X 和 Y 可能同时做这个写前读取的操作，并且同时得出一个结论：还没有其他进程在写入，我可以写。这样还是会造成更新丢失的问题。
为了解决上面的问题，存储节点还需要增加一个功能，就是它必须记住谁最后一个做过写前读取的操作。并且只允许最后一个完成写前读取的进程可以进行后续写入，同时拒绝之前做过写前读取的进程写入的权限。
以上就是 paxos 算法的全部核心思想了，是不是很简单？剩下的就是如何实现的简单问题了：如何标识一个客户端如 X 和 Y，如何确认谁是最后一个完成写前读写的进程，等等。
【Leslie Lamport】就这么把这么简单的一个算法写了个 paper 就获得了图领奖！骚年，改变世界就这么容易！
首先明确要解决的问题：
我们要介绍的 paxos 实际上是最朴实的 classic paxos，在这之后我们顺提下几个老爷子对 paxos 的优化，multi paxso 和 fast paxos，它们都是针对 paxos 的理论层面的优化。
paxos 算法中解决了如何在不可靠硬件基础上构建一个可靠的分布式系统的方法。但 paxos 核心算法中只解决网络延迟/乱序的问题，它不试图解决存储不可靠和消息错误的问题，因为这两类问题本质上跟分布式关系不大，属于数据校验层面的事情。
本文尽量按照【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（客户端）。
在存储端（Acceptor）也有几个概念：
last_rnd 是 Acceptor 记住的最后一次进行写前读取的 Proposer（客户端）是谁，以此来决定谁可以在后面真正把一个值写到存储中。 v 是最后被写入的值。 vrnd 跟 v 是一对，它记录了在哪个 Round 中 v 被写入了。
首先是 paxos 的 phase-1，它相当于之前提到的写前读取过程。它用来在存储节点（Acceptor）上记录一个标识：我后面要写入；并从 Acceptor 上读出是否有之前未完成的 paxos 运行。如果有则尝试恢复它；如果没有则继续做自己想做的事情.
request:
rnd: int
response:
last_rnd: int
v: "xxx",
vrnd: int
Proposer X 收到多数（quorum）个应答，就认为是可以继续运行的。如果没有联系到多于半数的 acceptor，整个系统就 hang 住了，这也是 paxos 声称的只能运行少于半数的节点失效。
所有应答中都没有任何非空的 v，这表示系统之前是干净的，没有任何值已经被其他 paxos 客户端完成了写入（因为一个多数派读一定会看到一个多数派写的结果），这时 Proposer X 继续将它要写的值在 phase-2 中真正写入到多于半数的 Acceptor 中。 如果收到了某个应答包含被写入的 v 和 vrnd，这时，Proposer X 必须假设有其他客户端（Proposer）正在运行，虽然 X 不知道对方是否已经成功结束， 但任何已经写入的值都不能被修改！所以 X 必须保持原有的值。于是 X 将看到的最大 vrnd 对应的 v 作为 X 的 phase-2 将要写入的值。 这时实际上可以认为 X 执行了一次（不知是否已经中断的）其他客户端（Proposer）的修复。
在第 2 阶段 phase-2，Proposer X 将它选定的值写入到 Acceptor ，这个值可能是它自己要写入的值，或者是它从某个 Acceptor 上读到的 v（修复）。
request:
v: "xxx",
rnd: int
reponse:
ok: bool
当然这时（在 X 收到 phase-1 应答，到发送 phase-2 请求的这段时间），可能已经有其他 Proposer 又完成了一个 rnd 更大的 phase-1，所以这时 X 不一定能成功运行完 phase-2。
没冲突的例子不解释了
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。
继续上面的例子，看 X 如何处理被抢走写入权的情况：
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。
Paxos 还有一个不太重要的角色 Learner，是为了让系统完整加入的，但并不是整个算法执行的关键角色，只有在最后在被通知一下。
Paxos 优化
Paxos 优化
第一个优化 multi-paxos：
再加上 commit 概念（commit可以理解为: 值v送达到多数派这件事情是否送达到多数派了） 和组成员变更（将 quorum 的定义从“多于半数”扩展到“任意2个quourm必须有交集”）
第二个优化 fast-paxos：
fast-paxos 为了能在退化成 classic paxos 时不会选择不同的值, 就必须扩大 quorum 的值。也就是说 fast-round 时，quorum 的大小跟 classic paxos 的大小不一样。同样我们先来看看为什么 fast-quorum 不能跟 classic-quorum 一样，这样的配置会引起 classic 阶段回复时选择错误的值 y₀：
要解决这个问题，最粗暴的方法是把 fast-quorum 设置为 n，也就是全部的 acceptor 都写入成功才认为 fast-round 成功（实际上是退化到了主从同步复制）。这样，如果 X 和 Y 两个 proposer 并发写入，谁也不会成功，因此 X 和 Y 都退化到 classic paxos 进行修复，选任何值去修复都没问题。因为之前没有 Proposer 认为自己成功写入了。.
下面是一个 fast-round 中 X 成功，Y 失败的冲突的例子：
再来看一个 X 和 Y 都没有达到 fast-quorum 的冲突：
一个很容易验证的优化，各种情况下都能得到一致的结果。
[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
Databend 文档：https://databend.rs/
Twitter：https://twitter.com/Datafuse_Labs
Slack：https://datafusecloud.slack.com/
Wechat：Databend
GitHub ：https://github.com/datafuselabs/databend