Paxos算法——问题与思考

1. 算法背景

状态复制(State Replication). 对于一组节点，如果所有节点均以相同的顺序执行一个（可能是无限的）命令序列c₁, c₂, c₃, ..., 则这组节点实现了状态复制。
—— 《区块链核心算法解析》

在许多分布式系统中，都有分布式的节点保持状态一致的要求，例如在分布式数据库中要保证 log 文件在各节点一致，那么就需要使用分布式一致性算法，如 Paxos。 对于金融科技行业的从业人员来说，状态复制经常等同于区块链。

2. 消息模型

在我们下面要讨论的分布式系统中，设定了下面几条消息传递的规则：

• 消息传递（Message Passing）：在分布式系统中，各个节点都可以通过发送消息（Message）来与其他节点通信
• 消息丢失（Message Loss）：在消息传递的过程中，任何一条消息都不能保证可以安全地到达消息的接受者
• 消息确认（Acknowledgements）：当接受者接收到消息后，可以根据之前设定的规则选择是否回复消息的确认
• 可变消息延迟（Variable Message Delay）：每条消息在实际应用中传递是时间是不定的，也不一定相同
• 非拜占庭问题（non-Byzantine Problem）：消息在传递的过程中不存在被篡改的问题

3. 讨论 Paxos 之前

实现 node 间的状态复制，我们很容易想到下面的解决办法：

3.1 单服务器实现状态一致

使用单个服务器，很容易知道，我们只需要从所有发送到服务器的value中选取一个作为最终的存储对象，再将所选中的value发送给分布式系统中的其他所有节点即可。
很明显这种方法下，只有一个服务器，存在单点故障的问题

3.2 Two-Phase Protocol

两阶段协议（Two-Phase Protocol），简述就是一个client在企图向所有的分布式server提交value时，必须获得所有server的锁，然后才能向server发送提交value的命令；如果不能获得所有server的锁则释放已经获得的锁，重新尝试获得所有锁。
两阶段协议相比上面所述的单服务器协议而言，所需条件更为严格，因为一个client必须同时获得所有server的锁才能提交value。

4. Paxos 算法

4.1 介绍

Paxos 算法在网络上已经有许多人以各种简单易懂的方式解释过（推荐知乎这个问题下的第2个与第1个回答），本文主要记录自己在思考中所遇到的一些问题。

在Paxos 系统中存在这三种角色， proposer acceptor learner，在Paxos 算法的执行过程中主要有这两个阶段（这里直接截取了paxos make simple论文）：

阶段1 阶段2

而对一个value存在这三个阶段：prepare accept chosen

4.2 思考

网络上很多帖子讲不清楚 Paxos 算法的问题都在于，没有讲清楚最后一个value被accept与被chosen的区别。在知乎这个回答下面其实作者已经快完全说清了 Paxos 算法（举的例子也很生动），但是最后没有说明白value被accpet与chosen的区别与联系，所以就会有如下图中这样的评论

某评论

可以看到我给这条评论点了赞，因为之前我也被这个问题困扰过。产生这个问题的原因就是：混淆了accpet与chosen。
因为之前我们一直强调 Paxos 算法有两个阶段，以及强调当一个value被某acceptor accept，该acceptor就不会accept其他value。

4.3 说明

以刚才说的那个知乎回答为例，我们假设在一个系统中有两个 proposer三个acceptor，暂时不提learner，该系统发生了如下时间线的事情：

|- proposer1 拿到了3个acceptor对 prepare 请求的确认回复，开始向3个acceptor发送accept请求
|    |- proposer1 的accpet 请求顺利到达acceptor1，acceptor1 accept 了 value1
|    |- 因为延时等问题proposer1发出的accept请求没能及时到达acceptor2与acceptor3
|- proposer2 更新了acceptor2与acceptor3的 prepare number
|    |- proposer2 向三个acceptor都发送accept请求，acceptor2与acceptor3 accept了value2，acceptor1则拒绝了value2

之前的疑惑就在于，以为 acceptor1 accept 了 value1后，value就被选定了，acceptor2与acceptor3 不能再accept 其他value了，但其实acceptor1 accept 了 value1后，该value只是被aaceptor1 accept，并没有被整个系统 chosen。
我们回顾一下论文中对chosen 的定义：

chosen的定义
也就是说，在上面的例子中value真正被chosen是在acceptor2与acceptor3 accept 了value2 那一刻，而不是 acceptor1 accept 了 value1 那一刻。

Q1：有人要问了，那acceptor1 accept了 value1，acceptor2与acceptor3 accept 了value2 ，那岂不是没有实现状态一致吗？出现这个问题除了之前说的，混淆了accept与chosen以外，也和网络上很多关于Paxos 算法的文章省略了对learner的讨论有关系。
A1：首先我们应该明确，一个value是否被chosen与acceptor是无关的，acceptor在accept一个value之后，它的使命就完成了，至于这个value最后是否能够被chosen不是它考虑的问题。

Q2：有人又要问了，那acceptor怎么知道自己accept的value 有没有被chosen呢？答案是：其实它没有知道的必要，如果它想知道的话，通过learner。
A2：如果acceptor想知道哪个value被chosen的话，可以通过询问learner（learner可以有一个也可以有多个），如果此时已经有value被chosen了，learner可以告诉该acceptor被chosen的value2，然后该acceptor记录下被chosen的value（如果它有必要记录的话）

其实我们在上面的例子中，如果开上帝视角的话，在acceptor2与acceptor3 accept 了value2 的那一刻，value2的值已经被chosen了，但是此时learner节点们还不知道，所有就需要learner去learn哪个value被chosen了（To learn that a value has been chosen）

关于learner 如何learn 到哪个value被chosen，在 Paxos make simple 的论文中有讨论，也比较简单（其实就是通过消息去询问或者被告知是否有一个value被大多数（超过一半）acceptor accept）。论文中该部分截图如下：

how value be chosen how value be chosen

5. 结语

这篇文章主要不是介绍怎么去形象地理解 Paxos 算法，而是将自己在理解中遇到的一些问题整理回顾一下。回到开篇中我们说到的分布式系统中各个节点保持状态一致的问题，其实看到这里我们应该能想到，只要在每个节点中，都有一个扮演 learner 的进程，那么如果有一个 value被chosen，那么该系统就可以实现对某一个值或某一个 log 文件达成各节点一致。之所以说如果有一个，是因为 Paxos 算法存在活锁的问题，有可能永远也选不出一个value被chosen，这也就是FLP 不可能性。

我的第一篇博文，献给 zyy 同学（推眼镜