DDIA: 数据复制

复制主要是指通过网络在多台机器上保存相同的数据副本。通过数据复制，我们期望能够达到以下目的：

• 降低访问延迟：使数据在地理位置上更接近用户
• 提高可用性（容错）：当部分节点异常，系统仍然可以继续提供服务
• 提高读吞吐量：多个数据副本可以同时提供数据访问服务

在讨论数据复制时，假设集群中的每一台机器都能保存完整的数据集副本。

数据复制的难点在于如何处理持续更新的数据；常见的数据复制方法有三种：主从复制，多主节点复制，无主节点复制。

主从复制

每个保存数据库完整数据集的节点称为副本。当存在多个副本，如何保证不同副本之间的数据一致性是需要考虑的问题。常见的解决方案基于主从复制，其基本流程如下：

1. 指定某个副本为主副本。当客户端写数据时，必须将写请求发送给主节点；而主节点首先将数据写入本地存储
2. 其他副本称为从副本。主节点将新数据写入本地之后，再将数据更改作为复制的日志或者更改流发送给所有的从副本。每个从副本获得更改日志后将其应用到本地，并且严格保持与主副本相同的写入顺序。
3. 客户端从数据库中读数据时，可以在主副本或者从副本上执行查询。

只有主副本可以接受写请求，从副本只读

同步复制与异步复制

在将数据由主节点复制到从节点时，可以选择使用同步复制还是异步复制。

结合上图的流程，假设用户需要更新自己的首页头像图片，基本流程为：用户将更新请求发送到主节点，主节点收到更新请求并更新自身数据，之后将数据更新发送给从节点。之后，主节点通知用户更新完成。

主从复制，包括一个同步的从节点，一个异步的从节点

在上图中，从节点 1 同步复制：主节点需要等待直到从节点 1 完成写入；

从节点 2 异步复制：主节点发送完消息之后立即返回，不用等待从节点 2 的完成确认。

对于异步复制，可能会导致从节点落后主节点较长的时间；比如从节点 2 在收到复制日志之前，有较大的延迟。

对于主从复制，系统并没有保证一定会在多久时间内完成复制

同步 VS 异步

1. 同步复制的优点：一旦向用户确认，从节点可以明确保证完成了与主节点的更新同步，数据已经处于最新版本。即使此时主节点发生了故障，也是可以在从节点继续访问最新的数据。
2. 同步复制的缺点：如果同步的从节点无法完成同步确认（可能是从节点崩溃，或者网络故障等），那么用户写入就不能视为成功。主节点会阻塞其后所有的写操作，直到同步副本确认完成，从而影响整体的性能。
3. 异步复制的优点：不管从节点上数据多么滞后，主节点总是可以继续响应写请求，系统的吞吐性能更好。
4. 异步复制的缺点：如果主节点发生故障且不可恢复，那么所有尚未复制到从节点的写请求都会丢失。意味着即使向客户端确认了写操作，却无法保证数据的持久化。

结合上述优缺点，如果把所有的从节点设置为同步复制，那么任何一个同步节点的中断都会导致整个系停滞不前。所以在实践中，通常是其中一个从节点是同步的，而其他节点是异步模式。这样可以保证至少两个节点拥有最新的数据副本，这种配置也被称为半同步。

配置新的从节点

如果需要增加新的副本以提高容错能力或者替换新的副本，那么就需要配置新的从节点，此时需要确保新的从节点与主节点保持数据一致。

在配置新的节点时，客户端仍然会不断地往主节点中更新数据，因此常规的文件拷贝方式会导致不同的节点上呈现出不同时间点的数据，不能保证数据一致；另外，锁定数据库（使其不可写）的方式会使得整个服务无法处理写请求，违反高可用的设计目标。

不停机，数据服务不中断地配置新的从节点的步骤：

1. 在某个时间点对主节点的数据副本产生一个一致性快照（避免长时间锁定）

   创建快照时，快照与系统复制日志的某个确定位置相关联，在 MySQL 中称为 binlog coordinates，PostgteSQL 中称为 log sequence number

2. 将快照复制到新的从节点

3. 从节点连接到主节点并获取快照点之后发生的数据更改日志

4. 根据获得的日志，从节点将这些快照之后的所有数据变更应用到本地，这个过程称为追赶。之后可以继续复制变更日志，从而保证数据一致

处理节点失效

我们期望通过主从复制来实现系统的高可用，即使部分节点失效，仍然能够保证系统总体的持续运行。

从节点失效：追赶式复制

从节点的磁盘上保存了接收到的数据变更日志；如果从节点崩溃后重启，可以在将本地日志应用后，连接到主节点，请求中断期间所有的数据变更日志，并应用到本地来追赶主节点。之后就和正常情况一样持续接收来自主节点的数据流变化。

主节点失效：节点切换

主节点失效的话，需要涉及到主从身份的状态转换；切换过程如下：

1. 确认主节点失效：节点失效可能有多种原因：系统崩溃，停电，网络问题等；大部分系统都采用基于超时机制来确认节点的有效性：节点之间互相频繁发送心跳存活消息，如果发现某个节点在一段比较长时间内（如 30s）没有响应，那么就可以认为节点失效。
2. 选举出新的主节点：新的主节点可以通过选举的方式来确认（多数节点达成共识）；也可以由之前选定的某控制节点来选定新的主节点。候选节点最好与原主节点之间的数据差异最小，可以减小数据丢失的风险。
3. 重新配置系统使新主节点生效：新主节点确认之后，客户端需要将写请求路由到新的主节点，同时其他从节点要接受来自新主节点上的数据变更；而且我们要确保原主节点重新上线之后被降级为从节点，并认可新的主节点，不然可能会存在脑裂问题。

在主从切换的过程中仍然存在许多问题：

1. 如果系统使用异步复制，失效前原主节点并没有将最新数据复制到从节点；那么原主节点失效后重新上线，但是并没有意识到角色变化，仍然会尝试同步其他从节点，那么新的主节点就会收到冲突的写请求。常见的解决方案是，原主节点上未完成复制的写请求直接丢弃（可能会违背数据更新持久化）
2. 可能会有两个节点都认为自己是主节点（脑裂），这两个主节点都可能接受写请求，从而导致数据丢失或破坏。这种情况下，可以强制关闭其中一个节点。
3. 健康检测超时时间的设置：如果设置超时时间过长，那么主节点失效之后总体的恢复时间就较长；如果超时时间过短，那么就会导致不必要的主从切换，可能会对系统性能及可用性造成严重影响（响应时间增长，延迟增加等）

复制日志的实现

• 基于语句复制：主节点记录每个写请求的操作语句，并将该语句作为日志发送给从节点
• 基于预写日志(WAL)传输：所有对数据库的更新都会被记录到预写日志中，因此可以使用该日志在另一个节点上构建副本
• 基于行的逻辑日志复制：逻辑日志是指一些列记录来描述数据表行级别的写请求，如 MySQL 中的 binlog
• 基于触发器复制：通过触发器注册自己的应用层代码，使得当系统数据发生更改时，自动执行自定义代码

复制滞后

支持容错（提高可用性）是使用复制的其中一个原因，可扩展性（使用多节点来处理更多的请求）和低延迟（将副本部署在地理上距离用户更近的地方）也是我们的目标。

主从复制中只有主节点支持写，从节点只读。我们可以通过添加较多的从节点来提高读请求的吞吐量；不过其复制方式只能选择异步复制。

如果使用同步复制所有从节点，那么单个节点故障或者网络中断都会使得整个系统无法写入；而节点越多，发生故障的概率越大。

不过使用异步复制会使得主从节点之间产生数据不一致问题，这种不一致只是一个短暂的状态，如果停止写数据库，那么经过一段时间之后，从节点最终会与主节点的数据保持一致，被称为最终一致性。

最终一致性不能保证主从之间延迟的时间，理论上没有上限。

读自己的写

对于读负载高，写负载低的系统，通常的实现方式是：提交数据发送到主节点，但是当用户读取数据时，数据可能来自从节点。

不过，对于异步复制来说，从节点数据存在滞后问题；如果用户在更新数据之后立马查看数据，那么读请求可能会发送到滞后的从节点上，从而无法查看到最新的数据。

用户发起写请求，然后在滞后的副本上读取数据，此时需要 read-after-write 一致性

为了避免上述情况发生，需要实现“写后读一致性”，即“读写一致性”：用户读取自己更新的数据时，总能看到最近的更新；但是对其他用户没有任何保证，其他用户可能过段时间才能看到该更新。

实现读写一致性有多种方案：

1. 用户总是在主节点读取与自己相关的数据，而在从节点读取其他用户的数据
2. 数据更新一段时间范围内（如一分钟）均从主节点读，超过该阈值则从从节点读；该方案需要监控主从延迟
3. 客户端请求时携带数据最近的更新时间戳，服务端收到请求之后先判断当前节点是否包含最新的数据（比较时间戳），如果包含则直接处理，否则将请求转发给另一个节点处理

单调读

对于异步复制还可能出现另一种问题：用户从多个副本进行了多次读取，可能会出现前一次读取返回了较新的数据，后一次读取返回了旧数据；看起来感觉用户数据回滚了。

用户读取到最新内容之后有读到了过期的内容，此时需要单调读一致性

为了避免数据回滚的现象，我们可以采用“单调读一致性”：这是一个比强一致性弱，但是比最终一致性强的保证。

为了实现单调读，我们需要确保每个用户总是从固定的一个数据副本进行读取（不同用户可以访问不同副本）。比如，根据用户 ID hash 来确定副本。

前缀一致读

由于多个从节点的滞后程度不同，导致观察者先看到结果后看到原因

为了防止这种问题，需要保证“前缀一致性读”：对于某个顺序的写请求，那么读取时也需要按照相同的顺序。

为了实现前缀一致性读，可以将具有因果关系的写入都交给同一个数据分区来完成。

复制滞后的解决方案

对于最终一致性系统，我们需要考虑如果主从延迟增加到几分钟或者几小时，该系统表现是否符合预期。如果不符合预期，那么需要更强的一致性保证，比如写后读，单调读等。

如果需要强一致性，那么就需要引入共识机制。

多主节点复制

主从复制的缺点是：只有一个主节点，所有写入都必须经过主节点；那么系统的写入操作可扩展性不强，同时如果主节点异常阶段会使得系统写入被阻塞。

可以根据主从模型进行扩展，配置多个主节点，每个主节点都可以接受写请求；每个主节点都需要将数据更改转发到其他所有节点，这种方式被称为多主节点复制。

每个主节点同时是其他主节点的从节点

适用场景

多数据中心

在一个数据中心内适用多个主节点没有太大意义，反而使系统更加复杂，比较合适的场景是多数据中心。

为了容忍数据中心级别的故障，可以把数据库的副本横跨多个数据中心。可以在每个数据中心配置一个主节点；每个数据中心内采用常规的主从复制方案；而在数据中心之间，各个数据中心的主节点来负责同其他数据中心的主节点进行数据交换，更新。

对于多数据中心，如果采用主从复制，由于主节点只能存在其中一个数据中心内，会导致所有写请求都会经过该中心，反而会影响系统性能

横跨多数据中心的多主节点复制模型

如果数据库还采用了分区，那么不同分区的主副本可能存放在不同的主节点上，但是对于给定的某个分区，只有一个主节点。

多主复制 VS 主从复制

1. 性能

   对于主从复制，每个写请求都需要发送到主节点所在的数据中心，会导致延迟大大增加。

   在多主复制中，每个写操作都可以在本地数据中心操作，然后采用异步复制的方式将更新同步到其他数据中心，性能更好。

2. 数据中心失效容忍

   如果主从复制的主节点所在中心失效，那么需要从另一个数据中选取从节点作为主节点。

   在多主节点模型中，每个数据中心都可以独立与其他中心运行；可以等到失效的中心恢复后再将数据同步过去。

3. 网络问题容忍

   数据中心之间的通信没有中心内可靠。对于主从复制，写操作是同步操作，对于中心之间的网络稳定性更加依赖；多主节点模型通常采用异步复制，能够更好容忍这类问题。

虽然多主复制有各种优势，但是也有一个很大的缺点：不同数据中心可能会同时修改相同的数据，因而产生写冲突。

处理写冲突

两个用户同时编辑 wiki 页面，用户 1 将标题从 A 改为 B，同时用户 2 将标题从 A 改成了 C。每个用户都将更新顺利提交到本地主节点，但是当数据被异步复制到对方时，发现存在写冲突。

多个主节点同时更新同一条记录产生写冲突

处理写冲突的方案有：

1. 同步与异步冲突检测

   同步冲突检测：等待写请求同步到所有副本后，再通知用户写入成功；但是这样会失去多主节点的优势。

2. 避免冲突

   在应用层保证对特定记录的写请求总是通过同一个主节点，这样就不会产生写冲突。

3. 收敛于一致状态

   不管是主从复制还是多主复制，至少应该确保数据在所有副本中的最终状态一定是一致的。实现收敛可能有以下方式：

   • 每个写入分配 uuid，挑选最高的 id 写入作为胜利者，被称为最后写入者获胜。但是这种方式很容易造成数据丢失。
   • 以某种方式将冲突的值合并，例如按照字母顺序排序后拼接，A/B

多主复制的拓扑结构

复制的拓扑结构描述了写请求从一个节点传播到其他节点的通信路径。

常见的拓扑结构有：

• 环形拓扑
  • 每个节点接收来自前序节点的写入，并将这些写入（加上自己的的写入）转发给后序节点
• 星型拓扑
  • 一个指定的根节点将写入转发给所有其他节点
• 全部至全部型
  • 每个主节点将其写入同步到其他所有主节点

无主节点复制

单主节点 & 多主节点复制中，客户端先向主节点发送写请求，然后系统将写请求复制到其他副本。对于无主节点复制，选择放弃主节点，允许任何副本直接接收来自客户端的请求。

亚马逊的 Dynamo 系统是无主复制的典型

在有些无主节点系统中，客户端直接将写请求发送到多副本；而在另一些系统中，由一个协调者节点代表客户端进行写入。

节点失效时写入数据库

对于主从复制模型，主节点失效时，如果想继续处理写操作，那么需要先进行节点切换；对于无主节点模型，则不需要节点切换。

1. 客户端将写请求并行发送给三个副本，有两个副本可以正常处理请求，而失效的副本无法处理。如果两个正常工作的节点可以成功确认写操作，那么客户端收到两个确认之后，即可认为写入成功；完全忽律其中一个副本无法写入的情况。
2. 失效的节点重新工作后，在其失效期间的数据尚未同步，此时用户可能会访问到过期的数据。因此，当客户端读取数据时，将读请求并行发送给三个副本；多个副本的响应结果可能不同，可以通过版本号等技术确定哪个值更新。

读修复 & 反熵

复制模型应该确保所有数据最终复制到所有副本上。为了保证失效节点重新追上错过的写请求，经常使用两种机制：

1. 读修复

   当客户端并行读取多个副本时，可以检测到过期的返回值；因而可以将新值写入该副本，这种方法适合频繁读取的场景。

2. 反熵过程

   通过一些后台进程不断查找副本之间的数据差异，将任何缺少的数据从一个副本复制到另一副本。

   与基于主节点复制的复制日志不同，反熵过程并不保证数据以特定的顺序复制写入，并且会引入明显的滞后。

有的系统可能没有实现反熵过程，那么当缺少反熵过程时，由于读修复只在发生读取时才能执行修复，那么对于一些很少访问的数据来说，有可能在某些副本中已经丢失而无法被检测到，从而降低写的持久性。

读写 quorum

一般情况下，如果有 n 个副本，写入需要 w 个节点确认，读取至少查询 r 个节点，则只要 w + r > n，那么读取的节点中一定会包含最新值。在之前的例子中，n = 3, w = 2, r = 2；满足上述这些 r, w 的读写操作称之为法定票数读（仲裁读）或法定票数写（仲裁写）。

r & w 是用于判断读写是否有效的最低票数；通常 w = r =(n+1)/2

仲裁条件 w + r > n 定义了系统可容忍的失效节点书：

• w < n，如果一个节点不可用，仍然可以处理写入
• r < n，如果一个节点不可用，仍然可以处理读取
• 假定 n = 3, w = 2, r = 2，则可以容忍一个节点不可用
• 假定 n = 5, w = 3, r = 3，则可以容忍两个不可用的节点

通常，读取与写入总是并行发送到所有的 n 个副本；参数 w & r 只是决定要等待的节点数，即有多少个节点需要返回结果，才能判断出结果的正确性

如果可用节点数小于 w 或者 r，那么写入或者读取就会返回错误。

Quorum 一致性的局限性

w + r > n 使客户端能够获取最新值是因为，成功写入的节点集合和读取的节点集合必然有重合，这样读取的节点中至少又一个具有最新值。

通常会假定 w & r 为大多数（多于 n / 2）节点，此时能够容忍 n / 2 个节点故障；但是 quorum 并不一定非得是多数，读写的节点集中又一个重叠的节点才是关键。

如果 w + r ≤ n，此时可以获得更低的延迟和更高的可用性；但是读取请求中可能恰好没有包含最新值的节点，客户端就会获取一个过期的旧值。

不过，即使满足 w + r > n，也可能存在返回旧值的边界条件：

• 如果采用了 sloppy quorum，那么写操作的 w 个节点和读取的 r 个节点可能完全不同，因此无法保证读写请求一定存在重叠的节点
• 如果写操作与读操作同时发生，写操作肯跟仅在一部分副本上完成，此时读取返回是旧值还是新值存在不确定性
• 如果某些副本写入成功，其他副本写入失败，且成功副本数 < n，哪些成功的副本不会进行回滚；那么后续的读仍可能返回新值
• 两个写操作同时发生，无法明确先后顺序；这种情况下采用了 Last Write Win 方案，此时可能会把新值给抛弃

虽然 Quorum 设计上似乎可以保证读取最新值，但是实际情况往往更加复杂。

宽松的 Quorum & 数据回传

Quorum 可以容忍某些节点故障或者变慢，并且只需要等待 w / r 个节点的响应（而不是 n 个节点），所以对于高可用与低延迟的场景还是很有帮助。

考虑网络中断的情况，假设某个客户端无法维持满足最低的 w & r 所要求的连接数，从而无法正常工作；但是能够连接到其他数据库节点，只不过这些节点不再 n 个节点的集合中。这种情况下，我们可以采用宽松的 Quorum 机制：写入和读取仍然需要 w & r 个成功的响应，但是包含了哪些并不在之前指定的 n 个节点集合中。一旦网络问题得到解决，临时节点需要把接收到的写入全部发送到原始节点上，即数据回传。

Sloppy Quorum 对于提高写入可用性比较有帮助：只要任何 w 个节点可用，数据库就可以接受新的写入；然而这会意味着即使满足w + r > n，也不能保证在读取某个记录时，一定能够读到最新值。

因为新值可能被临时写入 n 之外的那些节点且尚未回传过来

并发写冲突

Dynamo 风格的数据库允许多个客户端同时对相同的记录进行并发写，即使采用严格的 quorum 机制也会发生写冲突；同时，读时修复 & 数据回传也会导致并发冲突。

并发写时缺乏顺序保证

最后写入者获胜

有一种可以实现最终收敛的方式：每个副本总是保存最新值，允许覆盖并丢弃旧值。

丢弃并发写入

为了确定写入的顺序，可以强制对并发写入进行排序：可以为每个写请求附加一个时间戳，然后选择最大的时间戳，丢弃较小的时间戳写入（Last Write Win）。LWW 可以实现最终的收敛，但是是以牺牲数据持久化为代价（多个并发写只会保留一个，其他的都会被丢弃）。

如果某些场景可以接受覆盖写，那么可以使用 LWW；如果覆盖，丢失数据不可接受，那么 LWW 不是解决冲突的好选择。

Happen-Before 关系和并发

对于两个动作 A，B：

• 如果 B 知道 A，或者依赖 A，或者以某种方式在 A 基础上构建，则称 A 在 B 之前发生
• 如果两个操作都不在另一个之前发生，或者两者都不知道对方，那么 A & B 是并发的

因此对于 A，B 两个动作，一共有三种可能性：A 在 B 之前发生，B 在 A 之前发生，A & B并发。

通常如果两个动作同时分发生，那么可以称为并发；但是由于分布式系统时钟的问题，很难严格确定发生的时间是否相同。因此，为了更好地定义并发，我们并不依赖确切的发生时间，即不管物理的时机如何，如果两个操作都不需要意识到对方，即可称其为并发操作。

下面是两个客户端同时向购物车添加商品：

并发操作购物车说明事件的因果关系

对应的时序图

合并同时写入的值

如果使用 LWW 的话，会有部分数据丢失；为了防止数据丢失，可以将并发的值进行合并。

版本矢量

还有一种方法：为每个副本和每个主键均定义一个版本号，每个副本在处理写入时增加自己的版本号，并跟踪从其他副本看到的版本号。通过这些信息来确定要覆盖哪些值，保留哪些并发值。