bookstack
distributed system 分布式系统 复制

复制概述

复制问题是分布式系统中的许多问题之一。我选择专注于它，而不是其他问题，如领导者选举、故障检测、互斥、共识和全局快照，因为它通常是人们最感兴趣的部分。例如，平行数据库的一个区分方式是它们的复制特性。此外，复制为许多子问题提供了背景，例如领导者选举、故障检测、共识和原子广播。

复制是一个组通信问题。什么样的安排和通信模式能给我们带来所需的性能和可用性特征？我们如何确保在网络分区和同时节点故障的情况下实现容错、持久性和非分歧？

同样，有许多方法可以处理复制。这里我将采取的方法只是查看具有复制的系统可能的高层模式。以视觉方式查看有助于将讨论集中在整体模式上，而不是具体的消息传递上。我的目标是探索设计空间，而不是解释每个算法的具体细节。

让我们首先定义复制的样子。我们假设有一个初始数据库，客户端发出请求以更改数据库的状态。

然后，安排和通信模式可以分为几个阶段：

  1. （请求）客户端向服务器发送请求
  2. （同步）复制的同步部分发生
  3. （响应）响应返回给客户端
  4. （异步）复制的异步部分发生

这个模型大致基于this article。请注意，任务每个部分中交换的消息模式取决于具体的算法：我故意不讨论具体的算法。

鉴于这些阶段，我们可以创建什么样的通信模式？我们选择的模式对性能和可用性有什么影响？

同步复制

第一个模式是同步复制（也称为主动复制、急切复制、推送复制或悲观复制）。让我们画出它的样子：

在这里，我们可以看到三个不同的阶段：首先，客户端发送请求。接下来，我们称之为复制的同步部分发生。这个术语指的是客户端被阻塞——等待系统的回复。

在同步阶段，第一台服务器联系另外两台服务器，并等待从所有其他服务器接收到回复。最后，它向客户端发送响应，告知其结果（例如，成功或失败）。

这一切看起来都很简单。我们可以对这种特定的通信模式安排说些什么，而不讨论同步阶段算法的细节？首先，观察到这是一个N - of - N的写入方法：在返回响应之前，必须被系统中的每个服务器看到并确认。

从性能的角度来看，这意味着系统的速度将与其中最慢的服务器相同。由于它要求每个服务器在继续之前都要回复，因此系统对网络延迟的变化非常敏感。

鉴于N-of-N的方法，系统无法容忍任何服务器的丢失。当一台服务器丢失时，系统无法再写入所有节点，因此无法继续。它可能能够提供对数据的只读访问，但在此设计中，节点故障后不允许进行修改。

这种安排可以提供非常强的持久性保证：当响应返回时，客户端可以确定所有N台服务器都已接收、存储并确认了请求。为了丢失一个已接受的更新，所有N个副本都需要丢失，这几乎是你能提供的最佳保证。

异步复制

让我们将其与第二种模式进行对比——异步复制（也称为被动复制、拉取复制或懒惰复制）。正如你可能猜到的，这与同步复制相反：

在这里，主节点（/领导者/协调者）立即向客户端发送响应。它可能最多在本地存储更新，但不会进行任何重要的同步工作，客户端也不需要等待服务器之间进行更多轮的通信。

在稍后的某个阶段，复制任务的异步部分发生。在这里，主节点使用某种通信模式联系其他服务器，其他服务器更新其数据副本。具体细节取决于所使用的算法。

我们可以对这种特定的安排说些什么，而不深入算法的细节？好吧，这是一种写入1 - of - N的方法：响应立即返回，更新传播在稍后进行。

从性能的角度来看，这意味着系统速度很快：客户端不需要花费额外的时间等待系统内部完成工作。由于内部延迟的波动不会导致客户端额外等待，因此系统对网络延迟的容忍度更高。

这种安排只能提供弱的或概率性的持久性保证。如果没有出现问题，数据最终会复制到所有N台机器。然而，如果在此之前唯一包含数据的服务器丢失，数据将永久丢失。

鉴于1-of-N的方法，只要至少有一个节点在线，系统就可以保持可用（至少在理论上，尽管在实践中负载可能会过高）。像这样的纯懒惰方法不提供持久性或一致性保证；你可能被允许写入系统，但如果发生故障，则无法保证你能读取到你所写入的内容。

最后，值得注意的是，被动复制无法确保系统中的所有节点始终包含相同的状态。如果你在多个位置接受写入，并且不要求这些节点同步达成一致，那么你将面临分歧的风险：读取可能会从不同位置返回不同的结果（特别是在节点故障和恢复后），并且无法强制执行全局约束（需要与所有人通信）。

我并没有真正提到读取（而不是写入）期间的通信模式，因为读取的模式实际上是从写入的模式推导而来的：在读取期间，你希望联系尽可能少的节点。我们将在法定人数的上下文中进一步讨论这一点。

我们只讨论了两种基本安排，而没有涉及具体的算法。然而，我们已经能够推断出相当多的关于可能的通信模式以及它们的性能、持久性保证和可用性特征的信息。

主要复制方法概述

在讨论了两种基本的复制方法：同步复制和异步复制后，让我们看看主要的复制算法。

有许多不同的方法来对复制技术进行分类。我想介绍的第二个区别（在同步与异步之后）是：

  • 防止分歧的复制方法（单副本系统）和
  • 风险分歧的复制方法（多主系统）

第一组方法具有“像单一系统一样运行”的特性。特别是，当发生部分故障时，系统确保只有一个副本处于活动状态。此外，系统确保副本始终达成一致。这被称为共识问题。

如果多个进程（或计算机）对某个值达成一致，则它们实现了共识。更正式地说：

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

互斥、领导者选举、多播和原子广播都是更一般的共识问题的实例。维护单副本一致性的复制系统需要以某种方式解决共识问题。

维护单副本一致性的复制算法包括：

  • 1n 消息（异步主/备份）
  • 2n 消息（同步主/备份）
  • 4n 消息（两阶段提交，Multi-Paxos）
  • 6n 消息（三阶段提交，Paxos与重复领导者选举）

这些算法在容错性方面各不相同（例如，它们可以容忍的故障类型）。我简单地根据算法执行期间交换的消息数量对它们进行了分类，因为我认为尝试回答“通过增加消息交换我们得到了什么？”这个问题是有趣的。

下面的图表，改编自Ryan Barret在Google的内容，描述了不同选项的一些方面：

上图中的一致性、延迟、吞吐量、数据丢失和故障转移特性实际上可以追溯到两种不同的复制方法：同步复制（例如，等待响应）和异步复制。当你等待时，你会获得更差的性能，但更强的保证。我们在讨论分区（和延迟）容忍性时，将明显看到2PC和法定人数系统之间的吞吐量差异。

在该图中，强制执行弱（/最终）一致性的算法被归为一类（“八卦”）。然而，我将更详细地讨论弱一致性的复制方法——八卦和（部分）法定人数系统。“事务”行实际上更多地指的是全局谓词评估，而在弱一致性系统中不支持（尽管可以支持局部谓词评估）。

值得注意的是，强制执行弱一致性要求的系统具有较少的通用算法，而更多的技术可以选择性地应用。由于不强制单副本一致性的系统可以像由多个节点组成的分布式系统一样自由行动，因此需要修复的明显目标较少，重点更多地放在为人们提供一种推理他们所拥有的系统特性的方法上。

例如：

  • 客户端中心的一致性模型试图在允许分歧的同时提供更易理解的一致性保证。
  • CRDT（收敛和可交换的复制数据类型）利用某些状态和基于操作的数据类型的半格特性（结合性、交换性、幂等性）。
  • 合流分析（如Bloom语言中）利用关于计算单调性的的信息来最大限度地利用无序。
  • PBS（概率性有界过时性）使用模拟和从现实世界系统收集的信息来描述部分法定人数系统的预期行为。

我会在稍后进一步讨论这些内容，首先，让我们看看维护单副本一致性的复制算法。

主/备复制

主/备复制（也称为主副本复制、主从复制或日志传输）可能是最常用的复制方法，也是最基本的算法。所有更新都在主节点上执行，操作的日志（或替代的更改）通过网络传输到备份副本。有两种变体：

  • 异步主/备复制
  • 同步主/备复制

同步版本需要两条消息（“更新” + “确认接收”），而异步版本只需一条消息（“更新”）。

主/备复制非常常见。例如，默认情况下，MySQL复制使用异步变体。MongoDB也使用主/备复制（并有一些额外的故障转移程序）。所有操作都在一个主服务器上执行，该服务器将其序列化到本地日志中，然后异步复制到备份服务器。

正如我们在异步复制的上下文中讨论过的，任何异步复制算法只能提供弱的持久性保证。在MySQL复制中，这表现为复制延迟：异步备份总是至少落后于主节点一个操作。如果主节点发生故障，则尚未发送到备份的更新将丢失。

主/备复制的同步变体确保在返回客户端之前，写入操作已存储在其他节点上——代价是等待其他副本的响应。然而，值得注意的是，即使这个变体也只能提供弱保证。考虑以下简单的故障场景：

  • 主节点接收到写入并将其发送到备份
  • 备份持久化并确认写入
  • 然后主节点在向客户端发送确认之前发生故障

客户端现在假设提交失败，但备份已提交；如果备份被提升为主节点，则将是错误的。可能需要手动清理以调和失败的主节点或分歧的备份。

当然，我在这里简化了。虽然所有主/备复制算法遵循相同的一般消息模式，但它们在处理故障转移、备份长时间离线等方面有所不同。然而，在这种方案中，无法对主节点的不合时宜的故障保持弹性。

在基于日志传输/主/备的方案中，关键是它们只能提供最佳努力保证（例如，如果节点在不合时宜的时间发生故障，它们容易受到丢失更新或错误更新的影响）。此外，主/备方案容易受到“分脑”问题的影响，即由于临时网络问题导致故障转移到备份，并使主节点和备份同时处于活动状态。

为了防止不合时宜的故障导致一致性保证被违反，我们需要增加另一轮消息，这将引入两阶段提交协议（2PC）。

两阶段提交(2PC)

两阶段提交（2PC）是一种在许多经典关系数据库中使用的协议。例如，MySQL Cluster（与常规MySQL不同）使用2PC提供同步复制。下图说明了消息流：

[ Coordinator ] -> OK to commit?     [ Peers ]
                <- Yes / No

[ Coordinator ] -> Commit / Rollback [ Peers ]
                <- ACK

在第一阶段（投票）中，协调者将更新发送给所有参与者。每个参与者处理更新并投票决定是提交还是中止。当投票决定提交时，参与者将更新存储到临时区域（写前日志）。在第二阶段完成之前，更新被视为临时的。

在第二阶段（决策）中，协调者决定结果并通知每个参与者。如果所有参与者投票提交，则将临时区域中的更新变为永久。

在提交被视为永久之前设置第二阶段是有用的，因为它允许系统在节点失败时回滚更新。相比之下，在主/备复制（“1PC”）中，没有步骤可以回滚在某些节点上失败而在其他节点上成功的操作，因此副本可能会出现分歧。

2PC容易导致阻塞，因为单个节点故障（参与者或协调者）会阻止进展，直到该节点恢复。由于第二阶段的存在，恢复通常是可能的，在此期间其他节点会被告知系统状态。请注意，2PC假设每个节点的稳定存储中的数据永远不会丢失，并且没有节点会永远崩溃。如果稳定存储中的数据在崩溃中损坏，数据丢失仍然是可能的。

节点故障期间的恢复程序的细节相当复杂，因此我不会深入具体细节。主要任务是确保写入磁盘是持久的（例如，刷新到磁盘而不是缓存）并确保做出正确的恢复决策（例如，了解回合的结果，然后在本地重做或撤销更新）。

正如我们在关于CAP的章节中了解到的，2PC是CA——它不具备分区容忍性。2PC所处理的故障模型不包括网络分区；从节点故障恢复的规定方法是等待网络分区恢复。没有安全的方法可以提升新的协调者，如果一个协调者失败，则需要手动干预。2PC也相当敏感于延迟，因为它是一种N-of-N写入方法，写入必须等到最慢的节点确认后才能继续。

2PC在性能和容错性之间取得了不错的平衡，这就是它在关系数据库中受欢迎的原因。然而，较新的系统通常使用分区容忍的共识算法，因为这样的算法可以在临时网络分区中提供自动恢复，并更优雅地处理节点之间增加的延迟。

接下来，让我们看看分区容忍的共识算法。

分区容忍的共识算法

分区容忍的共识算法是我们在维护单副本一致性的容错算法中所能达到的极限。还有一类容错算法：容忍任意（拜占庭）故障的算法；这些算法包括通过恶意行为导致故障的节点。这类算法在商业系统中很少使用，因为它们运行成本更高且实现更复杂——因此我将不再讨论它们。

在分区容忍的共识算法中，最著名的算法是Paxos算法。然而，它 notoriously 难以实现和解释，因此我将重点关注Raft，这是一种较新的（约2013年初）算法，旨在更容易教授和实现。让我们首先看看网络分区和分区容忍共识算法的一般特性。

什么是网络分区？

网络分区是指到一个或多个节点的网络链接故障。这些节点本身仍然保持活动状态，甚至可能能够接收来自网络分区一侧的客户端请求。正如我们之前在讨论CAP定理时了解到的，网络分区确实会发生，并且并非所有系统都能优雅地处理它们。

网络分区很棘手，因为在网络分区期间，无法区分远程节点故障和节点不可达。如果发生网络分区但没有节点故障，则系统被分为两个同时活动的分区。下面的两个图示说明了网络分区如何看起来类似于节点故障。

一个包含2个节点的系统，故障与网络分区的对比：

一个包含3个节点的系统，故障与网络分区的对比：

强制执行单副本一致性的系统必须有某种方法来打破对称性：否则，它将分裂成两个独立的系统，这两个系统可能会相互分歧，并且无法再维持单一副本的假象。

对于强制执行单副本一致性的系统，网络分区容忍性要求在网络分区期间，系统的只有一个分区保持活动状态，因为在网络分区期间无法防止分歧（例如，CAP定理）。

多数决策

这就是分区容忍共识算法依赖于多数投票的原因。要求多数节点——而不是所有节点（如在2PC中）——对更新达成一致，允许少数节点因网络分区而宕机、缓慢或不可达。只要(N/2 + 1)-of-N节点处于活动状态并可访问，系统就可以继续运行。

分区容忍共识算法使用奇数个节点（例如3、5或7）。仅有两个节点时，故障后无法形成明确的多数。例如，如果节点数量为三，则系统对一个节点故障具有弹性；如果有五个节点，系统对两个节点故障具有弹性。

当发生网络分区时，各个分区表现出不对称性。一个分区将包含大多数节点。少数分区将停止处理操作，以防止在网络分区期间出现分歧，但多数分区可以保持活动状态。这确保了系统状态的唯一副本保持活动。

多数决策也很有用，因为它们可以容忍分歧：如果发生扰动或故障，节点可能会投出不同的票。然而，由于只能有一个多数决策，暂时的分歧最多只能阻止协议继续（放弃活性），但不能违反单副本一致性标准（安全属性）。

角色

系统可以有两种结构方式：所有节点可能具有相同的职责，或者节点可能具有不同的、独特的角色。

用于复制的共识算法通常选择为每个节点分配不同的角色。拥有一个固定的领导者或主服务器是一种优化，使系统更高效，因为我们知道所有更新必须通过该服务器。不是领导者的节点只需将请求转发给领导者。

请注意，拥有不同的角色并不妨碍系统从领导者（或任何其他角色）的故障中恢复。仅仅因为在正常操作期间角色是固定的，并不意味着在故障后不能通过重新分配角色来恢复（例如，通过领导者选举阶段）。节点可以重用领导者选举的结果，直到节点故障和/或网络分区发生。

Paxos和Raft都利用了不同的节点角色。特别是，它们有一个领导节点（在Paxos中称为“提议者”），负责在正常操作期间进行协调。在正常操作期间，其余节点是跟随者（在Paxos中称为“接受者”或“投票者”）。

纪元

在Paxos和Raft中，每个正常操作的周期称为一个纪元（在Raft中称为“任期”）。在每个纪元中，只有一个节点是指定的领导者（类似的系统在日本中使用，时代名称在皇位继承时更改）。

在成功选举后，相同的领导者协调直到纪元结束。如上图所示（来自Raft论文），某些选举可能会失败，导致纪元立即结束。

纪元充当逻辑时钟，使其他节点能够识别过时节点何时开始通信——被分区或失效的节点将具有比当前纪元更小的纪元编号，其命令将被忽略。

通过决斗进行领导者更换

在正常操作期间，分区容忍的共识算法相对简单。正如我们之前所见，如果我们不关心容错性，我们可以直接使用2PC。大多数复杂性实际上来自于确保一旦达成共识决策，它不会丢失，并且协议能够处理由于网络或节点故障导致的领导者更换。

所有节点开始时都是跟随者；在开始时选举一个节点作为领导者。在正常操作期间，领导者保持心跳，这使得跟随者能够检测到领导者是否故障或被分区。

当一个节点检测到领导者变得无响应（或者在初始情况下，没有领导者存在）时，它会切换到一个中间状态（在Raft中称为“候选者”），在该状态下，它将任期/纪元值增加一，发起领导者选举并竞争成为新的领导者。

为了被选为领导者，节点必须获得多数票。分配投票的一种方法是简单地按先到先得的原则分配；这样，最终会选出一个领导者。在尝试选举之间添加随机的等待时间将减少同时尝试选举的节点数量。

纪元内的编号提案

在每个纪元中，领导者一次提出一个值供投票。在每个纪元内，每个提案都用一个唯一的严格递增的编号进行编号。跟随者（投票者/接受者）接受它们收到的特定提案编号的第一个提案。

正常操作

在正常操作期间，所有提案都通过领导节点。当客户端提交提案（例如，更新操作）时，领导者联系法定人数中的所有节点。如果没有竞争提案存在（基于跟随者的响应），领导者提出该值。如果大多数跟随者接受该值，则该值被视为已接受。

由于可能还有其他节点也在尝试充当领导者，我们需要确保一旦某个提案被接受，其值永远不会改变。否则，已经被接受的提案可能会被竞争领导者撤回。Lamport将其表述为：

P2：如果一个值为v的提案被选择，则每个更高编号的被选择提案的值为v。

确保这一属性成立需要跟随者和提议者都受到算法的约束，永远不能更改已被多数接受的值。请注意，“值永远不能改变”是指协议的单次执行（或运行/实例/决策）的值。典型的复制算法将运行多次算法的执行，但大多数关于算法的讨论集中在单次执行上，以保持简单。我们希望防止决策历史被更改或覆盖。

为了强制执行这一属性，提议者必须首先询问跟随者其（最高编号的）已接受提案及其值。如果提议者发现已经存在提案，则必须完成该协议的执行，而不是提出自己的提案。Lamport将其表述为：

P2b：如果一个值为v的提案被选择，则任何提议者提出的每个更高编号的提案的值为v。

更具体地说：

P2c：对于任何v和n，如果一个值为v且编号为n的提案被[领导者]提出，则存在一个由大多数接受者[跟随者]组成的集合S，使得（a）S中的没有接受者接受任何编号小于n的提案，或者（b）v是所有编号小于n的提案中被S中的跟随者接受的最高编号提案的值。

这是Paxos算法的核心，以及从中派生的算法。要提议的值在协议的第二阶段之前不会被选择。提议者有时必须简单地重新传输先前做出的决策以确保安全（例如，P2c中的条款b），直到它们达到一个点，在该点它们知道可以自由地施加自己的提案值（例如，条款a）。

如果存在多个先前的提案，则提议最高编号的提案值。提议者只能在没有任何竞争提案的情况下尝试施加自己的值。

为了确保在提议者询问每个接受者其最新值的时间内没有竞争提案出现，提议者要求跟随者不要接受编号低于当前提案的提案。

将各个部分结合起来，使用Paxos达成决策需要两轮通信：

[ Proposer ] -> Prepare(n)                                [ Followers ]
             <- Promise(n; previous proposal number
                and previous value if accepted a
                proposal in the past)

[ Proposer ] -> AcceptRequest(n, own value or the value   [ Followers ]
                associated with the highest proposal number
                reported by the followers)
                <- Accepted(n, value)

准备阶段允许提议者了解任何竞争或先前的提案。第二阶段是提出一个新值或先前接受的值。在某些情况下——例如，如果两个提议者同时处于活动状态（决斗）；如果消息丢失；或者如果大多数节点故障——则没有提案被大多数接受。但这是可以接受的，因为提议的值的决策规则趋向于单一值（在上一次尝试中具有最高提案编号的值）。

实际上，根据FLP不可能性结果，这是我们所能做到的最好：解决共识问题的算法必须在消息传递的界限保证不成立时放弃安全性或活性。Paxos放弃了活性：它可能不得不无限期延迟决策，直到没有竞争领导者的时刻，并且大多数节点接受一个提案。这比违反安全保证更可取。

当然，实现这个算法比听起来要困难得多。即使在专家手中，许多小问题也会累积成相当可观的代码量。这些问题包括：

  • 实际优化：
    • 通过领导权租约（而不是心跳）避免重复的领导者选举
    • 在领导者身份不变的稳定状态下避免重复的提案消息
  • 确保跟随者和提议者不会在稳定存储中丢失项目，并且存储在稳定存储中的结果不会被微妙地损坏（例如，磁盘损坏）
  • 以安全的方式使集群成员资格发生变化（例如，基础Paxos依赖于大多数总是交集在一个节点上，如果成员资格可以任意变化，这一条件就不成立）
  • 在崩溃、磁盘丢失或新节点配置后，以安全和高效的方式使新的副本更新到最新状态的程序
  • 在合理的时间段后，快照和垃圾回收所需数据的程序，以保证安全（例如，平衡存储要求和容错要求）

谷歌的Paxos Made Live论文详细介绍了其中的一些挑战。

分区容忍的共识算法：Paxos、Raft、ZAB

希望这能让你对分区容忍共识算法的工作原理有一个了解。我鼓励你阅读进一步阅读部分中的一篇论文，以掌握不同算法的具体细节。

_Paxos_。Paxos是编写强一致性分区容忍复制系统时最重要的算法之一。它被许多谷歌系统使用，包括用于BigTable/Megastore的Chubby锁管理器、谷歌文件系统以及Spanner。

Paxos以希腊岛屿Paxos命名，最初由Leslie Lamport在1998年的论文《兼职议会》中提出。它通常被认为难以实现，并且有一系列来自具有相当分布式系统专业知识的公司的论文进一步解释了实际细节（请参见进一步阅读）。你可能想阅读Lamport对此问题的评论这里和这里。

这些问题主要与Paxos以单轮共识决策的形式描述有关，但实际工作实现通常希望高效地运行多轮共识。这导致了许多核心协议的扩展，任何有兴趣构建基于Paxos的系统的人都需要消化这些内容。此外，还有其他实际挑战，例如如何促进集群成员资格的变化。

_ZAB_。ZAB - Zookeeper原子广播协议在Apache Zookeeper中使用。Zookeeper是一个为分布式系统提供协调原语的系统，被许多以Hadoop为中心的分布式系统用于协调（例如，HBase、Storm、Kafka）。Zookeeper基本上是开源社区的Chubby版本。从技术上讲，原子广播是一个不同于纯共识的问题，但它仍然属于确保强一致性的分区容忍算法的范畴。

_Raft_。Raft是这一系列算法的最新（2013年）补充。它旨在比Paxos更容易教授，同时提供相同的保证。特别是，算法的不同部分更加清晰地分开，论文还描述了集群成员资格变化的机制。它最近在受ZooKeeper启发的etcd中得到了应用。

强一致性的复制方法

在本章中，我们考察了强一致性强制的复制方法。从同步工作与异步工作的对比开始，我们逐步深入到容忍越来越复杂故障的算法。以下是每种算法的一些关键特性：

主/备复制

  • 单一、静态主节点
  • 复制日志，备份不参与执行操作
  • 复制延迟没有界限
  • 不具备分区容忍性
  • 手动/临时故障转移，不具备容错性，“热备份”

2PC

  • 一致投票：提交或中止
  • 静态主节点
  • 2PC无法在提交期间同时容忍协调者和节点的故障
  • 不具备分区容忍性，尾延迟敏感

Paxos

  • 多数投票
  • 动态主节点
  • 在协议的一部分中对n/2-1的同时故障具有鲁棒性
  • 对尾延迟不太敏感

推荐阅读

Primary-backup and 2PC

Paxos

Raft and ZAB