从拜占庭将军问题到分布式系统的一致性_拜占庭问题

本篇我们会以拜占庭问题为引，来谈论一下关于分布式系统中一致性的问题。

拜占庭问题

拜占庭问题（Byzantine failures）也叫拜占庭将军问题，是由莱斯利·兰伯特提出的点对点通信中的基本问题。含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。

拜占庭问题其本质是一个协议问题，拜占庭帝国军队的将军们必须全体一致决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如果将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到这些目的之一，则任何攻击行动的结果都是要失败的，只有完全达成一致的努力才能获得胜利。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何才能达成一致的协议，而拜占庭问题也就此形成。

图1. 拜占庭将军问题

拜占庭问题可以这样描述，军队的几个师驻扎在敌城外, 每个师都由各自的将军指挥。将军们只能通过信使相互沟通，在观察敌情之后，他们必须制定一个共同的行动计划，如 进攻(Attack) 或者 撤退(Retreat) ，且只有当半数以上的将军共同发起进攻时才能取得胜利。

当三个将军都忠诚时，可以通过投票确定一致的行动方案，图2展示了一种场景，即 General A、B 通过观察敌军军情并结合自身情况判断可以发起攻击，而 General C通过观察敌军军情并结合自身情况判断应当撤退。最终三个将军经过投票表决得到结果为 进攻:撤退 = 2:1，所以将一同发起进攻取得胜利。对于三个将军，每个将军都能执行两种决策（进攻或撤退）的情况下，共存在 6 种不同的场景，图2 是其中一种, 对于其他 5 种场景可简单地推得，通过投票三个将军都将达成一致的行动计划。

图2. 三个将军均为忠诚的场景

当三个将军中存在一个叛徒时，就有可能扰乱正常当作战计划。比如图3，当 General C 为叛徒时，他给 General A 和 General B 发送了不同的消息，在这种场景下 General A 通过投票得到 进攻:撤退 = 1:2，最终将做出撤退当行动计划，General B 通过投票得到 进攻:撤退 = 2:1，最终将作出进攻的行动计划。结果只有General B发起了进攻并战败。

图3. 二忠一判的场景

事实上，对于三个将军中存在一个叛徒的场景，想要总能达到一致的行动方案是不可能的。详细的证明可参看Leslie Lamport的论文。此外，论文中给出了一个更加普适的结论：如果存在 m 个叛将, 那么至少需要 3m+1 个将军, 才能最终达到一致的行动方案。当然在这篇论文中也给出了解决方案，分别是口信消息型解决方案（A solution with oral message）和签名消息型解决方案（A solution with signed message），感兴趣大家可以去这篇文章 看看，我这里不再详述。

共识与一致性

上面我们说到，拜占庭是一个协议共识问题，也就是说让多数人达成一致的意见，即少数人服从多数人。这一术语很多时候会与一致性（Consistency）放在一起讨论，而二者的含义并不完全相同。

一致性

一致性（Consistency），早期也叫（Agreement），在分布式系统领域中是指对于多个服务节点，给定一系列操作，在约定协议的保障下，使得它们对处理结果达成“某种程度”的协同。

理想情况（不考虑节点故障）下，如果各个服务节点严格遵循相同的处理协议（即构成相同的状态机逻辑），则在给定相同的初始状态和输入序列时，可以确保处理过程中的每个步骤的执行结果都相同。因此，传统分布式系统