背景

在计算机通信理论中，有一个著名的两军问题，讲述通信的双方通过 ACK 来达成共识，永远会有一个在途的 ACK 需要进行确认，因此无法达成共识。

两军问题和 BasicPaxos 非常相似

1） 通信的各方需要达成共识；

2） 通信的各方仅需要达成一个共识；

3） 假设信道不稳定，有丢包、延迟或者重放，但消息不会被篡改。

BasicPaxos 最早以希腊议会的背景来讲解，但普通人不理解希腊议会的运作模式，因此看 BasicPaxos 的论文会比较难理解。两军问题的背景大家更熟悉，因此尝试用这个背景来演绎一下 BasicPaxos。

为了配合 BasicPaxos 的多数派概念，把两军改为 3 军；同时假设了将军、参谋和通信兵的角色。

假设的 3 军问题

1） 1 支红军在山谷里扎营，在周围的山坡上驻扎着 3 支蓝军；

2） 红军比任意 1 支蓝军都要强大；如果 1 支蓝军单独作战，红军胜；如果 2 支或以上蓝军同时进攻，蓝军胜；

3） 三支蓝军需要同步他们的进攻时间；但他们惟一的通信媒介是派通信兵步行进入山谷，在那里他们可能被俘虏，从而将信息丢失；或者为了避免被俘虏，可能在山谷停留很长时间；

4） 每支军队有 1 个参谋负责提议进攻时间；每支军队也有 1 个将军批准参谋提出的进攻时间；很明显，1 个参谋提出的进攻时间需要获得至少 2 个将军的批准才有意义；

5） 问题：是否存在一个协议，能够使得蓝军同步他们的进攻时间？

接下来以两个假设的场景来演绎 BasicPaxos；参谋和将军需要遵循一些基本的规则

1） 参谋以两阶段提交（prepare/commit）的方式来发起提议，在 prepare 阶段需要给出一个编号；

2） 在 prepare 阶段产生冲突，将军以编号大小来裁决，编号大的参谋胜出；

3） 参谋在 prepare 阶段如果收到了将军返回的已接受进攻时间，在 commit 阶段必须使用这个返回的进攻时间；

两个参谋先后提议的场景

1） 参谋 1 发起提议，派通信兵带信给 3 个将军，内容为（编号 1）；

2） 3 个将军收到参谋 1 的提议，由于之前还没有保存任何编号，因此把（编号 1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（ok）；

3） 参谋 1 收到至少 2 个将军的回复，再次派通信兵带信给 3 个将军，内容为（编号 1，进攻时间 1）；

4） 3 个将军收到参谋 1 的时间，把（编号 1，进攻时间 1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（Accepted）；

5） 参谋 1 收到至少 2 个将军的（Accepted）内容，确认进攻时间已经被大家接收；

6） 参谋 2 发起提议，派通信兵带信给 3 个将军，内容为（编号 2）；

7） 3 个将军收到参谋 2 的提议，由于（编号 2）比（编号 1）大，因此把（编号 2）保存下来，避免遗忘；又由于之前已经接受参谋 1 的提议，因此让通信兵带信回去，内容为（编号 1，进攻时间 1）；

8） 参谋 2 收到将军的回复，由于回复中带来了已接受的参谋 1 的提议内容，参谋 2 因此不再提出新的进攻时间，接受参谋 1 提出的时间；参谋 2 再次派通信兵带信给 3 个将军，内容为（编号 2，进攻时间 1）；

9） 3 个将军收到参谋 2 的时间，把（编号 2，进攻时间 1）保存下来，避免遗忘；同时让通信兵带信回去，内容为（Accepted）；

10） 参谋 2 收到至少 2 个将军的（Accepted）内容，确认进攻时间已经被大家接收；

两个参谋交叉提议的场景

1） 参谋 1 发起提议，派通信兵带信给 3 个将军，内容为（编号 1）；

2） 3 个将军的情况如下

1. 将军 1 和将军 2 收到参谋 1 的提议，因为还没有其他参谋提议，因此将军 1 和将军 2 把（编号 1）记录下来；同时让通信兵带信回去，内容为（ok）；

2. 负责通知将军 3 的通信兵被抓，因此将军 3 没收到参谋 1 的提议；

3） 参谋 2 在同一时间也发起了提议，派通信兵带信给 3 个将军，内容为（编号 2）；

4） 3 个将军的情况如下

1. 将军 2 和将军 3 收到参谋 2 的提议，将军 2 和将军 3 把（编号 2）记录下来；将军 2 记录编号 2，是因为编号 2 比之前记录的编号 1 大；将军 3 记录编号 2，是因为之前没有参谋向他提议；这两个将军同时让通信兵带信回去，内容为（ok）；

2. 负责通知将军 1 的通信兵被抓，因此将军 1 没有收到参谋 2 的提议；

5） 参谋 1 收到至少 2 个将军的回复，再次派通信兵带信给有答复的 2 个将军，内容为（编号 1，进攻时间 1）；

6） 2 个将军的情况如下

1. 将军 1 收到了（编号 1，进攻时间 1），和自己保存的编号相同，因此把（编号 1，进攻时间 1）保存下来；同时让通信兵带信回去，内容为（Accepted）；

2. 将军 2 收到了（编号 1，进攻时间 1），由于（编号 1）小于已经保存的（编号 2），因此让通信兵带信回去，内容为（Rejected，编号 2）；

7） 参谋 2 收到至少 2 个将军的回复，再次派通信兵带信给有答复的 2 个将军，内容为（编号 2，进攻时间 2）；

8） 将军 2 和将军 3 收到了（编号 2，进攻时间 2），和自己保存的编号相同，因此把（编号 2，进攻时间 2）保存下来，同时让通信兵带信回去，内容为（Accepted）；

9） 参谋 2 收到至少 2 个将军的（Accepted）内容，确认进攻时间已经被多数派接受；

10） 参谋 1 只收到了 1 个将军的（Accepted）内容，同时收到一个（Rejected，编号 2）；参谋 1 重新发起提议，派通信兵带信给 3 个将军，内容为（编号 3）；

11） 3 个将军的情况如下

1. 将军 1 收到参谋 1 的提议，由于（编号 3）大于之前保存的（编号 1），因此把（编号 3）保存下来；由于将军 1 已经接受参谋 1 前一次的提议，因此让通信兵带信回去，内容为（编号 1，进攻时间 1）；

2. 将军 2 收到参谋 1 的提议，由于（编号 3）大于之前保存的（编号 2），因此把（编号 3）保存下来；由于将军 2 已经接受参谋 2 的提议，因此让通信兵带信回去，内容为（编号 2，进攻时间 2）；

3. 负责通知将军 3 的通信兵被抓，因此将军 3 没收到参谋 1 的提议；

12） 参谋 1 收到了至少 2 个将军的回复，比较两个回复的编号大小，选择大编号对应的进攻时间作为最新的提议；参谋 1 再次派通信兵带信给有答复的 2 个将军，内容为（编号 3，进攻时间 2）；

13） 将军 1 和将军 2 收到了（编号 3，进攻时间 2），和自己保存的编号相同，因此保存（编号 3，进攻时间 2），同时让通信兵带信回去，内容为（Accepted）；

14） 参谋 1 收到了至少 2 个将军的（accepted）内容，确认进攻时间已经被多数派接受；

小结

BasicPaxos 算法难理解，除了讲故事的背景不熟悉之外，还有以下几点

1） 参与的各方并不是要针锋相对，拼个你死我活；而是要合作共赢，最终达成一个共识；当大家讲起投票的时候，往往第一反应是要针锋相对，没想到是要合作共赢；很明显可以想到，在第二个场景下，如果参谋 1 为了逞英雄，强行要提交他提出的进攻时间 1，那么最终是无法达成一个共识的；这里的点就在于参谋 1 违反了规则，相当于产生了拜占庭错误；

2） 常规的通信协议设计，对于写操作，通常都是只返回成功和失败的状态，不会返回更多的东西；但 BasicPaxos 的 prepare 和 commit，将军除了返回成功还是失败的状态之外，还会把之前已经发生的一些状态带回给参谋，这个和常规的通信协议是不同的；

3） 在两军问题的背景下，其实知道进攻时间被至少 2 个将军接受的是参谋，而不是将军；在“两个参谋交叉提议的场景”下，当参谋 1 没有做第 2 次 prepare 之前，将军 1 记录的其实是一个错误的进攻时间；理论上来说，任何一个将军在任何一个时刻都无法判断自己不是处在将军 1 的场景下；因此 BasicPaxos 在 3 个蓝军组成的系统中达成了一个共识，但并没有为每个将军明确了共识；

4） 本文的两个场景都以“两个参谋”来讲，这里的“两个参谋”可能是真的两个不同的参谋，也可能是同一个参谋因为某种原因先后做了多次提议；对应分布式系统的场景

1. 真的有两个并发的 client

2. 两个 client 一先一后；第一个 client 执行到某个步骤因为某种原因停止了；过了一段时间，另外一个 client 接着操作同一个数据

3. 同一个 client 重试；第一次执行到某一步骤因为某种原因停止了，立即或者稍后进行了重试

后记

写这篇文章的时候，参考了以下两篇文章：

Paxos 算法细节详解(一)--通过现实世界描述算法

http://www.cnblogs.com/endsock/p/3480093.html

第一篇文章用了我们喜闻乐见的背景，大部分内容非常容易理解，尤其是用比特币来映射编号，非常贴切；只是对于 proposer-1 小姐最后的“背叛”会有点违反常识。看完这个故事之后就一直在想更贴切的背景。在两军问题中，蓝军各方是要合作达成一个共识；对于参谋来说，获得了前一个参谋的提议就接受，而不再提出自己的提议是符合逻辑的，这个和 paxos 也更加吻合。在实际的分布式系统中，如果遇到冲突，涉及的各方也不是要针锋相对争个你死我活，想要的只是能发现冲突，只有一方成功、或者全部失败都无所谓，只要能保证数据一致就行。

以两军问题为背景，在提议编号上找不到合适的映射点，比较生硬，这一点不如第一篇文章中的故事。

Question 7: The Two Generals’ Problem of reaching consensus on when to attack is unsolvable, how come it’s possible to have consensus with Paxos?

http://bogdan.pistol.gg/2014/10/20/paxos-algorithm-explained-part-2-insights/#q7

paxos 最终仍然无法解决两军问题，即使是扩展到 3 军也是无法解决的。在 3 军背景下，按 paxos 算法的定义，最后是达成了一个共同的进攻时间，3 军中的任何一方都可以通过 paxos 算法读取出这个进攻时间。但 3 军怎么知道在什么时候去读取、其他人是否已经读取，这是一个和两军问题同样的问题；同时由于通信兵可能无限延迟，可能部分蓝军在进攻时间之前读取到了，部分蓝军可能在进攻时间之后才读取到，所以两军最终还是无解的。第二篇参考文章中也详细描述了这些问题。所以写 paxos 和两军问题，不是说 paxos 解决了两军问题，只是借用两军问题的背景来演绎 paxos。

本文转自微信后台团队如有侵权请联系我们删除。

OpenIMgithub 开源地址：

https://github.com/OpenIMSDK/Open-IM-Server

OpenIM 官网 ：https://www.rentsoft.cn

OpenIM 官方论坛：https://forum.rentsoft.cn/

更多技术文章：

开源 OpenIM：高性能、可伸缩、易扩展的即时通讯架构

https://forum.rentsoft.cn/thread/3

【OpenIM 原创】简单轻松入门 一文讲解 WebRTC 实现 1 对 1 音视频通信原理https://forum.rentsoft.cn/thread/4