概念
- 分布式系统是一个其组件分布在不同的、联网的计算机上，组件之间通过传递消息进行通信和协调，共同完成一个任务的系统
- 分布式系统其实就是研究如何协调这些联网的计算机来共同完成任务
- 整个系统对于客户端用户而言，可以看作一台计算机
为什么需要
- 高性能
- 可扩展性
- 高可用性
- 必要性
分布式系统模型
两将军问题 (Two Generals' Problem)
背景：
两将军问题是由Jim Gray在1978年提出的，描述了在分布式系统中如何在不可靠的通信渠道下达成一致性的问题。这个问题的本质是讨论在不可靠的通信情况下，两个远程节点是否能就某个行动达成一致。
问题描述：
- 想象有两位将军，分别指挥着两支军队，他们需要同时进攻敌军以获得胜利。
- 他们的军队分别驻扎在一座山的两侧，山谷里有敌军驻守。
- 两位将军只能通过信使进行通信，但信使必须穿过敌人的领地，有可能被捕，导致消息未能传达。
两位将军必须达成一致的决定：是同时进攻还是撤退。如果其中一位将军未能按时进攻，另一位将军的军队可能会被敌军击败。
关键问题：
由于通信的不确定性，即便某个将军接收到“准备进攻”的消息，他们也无法确定对方是否收到了确认回复。即使收到了确认的消息，发送确认的将军仍然无法确定他的确认消息是否被对方接收到。因此，无法保证两个将军能够在任何情况下达成一致。
结论：
在不可靠的通信网络中，两个节点之间无法通过有限次数的消息交换来保证达成一致。这说明，在分布式系统中，完全一致性是无法通过仅仅依赖通信来实现的。
拜占庭将军问题 (Byzantine Generals' Problem)
背景：
拜占庭将军问题由Leslie Lamport、Robert Shostak和Marshall Pease在1982年提出，用来描述在分布式系统中，有恶意节点存在的情况下，如何达成一致性的问题。
问题描述：
- 假设有一群拜占庭将军指挥着各自的军队，他们必须在敌人的城堡周围协同作战，决定是同时进攻还是撤退。
- 其中一些将军可能是叛徒，他们试图通过发送虚假消息来扰乱其他将军的决策，导致整个军队失败。
每位将军可以向其他将军发送消息，他们必须根据收到的消息决定是否进攻。问题是，即使部分将军是叛徒，忠诚的将军如何达成一致的决策。
关键问题：
拜占庭将军问题的核心在于，即使在某些节点（将军）可能是恶意的情况下，系统如何确保忠诚节点达成一致性。
结论：
拜占庭将军问题是分布式计算中一个重要的模型，尤其是在涉及到共识协议时，如区块链和分布式数据库系统中。拜占庭容错算法允许系统在存在恶意节点的情况下，依然能够达成一致性决策。
比较与总结
- 两将军问题主要讨论的是在不可靠通信下达成一致的困难，得出的结论是不可能达成完全一致。
- 拜占庭将军问题则进一步扩展到分布式系统中，考虑到部分节点可能是恶意的，讨论如何在这种情况下达成一致。
网络链路模型
1. 可靠链路 (Reliable Link)
定义：
可靠链路是一种保证消息传输的通信链路。它的主要特性是确保发送的消息能够最终被正确地传递到接收方，且没有消息丢失、重复或乱序。
特性：
- 无消息丢失：所有发送的消息都会最终被接收方接收到。
- 无消息重复：每条消息只会被接收方接收到一次。
- 无消息乱序：消息按照发送的顺序被接收。
实现：
可靠链路通常通过各种确认机制（如TCP中的ACK）来确保消息的成功传递。如果发送的消息未能被确认，发送方会重发该消息，直到接收到确认为止。
应用场景：
可靠链路广泛应用于需要保证数据完整性的场景，如文件传输、数据库复制和其他关键数据传输任务。
2. 公平损失链路 (Fair Lossy Link)
定义：
公平损失链路允许消息在传输过程中可能会丢失，但保证不会无限制地丢失某条消息。换句话说，虽然消息传输不是完全可靠的，但每条消息都有公平的机会被传递。
特性：
- 可能丢失消息：消息传输过程中可能会有部分消息丢失。
- 无消息重复：每条消息在被接收方接收时只会收到一次。
- 无消息乱序：消息按照发送的顺序被接收。
“公平性”含义：
- 公平性意味着虽然链路可能会丢失一些消息，但不会有某一条消息永远无法传递到接收方。
实现：
公平损失链路一般通过随机的丢包机制来实现，确保没有某条消息被无故长期丢弃。
应用场景：
公平损失链路适用于对可靠性要求不高，但希望有较高传输效率的场景，如实时音视频传输、在线游戏中的状态同步等。
3. 任意链路 (Arbitrary Link)
定义：
任意链路是指一种没有任何传输保证的链路，消息在传输过程中可能会丢失、重复、乱序或完全无法传输。
特性：
- 可能丢失消息：消息可能会在传输过程中丢失。
- 可能消息重复：同一条消息可能会被接收方多次接收。
- 可能消息乱序：消息可能会以与发送顺序不同的顺序到达接收方。
实现：
任意链路通常没有任何额外的机制来确保消息的可靠传输，完全依赖于底层的网络环境。
应用场景：
任意链路一般用于没有强一致性要求的应用场景，或者用于测试和模拟不可靠网络环境的场景，如网络拓扑仿真、恶劣网络环境下的应用测试等。
总结
- 可靠链路：确保所有消息都能正确传递，并且不会有消息丢失、重复或乱序。
- 公平损失链路：允许消息丢失，但确保每条消息都有被传递的机会，且不会重复或乱序。
- 任意链路：没有任何传输保证，消息可能丢失、重复、乱序或完全无法传递。
这些链路模型反映了不同的网络条件和要求，在分布式系统设计中，选择合适的链路模型可以帮助处理各种网络传输的不确定性。
节点故障类型
崩溃-停止 (Crash-Stop)
定义： 崩溃-停止故障指的是系统中的某个节点突然停止工作，不再进行任何操作，也不会发送任何消息。这种故障是“非拜占庭”故障的一种，即故障的原因不是由于恶意行为，而是由于硬件或软件的错误。 特点：
- 节点完全停止响应。
- 节点不会发送任何错误信息或欺骗性信息。
- 可以通过重启故障节点来恢复服务。 处理方式： 通常采用心跳机制来检测节点是否存活。如果一个节点在预定时间内没有发送心跳信号，则认为该节点发生了崩溃-停止故障。随后，系统可以尝试重启该节点或采取其他恢复措施。
崩溃-恢复 (Crash-Restart)
定义： 崩溃-恢复故障是指系统中的节点在停止工作之后，能够恢复到某个一致的状态，并重新加入到系统中。 特点：
- 节点在故障后能够恢复。
- 恢复的节点可能丢失了故障前的部分或全部状态信息。
- 需要机制来确保恢复后的节点能够与系统中的其他节点保持一致性。 处理方式： 系统通常会采用日志记录和状态复制的方式来保证一致性。恢复节点时，会通过这些日志和状态信息来重建节点状态，并重新同步数据。
拜占庭故障 (Byzantine Fault)
定义： 拜占庭故障是指系统中的节点可能表现出任意行为，包括发送错误信息、伪造信息、不发送信息或进行协同攻击等。这种故障假设节点可能被恶意攻击者控制。 特点：
- 节点行为不可预测，可能出于恶意。
- 故障节点可能向其他节点发送矛盾或错误的信息。
- 处理拜占庭故障需要更强的算法和协议来确保系统的安全性和一致性。 处理方式： 处理拜占庭故障通常需要使用拜占庭容错（Byzantine Fault Tolerance, BFT）算法，如PBFT（Practical Byzantine Fault Tolerance）。这些算法能够保证即使有一定数量的节点表现出任意恶意行为，整个系统仍然能够达成一致并继续正常运作。 在设计和维护分布式系统时，理解并妥善处理这些故障类型是至关重要的，以确保系统的可靠性、可用性和安全性。
消息传递语义
消息传递语义定义了分布式系统中消息发送和接收的规则和保证。这些语义有助于开发者理解在不同情况下消息传递的行为，以及如何构建可靠的分布式应用程序。
至多一次 (At-most-once)
定义： 消息至多被传递一次，可能根本不被传递。 特点：
- 消息可能会在传输过程中丢失。
- 没有重复消息的保证。
- 通常用于对数据完整性要求不高的场景。
至少一次 (At-least-once)
定义： 消息至少被传递一次，但可能会被传递多次。 特点：
- 消息不会在传输过程中丢失，但可能会重复。
- 接收者需要处理可能的重复消息。
- 适用于可以容忍重复处理的场景。
精确一次 (Exactly-once)
定义： 消息精确地被传递一次，既不会丢失也不会重复。 特点：
- 需要复杂的协议来保证消息的精确一次传递。
- 通常涉及到消息的确认和幂等处理。
- 适用于对数据完整性要求极高的场景。