上层应用的基石：分布式协议
故障模式
故障发生和检测的方式对于许多算法都很重要。以下是最常用的：
故障停止
故障停止意味着如果节点出现问题，每个人都能知道并检测到它，并能从稳定的存储中恢复状态。这在理论和协议上都是简单的模式，但在实践中却很难实现（在某些情况下甚至是不可能的）
崩溃故障
崩溃故障意味着，如果节点或代理出现问题，它就会崩溃，然后再也不会回来。你要么永远正确，要么永远迟到。这在理论上比故障停止更容易设计（但操作起来非常麻烦，因为冗余是游戏的名字，永远都是）。
遗漏故障
遗漏故障意味着你必须给出符合协议的正确结果，否则就永远无法回答。
性能故障
性能故障则假定，在发送信息内容方面遵守协议的同时，也有可能延迟发送结果。
拜占庭式的失败
拜占庭故障意味着任何事情都可能出错（包括有人故意用坏软件冒充好软件来破坏协议）。有一类特殊的可检测认证的拜占庭故障，它至少会限制你不能伪造来自其他节点的其他信息，但这只是可选项。拜占庭模式是最糟糕的。
常见的实际故障模式
在实践中，当你从计算机科学转向工程学时，你会发现故障类型更加多样化，但也可以映射到任何理论模型。
1、网络分裂
有些节点可以互相通话，但有些节点却无法与其他节点联系。一个常见的例子是，基于美国的网络可以在内部正常通信，基于欧盟的网络也可以，但两者都无法互相通话
2、非对称网络分裂
节点组之间的通信是不对称的。例如，假设美国网络可以向欧盟网络发送信息，但欧盟网络却无法作出回应。这种情况在使用 TCP 时比较少见（尽管以前也发生过），而在使用 UDP 时则可能很常见。
3、脑裂
许多系统处理故障的方法是保持多数系统继续运行。当网络分裂的双方都认为自己是领导者，并开始做出相互冲突的决定时，就会出现分裂脑。
4、超时
超时尤其棘手，因为它们是非确定性的。它们只能从一端观察到，而且你永远不知道最终被解释为失败的超时是否真的是失败，或者只是由于网络、硬件或 GC 暂停造成的延迟。有时，如果信息已被看到，重传就不安全了（即它不是幂等的），而超时基本上使人无法知道重传是否安全：信息是否已被执行、丢弃，还是仍在传输中或在某个缓冲区中？
5、排序导致的报文丢失
一般情况下，使用 TCP 和碰撞往往意味着很少有报文在系统间丢失，但经常出现的情况包括节点宕机（或软件崩溃）几秒钟，在此期间错过了一条不会重复的信息在不同节点之间临时接收更新。例如，服务 A 在总线（无论是 Kafka 还是 RMQ）上发布的消息最终可能被服务 B 读取、转换或执行并重新发布，而服务 C 有可能先于 A 读取 B 的更新，从而造成因果关系问题。
6、时钟漂移
并非所有系统上的所有时钟都能正确同步（即使使用 NTP），而且同步速度也会不同。使用时间戳对事件进行排序几乎肯定会产生错误，如果时间戳来自多台计算机，错误就会更多。
7、客户端是系统的一部分
一个非常常见的误区是忘记了参与分布式系统的客户端也是系统的一部分。如果客户端无法理解其接收到的事件或数据，服务器端的一致性就不一定有多大价值。对于数据库客户端来说，这一点尤其隐蔽，因为它们在进行非瞬时事务处理时会超时，而且无法知道是否可以再次尝试。
8、从多个备份恢复
单个备份很容易处理。多重备份会遇到一个问题，即一致切割（高级视图）和分布式快照，这意味着并非所有备份都是在同一时间进行的，这会带来不一致性，可被视为数据损坏。
如何解决故障和失败
共识
这是分布式系统的核心问题之一：系统中的所有节点或代理如何就一个值达成一致？它之所以如此重要，是因为如果能就一个值达成一致，就能做很多事情。
选择一个非常有用的值，最常见的例子就是选出一个执行决策的领导者的名字，这样你就不用再建立更多的共识了，因为共识太痛苦了。
关于什么是共识，存在各种说法，包括每个人都完全同意？(强）还是只是多数？(t-resilient），以及在各种同步或失败模型中提出同样的问题。
需要注意的是，虽然像 Paxos 这样的经典协议会使用领导者来确保一致性，并在保持一致的同时加快执行速度，但很多系统都会放弃这些要求。
细节阅读
- original paper
- blog post review (archive)
- Raft（简单协议介绍）
- Paxos（兼职议会）
- Paxos made Live（谷歌在使 paxos 工作方面的经验报告）
- Paxos 变体
- ZAB（动物园管理员算法）
CAP 定理
CAP 定理在很长一段时间内都只是一个猜想，但在 2000 年代初得到了证明，从而产生了许多最终一致的数据库。
分布式系统有三个特性：
- 一致性：每次向系统写入并从系统中读取时，都会得到写入的值或更新值。
- 可用性：每次请求都会得到响应（包括读取和写入）
- 分区容忍性：网络可能会丢失信息
从理论上讲，你可以得到一个既可用又一致的系统，但这只适用于完美网络上的同步模型。这种情况并不存在，因此在实际应用中，P 总是存在的。
CAP 定理的基本原理是，在给定 P 的情况下，你必须选择 A（继续接受写入并可能损坏数据）或 C（停止接受写入以保存数据，并宕机）。
论文：
- CAP visual proof
- You can't sacrifice partition tolerance
幂等性
幂等性非常重要，需要有自己的条目。闲置意味着，当信息被多次查看、重发或重放时，它们对系统的影响不会与只发送一次时有什么不同。
常见的策略是让每条信息都能引用以前看过的信息，这样就可以定义一个排序来防止重播旧信息，设置唯一的 ID（如事务 ID）和一个存储空间来防止重播事务，等等。
论文
- Idempotence is not a medical condition
状态机复制
这是一个理论模型，根据该模型，如果给定相同的状态序列并对其进行相同的操作（不考虑各种非确定性），所有状态机最终都会得到相同的结果。这个模型对于大多数可靠的系统都至关重要，因为这些系统都会尝试以相同的顺序向所有子系统重放所有事件，从而确保所有地方的数据集都是可预测的。这通常是通过选择一个领导者来实现的；所有的写入都通过领导者完成，所有的跟随者都会得到系统的一致复制状态，使他们最终成为领导者，或将自己的状态扇形扩展到其他参与者。基于状态的复制在概念上可能比状态机复制更简单，其理念是，如果只复制状态，最终就能得到状态！问题是，要做到快速高效非常困难。如果你的状态有几兆兆字节那么大，你可不想每次操作都要重新发送。常见的方法包括对数据进行拆分、散列和分块，以检测变化并只发送变化的部分（想想 rsync）；用梅克尔树merkle trees 来检测变化；或者对源代码打补丁。
信息传递定义
信息可以按不同顺序发送零次或多次。下面介绍一些术语来定义它们：
- 单播是指信息只发送给一个实体
- 任播（anycast）是指向任何有效实体发送信息
- 广播是指将信息发送给所有有效实体
- 原子广播（atomic broadcast）或总顺序广播（total order broadcast）是指系统中的所有非故障行为体都以相同的顺序接收相同的信息，无论该顺序是什么
- 流言（gossip）是指在对等体之间转发信息，希望最终每个人都能收到所有信息的协议系列。
- 至少传递一次是指每条信息将被传递一次或多次；监听者希望看到所有信息，但可能不止一次
- 最多发送一次是指每个发送者只发送一次信息。监听者有可能永远看不到。
- 完全一次发送是指每条信息保证只被发送和看到一次。这是一个很好的理论目标，但在实际系统中是不可能实现的。最终只能通过其他方法来模拟（例如，将原子广播与特定标志和排序保证结合起来）
顺序控制
总排序是指所有信息只有一种严格的排序和比较方式，就像 3 总是大于 2 一样。
部分排序意味着某些信息可以与某些信息进行比较，但不一定是所有信息。例如，我可以决定，对密钥 k1 的所有更新可以相互之间有一个总顺序，但独立于对密钥 k2 的更新。因此，在所有密钥的所有更新之间存在部分顺序，因为 k1 的更新与 k2 的更新没有任何信息关联。
因果顺序指的是，所有依赖于其他信息的信息都是在这些信息之后收到的（你不可能在了解一个用户之前就知道他的头像）。它是部分顺序的一种特殊类型。
没有 "最佳 "排序，每种排序都提供了不同的可能性，并伴随着不同的成本、优化和相关故障模式。
一致性模型
有几十种不同级别的一致性，维基百科、彼得-贝利斯（Peter Bailis）的相关论文或凯尔-金斯伯里（Kyle Kingsbury）的相关文章都对它们进行了概述
- 线性化是指每个操作都是原子性的，不会受到其他操作的影响，就好像所有操作都是一次运行一个一样。顺序是已知的、确定的，在某个写入开始后开始的读取将能看到该数据。
- 串行化意味着，虽然所有操作看起来都是原子操作，但并不保证这些操作会以何种顺序进行。这意味着某些操作可能在另一个操作之后开始，但在另一个操作之前完成，只要隔离维护得当，这并不是问题。
- 顺序一致性是指，即使操作可能是不按顺序进行的，它们看起来也是按顺序进行的。
- 因果一致性是指，只有在逻辑上相互依赖的操作才需要彼此排序
- 已提交读取的一致性是指任何已提交的操作都可在系统中继续读取 可重复读取是指在一个事务中，多次读取相同的值总会得到相同的结果 读写一致性是指您完成的任何写入操作都必须能被随后的同一客户端读取 最终一致性（Eventual Consistency）是一种特殊的一致性测量方法，它表示系统可以不一致，只要最终能再次保持一致。因果一致性就是最终一致性的一个例子。 强最终一致性与最终一致性类似，但要求并发更新之间不能发生冲突。这通常是 CRDT 的特点。