零基础入门分布式系统 5. Replication

我们现在来看看的replication数据复制的问题，也就是在多个节点上维护相同数据的拷贝，每个节点被称为replica 副本。数据复制是许多分布式数据库、文件系统或其他存储系统的标准特性之一。它是我们实现容错的主要机制之一：如果一个副本出现故障，我们可以继续访问其他副本上的数据备份。

Replication 数据复制

• 在多个节点上保留相同数据的副本
• 数据库、文件系统、缓存、......
• 一个拥有数据拷贝的节点被称为replica 副本
• 即使一些副本故障，其他副本仍然可以使用
• 将负载分散到多副本上
• 如果数据没有变更，数据复制是很容易的：只需复制一份即可
• 我们的重点将关注数据变更的场景

对比RAID（Redundant Array of Independent Disks 独立磁盘冗余阵列）：在一台计算机内进行复制

• RAID只有一个控制器；但在分布式系统中，每个节点独立运行
• 分布式系统的副本可以分布在世界各地，靠近用户端

5.1 Manipulating remote state

当数据不变时，备份很容易，只需要对数据进行一次性的复制。因此，复制的主要问题是管理数据的变更。在我们讨论复制的细节之前，让我们看看分布式系统中的数据变更是如何发生的。

以"点赞"行为为例，当你点击"赞/喜欢"按钮时，你“点赞”的事实以及已往“点赞”的人数需要被存在某个地方，以便它们可以显示给你和其他用户。这通常发生在社交网络服务器上的一个数据库中。我们可以把存储在数据库中的数据看作是它的状态state。

更新数据库的请求可能会在网络中丢失，或者已经执行更新的确认也可能丢失。我们通常通过重试该请求来提高可靠性。然而，重试可能会导致请求被多次处理，导致数据库中出现不正确的状态。

一个防止更新多次生效的方法是deduplicate 去重request。然而，在崩溃-恢复系统模型中，需要将request（或一些关于request的元数据，如向量时钟）存储在稳定的存储中，这样即使在崩溃后也能准确地检测到重复的请求。

另一种记录重复请求以达到去重的方案是让请求idempotent幂等。

重试行为：

• At-most-once 最多一次语义：发送请求，不重试；更新可能丢失，不会发生
• At-least-once 最少一次语义：重试请求，直到确认，可导致重复更新
• Exactly-once 精确一次语义：重试+幂等或去重

递增一个计数器不是幂等的，但是向一个集合添加一个元素是幂等的。因此，如果需要一个计数器（如点赞的数量），最好是在数据库中实际维护元素集，并通过计算该集合的量数从中得出计数器值。

幂等更新的重试是安全的，因为执行几次和执行一次的效果是一样的。Idempotence 幂等性允许更新具有exactly-once 精确一次的语义：即更新实际上可以被执行多次，但其效果与刚好执行一次是等价的。幂等性通常出现在RPC的语境中，其中重试是非常常见的。

当多个更新同时发生的时候，幂等性会遇上一个问题。客户端1将一个用户ID添加到一个帖子的点赞集合中，但ack确认丢包。客户端2从数据库中读取点赞集合（包括客户端1添加的用户ID），然后再次发出请求，删除该用户ID。同时，客户端1重试请求，但它不知道客户端2的更新。因此，客户端1重试的结果是将用户ID再次添加到集合中。这造成了非预期结果，因为客户端2观察到了客户端1的变更，所以删除是在添加集合元素之后发生的，因此我们期望在最终状态下，用户ID不应该出现在集合中。在这种场景下，向集合中幂等地添加元素并不能使重试安全。

类似的场景比如，我们有两个副本。在第一种情况下，客户端首先将x添加到数据库的两个副本中，然后试图从两个副本中删除x。然而，对副本B的删除请求丢包了，并且客户端在重试之前崩溃了。在第二种情况下，客户试图将x添加到两个副本中，但对副本A的请求丢包，并且客户端崩溃。

在这两种情况下，结果是一样的：x在副本B中存在，而在副本A中不存在。然而，预期的效果是不同的：在第一种情况下，客户希望x从两个副本中删除，而在第二种情况下，客户端希望x在两个副本中存在。当两个副本协调它们的不一致状态时，我们希望它们最终都处于客户端预期的状态。如果副本无法区分这两种情况，就达不到这个期望。

为了解决这个问题，我们可以做两件事。首先，我们给每个更新操作附加一个逻辑时间戳，并将该时间戳作为更新所写数据的一部分存储在数据库中。然后，当被要求从数据库中删除一条记录时，我们实际上并不删除它，而是写一个特殊的类型的更新（称为tombstone 墓碑），将其标记为删除。在图上，含有false标签的就是tombstone 墓碑。

在许多复制系统中，副本运行一个检测并协调差异的协议（这被称为anti-entropy反熵），因此副本最终持有相同数据的一致性拷贝。由于有了墓碑，反熵进程可以分辨出已经删除的记录和尚未创建的记录之间的区别。而且，由于有了时间戳，我们可以分辨出一条记录的哪个版本比较旧，哪个版本比较新。然后，反熵进程会保留较新的记录并丢弃较旧的记录。

这种方法也有助于解决前面的问题：重试的请求具有与原始请求相同的时间戳，所以重试不会覆盖一个因果关系更晚、时间戳更大的请求所写的值。

给每个更新附加一个时间戳的技术对于处理并发更新也很有用。在上图中，客户端1想把键x设置为值v1（时间戳t1），而同时客户端2想把相同的键x设置为值v2（时间戳t2）。副本A先接收v2，后接收v1，而副本B则以相反的顺序接收更新。为了确保两个副本最终处于相同的状态，我们依靠的不是它们接收请求的顺序，而是它们的时间戳的顺序。

这种方法的详细实现取决于所使用的时间戳类型。如果我们使用Lamport时钟，两个并发的更新将被任意排序，这取决于时间戳如何分配。在这种情况下，我们得到了所谓的最后写入胜出 last writer wins（LWW）的语义：具有最大时间戳的更新生效，任何对同一键的较小时间戳并发更新都被丢弃了。这种方法操作起来很简单，但是当多个更新同时进行时，它代表着数据丢失。在一些系统中，丢弃并发的更新没有影响；有些情况下则是个问题。

当丢弃并发的更新不可行时，我们需要使用一种能够检测到并发何时发生的时间戳，例如向量时钟。有了这种偏序的时间戳，我们可以知道什么时候一个新的值应该覆盖一个旧的值（当旧的更新发生在新的更新之前）；当几个更新并发的时候，我们可以保留所有并发写入的值。这些同时写入的值被称为conflicts冲突（或者有时称为siblings兄弟）。应用程序可以在之后将冲突合并回一个单一的值。

向量时钟的缺点是开销很大：每个客户端都需要在向量中占据一个条目，在有大量客户端的系统中（或者客户端每次重启都会获得一个新的身份），这些向量会变得很大，甚至会比数据本身占用更多空间。别的类型的逻辑时钟，如dotted version vectors 点状版本向量[Preguica et al., 2010]，可以优化这类系统。

5.2 Quorums

正如本章开篇时所说，复制技术帮助我们提高系统的可靠性：当一个副本不可用时，其余的副本可以继续处理请求。不可用性可能来自于一个有问题的节点（如崩溃或硬件故障），或者来自于网络分区（无法通过网络到达一个节点），或者计划中的维护（如重启一个节点以安装软件更新）。

然而，具体如何实现复制对系统的可靠性有很大影响。如果没有容错，拥有多个副本反而会使可靠性变差：副本越多，某一时刻某一副本出现故障的概率就越大（假设故障发生相互独立）。然而，如果系统在一些副本故障时仍然可以继续工作，那么可靠性就会提高：所有副本在同一时间出现问题的概率要比一个副本出现问题的概率低很多。

我们来看看如何在复制中实现容错。首先，考虑这个例子。假设我们有两个副本，A和B，它们一开始将键x与一个值v0（和时间戳t0）相关联。一个客户端尝试将x的值更新为v1（时间戳为t1）。B的更新成功了，但是A的更新失败了，因为A是暂时不可用。随后，客户端试图读取它所写入的值；A处读取成功，但在B读取失败。结果，读到的不是客户端之前写的值v1，而是初始值v0。

这种情况是有问题的，因为从客户端的角度看，它所写的值似乎已经丢失了。想象一下，你在网上发了一个微博，刷新页面，却没有看到你刚刚发的那条。由于这种行为让用户感到困惑，许多系统要求read-after-write consistency 写后读一致性（也被称为read-your-writes consistency 读你所写一致性），在这种情况下，我们确保在客户端写完一个值后，同一个客户端能够读回它刚刚写的值。

严格来说，在read-after-write一致性中，一个客户端在写完之后可能无法读取它所写的值，因为同时另一个客户端可能已经并发覆盖了这个值。因此，我们说read-after-write一致性要求读取最后写入的值，或者后一个值。

在这个例子中，我们可以通过确保总是同时向两个副本读或写read-after-write一致性。然而，这意味着读或写不再是容错的：如果一个副本不可用，需要两个副本响应的写或读将无法完成。

我们可以通过使用三个副本来解决这个难题。我们将每个读写请求发送到所有三个副本，但只要我们收到≥2个响应，我们就认为请求成功了。在这个例子中，写请求在副本B和C上成功，而读请求在副本A和B上成功。通过对读和写采取 "三选二"的策略，可以保证至少有一个对读请求的响应是来自拥有最近写更新的副本（在本例中是副本B）。

不同的副本可能会对同一个读请求返回不同的响应：本例中，A处的读取返回初始值(t0, v0)，而B处的读取则返回该客户端之前写入的值(t1, v1)。使用时间戳，客户端可以知道哪个响应是最新的一个，并将v1返回给应用程序。

在本例中，响应写请求的副本集合{B，C}是一个write quorum，并且响应读请求的集合{A, B}是一个read quorum。而quorum是需要成功响应节点的最小集合。(这个术语来自政治学，在政治学中，quorum 法定人数指的是一个议会或委员会中做出有效决定所需的最低票数）。为了确保read-after-write一致性，write quorum和read quorum必须有一个非空的交集：换句话说，read quorum必须包含至少一个已经确认了写请求的节点。

在分布式系统中，一个常见的quorum选择是majority quorum 多数仲裁，它是由严格大于一半的节点组成的节点子集。在有{A, B, C}三个节点的系统中，majority quorum可以是{A, B}，{A, C}和{B, C}。一般来说，在一个有奇数n的节点的系统中 ，任何(n+1)/2大小的子集都是majority quorum（3取2，5取3，...）。如果是偶数n的节点，这需要被向上取整为(n+2)/2.例如，4取3构成majority quorum。majority quorum代表着：任何两个quorum总是有至少一个共同的元素。 除了多数之外，其他的quorum结构也是存在的[Whittaker et al.，2021]。

一个系统需要w个写入确认（即write quorum的大小为w），说明只要不超过n-w个副本不可用，就可以继续处理更新。一个系统需要r个读取确认，说明只要不超过n-r个的副本不可用，就可以继续读取。对于majority quorum，这意味着有三个副本的系统可以容忍一个副本不可用，有五个副本的系统可以容忍两个副本不可用，以此类推。

在这种基于quorum的复制法中，一些更新可能在任何时刻从副本中丢失：前一个例子中，由于写请求丢包，副本A丢失了(t1, v1)更新。为了使副本之间恢复一致，一种方案是依靠反熵进程。

另一个方案是让客户端帮助传播更新。例如上图，客户端从B读取(t1, v1)，但它从A收到了较旧的值(t0, v0)，而C没有回应。由于客户端现在知道更新(t1, v1)需要传递给A，它可以将该更新发送给A（使用原始时间戳t1，因为这不是一个新的更新，而是以前更新的重试）。客户端也可以将更新发送给C，即使它不知道C是否需要它（如果事实证明C已经有了这个更新，那么只浪费了少量的网络带宽）。这个过程被称为read repair 读修复。客户端可以对它发出的任何读请求进行读修复，而无论它是否是最初执行有关更新的客户端。

使用这种复制模式的数据库通常被称为Dynamo模式，这是以Amazon的Dynamo数据库[DeCandia et al.，2007]命名，该数据库将这种模式推广出来。这种方法实际上早于Dynamo[Attiya et al.，1995]。

5.3 Replication using broadcast

quorum方法本质上使用了best-effort尽力而为广播：客户端向所有的副本广播每一个读或写请求，但该协议是不可靠的（请求可能会丢失），并且不保证顺序。

复制的另一种方案是使用第4章中的广播协议。让我们首先考虑一下FIFO-total order广播，这是我们看到的最强大的广播形式。

使用FIFO-total order广播很容易建立一个复制系统：我们将每个更新请求广播给所有副本，副本根据每个递交的消息更新自身状态。这被称为状态机复制state machine replication（SMR），因为每个副本作为一个状态机，以递交的消息作为输入。我们只要求更新逻辑是deterministic确定的：任何两个处于相同状态的副本，被赋予相同的输入，最终输出必须处于相同的状态。甚至error也必须是确定的：如果一个副本的更新成功了，但另一个失败了，它们就会不一致。

SMR的一个特性是，只要逻辑是确定性的，从一个状态到下一个状态的逻辑可以任意复杂。例如，数据库可以执行具有任意业务逻辑的整个事务，而这个逻辑可以同时依赖于广播信息和数据库的当前状态。一些分布式数据库以这种方式执行复制，每个副本独立执行相同的确定性交易代码（这被称为active replication 主动复制）。这一原理也是blockchains 区块链、cryptocurrencies 加密货币和distributed ledgers分布式账本的基础：区块链中的"链（chain of blocks）"正是由全序广播协议传递的消息序列，每个副本确定性地执行这些区块中描述的交易，以确定账本的状态（例如，谁拥有哪些钱）。一个 "smart contract智能合约"只是一个副本收到特定的消息时执行的确定性程序。

状态机复制的缺点正是全序广播的限制性。当一个节点想通过全序广播来广播一个消息时，它不能立即将该消息传递给自己。由于这个原因，当使用状态机复制时，想要更新状态的副本不能立即生效，而是要经过广播进程，与其他节点协调，并等待更新信息被送回给自己。状态机复制的容错性取决于底层全序广播的容错性。尽管如此，基于全序广播的复制依然被广泛使用。

之前我们提到过，实现全序广播的一种方法是指定一个节点作为leader领导者，并将所有的广播信息导向它，以获得一个递交顺序。这一原理也被广泛用于数据库复制：许多数据库系统指定一个副本作为leader领导者、primary主副本或master主站。任何可能修改数据库的事务都必须在领导者副本上执行。领导者可以同时执行多个事务；但是，它以一个全序commit提交这些事务。当一个事务提交时，领导者副本将该事务的数据变更广播给所有跟随者follower副本，跟随者按照提交顺序应用这些变更。这种方法被称为passive replication被动复制或primary-backup replication主备复制，它等价于事务提交记录的全序广播。

状态机复制使用FIFO-全序广播。那么我们也可以其他较弱的广播模型将它们用于复制吗？答案是肯定的；但是，需要更加谨慎地确保副本一致性。仅仅确保状态更新是确定性的还不够。

例如，我们可以使用因果广播，当一个更新发生在另一个之前时，它可以确保跨副本的递交顺序相同，但它可能将以任意顺序递交并发更改。如果我们想确保无论以何种顺序递交并发更改，副本最终处于相同的状态，我们需要使这些更新满足交换律commutative：也就是说，我们必须确保无论这些更新以何种顺序应用，最终结果是一致的。