分布式系统与计算机网络 漫谈分布式系统(2)

为了表达上更直观，下面我们还是假设某些节点宕机了。那在这个时候，剩下的节点在缺少了某些节点参与决策的情况下，还能不能对于提议达成一致呢？即使是达成了一致，那么在那些宕机的节点重新恢复过来之后（注意这时候它们对于其它节点之间已经达成一致的提议可能一无所知），它们会不会对于已经达成的一致提议重新提出异议，从而造成混乱？所有这些问题，都是分布式一致性协议需要解决的。

我们这里没有足够的篇幅来详细讨论这些协议具体的实现了，感兴趣的读者可以去查阅相关的论文。实际上，理解问题本身比理解问题的答案要重要的多。总之，我们需要知道的是，我们已经有了一些现成的分布式一致性算法，它们能解决上面讨论的这些问题，保证在一个去中心化的网络中，各个节点之间最终能够对于提议达成一致。而且，一般来说，只要网络中的大部分节点(或一个quorum)仍然存活（即它们相互间可以收发消息），这个一致性的提议就可以达成。

拜占庭将军问题

我们前面讨论的一致性协议，有一个重要的前提条件，就是：各个节点都是可以信任的，它们都严格遵守同样的一套规则。这个条件，在一个公司的内部网络中可以认为是基本能满足的。但如果这个条件不满足会怎么样呢？假设网络中有些节点是恶意的，它们不但不遵守协议，还故意捣乱（比如胡乱发送消息），那么其它正常的节点还能够顺利工作吗？

在分布式系统理论中，这个问题被抽象成了一个著名的问题——拜占庭将军问题(Byzantine Generals Problem)。这个问题由大名鼎鼎的Leslie Lamport提出，也就是Paxos的作者。同时，Lamport还是2013年的图灵奖得主。

这要从一个故事开始说起（当然这个故事是Lamport编出来的）。拜占庭帝国的几支军队攻打到了敌人的城市外面，然后分开驻扎。每一支军队由一位拜占庭将军(Byzantine general)率领。为了制定出一个统一的作战计划，每一位将军需要通过信差(messenger)与其它将军互通消息。但是，在拜占庭将军之间可能出现了叛徒(traitor)。这些叛徒将军的目的是阻挠其他忠诚的将军(loyal generals)达成一致的作战计划。为了这一目的，他们可能做任何事，比如串通起来，故意传出虚假消息，或者不传出任何消息。

我们来看一个简单的例子。假设有5位将军，他们投票来决定是进攻还是撤退。其中两位认为应该进攻，还有两位认为应该撤退，这时候进攻和撤退的票数是2:2打平了。第五位将军恰好是个叛徒，他告诉前两位应该进攻，但告诉后两位应该撤退，结果前两位将军最终决定进攻，而后两位将军却决定撤退。没有达成一致的作战计划。

这个问题显然比我们在前一章讨论的可信任环境下的一致性问题要更难。要解决这个问题，我们是希望能找到一个算法，保证在存在叛徒阻挠的情况下，我们仍然能够达成如下目标：A. 所有忠诚的将军都得到了相同（一致）的作战计划。比如都决定进攻，或都决定撤退，而不是有些将军认为应该进攻，其他将军却决定撤退。B. 忠诚的将军不仅得到了相同的作战计划，还应该保证得到的作战计划是合理的(reasonable)。比如，本来进攻是更有利的作战计划，但由于叛徒的阻挠，最终却制定出了一起撤退的计划。这样我们的算法也算失败了。

可以看出，上面的目标A，是比较明确的，至少给定一个算法很容易判定它有没有达到这个目标。但目标B却让人无从下手。一个作战计划是不是「合理」的，本来就不好定义。即使没有叛徒的存在，忠诚的将军们也未必就一定能制定出合理的计划。这涉及到科学研究中一个非常重要的问题，如果一个事情不能用一种形式化的方式清晰的定义出来，对于它的研究也就无从谈起，这个事情本身也无法上升到科学的层面。Lamport在对拜占庭将军问题的研究中，一个突出的贡献就是，把这个看似不太好界定的问题，巧妙地归约到了一个能用数学语言精确描述的问题上去。下面我们就看一下这个过程是怎么做的。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-65268-2.html