两将军问题和 TCP 三次握手
两将军问题，又被称为两将军悖论、两军问题， 是一个经典的计算机思想实验。
首先， 为避免混淆，我们需要认识到两将军问题虽然与拜占庭将军问题相关，但两者不是一个东西。拜占庭将军问题是一个更通用的两将军问题版本， 通常在分布式系统故障容错、区块链中广泛讨论。
1.双将军问题
两支军队，驻扎在两个山头，准备攻击山谷里的同一伙敌人，两将军只有同时发起进攻才能获胜，两将军通信的的唯一方式是派遣信使通过山谷，山谷处于敌占区。
如果信使被俘获了，那么攻击信息将会丢失。
宏观现象一： 两将军先后派遣信使，交替确认收到的攻击信息，交替确认是无止尽的，两将军不能达成共识。
微观现象二： 将军 A 派遣信使，过了很长时间未收到回复，将军 A 不知道是自己的信使被俘获了还是将军 B 的确认信使被俘获了。
我们意识到即使双方不断确认收到对方的上一条信息，都不能确保对方与自己达成(同一时间攻击的共识)。
两将军问题是无解的，目前的 tcp 三次握手、四次挥手都是工程解 (这个一会再聊)。
2.双将军问题的头脑风暴
许多人试图解决/缓解双将军问题，提出了一些能落地的实践。
这里我们依旧还是假设通道的不确定性，信使只会被俘获，但是不会叛变篡改。
2.1 霰弹打鸟
如果 A 将军每次派遣 100 名信使(编号 1 到 100)，期待 B 将军最差也能收到一名信使的信息。
B 将军根据收到的信使数量，评估这条通道的可靠性，并根据概率也派遣合适数量的确认信使。
eg: A 将军派遣 100 信使，B 将军收到 10 名信使的信息，B 将军基本可确认这条信道可靠度为 1/10，B 将军最少应派出 10 名信使(根据概率会有 1 名信使到达对岸)。
2.2 间歇性重试
霰弹打鸟的姿势太费信使了，但是可以帮助将军提高信心，达成共识。
还有一种少费信使(并能提高将军信心)的策略，假设跨越山谷到达对岸并返回耗时 20min， A 将军可间隔 20min 派遣信使到对岸，直到收到对岸 B 将军的首次信使确认(就不再派遣)。
以上两种策略分别是对速度和成本的权衡，采用哪一种取决于哪一种更适合我们遇到的问题。
3. 为什么说tcp 三次握手是双将军问题的工程解？
知乎上有个问题：TCP 为什么是三次握手，而不是两次或四次？
分别从三个角度回答。
希望大家仔细读一读。
首先我们要知道：
三次握手是为了在两个方向上同步(syn)序列号(seq=m)，同步一次序列号需要一去一回两个包，俩方向就 4 个包。第 2，3 个包由一侧发出可以合并到一起所以最后三个包。
但是根据双将军问题，谁说一来一回两个包就能确保同步成功。
为了缓解双将军问题，tcp3 次握手增加了超时重试的机制。注意，只有同步连接 SYN 的发起方，才会重试。
第一个包： A 发送给 B 的 SYN 中途丢失，没有到达 B
A 会周期性超时重传，直到收到 B 的确认。
第二个包，即是发送给 A 的 SYN+ACK 中途丢失，没有到达 A
B 会周期性超时重传，直到收到 A 的确认 （此时，第一个包：A 因为没有收到 ACK 确保，A 也回重试）
第三个包：即 A 发送给 ACK 中途丢失，没有到达 B
A 发完 ACK，单方面认为 tcp Established 状态，而 B 显然认为 tcp 为 Active 状态。
a. 假定此时双方都没有数据发送，B 会周期性超时重传，直到收到 A 的确认，收到之后 B 的 TCP 连接也为 Established 状态，双向可以发包。
b. 假定此时 A 有数据发送，B 收到 A 的 Data + ACK，自然会切换为 established 状态，并接受 A 的 Data。
c. 假定 B 有数据发送，数据发送不了，会一直周期性超时重传 SYN + ACK，直到收到 A 的确认才可以发送数据。
总结
本文记录了两将军问题:
对于不可靠信道，即使双方不断确认收到对方的上一条信息，也不能确保对方与自己达成共识 。
TCP 三次握手是在两个方向确认包的序列号， 增加了超时重试， 是两将军问题的一个工程解。
（本文部分内容提炼自知乎，感谢这届网友的智慧）
https://finematics.com/two-generals-problem/
https://www.bilibili.com/read/cv16604716
版权声明: 本文为 InfoQ 作者【有态度的马甲】的原创文章。
原文链接:【http://xie.infoq.cn/article/84fa676ccbc63896e4849dde7】。文章转载请联系作者。
急性子，入戏慢。 2018.06.17 加入
阿里云社区专家博主，同程旅行基础架构 ； 热衷分享，执着于阅读写作，佛系不水文，有态度公众号：《精益码农》； 持续输出高价值Go、.NET、云原生原创文章。
评论