# Replication

## 简介

数据集复制是分布式系统的必备功能，复制的目的主要在于：

* 服务高可用 (High Availability)：在一到多台机器，甚至其中一个数据中心崩溃时，系统正常运行
* 抗网络中断 (Disconnected Operation)：存在网络干扰时，系统正常运行
* 减少网络延迟 (Latency)：将数据放在离用户近的地方，让响应更及时
* 提高系统扩展性 (Scalability)：将读请求分散到复制节点上，提高读请求的服务能力

根据节点的职责设定可以将现有的复制方案分成三类：

* 单领导复制 (Single-Leader Replication)：clients 将所有的写请求发给唯一的 leader，后者将数据的修改事件发送给其它复制节点，即 followers。读操作可以在任意复制节点上执行，但有时候可能读到过期 (stale) 的数据。
* 多领导复制 (Multi-Leader Replication)：clients 将所有的写请求发送到多个中的某个 leader 上，后者将数据的修改事件发送给其它 leaders 和 followers 。
* 无领导复制 (Leaderless Replication)：clients 将所有的写请求同时发送给多个复制节点，根据各节点的响应得到最新的数据，同时帮助返回过期数据的节点更新数据。

以上复制方案有各自的优缺点。由于单领导复制的方案思路简单、便于理解，同时它对数据一致性的保证明确，因此它被广泛地使用；多领导/无领导复制方案尽管在面对节点故障、网络干扰以及延迟减少上表现很稳定，但它们通常难于理解，同时提供的数据一致性保证较弱、甚至含糊不清，导致开发者对于数据的一致性心中无数。

数据从 leader 同步到 followers 的过程有两种方式，同步复制和异步复制。尽管异步复制减少了系统的响应时间，但与此同时发生的复制延迟也为系统设计带来了新的问题。为此，不同的系统提出不同的一致性保证：

* 读后写一致 (Read-after-write Consistency)：用户自己一定能看到自己提交的数据
* 单调读一致 (Monotonic Reads)：用户在某时刻看到某数据，就不能在该时刻后看到更早版本的数据
* 因果读一致 (Consistent Prefix Reads)：用户看到数据的顺序应符合因果关系

## 单领导复制 (Single-Leader Replication)

保证每次数据变动都应用到所有复制节点，最常见的做法就是 leader-based replication，也称为 active/passive 或者 master/slave replication，其做法如下：

1. 任命一个复制节点为 leader，当 clients 写数据时，必须将请求发送到 leader，后者将数据写入其本地存储。
2. 剩下的复制节点自动成为 followers，在 leader 将数据写入本地存储的同时，它也将数据的修改事件发送给所有 followers。每个 follower 根据数据的修改事件信息更新本地存储，为了保证复制节点数据的一致性，它们应用数据修改的顺序必须通过某种机制保持一致。
3. 当 clients 想读取数据时，它可以请求任意复制节点，包括 leader 和 followers。

整个过程如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfCaNvmniBvf2tcC_kx%2F-LfCcps86dBJgipeVucq%2FScreen%20Shot%202019-05-18%20at%209.36.22%20PM.jpg?alt=media\&token=b4a35103-7156-4c0d-9ccf-2da273ee8459)

leader-based replication 广泛应用在各个场景：

* 关系型数据库：PostgreSQL、MySQL 等
* 非关系型数据库：MongoDB、RethinkDB 和 Espresso 等
* 分布式消息队列：Kafka 和 RabbitMQ 的高可用队列
* 网络文件系统
* 复制块存储设备

### 同步复制与异步复制

以下图中的场景为例：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfCmgZFDkuqDwk5ioDL%2F-LfCmwDqiGabLIh-LZtA%2FScreen%20Shot%202019-05-18%20at%209.51.10%20PM.jpg?alt=media\&token=79d07066-7327-44dd-a617-157f0cd5695c)

leader 复制到 follower1 的过程就是同步复制，leader 复制到 follower2 的过程就是异步复制。在 user1234 收到确认信息后，follower1 的数据已经同步，而 follower2 的数据尚未同步，后者称为复制延迟 (replication lag) 现象。

同步复制能保证 follower 与 leader 的数据一致，如果 leader 忽然故障，可以确保 follower 上存有完整的数据；但同步复制的过程中，只要一个复制节点的响应时间变慢就会影响整个过程，此时所有发送到 leader 上的写操作都将被阻塞。当复制节点数量变多时，出现一个复制节点变慢的概率将大大增加。正因为如此，让所有 followers 都采用同步复制的方式不切实际。通常在数据库中启动“同步复制”指的是其中一个 follower 采用同步复制，余下的 followers 采用异步复制，这种配置也称为半同步复制 (semi-synchronous)。

通常情况下，leader-based replication 被设置为完全异步复制，即所有 followers 都采用异步复制，此时数据库的响应时间最小，但可能出现 leader 故障之后未来得及写入的数据丢失的情况。后者意味着 client 写入数据并获得确认之后，数据仍有可能丢失。即便如此，异步复制仍被广泛使用。

### 配置新的 Followers

在运维过程中，我们常常需要配置新的 followers，如新增、替换故障节点，那么在不停机 (downtime) 的情况下，如何保证新的 follower 的数据与 leader 保持同步？

1. 获取 leader 数据库在某时刻的快照
2. 将快照复制到 follower
3. follower 向 leader 请求快照时刻之后的所有数据变动事件，并应用到本地存储

至此，新的 follower 已经跟上 leader，可以正常运行。

### 节点故障

分布式系统中的任意节点都可能故障，因此一个高可用的分布式系统必须能够在一个或少量节点故障后正常运行。以下将对不同角色的节点分开讨论：

#### Follower Failure: Catch-up Recovery

每个 follower 的本地磁盘都保存着 leader 发送的数据修改事件日志，如果 follower 崩溃、重启或者与 leader 之间的网络干扰，只要问题恢复，follower 就可以向 leader 请求最后一条日志之后的所有日志，并应用到本地存储，如此一来，follower 就跟上了 leader。

#### Leader Failure: Failover

leader 的故障恢复比 follower 复杂：

* 其中一个 follower 需要晋升为 leader
* clients 需要将写请求指向新的 leader
* 其它 followers 需要从新的 leader 那里请求数据修改事件

整个过程称为故障转移 (failover)。故障转移可以手动执行或自动执行，自动故障转移通常包含以下几个阶段：

1. 确定 leader 已经故障：许多问题可能导致 leader 故障，甚至非 leader 本身的问题也可能导致 followers 认为 leader 已经发生故障：崩溃、停电、网络中断等等。在网络中，其它节点无法辨别故障原因，因此通常采用心跳包来确认其它节点是否正常工作，一旦心跳响应超时，该节点就可以被认为发生故障。
2. 选举新的 leader：选举新 leader 通常有两种做法，通过中心控制节点 (controller node) 指定或由多数 followers 选举出来。通常 leader 的最合适候选人是拥有最新数据的 follower 节点。
3. 使系统在新 leader 的带领下继续运行：clients 需要发现新的 leader。如果旧的 leader 故障恢复以后，它可能仍然认为自己是 leader，系统需要保证旧的 leader 能够发现并承认新的 leader，回到 follower 身份。

故障转移的过程有很多难点：

* 若使用异步复制，旧的 leader 收到请求以后，尚未成功将数据修改事件信息发送给 followers  时出现故障，新的 leader 就无法知道这些请求已经发生。最常见的做法就是让新的 leader 放弃这些修改，但对于 clients 来说，即使收到写数据成功的消息后也无法完全确定数据已经持久化 (durability)。GitHub 曾经因为 MySQL 故障转移的过程放弃最新的修改数据而出现 MySQL 与 Redis 之间出现数据不一致，导致部分私有数据泄露。
* 在某些情形下，可能出现两个节点都认为自己是 leader，这种情况成为 split brain。如果两个 leader 都接收写请求，就会出现数据冲突、丢失或者破坏。因此有些系统发现两个 leaders 会关停其中一个。
* 确认 leader 已经故障的超时设置既不能太长也不能太短，太长将导致故障转移的过程太长，太短将导致一些不必要的故障转移。

这些问题没有简单的解决方案，因此许多运维团队更青睐于手动执行故障转移。

### Implementation of Replication Logs

leader 发送到 followers 的数据修改事件日志称为复制日志 (replication logs)，本节介绍其实现。

#### Statement-based Replication

以关系型数据库为例，statement-based replication 就是将所有 SQL 语句转发给 followers，每个 follower 在本地解析并执行相应的 SQL 语句。这种做法有很多问题：

* statement 如果存在随机函数，如 NOW()、RAND()，在不同的 follower 上执行结果都不一样
* statement 的执行结果如果依赖于数据库中的其它数据和状态，为了保证结果一致，就需要所有复制节点执行 statement 的顺序一致，若存在多个事务并发执行，情况就更加复杂
* statement 可能存在副作用，副作用在不同复制节点上的效果可能不同
* ...

statement-based replication 在 MySQL (<5.1) 中曾被使用。VoltDB 也使用这种复制方式，但它要求所有的事务的结果必须是确定 (deterministic) 的。

#### Write-ahead Log (WAL) Shipping

不论数据库底层使用什么样的存储引擎，通常都需要在真正写入数据之前先写入日志：

* log-structured：日志本身就是数据
* B-tree：每个修改都需要先写入预写日志 (write-ahead)

在任意情况下，我们都可以使用这些日志本身来作为 replication logs。这种方法曾经在 PostgreSQL 和 Oracle 中使用。它的主要缺点是这种日志描述数据的方式较为底层 (low-level)，这使得 replication log 与存储引擎耦合度更高，如果数据库改变存储格式会带来较大的麻烦，在迁移过程可能需要停机 (downtime)。

#### Logical (row-based) Log Replication

将存储引擎日志与复制日志解耦，单独设计复制日志，使得复制日志与数据底层表示形式分离，就是 逻辑日志复制 (logical log replication)。在关系型数据库中，通常一条逻辑日志由一组以行为单位的记录构成：

* 插入一行：日志包含该行数据每列的数值
* 删除一行：日志包含足够信息唯一指向该行，通常可以使用主键
* 更新一行：日志包含足够信息唯一指向该行，同时记录更新的所有列数据

一个修改多行数据的事务需要记录多条上述的日志记录，并在结尾加上表示 commit 的特殊日志记录，MySQL 的 binlog 就使用这种方式。

#### Trigger-based Replication

前面提到的三种复制方式都是由数据库内部来实现，如果开发者想要更大的自由度，如：

* 只复制一部分数据
* 将数据从一个数据库复制到另一个数据库
* 定制其它应用逻辑

即将复制的逻辑提升到应用层来做，就可以使用 trigger + stored procedure 来完成。但这种方式比较脆弱，维护工作量大，只有在对灵活性要求极高的场景下才可能使用。

### 复制延迟的问题 (Problems with Replication Lag)

leader-based replication 适合读多写少的场景，当读请求量增加时，我们可以通过增加更多的 followers 来支撑系统的正常运行。但这种方案必须配合异步复制才可能付诸实践，因为更多的复制节点会提高单个节点发生故障的概率，而后者将造成写操作阻塞。在之前的介绍中提到过，异步复制会使得不同节点在一段时间内可能出现数据不一致，复制过程完成后，复制节点之间的数据将保持一致，称为最终一致性 (eventual consistent)。然而，这段数据不一致的时间长度无法保证，特别是在数据库负载较高、网络延迟较高的时候，这样的延迟可能为应用带来一些 “意外”，本节将介绍三种 “意外”。

#### 读后写 (Reading Your Own Writes)

想象下图中的场景：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfFBgwSrKuRd-eG6uuq%2F-LfFJtRfSTiJJthfS7dW%2FScreen%20Shot%202019-05-19%20at%209.41.30%20PM.jpg?alt=media\&token=488af4e4-c75b-4f7a-a683-8b1f30310811)

当 User1234 提交写评论请求到 leader 后，leader 将评论写入本地存储并将复制日志发送到 follower1 和 follower2，在异步复制下，leader 未等待 followers 的响应直接告诉 User1234 评论写成功，然而当用户写完之后立即刷新页面时，由于读请求被打到了 follower2 节点，后者尚未收到来自 leader 的复制日志，因此返回空结果。对于 User1234 来说这种现象就比较费解了：“我明明写了你也告诉我成功了，怎么查的时候却没有呢？”这个过程称为 reading your own writes。

在这种情况下，我们需要引入写后读一致性 (read-after-write consistency) 的概念，如果数据库能保证写后读一致性，那么用户永远能够在提交数据成功后查到自己提交的数据，这种一致性保证不保证其他用户能够在你写入后看到新数据。

我们能够在 leader-based replication 系统中实现 read-after-write consistency 吗？有很多方式可以实现这种目的，下面举几个例子：

* 当用户读取一些可能被自己编辑过的内容时，发送请求给 leader，否则发送请求给 followers。如读取个人信息时请求 leader，读取他人信息时请求 followers。
* 如果大多数信息都可能被用户编辑，上面的方法就失效了。这时候我们可以在用户本地保存最近一分钟的修改和更新，在这一分钟内一旦读取这些修改和更新的数据，则请求 leader，其余请求走 followers。当然，这里”一分钟“的时长需要根据真实的复制过程估计出来，这与集群的部署方式、网络状况以及其它方面息息相关。
* 如果用户可以记住最后一次写入的时间戳，那么数据库系统就可以在处理读请求时保证复制节点中的该数据的更新时间至少比该时间戳新，如果收到请求的复制节点不满足需求，可以由其它满足请求的节点来处理请求。注意，这里的时间戳不是物理时间，而是系统中的逻辑时间。

如果你的应用部署在多个数据中心，情况则更加复杂。任何需要 leader 处理的请求都需要被路由到含有 leader 的那个数据中心上；如果用户通过多种设备访问应用，你需要提供跨设备写后读一致性 (cross-dvice read-after-write consistency)，保证用户在一台机器上写以后能够在另外一台机器上读到。

#### 单调读 (Monotonic Reads)

想象下图的场景：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfFSieKhCbgtc4Jka-r%2F-LfFTVdGSSzQlh3RSO0T%2FScreen%20Shot%202019-05-19%20at%2010.23.32%20PM.jpg?alt=media\&token=74dc7766-ccf9-4658-814e-c8ec5c828dd5)

当用户 user1234 提交写评论请求后，leader 将其持久化到本地磁盘并转发复制日志到 followers 后立即响应。由于复制日志到达不同 follower 的时间不同，可能出现 user2345 先在 follower1 上读到评论后，刷新页面，又在 follower2 上读不到该评论，我们称这种现象为时间倒流 (moving backward in time)。

在这种情况下，我们需要引入单调读 (monotonic reads) 的概念，即读到过的数据不会消失。实现单调读一致性的一种方法是保证每个 user 永远只从相同的复制节点上读取数据。若该复制节点出现故障，则请求需要被路由到其它节点。

#### 因果读 (Consistent Prefix Reads)

想象下图中的场景：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfFSieKhCbgtc4Jka-r%2F-LfFYW9EdVnzh4kKDcJn%2FScreen%20Shot%202019-05-19%20at%2010.45.24%20PM.jpg?alt=media\&token=e591d932-1234-40b8-84a2-c96c94720fb6)

Mr.Poons 问 Mrs. Cake ”How far into the future can yous ee, Mrs. Cake?"，Mrs.Cake 收到后回答 "About ten seconds usually, Mr. Poons." 在数据库分片 (sharding) 场景下，Mr. Poons 和 Mrs. Cake 的数据可能写到不同的分片上，尽管在 Mrs. Cake 看来一切正常，但对于第三方观察者来说，他要分别从 partition1 和 partition2 中读取对话信息，有可能出现先读到答案后读到问题的情况，即因果上不合逻辑。这种问题主要出现在分片数据库中。

在这种情况下，我们需要引入因果读 (Consistent Prefix Reads) 的概念，即有因果关系的数据出现的顺序应当受到保证。其中一种实现方式是保证有因果关系的写操作都在同样的 partition 上执行，但这并不适用于所有场景。也有人提出一些记录因果关系的算法，来提供因果读一致性的保证。

### 复制延迟的解决方案

由于异步复制的存在，在一段时间内可能因为复制延迟出现数据不一致问题。使得这些数据库无法提供强一致性保证。如果你的应用可以忍受数据在一段时间内，或者毫秒、秒甚至分钟级别的间隔，出现数据不一致。如果不能，那么你可能需要读后写、单调读或者因果读一致性这些若一致性保证。如果应用开发者可以完全不用担心这些问题那世界就完美了，但现实并非如此，在特殊情况下，开发者甚至需要在应用层去解决一致性问题。在单机数据库中事务的存在让开发者长时间内无需担心这一点，然而在转移到分布式数据库上，大多数系统都因为性能和可用性的原因放弃了对事务的支持，声称最终一致性在分布式系统上无法避免。这话并不绝对正确，许多解决方案等待我们去探索。

## 多领导复制 (Multi-Leader Replication)

在单领导复制架构下，如果 client 无法连接到唯一的 leader，它就无法写入数据。自然而然地，如果系统允许多个 leaders 共存，共同接受写请求，这样的问题就能够得到缓解。我们称之为多领导复制。这时，每个 leader 都可能同时拥有两种角色：leader 和其它 leader 的 follower。

### 多领导复制的应用场景

在单个数据中心 (DC) 内使用多领导复制通常没多大意义，因为带来的好处抵不过增加的系统复杂度，但在一些跨数据中心的应用中，多领导复制则有其用武之地。

#### 跨数据中心操作 (Multi-Datacenter Operation)

想象一个跨 DC 应用，若使用单领导复制，所有的写操作都将被路由到同一个 DC；如果每个 DC 都有一个 leader，每个 leader 各自就近处理写请求，然后再将数据变动复制到其它 DC 的 leaders，就能够提升系统的响应能力，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfHi9mQyMFWhJooCCwz%2F-LfHkUBx7tQLseqCWA5X%2FScreen%20Shot%202019-05-20%20at%209.01.19%20AM.jpg?alt=media\&token=dbf46837-5e60-4bc6-9722-27ee5e89f5ae)

我们可以在多个维度上对比单领导复制与多领导复制：

* 性能：单领导复制下，每个写请求都将通过网络路由到拥有 leader 的那个 DC，这给写操作增加了额外的延迟；多领导复制下，每个写请求可以直接在 DC 内部解决，减少写操作的延迟。
* 容忍数据中心停运：单领导复制下，若 leader 所在的 DC 停运，故障转移机制会从其他 DC 里的 followers 中选择新的 leader；多领导复制下，每个 DC 可以继续正常运行，当停运的 DC 恢复运行时，它可以通过请求复制日志逐渐追上其他 DC。
* 容忍网络问题：单领导复制下，每个写请求可能都需要经过公网，公网出现的波动将立即反馈在写请求的延迟上；多领导复制下，使用异步复制能使得分布式系统对公网的波动容忍度增加。

尽管多领导复制在多个维度上比单领导复制更加稳定，但它的劣势也很明显，相同的数据可能在多个 DC 中被修改，这些修改可能互相冲突，多领导复制必须能够正视这个问题才能付诸实践。除此之外，一些单领导复制下常用的特征与工具，如自增键、triggers、integrity constraints 等，都需要被提升到应用层支持。

#### 客户端离线操作 (Clients with Offline Operation)

多领导复制的另一个使用场景是当你的应用需要允许客户端离线操作。如 gitbook 本身，用户可能在两台终端上分别编辑同一个文档，这时每个装置本地都会有一个数据库作为 leader 接受写请求，同时不同的 leader 之间在网络连接存在时会执行异步复制的操作，从结构上看，这种应用很像多领导复制。

有许多工具致力于解决这种问题，如 CouchDB。

#### 合作编辑 (Collaborative Editing)

许多实时合作编辑的应用，如 Google Docs，允许多个用户并发地编辑同一段文档。尽管这与多领导复制看上去没有太多关系，但其实它们的结构同样有很大的相似性。每个人在本地写入的信息都将被存储到本地，然后异步地复制到其它正在编辑相同文档的用户上。

### 处理写冲突

多领导复制的最大难点在于解决写冲突。想象两个用户 user1 和 user2 同时编辑 wiki 页面，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfKmf8y8MUYVH6ykMZv%2F-LfKmiXU6j-V1vHWwn00%2FScreen%20Shot%202019-05-20%20at%2011.09.30%20PM.jpg?alt=media\&token=ba641682-f8f4-4c50-91de-dbac70f7d696)

leader1 接受了 user1 的请求将 title 改成 B，leader2 接受了 user2 的请求将 title 改成 C，当 leader1 与 leader2 同步数据时就出现了冲突。这种问题在单领导复制场景下不会出现。

#### 同步冲突检测与异步冲突检测

容易想到的一种解决写冲突的方式就是同步冲突检测，每次写入数据都等待数据复制到其它复制节点上后才告诉用户写成功，一旦发现冲突则立即反馈。但如果这么做，多领导复制的优势就无从体现，还不如直接使用单领导复制，因此同步冲突检测通常不是好选择。

#### 避免冲突

另一种思路是不让冲突发生，如果应用可以保证所有相同数据的写入都指向同样的 leader，那么冲突就不会发生。当然，这种方案还需要考虑 leader 发生故障的情况，后者可能使得我们的假设不成立。

#### 向某个一致的状态收敛

在单领导复制下，所有的写操作都会按照一样的顺序执行，如果有多个写操作的对象是同一个数据，那么最后一次写操作的结果就是该数据的最终值；在多领导复制下，并不存在真正的顺序，因此最终结果应该是怎样的也不是确定的，如本节开头的例子所示，user1 和 user2 的修改都可能作为最终结果，它们的写操作都是合理的，没有正误和先后之分。如果每个 leader 都按照自己看到操作的顺序来执行，那么不同 leader 的数据就可能出现不一致，这是用户无法接受的。因此，数据库需要有某种方式来解决冲突，让数据库的状态最终收敛，有很多方法可以实现最终收敛：

* 赋予每个写操作一个唯一 ID，以拥有最大 ID 值的写操作为最终结果。
* 赋予每个复制节点一个唯一 ID，以每个写操作发起的节点 ID 大小来确定数据的最终值。
* 用某种方式将数据值合并起来
* 使用特定的数据结构记录冲突信息，并在应用层来解决冲突

#### 定制化解决冲突的逻辑

通常情况下，应用层比数据库更加了解如何解决冲突，因此一些多领导复制的工具允许开发者将冲突解决的逻辑转化成代码，这些代码可能在读数据或写数据的时候执行。

### 多领导复制的拓扑结构

复制的拓扑结构 (replication topology) 描述一个写操作从 leader 传播到其它 leaders 的路径。如果只有两个 leaders，那么只有一种拓扑结构，就是二者直接相连，如果有三个以上的 leaders，就有更多的拓扑结构可供选择，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfMpbHcCa-0C-UDyYFY%2F-LfMqMw5jdHHHd2a_9Zc%2FScreen%20Shot%202019-05-21%20at%208.45.09%20AM.jpg?alt=media\&token=872c415c-4370-4f98-bb99-4462309d4de3)

* 环形/星形：写操作需要经过多个节点才能到达所有 leaders。如果有一个节点出现故障，就可能影响复制消息在其它节点之间传输。
* 全连接形：写操作可以直接到达所有 leaders。如果一些线路的网络速度比其它线路快，就可能出现消息传播出现问题，先发送的消息后到达，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfMpbHcCa-0C-UDyYFY%2F-LfMrp1UYn3WOdYYdold%2FScreen%20Shot%202019-05-21%20at%208.51.30%20AM.jpg?alt=media\&token=7b57af33-aace-486a-957e-2fd3bdc5510e)

这时就需要系统能提供因果一致性支持。

## 无领导复制 (Leaderless Replication)

另一种数据库复制的方法直接抛弃 leader 的概念，允许每个复制节点直接接受 clients 提交的写请求。无领导复制在 AWS 的 Dynamo 提出后迅速流行起来，Riak，Cassandra 和 Voldemort 都是受到 Dynamo 启发成长起来的项目，这些项目也被称为 Dynamo-style。

在一部分无领导复制的实现中，client 直接将写请求发送到多个复制节点；在另外一部分实现中，有一个 coordinator 节点帮助 client 将数据写到数据库中。

### 一个节点宕机情形下的数据写入

想象一个数据库由三个复制节点构成，其中一个复制节点已经失联。在单领导复制下，如果这个失联的节点恰好是 leader，故障转移就不可避免；在无领导复制下，就不存在故障转移的问题。如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfMpbHcCa-0C-UDyYFY%2F-LfMueS4W7Clo6ki_K4O%2FScreen%20Shot%202019-05-21%20at%209.03.53%20AM.jpg?alt=media\&token=c3f1485b-5b21-4a59-bd54-5acb4a969dbc)

假设对于该无领导复制系统，只要两个复制节点同意写入数据就认为数据写入成功，失联节点的响应与否也就不再阻塞写操作的推进。当失联的复制节点，即 replica3 故障恢复后，clients 就又能够继续从 replica3 读数据，这时候由于 replica3 刚刚恢复，部分数据已经过期。为了解决这个问题，clients 会同时向多个复制节点发送读请求，每条数据都会带上版本号，clients 可以根据回复的结果判断哪个是更新版本的数据。

#### Read Repair & Anti-entropy

当一个故障节点恢复后，如何让其数据同步到最新版本？Dynamo-style 系统主要使用两种方式：

*Read repair*

当 client 发现有复制节点还持有旧版本数据时，立即将新版本的数据写入其中。这种方案适用于读频繁的系统。但可能存在某些不常用数据长期不更新的情况。

*Anti-entropy process*

使用背景进程来不断检查数据在不同复制节点之间的差异，然后修正。

#### Quorums for Reading & Writing

假设复制系统中有 n 个复制节点，每个写请求都必须经过 w 个节点同意，每个读请求都必须发送给 r 个节点，只要 w+r > n，我们就可以保证 r 个节点中必然包含最新版本的数据。我们称满足要求的 r 和 w 为多数读 (quorum reads) 和多数写 (quorum writes)。

在 Dynamo-style 数据库中，n、w、r 可以配置，通常的选择是让 n 为某个奇数，然后设定 w 和 r 为 (n+1)/2，即恰好超过半数。当然，你可以自由调节这些参数，如果负载读多写少，增大 w 减少 r 就有助于系统性能提升。

n、w 和 r 的选择同时决定系统可以容忍的故障节点个数：

* 如果 w < n，当一个复制节点故障时，系统仍然可以处理写请求
* 如果 r < n，当一个复制节点故障时，系统仍然可以处理读请求
* n = 3, w = 2, r = 2，系统可以容忍 1 个节点故障
* n = 5, w = 3, r = 3，系统可以容忍 2 个节点故障，如下图所示

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfMpbHcCa-0C-UDyYFY%2F-LfMz92QNoEt4n1WN_wb%2FScreen%20Shot%202019-05-21%20at%209.23.31%20AM.jpg?alt=media\&token=f0d3895c-9a85-41d4-8e7b-4a64f75ed236)

尽管通常 w、r 的值设置为恰好过半数，但实际上只要写请求访问的复制节点与读请求访问的复制节点有重叠即可，因此所谓的 quorum 并不是真正的 quorum。若 w + r <= n，clients 就有可能读到过期数据，与此同时系统的延迟减少、可用性提高，因此 w、r 与 n 的选择实际上是一致性与系统性能以及健壮程度的取舍。

#### 多数一致性的局限性 (Limitations of Quorum Consistency)

* 如果使用 sloppy quorum，w 与 r 可能没有交集。
* 如果两个写请求几乎同时发生，无法判断谁先谁后。
* 如果一个读和一个写请求同时发生，且写请求只传播到了部分节点，未到 w，那么读请求是否应当返回最新的数据？
* 如果写请求成功复制到部分节点，但在另外的节点复制失败，系统返回客户端写数据失败。之前写的结果不会被回滚，此时如果读请求在部分节点上读到了写失败的数据，是否应当返回？
* 如果一个带着最新数据的复制节点发生故障，并通过一个带着旧版本数据的复制节点恢复数据，此时拥有最新数据的复制节点数量将小于 w，破坏了多数条件。
* 即使一切正常，仍然有可能遇到一些时间点带来的 edge cases。

因此，即便 quorums 理论上能保证每次读请求能返回最新版本的数据，在实践上并非简单。Dynamo-style 数据库通常适用于能接受最终一致性的场景。事实上，在单领导复制一节中介绍的写后读、单调读以及因果读一致性在无领导复制场景下都无法保证，后者只能提供最终一致性的保证。更强的一致性保证通常需要事务和共识的帮助。

#### 衡量最终一致性

在运维严重，监控数据库是否返回最新的数据十分重要。即使我们的应用可以容忍读取过期数据，我们仍然需要掌握应用的健康状态，如果应用的数据落后过多，就需要拉响警报。

对于单领导复制场景，数据库通常会暴露复制延时的指标。在但领导复制中，数据写的方向统一经过 leader，因此 leader 可以通过与 follower 之间的差距来计算该指标；对于无领导复制场景，数据写的方向没有固定顺序，对一致性的监控很困难；如果数据库在 clients 读数据时才更新过期数据 (read repair/anti-entropy)，恢复一致性的时间就没有上限。

#### 多 DC 操作

在多领导复制一节中，我们讨论过多 DC 操作，而无领导复制本来就是为容忍网络扰动、并发写冲突、延迟高峰等问题而设计的，因此多 DC 操作对它来说并不难。

Cassandra 和 Voldemort 通过无领导复制的模型来支持多 DC 设置，n 个复制节点分布于所有 DC，在配置中你可以制定每个 DC 放置多少个复制节点。每次写数据，client 都将请求发给所有复制节点，但只等待同一个 DC 内部的多数节点的确认响应，跨 DC 的请求异步处理，从而使得 DC 之间的延迟和网络分区对其不受影响。

Riak 则将 n 个复制节点都放置在同一个 DC 内，clients 与节点的交流都被限制在同一个 DC 内部。跨 DC 的复制由背景进程完成，像多领导复制。

### Sloppy Quorums and Hinted Handoff

尽管 quorums 在理论上能够容忍故障 (fault-tolerant)，但实际上它的容忍能力没有想象中的那么强大。简单的网络扰动就可能将 client 与大部分复制节点分割开，尽管这些复制节点运转正常，其它 clients 也可以正常读写数据，但对于被网络隔离的 client 来说，它可能无法再获得 w 或 r 个复制节点的回复。在更大的集群中，client 被网络隔离的发生频率可能更高，这时候数据库的设计者就面临一种权衡：

* 在无法获得 w 或 r 个复制节点回复的情况下直接抛错
* 仍然接收写请求，然后将数据写入 n 个复制节点之外的节点中，等待网络隔离恢复后，再把相关写操作同步到 n 个复制节点中

后者称为 sloppy quorum，网络隔离恢复后的同步称为 hinted handoff。sloppy quorum 对于增加写可用性，因为只要 w 个节点中的任意一个可用即可，然而这意味着即使 w + r > n，你也无法保证读请求能获取最后写入的数据，因为后者可能正被临时存放在 n 个复制节点外的节点。

sloppy quorums 在 dynamo-style 数据库中属于可配置项，Riak 默认开启，而 Cassandra、Voldemort 默认关闭。

### 并发写的检测

Dynamo-style 数据库允许多个 clients 向同一个 key 并发写数据，这意味着即使使用 strict quorum 配置，写冲突仍然可能发生，这种现象与多领导复制面对的问题类似。举例如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfXBT-8oLAx6cNHOsvc%2F-LfXI9OJLWhJaq_u5uKO%2FScreen%20Shot%202019-05-23%20at%209.27.07%20AM.jpg?alt=media\&token=d61bc75b-63cc-4ac6-8d2e-2657aad16738)

A 和 B 同时向数据库发送写入 X 的请求，但请求到达不同节点的时间点不一样：

* node1 收到 A 的写请求，但因为故障没收到 B 的写请求
* node2 先收到 A，后收到 B
* node3 先收到 B， 后收到 A

如果这种情况不加以制止，数据库将长期保持在数据不一致的状态，如上图所示，get X 操作既可能返回 A，也可能返回 B。

为了保证最终一致性，复制节点需要保证数据库中的数据向一个稳定的方向收敛，目前数据库本身对此并没有很智能、很自动的方法，因此应用开发者需要知道数据库内部如何处理冲突写问题。

本节最后再讨论一些并发写冲突的处理技术。

#### Last Write Wins (LWW)

让各个复制节点达到最终一致性的方法之一就是指保留最新的数据，任何旧的数据都将被覆盖，因此只要我们能够确定地在集群中判定写操作的先后顺序，就可以让所有复制节点上的数据收敛。

首先，这里的写操作没有顺序，我们说这些写操作是并发的就等价于说这些操作的顺序无法定义；即便如此，我们让然可以强加一些顺序，如给每个写操作加上时间戳，只取带着最大时间戳的数据为最终的数据值，在此之前的数据都被抛弃。这种冲突解决算法是 Cassandra 唯一支持的算法，是 Riak 的可选算法之一。

由于使用 LWW 算法可能导致数据丢失，即便所有的写请求都返回写入成功，最终只有一个数据被保留，在 一些场景如缓存下，这种数据丢失可以接受；在其它场景下则可能无法接受。因此在 LWW 算法下，唯一安全的策略就是在应用逻辑上保证所有写操作的 key 全局唯一，每个数据只会被写入一次而不再改变。

#### Happens-before Relationship

假设有 A、B 两个写操作，那么 A 和 B 之间的关系只可能有三种：

* A 在 B 之前发生
* A 和 B 并发
* A 在 B 之后发生

如果有算法能够捕捉到这种发生先后的依赖关系，我们同样能够让集群数据得到收敛。想象下图场景：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfbKCFCy0zD1qFaZFym%2F-LfbMM3ahgAYVBIrHcgI%2FScreen%20Shot%202019-05-24%20at%209.03.34%20AM.jpg?alt=media\&token=55f90683-0f34-403a-b967-601d51ed3a26)

1. client1 将 milk 放入购物车 (cart)，数据库之前尚未有 key  为 cart 的数据，于是存下 milk，并赋予 version1，并将数据和 version 都返回给 client1。
2. client2 将 eggs 放入同一个购物车 (cart)，但他并不知道 client1 已经放入 milk，数据库发现 client2 的请求没有任何 version 信息，因此可以认为 client2 与 client1 的写入操作是并发的，于是数据库将 eggs 和 milk 分别存储，并赋予 version2，将数据和 version 都返回给 client2。
3. client1 此时并不知道 client2 写入了数据，他希望将 flour 加入购物车，且认为加入后购物车中的数据为 \[milk, flour]。数据库通过版本号得知 client1 的请求是针对 version1 的状态，因此数据库将 \[milk, flour] 以及 \[eggs] 都写入，赋予 version3，覆盖 version1，但保留 version 2 的 \[eggs]，将数据和 version 返回。
4. 在此期间，client2 想要将 ham 放入购物车，在上一次返回信息中，client2 得知数据库中有 milk 和 eggs，因此他认为当 ham 放入购物车时，数据库中应当存有 \[eggs, milk, ham]。数据库收到请求后，发现 client2 的请求基于 version2，于是用新的数据覆盖 version2，生成 version4，返回给 client2。
5. 最后，client1 想加入 bacon，类似地，数据库将数据合并后赋予 version5。

我们发现在整个过程中，数据不会像在 LWW 算法中一样被随意覆盖，每个请求都包含有前序请求，从而保证历史可追溯，请求的依赖如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LfbKCFCy0zD1qFaZFym%2F-LfbPvGoPXoTimf-Ahm2%2FScreen%20Shot%202019-05-24%20at%209.19.09%20AM.jpg?alt=media\&token=9f0ad41e-c2ac-408e-98e8-6bf3423821d2)

整个算法描述如下：

* server 为每个 key 维护一个 version number，每次写操作发生，number 递增
* 当 client 读取 key，server 返回所有未被覆盖的数据，以及 version number，每个 client 写之前必须先读取 key
* 当 client 写入 key，必须在请求中包含上次读时获取的 version number，并将上次读取到的所有数据与新写入的数据合并，发送给 server
* 当 server 收到写请求，知道前序 version number 后，就可以将在它之前的版本数据覆盖。

每次 client 写入数据，都需要将新数据与上次读到的数据合并，这个过程放在应用层做非常复杂且容易出错，因此许多研究者也在思考如何将这种合并操作自动化。Riak 使用一系列数据结构，即 CRDTs，来自动合理地合并数据。

*Version Vectors*

上小节讨论了在一个复制节点下的捕捉 happens-before 依赖关系的算法，如何把这种算法拓展到多个复制节点呢？简单地说，每个复制节点需要保留一个 version number，所有复制节点的 version number 合并起来就是 version vectors，Riak 2.0 中使用了类似的算法。

## 参考

DDIA: chapter 5