《分布式系统：为了乐趣和利益》是一本广受欢迎的资源，用于理解和学习分布式系统。该书由作者 Mikito Takada 撰写，介绍了构建分布式系统的基本概念、原则和挑战。

这本书涵盖了与分布式系统相关的广泛主题，包括网络、容错性、一致性模型、分布式算法、可扩展性等等。它旨在以清晰易懂的方式解释复杂的概念，适合初学者和有经验的分布式系统从业者阅读。

在整本书中，作者提供了各种实际案例和案例研究，以说明分布式系统的实际应用和实践方面。它还强调了构建分布式系统涉及的权衡和设计考虑，帮助读者全面理解这个主题。

《分布式系统：为了乐趣和利益》作为开源资源，可以免费在线获取，非常适合任何对学习分布式系统感兴趣的人。

原文链接：Distributed systems: for fun and profit

2. 抽象层次的上下

在本章中，我们将在抽象层次之间穿梭，探讨一些不可能性结果（CAP 和 FLP），然后出于性能考虑回归到更低层次。

如果你有进行过编程，抽象层次的概念可能对你来说很熟悉。你总是在某个抽象层次上进行工作，通过某个 API 与较低层次的接口进行交互，并可能为用户提供一些更高层次的 API 或用户界面。计算机网络的七层 OSI 模型就是一个很好的例子。

分布式编程很大程度上涉及处理分布的后果（显而易见！）。也就是说，我们面临着现实中存在许多节点的现实和我们希望系统“像一个单一系统一样工作”的愿望之间存在着紧张关系。这意味着需要找到一个良好的抽象，平衡可能性、可理解性和性能。

当我们说 X 比 Y 更抽象时，我们是指 X 没有引入任何与 Y 根本不同的新内容。事实上，X 可能会去除 Y 的某些方面或以更易于处理的方式呈现它们。其次，X 在某种意义上比 Y 更容易理解，假设 X 从 Y 中去除的内容对于当前问题并不重要。

如尼采所写：

每个概念都是通过我们将不相等的事物等同起来形成的。没有一片叶子完全等同于另一片叶子，概念“叶子”是通过对这些个体差异进行任意抽象而形成的，通过遗忘区别；现在它产生了一个想法，即在自然界中可能存在除了叶子之外的东西，这些东西将是“叶子”的一种原始形式 - 所有叶子都已经被编织、标记、复制、着色、卷曲和绘制，但是由于技术不熟练，没有一份副本能够成为原始形式的正确、可靠和忠实的图像。

抽象本质上是虚构的。每种情况都是独特的，每个节点也是如此。但是抽象使得世界变得可管理：简化的问题陈述 - 不受现实约束 - 更易于分析，并且只要我们没有忽略任何重要的东西，解决方案就是广泛适用的。

事实上，如果我们保留下来的东西是重要的，那么我们可以得出的结果就会具有广泛的适用性。这就是为什么不可能性结果如此重要：它们采用了问题的最简单可能的表述，并证明在一些约束或假设条件下无法解决该问题。

所有的抽象都会忽略一些与现实独特的东西，以便将它们等同起来。关键是要摆脱一切非必要的东西。你如何知道什么是必要的？嗯，你可能事先不知道。

每次我们在系统规范中排除系统的某个方面时，我们都存在引入错误和/或性能问题的风险。这就是为什么有时我们需要朝着相反的方向前进，并有选择性地引入一些真实硬件和现实世界问题的方面。重新引入一些特定的硬件特性（例如物理顺序性）或其他物理特性可能足以获得足够好的性能的系统。

系统模型

在分布式系统中，分布是一个关键特性。具体而言，分布式系统中的程序具有以下特点：

  • 在独立节点上并发运行…
  • 通过可能引入非确定性和消息丢失的网络连接…
  • 没有共享内存或共享时钟。

这有许多含义：

  • 每个节点并发执行程序。
  • 知识是局部的：节点仅能快速访问本地状态，对于全局状态的任何信息都可能过时。
  • 节点可以独立发生故障并进行恢复。
  • 消息可能会延迟或丢失（与节点故障无关；很难区分网络故障和节点故障）。
  • 而且节点之间的时钟不同步（本地时间戳与全局实际时间顺序不对应，很难观察到）。

系统模型列举了与特定系统设计相关的许多假设。

系统模型是关于实现分布式系统的环境和设施的一组假设。

系统模型在其对环境和设施的假设方面存在差异。这些假设包括：

  • 节点的能力和故障方式
  • 通信链路的操作方式以及可能的故障方式
  • 整个系统的属性，例如有关时间和顺序的假设

健壮的系统模型是对假设最弱的模型：针对这种系统编写的任何算法都对不同的环境非常容忍，因为它有非常少且非常弱的假设。

另一方面，我们可以通过进行强假设来创建一个易于推理的系统模型。例如，假设节点不会发生故障意味着我们的算法不需要处理节点故障。然而，这样的系统模型是不现实的，因此在实践中很难应用。

让我们更详细地看一下节点、链路、时间和顺序的属性。

我们系统模型中的节点

节点作为计算和存储的主机。它们具有以下特点：

  • 能够执行程序。
  • 能够将数据存储到易失性内存（在故障时可能丢失）和稳定状态（在故障后可以读取）。
  • 时钟（可以被假设为准确或不准确）。

节点执行确定性算法：局部计算、计算后的本地状态和发送的消息是根据接收到的消息和接收消息时的本地状态唯一确定的。

有许多可能的故障模型描述了节点可能发生的故障方式。在实践中，大多数系统假设使用崩溃恢复故障模型：也就是说，节点只能通过崩溃来发生故障，并且可以在稍后某个时间点（可能）进行恢复。

另一种选择是假设节点可以以任意方式发生故障。这被称为拜占庭容错。拜占庭故障在实际的商业系统中很少处理，因为对任意故障具有弹性的算法运行成本更高，实现更复杂。在这里我不会讨论拜占庭容错。

我们系统模型中的通信链路

通信链接将各个节点彼此连接，并允许消息在任意方向上发送。许多讨论分布式算法的书籍假设每对节点之间都有独立的链接，这些链接为消息提供了先进先出（FIFO）的顺序，只能传递已发送的消息，并且已发送的消息可能会丢失。

某些算法假设网络是可靠的：消息永远不会丢失，也不会无限期地延迟。这在某些实际情况下可能是合理的假设，但一般来说，更倾向于将网络视为不可靠的，可能会发生消息丢失和延迟的情况。

当网络发生故障而节点本身仍可运行时，就会发生网络分区。在这种情况下，消息可能会丢失或延迟，直到网络分区被修复。分区的节点可能对某些客户端是可访问的，因此必须与崩溃的节点进行不同处理。下图说明了节点故障和网络分区的区别：

replication

通常很少对通信链接做进一步的假设。我们可以假设链接只能单向工作，或者可以为不同的链接引入不同的通信成本（例如由于物理距离引起的延迟）。然而，在商业环境中，除了长距离链接（广域网延迟）之外，这些很少是关注的问题，因此我在这里不会讨论它们；成本和拓扑的更详细模型可以在复杂性的代价下实现更好的优化。

时间/顺序假设

物理分布的一个结果是每个节点以独特的方式体验世界。这是无法避免的，因为信息只能以光速传播。如果节点之间的距离不同，那么从一个节点发送到其他节点的任何消息都会在其他节点以不同的时间到达，并有可能以不同的顺序到达。

时间假设是捕捉我们在多大程度上考虑这个现实的便捷方式。主要的两种选择是：

  • 同步系统模型。进程以同步方式执行；消息传输延迟有已知的上界；每个进程具有准确的时钟。
  • 异步系统模型。没有时间假设 - 例如进程以独立的速率执行；消息传输延迟没有上界；没有可靠的时钟存在。

同步系统模型对时间和顺序施加了许多限制。它基本上假设节点有相同的体验：发送的消息总是在特定的最大传输延迟内接收，并且进程以同步方式执行。这很方便，因为它允许您作为系统设计者对时间和顺序做出假设，而异步系统模型则不允许。

异步性是一种非假设：它只是假设您不能依赖于时间（或“时间传感器”）。

在同步系统模型中解决问题更容易，因为对执行速度、最大消息传输延迟和时钟准确性的假设有助于解决问题，您可以根据这些假设进行推断，并假设不方便的故障场景从不发生。

当然，假设同步系统模型并不特别现实。现实世界的网络会出现故障，并且消息延迟没有固定的上限。现实世界的系统最多是部分同步的：它们可能会偶尔正确工作并提供一些上限，但也会有消息无限期延迟和时钟不同步的时候。我在这里不会详细讨论同步系统的算法，但您可能会在许多其他入门书籍中遇到它们，因为它们在分析上更容易（但不现实）。

共识问题

在接下来的文本中，我们将改变系统模型的参数。接下来，我们将探讨两个系统属性的变化对系统设计选择的影响：

  1. 是否将网络分区包含在故障模型中。
  2. 同步与异步的时间假设。

我们将通过讨论两个不可能性结果（FLP 和 CAP）来说明这些影响。

当然，为了进行讨论，我们还需要引入一个需要解决的问题。我将讨论的问题是共识问题。

如果多台计算机（或节点）达成共识，则它们都同意某个值。更正式地说：

  1. 一致性：每个正确的进程必须就同一个值达成一致。
  2. 完整性：每个正确的进程最多决定一个值，如果它决定了某个值，则该值必须由某个进程提议。
  3. 终止性：所有进程最终都会达成决策。
  4. 有效性：如果所有正确的进程提议相同的值 V，则所有正确的进程决定的值必须为 V。

共识问题是许多商业分布式系统的核心。毕竟，我们希望在不必处理分布的后果（例如节点之间的分歧/偏离）的情况下获得分布式系统的可靠性和性能，而解决共识问题使得解决一些相关的更高级问题成为可能，例如原子广播和原子提交。

两个不可能的结果

第一个不可能性结果是 FLP 不可能性结果，它是一个与设计分布式算法相关的不可能性结果，对分布式算法设计者尤为重要。第二个结果是 CAP 定理，它是一个相关的结果，更与实践者相关，即需要在不同系统设计之间进行选择但不直接涉及算法设计的人。

FLP 不可能结果

FLP 不可能性结果（以其作者 Fischer、Lynch 和 Patterson 命名）只做简要概述，尽管在学术界被认为更为重要。FLP 不可能性结果考察了异步系统模型下的共识问题（严格来说是协议问题，它是共识问题的一种非常弱的形式）。假设节点只能通过崩溃来失败，网络是可靠的，并且异步系统模型的典型时序假设成立，例如消息延迟没有上界。

在这些假设下，FLP 结果表明：“在一个异步系统中，不存在解决共识问题的（确定性）算法，即使消息永远不会丢失，最多只有一个进程可能失败，并且只能通过崩溃（停止执行）来失败。”

这个结果意味着在一个非常简化的系统模型下，没有办法解决共识问题，而且解决方案可能被无限延迟。论证是，如果这样的算法存在，那么可以设计一种执行该算法的方式，其中通过延迟消息传递，它将保持未决状态（“bivalent”）的时间可以是任意长的，而这在异步系统模型中是允许的。因此，这样的算法是不可能存在的。

这个不可能性结果很重要，因为它强调了在异步系统模型下的一个权衡：解决共识问题的算法必须在消息传递的界限不满足时放弃安全性或活性。

这个洞察对于设计算法的人们特别重要，因为它对我们所知道的在异步系统模型中可解决的问题施加了严格限制。CAP 定理是一个相关的定理，对从业者更为相关：它做出稍微不同的假设（网络故障而不是节点故障），并对从业者在系统设计之间的选择有更明确的影响。

CAP 定理

CAP 定理最初是由计算机科学家 Eric Brewer 提出的一个猜想。它是一种流行且相当有用的思考系统设计中所作出的保证之间权衡的方式。实际上，它还被 Gilbert 和 Lynch 进行了形式化证明，并且与某个特定讨论站点认为的不同，Nathan Marz 并没有揭穿它。

该定理指出，在以下三个属性中：

  • 一致性（Consistency）：所有节点在同一时间看到相同的数据。
  • 可用性（Availability）：节点故障不会阻止存活节点继续运行。
  • 分区容忍性（Partition tolerance）：尽管由于网络和/或节点故障导致消息丢失，系统仍然可以继续运行。

只能同时满足其中两个属性。我们甚至可以将其绘制为一个漂亮的图表，从三个属性中选择两个，可以得到对应于不同交叉点的三种不同类型的系统：

CAP theorem

请注意，该定理指出中间部分（同时具有三个属性）是不可实现的。然后我们可以得到三种不同的系统类型：

  • CA（一致性 + 可用性）。例如，完全严格的法定人数协议，如两阶段提交协议。
  • CP（一致性 + 分区容忍性）。例如，多数法定人数协议，在这种协议中，少数分区是不可用的，比如 Paxos 协议。
  • AP（可用性 + 分区容忍性）。例如，使用冲突解决的协议，如 Dynamo 协议。

CA 和 CP 系统设计都提供相同的一致性模型：强一致性。唯一的区别在于，CA 系统无法容忍任何节点故障；CP 系统可以容忍在非拜占庭故障模型中给定 2f+1 个节点的情况下最多 f 个故障（换句话说，只要多数 f+1 个节点保持运行，它就可以容忍少数 f 个节点的故障）。原因很简单：

  • CA 系统不区分节点故障和网络故障，因此必须停止在任何地方接受写操作，以避免引入分歧（多个副本）。它无法判断远程节点是停机还是仅仅是网络连接断开：因此，唯一安全的做法是停止接受写操作。
  • CP 系统通过对分区的两侧施加不对称行为来防止分歧（例如保持单一副本一致性）。它只保留多数分区，并要求少数分区不可用（例如停止接受写操作），这保持了一定程度的可用性（多数分区）并确保了单一副本一致性。

我将在后面关于复制的章节中详细讨论这个问题，当我讨论 Paxos 时会更详细地讨论。重要的是，CP 系统将网络分区纳入其故障模型，并使用像 Paxos、Raft 或 viewstamped replication 这样的算法区分多数分区和少数分区。CA 系统不具备分区感知能力，并且在历史上更常见：它们通常使用两阶段提交算法，在传统的分布式关系数据库中很常见。

假设发生分区，该定理就会简化为可用性和一致性之间的二选一。

Based on http://blog.mikiobraun.de/2013/03/misconceptions-about-cap-theorem.html

首先，早期分布式关系数据库系统中使用的许多系统设计没有考虑到分区容忍性（例如，它们是 CA 设计）。在现代系统中，分区容忍性是一个重要的属性，因为如果系统在地理上分布（正如许多大型系统所做的那样），网络分区变得更加常见。

其次，在网络分区期间，强一致性和高可用性之间存在紧张关系。CAP 定理说明了在强一致性保证和分布式计算之间的权衡。

从某种意义上说，承诺一个由不可预测网络连接的独立节点组成的分布式系统“行为与非分布式系统不可区分”是相当困难的。

我将在稍后关于复制的章节中详细讨论这个问题，当我讨论 Paxos 时会更详细地讨论。重要的是，CP 系统将网络分区纳入其故障模型，并使用像 Paxos、Raft 或 viewstamped replication 这样的算法区分多数分区和少数分区。CA 系统不具备分区感知能力，并且在历史上更常见：它们通常使用两阶段提交算法，在传统的分布式关系数据库中很常见。

假设发生分区，该定理就会简化为可用性和一致性之间的二选一。

请注意，CAP 定理实际上提供了四个结论。这些结论强调了在分布式系统中的权衡和挑战，并提醒系统设计人员需要根据应用程序的需求做出合适的选择。

From the Simpsons episode Trash of the Titans

强一致性保证要求在分区期间放弃可用性。这是因为在两个无法互相通信的副本之间继续接受写操作时，无法防止它们发生差异。

如何解决这个问题？可以通过加强假设（假设没有分区）或降低保证来解决。一致性可以与可用性（以及与离线可访问性和低延迟相关的功能）进行权衡。如果将"一致性"定义为"所有节点同时看到相同的数据"的要求之下，那么我们可以同时实现可用性和某种（较弱的）一致性保证。

第三，强一致性和性能在正常操作中存在紧张关系。

强一致性/单副本一致性要求节点在每个操作上进行通信和达成一致。这导致在正常操作期间出现高延迟。

如果你可以接受除经典一致性模型之外的一致性模型，即允许副本滞后或发生差异，那么你可以在正常操作期间降低延迟，并在分区的情况下保持可用性。

当涉及的消息和节点较少时，操作可以更快地完成。但唯一的方法是放松保证：让一些节点更少地被访问，这意味着节点可能包含旧数据。

这也可能导致异常情况的发生。你不能再保证获得最新的值。根据所做的保证类型，你可能读取到比预期更旧的值，甚至可能丢失一些更新。

第四，并且间接地，如果我们不想在网络分区期间放弃可用性，那么我们需要探索除强一致性之外的其他一致性模型是否适用于我们的目的。

例如，即使用户数据在多个数据中心进行了地理复制，而这两个数据中心之间的连接暂时中断，在许多情况下我们仍然希望允许用户使用网站/服务。这意味着稍后需要协调两个不同的数据集，这既是技术上的挑战，也是业务风险。但通常情况下，技术挑战和业务风险是可以管理的，因此提供高可用性更可取。

一致性和可用性并不是二元选择，除非你将自己限制在强一致性上。但强一致性只是一种一致性模型：在这种模型中，为了防止数据的多个副本同时活跃，你必须放弃可用性。正如Brewer 本人指出的那样，“3 选 2”解释是误导性的。

如果你从这次讨论中只得到一个观点，那就是"一致性"不是一个单一、明确的属性。请记住：

ACID consistency != CAP consistency != Oatmeal consistency

相反，一致性模型是数据存储为使用它的程序提供的任何保证。

一致性模型是程序员和系统之间的契约，系统保证如果程序员遵循一些特定规则，对数据存储的操作结果将是可预测的。

CAP 中的"C"代表"强一致性"，但"一致性"并不等同于"强一致性"。

让我们来看一些替代的一致性模型。

强一致性与其他一致性模型

一致性模型可以分为两类：强一致性模型和弱一致性模型：

  • 强一致性模型（能够维护单个副本）

    • 线性一致性（Linearizable consistency）
    • 顺序一致性（Sequential consistency）

  • 弱一致性模型（不是强一致性）

    • 以客户端为中心的一致性模型（Client-centric consistency models）
    • 因果一致性（Causal consistency）：最强的一致性模型
    • 最终一致性模型（Eventual consistency models）

强一致性模型保证了更新的表面顺序和可见性与非复制系统等效。而弱一致性模型则不提供这样的保证。

请注意，这并不是一个详尽无遗的列表。再次强调，一致性模型只是程序员和系统之间的任意契约，因此可以是几乎任何形式。

强一致性模型

强一致性模型进一步可以分为两种相似但稍有不同的一致性模型：

  • 线性一致性（Linearizable consistency）：在线性一致性下，所有操作似乎以与全局实时操作顺序一致的顺序原子地执行。（Herlihy 和 Wing，1991 年）
  • 顺序一致性（Sequential consistency）：在顺序一致性下，所有操作似乎以某个与各个节点所见的顺序一致且在所有节点上相等的顺序原子地执行。（Lamport，1979 年）

关键的区别在于，线性一致性要求操作产生效果的顺序与实际实时操作顺序相等。而顺序一致性允许对操作进行重新排序，只要在每个节点上观察到的顺序保持一致即可。只有当能够观察到系统中所有的输入和时间时，才能区分这两种模型；从客户端与节点交互的角度来看，两者是等价的。

这种差异似乎微不足道，但值得注意的是，顺序一致性不具备组合性。

强一致性模型允许程序员将单个服务器替换为分布式节点集群，而不会遇到任何问题。

与保证强一致性的系统相比，所有其他一致性模型都存在异常行为，因为它们的行为与非复制系统有所区别。但通常这些异常行为是可以接受的，要么是因为我们不关心偶尔出现的问题，要么是因为我们编写了能够处理发生一致性问题的代码。

值得注意的是，对于弱一致性模型，实际上没有普遍适用的分类方法，因为“不是强一致性模型”（例如“在某种程度上与非复制系统有所区别”）可以是几乎任何形式。

以客户为中心的一致性模型

以客户端为中心的一致性模型是一种涉及客户端或会话概念的一致性模型。例如，以客户端为中心的一致性模型可能保证客户端永远不会看到数据项的旧版本。通常，这是通过在客户端库中构建额外的缓存来实现的，因此，如果客户端切换到包含旧数据的副本节点，客户端库会返回其缓存的值，而不是副本中的旧值。

如果客户端所在的副本节点不包含最新版本的数据，客户端仍然可能看到旧版本的数据，但它们永远不会看到旧值重新出现的异常情况（例如，因为它们连接到了不同的副本）。请注意，有许多以客户端为中心的一致性模型存在。

最终一致性

最终一致性模型表示，如果停止更改值，那么在一段不确定的时间后，所有副本将达成相同的值。这意味着在此之前，副本之间的结果以某种不确定的方式不一致。由于它是平凡可满足的（仅具备活性属性），如果没有补充信息，它就是没有用处的。

仅仅说某个东西是最终一致性的，就像说“人最终会死亡”一样。这是一个非常弱的约束条件，我们可能希望对两个方面进行更具体的描述：

首先，“最终"是多久的时间？有一个严格的下限或者至少对系统收敛到相同值通常需要多长时间的一些概念将是有用的。

其次，副本如何达成一致的值？一个始终返回"42"的系统是最终一致性的：所有副本都同意相同的值。但它不会收敛到一个有用的值，因为它只会持续返回相同的固定值。相反，我们希望对方法有更好的理解。例如，一种决策方法是始终选择具有最大时间戳的值。

因此，当供应商提到"最终一致性"时，他们指的是一些更具体的术语，例如"最终谁写入的优先，同时读取最新观察到的值"的一致性。“如何？“很重要，因为糟糕的方法可能导致写入丢失，例如如果一个节点上的时钟设置不正确并且使用时间戳。

我将在弱一致性模型的复制方法章节中更详细地研究这两个问题。

Further reading 进一步阅读