分布式系统阅读清单


计算机科学家在研究分布式系统理论时使用三种模型类型：

  1. 同步模型
  2. 半同步模型
  3. 异步模型

同步模型意味着系统内发送的每条信息都有一个已知的通信上限（发送和接收信息之间的最大延迟）以及节点或代理之间的处理速度。这意味着你可以确定在一段时间后，一条信息被错过了。这种模式适用于极少数情况，如硬件信号，主要是分布式系统证明的初学者模式。

异步模式意味着没有上限。代理和节点无限期地处理和延迟事情是合法的。你永远无法假设，一条你在过去 15 年中都没有看到的 "丢失 "信息不会恰好在明天送达。另一个节点也可能陷入一个持续 500 个世纪的 GC 循环，这很好。

在异步模型上证明某样东西是有效的，就意味着它在所有其他类型上也是有效的。这是证明的专家模式，在大多数情况下比现实世界的实现更难。

半同步模型是真实世界的欺骗模式。通信机制和节点的上限无处不在，但它们往往是可配置的，也是未指定的。这就使得协议设计者可以说："你知道吗，我们要在其中插入一条 ping 消息，如果你错过了太多的 ping 消息，我们就认为你死了"。

故障模式
故障发生和检测的方式对于许多算法都很重要。以下是最常用的：

  1. 故障停止
  2. 崩溃故障
  3. 遗漏故障
  4. 性能故障
  5. 拜占庭式的失败

首先，"故障停止 "意味着如果节点出现问题，每个人都能知道并检测到它，并能从稳定的存储中恢复状态。这在理论和协议上都是简单的模式，但在实践中却很难实现（在某些情况下甚至是不可能的）

崩溃故障意味着，如果节点或代理出现问题，它就会崩溃，然后再也不会回来。你要么永远正确，要么永远迟到。这在理论上比故障停止更容易设计（但操作起来非常麻烦，因为冗余是游戏的名字，永远都是）。

遗漏故障意味着你必须给出符合协议的正确结果，否则就永远无法回答。

性能故障则假定，在发送信息内容方面遵守协议的同时，也有可能延迟发送结果。

拜占庭故障意味着任何事情都可能出错（包括有人故意用坏软件冒充好软件来破坏协议）。有一类特殊的可检测认证的拜占庭故障，它至少会限制你不能伪造来自其他节点的其他信息，但这只是可选项。拜占庭模式是最糟糕的。

在默认情况下，大多数分布式系统理论都假定不存在腐败和故意破坏的坏人或代理，而由区块链和某些形式的包管理来解决混乱的故障。

大多数现代论文和文章都试图坚持使用崩溃或故障停止故障，因为它们往往是实用的。

共识
这是分布式系统的核心问题之一：系统中的所有节点或代理如何就一个值达成一致？它之所以如此重要，是因为如果能就一个值达成一致，就能做很多事情。

选择一个非常有用的值，最常见的例子就是选出一个执行决策的领导者的名字，这样你就不用再建立更多的共识了，因为共识太痛苦了。

关于什么是共识，存在各种说法，包括每个人都完全同意？(强）还是只是多数？(t-resilient），以及在各种同步或失败模型中提出同样的问题。

需要注意的是，虽然像 Paxos 这样的经典协议会使用领导者来确保一致性，并在保持一致的同时加快执行速度，但很多系统都会放弃这些要求。

FLP 结果
代表费舍尔-林奇-帕特森（Fischer-Lynch-Patterson），他们是 1985 年一篇论文的作者，该论文指出，在纯粹的异步模型中，只要有可能出现任何形式的故障，哪怕只是延迟，所有参与者都同意某个值的正确共识是无法解决的（尽管在同步模型中是可以解决的）。

这篇论文是该领域最有影响力的论文之一，因为它引发了其他学者的大量工作，以确定分布式系统中到底发生了什么。

细节阅读

故障检测
FLP 的研究结果表明，故障检测对于事物的运行具有超级关键的作用，在此之后，许多计算机科学人员开始研究故障检测的确切含义。

这项工作很难，而且往往没有我们希望的那么令人印象深刻。故障检测器有强检测器和弱检测器之分。前者意味着所有有故障的进程最终都会被所有无故障的进程识别出来，而后者则意味着只有一些无故障的进程才能发现有故障的进程。

然后是准确度：

  • 没有崩溃的进程不会被怀疑崩溃
  • 有可能根本就没有怀疑过非故障进程
  • 你可能会因为混乱而感到困惑，但在某些时候，非故障进程不再被怀疑为坏进程
  • 在某些时候，至少有一个非故障进程不会被怀疑

你可能会意识到，一个强大且完全准确的检测器（可以说是完美的）意味着你会得到一个共识，而既然在一个完全异步的系统模型中，共识是不可能真正实现的，那么你能可靠检测到的东西就有了硬性的限制。

这往往就是半同步系统模型的意义所在：如果将大于 T 的延迟视为故障，那么就可以开始进行充分的故障检测。

See this slide deck for a decent intro

CAP 定理
CAP 定理在很长一段时间内都只是一个猜想，但在 2000 年代初得到了证明，从而产生了许多最终一致的数据库。

分布式系统有三个特性：

  • 一致性：每次向系统写入并从系统中读取时，都会得到写入的值或更新值。
  • 可用性：每次请求都会得到响应（包括读取和写入）
  • 分区容忍性：网络可能会丢失信息

从理论上讲，你可以得到一个既可用又一致的系统，但这只适用于完美网络上的同步模型。这种情况并不存在，因此在实际应用中，P 总是存在的。

CAP 定理的基本原理是，在给定 P 的情况下，你必须选择 A（继续接受写入并可能损坏数据）或 C（停止接受写入以保存数据，并宕机）。

改进
CAP 在实际应用中比较严格。网络中并非所有分区都等同，也并非所有一致性级别都相同。

为 CAP 定理增加灵活性的两种最常见方法是产量/收获模型和 PACELC。

产量/收成模型（Yield/Harvest）本质上是说，你可以用不同的方式来看待系统：产量Yield是指你满足请求的能力（如正常运行时间），收成Harvest是指你实际能返回的所有潜在数据的比例。搜索引擎就是一个常见的例子，当搜索引擎忽略某些搜索结果以更快地做出响应时，就会通过减少收获量来提高产量并更频繁地做出响应。

PACELC 还认为，最终一致性数据库过于严格。在网络分区的情况下，您必须在可用性和一致性之间做出选择，但在其他情况下--当系统正常运行时--您必须在延迟和一致性之间做出选择。我们的想法是，你可以决定为了可用性而降低一致性（但只有在真正需要时才这样做），也可以决定始终放弃一致性，因为你必须快速运行。

需要注意的是，你不可能超越 CAP 定理（只要你尊重证明该定理的模型），任何声称能做到这一点的人通常都是蛇蝎心肠的推销员。

Resources

多年来，关于 CAP 定理和各种讨论的重述不计其数；尽管许多人一直试图提出这些结果非常可靠，无关紧要的论点，但这些结果在数学上已经得到了证明。

信息传递定义
信息可以按不同顺序发送零次或多次。下面介绍一些术语来定义它们：

  • 单播是指信息只发送给一个实体
  • 任播（anycast）是指向任何有效实体发送信息
  • 广播是指将信息发送给所有有效实体
  • 原子广播（atomic broadcast）或总顺序广播（total order broadcast）是指系统中的所有非故障行为体都以相同的顺序接收相同的信息，无论该顺序是什么
  • 流言（gossip）是指在对等体之间转发信息，希望最终每个人都能收到所有信息的协议系列。
  • 至少传递一次是指每条信息将被传递一次或多次；监听者希望看到所有信息，但可能不止一次
  • 最多发送一次是指每个发送者只发送一次信息。监听者有可能永远看不到。
  • 完全一次发送是指每条信息保证只被发送和看到一次。这是一个很好的理论目标，但在实际系统中是不可能实现的。最终只能通过其他方法来模拟（例如，将原子广播与特定标志和排序保证结合起来）

关于顺序：

  • 总排序是指所有信息只有一种严格的排序和比较方式，就像 3 总是大于 2 一样。
  • 部分排序意味着某些信息可以与某些信息进行比较，但不一定是所有信息。例如，我可以决定，对密钥 k1 的所有更新可以相互之间有一个总顺序，但独立于对密钥 k2 的更新。因此，在所有密钥的所有更新之间存在部分顺序，因为 k1 的更新与 k2 的更新没有任何信息关联。
  • 因果顺序指的是，所有依赖于其他信息的信息都是在这些信息之后收到的（你不可能在了解一个用户之前就知道他的头像）。它是部分顺序的一种特殊类型。

没有 "最佳 "排序，每种排序都提供了不同的可能性，并伴随着不同的成本、优化和相关故障模式。

幂等性
幂等性非常重要，需要有自己的条目。闲置意味着，当信息被多次查看、重发或重放时，它们对系统的影响不会与只发送一次时有什么不同。

常见的策略是让每条信息都能引用以前看过的信息，这样就可以定义一个排序来防止重播旧信息，设置唯一的 ID（如事务 ID）和一个存储空间来防止重播事务，等等。

 Idempotence is not a medical condition 

状态机复制
这是一个理论模型，根据该模型，如果给定相同的状态序列并对其进行相同的操作（不考虑各种非确定性），所有状态机最终都会得到相同的结果。

这个模型对于大多数可靠的系统都至关重要，因为这些系统都会尝试以相同的顺序向所有子系统重放所有事件，从而确保所有地方的数据集都是可预测的。

这通常是通过选择一个领导者来实现的；所有的写入都通过领导者完成，所有的跟随者都会得到系统的一致复制状态，使他们最终成为领导者，或将自己的状态扇形扩展到其他参与者。

基于状态的复制
基于状态的复制在概念上可能比状态机复制更简单，其理念是，如果只复制状态，最终就能得到状态！

问题是，要做到快速高效非常困难。如果你的状态有几兆兆字节那么大，你可不想每次操作都要重新发送。常见的方法包括对数据进行拆分、散列和分块，以检测变化并只发送变化的部分（想想 rsync）；用梅克尔树merkle trees 来检测变化；或者对源代码打补丁。

实用事项
这里有许多关于各种系统设计元素的资源值得挖掘。

系统设计中的端到端论证

分布式系统的系统设计基础实践方面：

  • 发送出去的信息不一定会被另一方收到
  • 另一方收到的信息不一定是另一方真正读取的信息
  • 另一方读取的信息不一定是另一方已经执行的信息

结论是，如果你希望任何信息都是可靠的，你就需要端到端确认，通常由应用层编写。

这些想法是 TCP 协议设计的基础，但作者也指出，仅仅停留在协议层面是不够的，还必须有应用层的参与。

分布式计算的谬误
这些谬误是

  • 网络是可靠的
  • 延迟为零
  • 带宽是无限的
  • 网络是安全的
  • 拓扑结构不会改变
  • 只有一个管理员
  • 传输成本为零
  • 网络是同质的

完整解释： the paper.

常见的实际故障模式
在实践中，当你从计算机科学转向工程学时，你会发现故障类型更加多样化，但也可以映射到任何理论模型。

本节非正式地列出了系统中常见的问题源。有关其他常见情况，请参阅 CAP 定理清单：the CAP theorem checklist 

网络分裂
有些节点可以互相通话，但有些节点却无法与其他节点联系。一个常见的例子是，基于美国的网络可以在内部正常通信，基于欧盟的网络也可以，但两者都无法互相通话

非对称网络分裂
节点组之间的通信是不对称的。例如，假设美国网络可以向欧盟网络发送信息，但欧盟网络却无法作出回应。

这种情况在使用 TCP 时比较少见（尽管以前也发生过），而在使用 UDP 时则可能很常见。

脑裂
许多系统处理故障的方法是保持多数系统继续运行。当网络分裂的双方都认为自己是领导者，并开始做出相互冲突的决定时，就会出现分裂脑。

超时
超时尤其棘手，因为它们是非确定性的。它们只能从一端观察到，而且你永远不知道最终被解释为失败的超时是否真的是失败，或者只是由于网络、硬件或 GC 暂停造成的延迟。

有时，如果信息已被看到，重传就不安全了（即它不是幂等的），而超时基本上使人无法知道重传是否安全：信息是否已被执行、丢弃，还是仍在传输中或在某个缓冲区中？

排序导致的报文丢失
一般情况下，使用 TCP 和碰撞往往意味着很少有报文在系统间丢失，但经常出现的情况包括

  • 节点宕机（或软件崩溃）几秒钟，在此期间错过了一条不会重复的信息
  • 在不同节点之间临时接收更新。例如，服务 A 在总线（无论是 Kafka 还是 RMQ）上发布的消息最终可能被服务 B 读取、转换或执行并重新发布，而服务 C 有可能先于 A 读取 B 的更新，从而造成因果关系问题。

时钟漂移
并非所有系统上的所有时钟都能正确同步（即使使用 NTP），而且同步速度也会不同。

使用时间戳对事件进行排序几乎肯定会产生错误，如果时间戳来自多台计算机，错误就会更多。

客户端是系统的一部分
一个非常常见的误区是忘记了参与分布式系统的客户端也是系统的一部分。如果客户端无法理解其接收到的事件或数据，服务器端的一致性就不一定有多大价值。

对于数据库客户端来说，这一点尤其隐蔽，因为它们在进行非瞬时事务处理时会超时，而且无法知道是否可以再次尝试。

从多个备份恢复
单个备份很容易处理。多重备份会遇到一个问题，即一致切割（高级视图）和分布式快照，这意味着并非所有备份都是在同一时间进行的，这会带来不一致性，可被视为数据损坏。

好在没有很好的解决办法，每个人都会遭受同样的痛苦。

一致性模型
有几十种不同级别的一致性，维基百科、彼得-贝利斯（Peter Bailis）的相关论文或凯尔-金斯伯里（Kyle Kingsbury）的相关文章都对它们进行了概述

线性化是指每个操作都是原子性的，不会受到其他操作的影响，就好像所有操作都是一次运行一个一样。顺序是已知的、确定的，在某个写入开始后开始的读取将能看到该数据。

  • 串行化意味着，虽然所有操作看起来都是原子操作，但并不保证这些操作会以何种顺序进行。这意味着某些操作可能在另一个操作之后开始，但在另一个操作之前完成，只要隔离维护得当，这并不是问题。
  • 顺序一致性是指，即使操作可能是不按顺序进行的，它们看起来也是按顺序进行的。
  • 因果一致性是指，只有在逻辑上相互依赖的操作才需要彼此排序
  • 已提交读取的一致性是指任何已提交的操作都可在系统中继续读取
  • 可重复读取是指在一个事务中，多次读取相同的值总会得到相同的结果
  • 读写一致性是指您完成的任何写入操作都必须能被随后的同一客户端读取
  • 最终一致性（Eventual Consistency）是一种特殊的一致性测量方法，它表示系统可以不一致，只要最终能再次保持一致。因果一致性就是最终一致性的一个例子。
  • 强最终一致性与最终一致性类似，但要求并发更新之间不能发生冲突。这通常是 CRDT 的特点。

需要注意的是，虽然这些定义具有明确的语义，学术界也倾向于尊重这些定义，但在业界各个项目或供应商的文档中，这些定义并没有被统一采用或得到尊重。

数据库事务作用域
默认情况下，大多数人都认为数据库事务是可线性化的，但它们往往不是，因为默认情况下线性化太慢了。

每个数据库可能有不同的语义，因此以下链接可能涵盖了最主要的语义。


请注意，虽然 PostgreSQL 文档可能是介绍该主题的最清晰、最易懂的文档，但不同的供应商会对相同的标准事务作用域赋予不同的含义。

逻辑时钟
这些数据结构可以在信息或状态转换之间创建总排序或部分排序。

最常见的有：

  • Lamport 时间戳，这只是一个计数器。它们可以在不被发现的情况下悄悄地粉碎冲突数据
  • 矢量时钟，每个节点包含一个计数器，在看到的每条消息上递增。他们可以检测数据和操作中的冲突。
  • 版本向量类似于向量时钟，但仅更改状态变化的计数器，而不是更改所有看到的事件
  • 点分版本向量是奇特的版本向量，允许跟踪客户端与服务器通信时感知到的冲突。
  • 间隔树时钟尝试通过需要更少的空间来存储特定于节点的信息并允许一种内置垃圾收集来解决其他时钟类型的问题。它还拥有有史以来最好的论文之一。

CRDT
CRDT 本质上是限制可以执行的操作的数据结构，以便它们永远不会发生冲突，无论它们以何种顺序完成或发生的并发程度如何。
可以将其视为关于某人如何编写永远不会出错但只留下数学知识的分布式 Redis 的规范。

这仍然是一个活跃的研究领域，无数的论文和变体不断涌现。

其他有趣的材料

将所有这些观点结合在一起的圣经是Martin Kleppmann 的《设计数据密集型应用程序》 。但请注意，我认识的每个绝对喜欢这本书的人都是通过阅读大量论文而在分布式系统方面拥有良好基础的人，并且非常感谢将所有这些都放在一个地方。我见过的大多数人在读书俱乐部中阅读这本书，目的是更好地了解分布式系统，但有时仍然发现它具有挑战性和令人困惑，并且受益于周围有人可以向他们提出问题以弥合一些差距。它仍然是我能想象到的所有东西都集中在一个地方的最清晰的来源。