1.3 “两将军”问题

如图1-1所示，假设有两支友军，分别由A和B两位将军统领。这两位将军都知道，仅当两支军队同时向敌军发起进攻时才能获胜，否则必败，因此两位将军要协商一个同时发起进攻的时间点。但两支友军驻扎在两座不同的山上，两山之间有一个山谷，两位将军只能派信使途经山谷向友军报信。然而山谷里驻扎着敌军，信使很有可能被敌军俘虏，导致消息无法在预期的时间内传递到友军。请问，是否存在一种确定的策略，只要两位将军按照这个策略执行，就能约定好同时发起进攻的时间呢？

乍一看，这个问题很简单。在日常生活中，我们经常会遇到类似的事情，例如张三和李四约好了明天下午4点喝茶，这与两位将军约定同时发起进攻的时间点在本质上没有区别。下面我们试着模拟一下两个将军的思考和行为，再做判断。

第1步：A将军向B将军发送消息“明日午时三刻何如？”

第2步：B将军收到了A将军发送的消息“明日午时三刻何如？”

第3步：A将军收到了B将军发送的消息“B同意”。

到这里，也许读者会认为两位将军已经就同时发起进攻的时间点达成一致了。但B将军敢在明日午时三刻发动进攻吗？不敢，因为B将军知道，虽然他（B将军）回复了“B同意”这条消息，但并不确定A将军是否收到了。如果A将军没有收到“B同意”这条消息，那么A将军就不会进攻，若B将军单独进攻，就只有死路一条，所以B将军不敢发动进攻。同理，A将军也想到了B将军会这么想，所以A将军也不会进攻。

也许读者又会问，让A将军再发送一条确认消息“A收到（B同意）”给B将军，不就可以了吗？那我们再继续模拟一下。

第4步：B将军收到了A将军发送的消息“A收到（B同意）”。

此时，B 将军敢在明日午时三刻发动进攻吗？仍然不敢，因为 B 将军知道，虽然他（B将军）收到了A将军发送的“A收到（B同意）”这条消息，但A将军并不知道B将军是否收到了。如果B将军没有收到“A收到（B同意）”这条消息，那么B将军就不会进攻，若A将军单独进攻，就只有死路一条，所以A将军也不会进攻。想到这里，B 将军就不会进攻了。同理，A 将军也想到了 B 将军会这么想，所以 A将军也不会进攻。

接下来，我们再来一个确认消息看能否让两位将军敢进攻。

第5步：A将军收到了B将军发送的消息“B收到（A收到（B同意））”。

此时，A 将军敢在明日午时三刻发动进攻吗？仍然不敢，因为 A 将军知道，虽然他（A将军）回复了“B收到（A收到（B同意））”这条消息，但B将军并不知道A将军是否收到了。如果A将军没有收到“B收到（A收到（B同意））”这条消息，那么A将军就不会进攻，若B将军单独进攻，就只有死路一条，所以B将军也不会进攻。想到这里，A将军也就不敢进攻了。同理，B将军也想到了A将军会这么想，所以B将军也不会进攻。

……

这样无限循环下去，一个看似能够轻松搞定的事情就变得无解了，这似乎有点违反直觉，我们把这种情况称为“脑裂”（Brain-Split）。这是一个形象的比喻：在正常情况下，一个人只有一个大脑，全身都要听从这个大脑的指挥。“脑裂”是指大脑分裂了，两个大脑互不买账，身体其他部位就不知道该听谁的了。“两将军”问题就是脑裂的结果，两位将军无法就何时发起进攻一事而做出一致的决定。

为什么会出现脑裂呢？关键在于“信使不可靠”。我们在日常生活工作中，以面对面或电话的方式约定某件事情时，其实是利用了一个潜在的假设——“通信是可靠的”。下面以张三约李四喝茶为例模拟一下。

张三约李四喝茶

假设张三想约李四喝茶。

第1步：张三跟李四说“明天下午4点喝茶怎样？”

第2步：李四跟张三说“行啊”。

第3步：张三听到了李四说的“行啊”。

仅仅通过这3步，张三和李四就都会于明天下午4点去喝茶。之所以李四会去喝茶，是因为李四认为通信是可靠的，张三一定会听到自己（李四）说的“行啊”两个字，因此张三一定会去。之所以张三会去，是因为张三听到了李四说的“行啊”两个字之后，就知道李四会去，并且知道李四知道自己（张三）也会去，所以张三也会去喝茶。可见，通信可靠是多么重要。

回到“两将军”问题。上述模拟过程的失败，只能让读者感觉解决到两将军问题并非易事，但并不能证明“两将军”问题不可解。幸运的是，1985年，Fischer、Lynch和Paterson三位计算机科学家共同发表了一篇论文，证明了一个不幸的结论——“异步系统无法实现共识”，这个结论被称为“FLP不可能结论”。其中，“信使会被俘虏”实际上就构造了一个异步系统，“何时发动进攻”就是所要达成的共识。根据FLP不可能结论，“两将军”问题无解。

“两将军”问题无解的现实影响

“两将军”问题无解对现实的影响是巨大的！“两将军”问题无解，实际上是说，对于任何两个进程，如果它们的通信不可靠，则无法可靠地达成任何共识。下面我们看看在工作中遇到的“两将军”问题。

1.双机热备技术

工作经验丰富的读者可能听过“双机热备”（或“双机高可用”）技术。这种技术宣称可以让两个节点形成主备关系，如果主节点出现故障，那么备节点就会自动接管，使整个服务得以继续运行。这种能够容忍单节点故障的技术称为高可用技术。但是，根据FLP不可能结论，如果两个节点间的通信不可靠，那么这两个节点就无法对“谁是主节点”这个问题达成共识，即出现脑裂。出现脑裂后，要么出现两个主节点的情况，要么出现没有主节点的情况，而无法保证一定会出现一主一备的情况。因此，可靠的双机热备方案是，要么加强通信链路的可靠性，要么引入第三节点。如果仅在两个节点上安装了“具有神奇功能”的软件，那肯定不是一个可靠的双机热备方案。

2.双活机房

与数据中心打交道的读者应该听过“双活机房”或类似的词。这种技术通过高速网络将两个异地机房互联，使分别部署在两个机房的两套系统形成主备关系。该技术宣称，如果主机房断电断网，那么备机房的系统就会自动接管业务，使整个服务得以继续运行。在灾难发生时，例如水灾、地震等，由于这种技术能够跨地域提高服务持续运行的能力，因此比双机热备技术更“高级”。

但实际上，因为异地机房通过广域网进行通信，如果网络不可靠，双活机房仍然有可能出现脑裂问题。实际上，广域网通信的成本远远高于局域网，在相同的代价下，异地两机房的互联可靠性远远低于同址两节点的互联可靠性，更容易出现脑裂现象。因此，如果要实现跨地域的高可用，则应该在第三机房部署第三节点以避免脑裂。

3.TCP协议中的TIME_WAIT

精通TCP协议的读者应该知道TIME_WAIT状态。当进程A关闭一个TCP连接时，进程A的TCP/IP协议栈会将该连接的状态改为TIME_WAIT，并等待若干分钟后，才真正释放该连接的资源，例如所占用的IP和端口。如果不等待足够长的时间，那么进程A就不能确定对端进程B是否收到了报文ACK，从而导致其他问题。例如，如果在进程A和进程B之间新建TCP连接时，进程A和进程B都有可能接收到上一个TCP连接的报文，从而导致新的TCP连接无法正常工作（由于这不是一本关于TCP协议的书，故不详细展开）。这其实与FLP不可能结论也有关。

FLP不可能结论指出，如果通信不可靠，那么任何两个进程都无法达成共识。也就是说，通过一个TCP连接互联的两个进程其实是无法对“对方进程是否发送/接收了报文ACK”这个问题达成一致的。因此，TCP/IP协议栈不得不选择一个很长的超时值，例如2分钟，甚至更长。从分布式算法的角度看，选择很长的超时值，实际上是在规避进程间通信不可靠的问题。至于为什么说“规避”，需要继续学习本书才能理解。

通过上述分析不难看出，一个小小的“两将军”问题就可以解释那么多的现实问题，分布式算法在我们的工作和生活中更是几乎无处不在。掌握分布式算法的原理和应用，不仅能够帮助我们回答很多问题，让我们知道哪些事情可能、哪些事情不可能，还能让我们更好地改变世界。