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

这两类错误的含义并没有字面上那么好理解。

先说说拜占庭错误。在「拜占庭将军问题」中，叛徒的恶意行为固然是属于这一类错误的。在不同的将军看来，叛徒可能发送完全不一致的作战提议。而在计算机系统中，出现故障的节点或部件也可能表现出前后不一致的行为，虽然这并非恶意，但也属于这一类错误。比如信道不稳定，导致节点发送给其它节点的消息发生了随机错误，或者说，消息损坏了(corrupted)。再比如，在系统中，commit之后的数据明明已经同步给磁盘了（通过操作系统的fsync），但由于突然断电等原因，最终数据还是没有真正落盘成功，甚至出现数据错乱。

再看一下非拜占庭错误。Lamport在他关于Paxos的一篇论文中也使用了non-Byzantine这个词（见《Paxos Made Simple》）。但是这个词的命名的确让人有点不好理解。在分布式系统中，如果节点宕机了，或者网络不通了，都会导致某些节点不能工作。其它节点其实没法区分这两种情况，在它看来，只是发现某个节点暂时联系不上了（即接收消息超时了）。至于是因为那个节点本身出问题了，还是网络不通了，或者是消息出现了严重的延迟，是无法区分的。而且，过一会之后，节点可能会重新恢复（或是自己恢复了，或经过了人工干预）。换句话说，对于出现这种错误的节点，我们只是收不到它的消息了，而不会收到来自它的错误消息。相反，只要收到了来自它的消息，那么消息本身是「忠实」的。

可见，拜占庭错误是更强的一类错误。在「拜占庭将军问题」中，叛徒发送前后不一致的作战建议，属于拜占庭错误；而不发送任何消息，属于非拜占庭错误。所以，解决「拜占庭将军问题」的算法，既能处理拜占庭错误，又能处理非拜占庭错误。这听起来稍微有些奇怪，不过这只是命名带来的问题。

总之，「拜占庭将军问题」的解法应该是最强的一类分布式一致性算法，它理论上能够处理任何错误。而Paxos只能处理非拜占庭错误。通常把能够处理拜占庭错误的这种容错性称为「Byzantine fault tolerance」，简称为BFT。

这样说来，BFT的算法应该可以解决任何错误下的分布式一致性问题，也包括Paxos所解决的问题。那为什么不统一使用BFT的算法来解决所有的分布式一致性问题呢？为什么还需要再费力气设计Paxos之类的一些算法呢？我们前面没有仔细讨论解决「拜占庭将军问题」的算法，所以这里也不做仔细的分析了。但容易想象的是，提供BFT这么强的错误容忍性，肯定需要付出很高的代价。比如需要消息的大量传递。而Paxos不需要提供那么强的容错性，因此可以比较高效地运行。另外，具体到Lamport在论文中给出的解决「拜占庭将军问题」的算法，它还对系统的记时假设(timing assumption)有更强的要求。这也容易理解，既然算法的容错性要求这么高，自然对于运行环境的假设(assumption)也有可能要高一点。由于这个问题是分布式系统中一个挺关键的问题，所以我们在这里单独拿出来讨论一下。在Lamport在论文中，算法对于系统的假设有这么一条：The absence of a message can be detected.

这条假设要求，如果某位叛徒将军没有发送任何消息（当然也可能是消息丢失了），那么这件事是可以检测出来的。显然，这只能依赖某种超时机制(time-out)，依赖节点之间的时钟达到一定程度的同步，即时钟的偏移不能超过一个最大值。这实际上是一种同步模型(synchronous model)。而Paxos的系统假设在这一点上就没有这么强，它是基于异步模型(asynchronous model)，对系统时钟没有特定的要求。我在之前的另一篇文章《基于Redis的分布式锁到底安全吗？》一文中也有提到过这个问题。这有时候会成为分布式算法带来一些争议的根源。

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