前言
网上关于 Paxos / Raft 的文章已经很多了，大部分文章都太过于侧重算法流程描述，始终无法让我在脑子里对 Paxos 和它解决的问题形成一个较好的认知。
查阅了更多资料后，总算是对 Paxos 形成了一个比较清晰的初步认知，特写博一篇记录一下。
如果你已经看过一些 Paxos 文章，大致了解这个算法的流程，但是却对这个算法仍然感到一些迷惑，那么这篇文章应该比较适合你。
何谓共识 —— Paxos 诞生的背景
假设我想设计一个“美国总统查询服务”，功能很简单，请求“美国总统是谁”，服务器将响应一个人名。
当然，服务器刚刚启动的时候并不知道美国总统是谁，我们允许从外部发送请求初始化服务器，告诉他美国总统是谁。
简单地说，我们的服务器支持以下两个 RPC 接口：
- Init(name): 如果服务器还不知道谁是美国总统，就设置 name 作为美国总统，否则的话，忽略这次请求。换言之，Once set, can't be modified。
- Query()：服务器返回它所认知的美国总统。
听起来是一个最简单不过的 Echo 服务加强版，用一个内存变量记一下美国总统是谁就可以了。
但是，我们知道，单机系统无法实现容灾和高可用，如果这个服务我们想升级一下怎么办？如果这个服务主机崩溃了，断网了怎么办？
届时服务将存在不可用期。
因此，我们需要一个分布式的“美国总统查询服务”。
但是这就引入了另外一个问题，也就是 Paxos 要解决的问题 —— 如何让这多台服务器对“美国总统”这个值达成共识？
一个听起来简单实际也可行的做法是：只有一个 Client 在尝试 Init()，并且它会不断Init()，直到 3 台主机都表示 Init() 成功。
但实际上，我们不应该假设我们具备 “只有一个 Client 在尝试 Init()” 这样的能力，这等价于我们在代码里 Hardcode 了 name 是什么，而不是将设置它的权力交给外界 RPC。
因此，我们需要图上所示的从多个不可控的外部触发 Init() 的能力。
那么，该听谁的呢？不同服务器对“谁是总统”这个问题可能存在不同的答案。这就很糟糕了。
我们可以容忍服务器们接受一个错误的人作为总统，但不能容忍它们认为存在多个不同的总统。
为什么呢，因为二者的核心区别在于，服务器是否具备达成共识的能力，对于前者，即使服务器们一时状态有误，我们也完全可以通过外部感知，并发送指令去调整服务器达到一个期望的状态。
但是你刚才不是说，Once set, can't be modified 吗？怎么现在又可以调整了。
这里的“调整”和刚刚的“modified”并不是同一回事，“modified”是指共识一旦达成，就不能改变，而“调整”是指，我们知道服务器们有了一个错误的共识，我们需要让他们形成一个新的共识，这并不影响它们之前的错误共识，也就是 List<共识>。
List<共识>() 是一个非常非常强大的能力。
因为共识可以是很多东西，可以是一条指令，可以是一条文本信息。
List<文本信息>，我们就得到了一个文件。
List<指令>，我们就得到了一个CPU。
List<binlog>，我们就得到了一个MySQL。
List<共识(binlog)>，我们就得到了一个具备容灾和高可用能力的分布式 MySQL。
List<共识(text)>，我们就得到了一个具备容灾和高可用能力的分布式文件系统。
这就是共识的力量，它让多台通过不可靠网络连接的机器，Work As One！而共识的力量，正是来源于 Paxos。对于有状态的服务，你几乎可以把 Paxos 和多机容灾高可用画上等号。
共识，共识，还是共识。
走向共识
前面介绍了 Paxos 解决了什么问题以及它的意义，现在还是回到问题本身。
那么，该听谁的呢？
首先，再重复一下重点，我们可以容忍服务器们接受一个错误的人作为总统，但不能容忍它们认为存在多个不同的总统。
因此，我们现在研究的问题是让多机达成一致，听谁的无所谓，但一定要听一个人的。
让我们先来随便想一些办法看看可不可行：
-
策略一. 外部触发 Init() 的时候，必须同时 Init() 所有机器，才算 Init() 成功，否则会一直重试直至都成功。
显然，在外部并发 Init() 的场景下，你极有可能先成功了一台，在尝试第二台的时候，发现这一台已经被其他人 Init() 过了，根据 Once set, can't be modified，你将永远不可能成功。并且此时集群状态已经乱掉，无法达成共识了。 -
策略二. 多次Init()原子化
策略一的问题出在哪儿呢？对的，多个 Init 不是原子的，要是有把互斥锁一样的东西，能让我们做到 “要么都成功，要么都失败” 就好了。
怎么做到这一点呢？对的，事先告知一下服务器们是不是就可以了？
a. 发起 Init() 前，先发起一轮 Informal()，通知服务器我们马上要发 Init() 过来了，现在开始你只能听我的。
b. 如果所有服务器都表示 ok，此时再做策略一描述的过程。否则的话，放弃 Init()。
这个策略的确可以保证让多机达成一致，但它却存在两个问题：
a. 根据策略中对 Informal() 流程的描述，同一时刻，不同服务器可能被不同 Client Informal()，因此可能永远也没有 Client 成功走到步骤二。
b. 要是有一个 Server 宕机了呢？难道 Client 要一直阻塞在那儿疯狂重试？ -
策略三. 允许 Server 被多次 Informal()，同时在 Informal() 和 Init() 之间插入一个 PreInit() 阶段
让我们看看这个策略是怎么解决上面的问题的。
允许 Server 被多次 Informal
也就是说，如果 Server 先被一个 Client Informal() 了，如果后面来了其他 Client 的 Informal()，那么就接受新的 Client 的 Informal()，抛弃旧的。
有人会说，你这不是扯淡吗？假如有一个 Client 先全部 Informal() 成功了，然后又 Init() 了一部分成功，结果剩下那一部分 Server 被其他 Client 给 Informal() 了，根据 Once set, can't be modified，这不就不一致了？
别着急，策略里不是还有一句话吗？
在 Informal() 和 Init() 之间插入一个 PreInit() 阶段
Informal() -> PreInit() -> Init()
PreInit() 是干什么的呢？你可以理解为，它和 Informal() 一模一样，区别在于，它带上了 Init(name) 的 name 给服务器，但是让服务器不真正接受这个 name，而是告诉他 “我马上要提交这个 name 了，万一待会有其他人给你发 Informal()，你就告诉它你已经接受了这个 name 了，让它改用这个 name”
重新回忆一下刚刚那句话，我们可以容忍服务器们接受一个错误的人作为总统，但不能容忍它们认为存在多个不同的总统。
因此，这个阶段的作用其实就是让后来的 Client “舍小家为大家”，放弃自己要设的 name，改设先前已经有过的 value，从而达成一致。
策略三是不是就天衣无缝了呢？其实不是的。
想象这样一个场景：由于时间差，两个 Client 交替 Informal() 成功，各实际拉拢了一半 Server，但两个 Client 都认为自己已经全部 Informal() 成功，因此进入 PreInit() 阶段，各自带入了 name 为 A 和 B。毫无疑问，此时双方只能各成功了一半 Server，因此准备发起整个流程的重试（还记得之前说的吗，“直到 3 台主机都表示 Init() 成功”）。
重试时，尴尬的情况就来了，Informal() 一波后，有一半 Server 告知 Client 用 A 值做 name，有一半 Server 告知 Client 用 B 值做 name。Client 到底应该用哪个值作为自己的立场呢？
没错，聪明的你或许想到了，反正达成共识就行，Client 的每轮 Informal() 都带一个随机生成的 ID，谁的 ID 大就听谁的不就可以了吗？当然，由于信息的时效性和避免 ID 重复，这个 ID 我们不一定要随机，而是采用时间戳来生成，实现“以最新的提议为准”。
有没有发现，把 Informal() 改名为 Prepare()，PreInit() 改名为 Accept()，Init() 改名为 Learn()，这个策略越来越像你在论文和其他文章里看到的 Paxos 了。
到这里，共识的问题算是解决了。从策略二进化到策略三，我们解决了策略二存在的第一个问题，现在还有第二个问题，Server 宕机了怎么办？
-
策略四. Informal() / PreInit() / Init() 每次不一定要全部通过才进入下一阶段，超过多数就可以
为什么这么做可以？因为一个集群只有一个多数派，每个 Server 只认可一个值，你不可能找到两个交集为空的 Server 集合，使得它们各认可一个值而导致共识矛盾。
这一步其实算是水到渠成，有了策略三的铺垫，不费太多功夫我们就可以进化到策略四。
结尾
现在，把 Informal() 改名为 Prepare()，把 PreInit() 改名为 Accept()，Init() 改名为 Learn() 吧。你已经获得了 Paxos 的雏形。
关于 Paxos 的详细算法流程，网络上的文章已经很多也很详细，这里就不再赘述了，这篇文章的出发点，更多的还是提供一个理解 Paxos 背景与目标的视角。
毕竟，人脑不是 CPU，程序员不是服务器。比形式化的算法流程更重要的，是背后的思想。