分布式数据库：单主复制、多主复制和无主复制

为什么需要副本：

• 使得数据与用户在地理上接近（从而减少延迟）
• 即使系统的一部分出现故障，系统也能继续工作（从而提高可用性）
• 扩展可以接受读请求的机器数量（从而提高读取吞吐量）

复制的困难之处在于处理复制数据的变更（change）  ，为此诞生了三种流行的变更复制算法：单领导者（single leader），多领导者（multi leader）和无领导者（leaderless）。

1 基于领导者的复制

基于领导者的复制（leader-based replication），也称为主动/被动、主/从复制

1. 副本之一被指定为领导者（leader，也称为主库）。其他副本被称为追随者（followers，也称只读副本、从库、备库）
2. 当客户端要想向数据库写入时，将请求发给领导者，领导者将新数据写入其本地存储。同时领导者将数据变更发送给所有追随者，称之为复制日志（也称变更流）。
3. 每个追随者拉取日志并更新本地数据库副本，并执行保存。
4. 只有领导者才能接收写操作，对于客户端来说，从库都是只读的。

许多关系数据库都内置了主从复制，非关系数据库和某些不是数据库也有所使用（MongoDB、Kafka、RabbitMQ等）

1.1 同步复制与异步复制

• 同步复制：能保证有与主库一致的最新数据副本，如果主库突然失效，从库上也能找到数据。而异步复制不行。
• 异步复制：主库发送消息时不需要等待从库的响应。同步复制时若从库没有响应，主库就无法处理写入操作，会阻止所有写入。

实际情况下通常使用半同步，将一个追随者设置为同步，其他追随者设置为异步。

1.2 设置新从库

在客户端不断向数据库写入数据时设置新从库，不能简单的复制，因为数据总是在变化。

锁定数据库会违背高可用的目标，如何不停机的拉起新从库呢：

1. 获取主库的一致性快照，而不必锁定整个数据库。
2. 将快照复制到新从库节点
3. 从库连接主库，拉取快照之后的所有数据变更。这依赖于快照与主库复制日志中的位置（例如MySQL 的二进制日志坐标-binlog coordinates）。

1.3 处理节点宕机

目标：即使个别节点失效，系统也能运行，并尽可能控制节点停机带来的影响。

在以下情况时，可以用如下方法：

从库失效：追赶恢复

从库可用从日志中知道，发生故障之前处理的最后一个事务。所以从库连接回主库后，请求这些数据变更即可。

主库失效：故障切换

手动或自动进行。步骤如下：

1. 确认主库失效。（大部分系统使用超时来确认）
2. 选择一个新数据库。可用通过选举过程或控制器节点来指定新数据库，一般使用拥有旧主库最新数据副本的从库。
3. 重新配置系统以启用新数据库。系统需要确保老主库回来时变成一个从库。

故障切换会有很多问题：

• 异步复制时，老主库加入回集群后，新主库可能收到老主库宕机前还没发出去的写入操作，从而造成冲突。而丢弃掉老主库未复制的写入会打破对于持久性的期望
• 当数据库需要和其他外部存储相协调时，丢弃写入内容是极其危险的操作。例如GitHub的一次事故中，Redis的主键比新主库的主键新，造成了一些数据的泄露。
• 两个节点都认为自己是主库的情况称之为脑裂（split brain），十分危险。两个主库都可用接受写操作，却没有冲突解决机制，数据会造成丢失和损坏。一些系统会在检测到两个主库节点时关闭一个，诞生粗糙的设计可能导致两个主库都关闭。
• 主库被宣告死亡时应该如何配置？超时时间设置得越长，恢复需要的时间也越久，但是设置太短会造成不必要的故障切换。

节点故障、不可靠的网络、对副本一致性，持久性，可用性和延迟的权衡 ，这些问题实际上是分布式系统中的基本问题。第8章和第9章将更深入地讨论它们。

1.4 复制日志的实现

基于语句的复制

不能使用基于语句的复制，即简单的将SQL语句记录

• 非确定性函数会产生不同的值，例如NOW()或RAND()
• 自增列（auto increment）使每个副本执行语句的顺序必须一致
• 有副作用的语句（触发器、存储过程、用户定义的函数）可能在每个副本上产生不同的副作用

传输预写式日志（WAL）

在第三章中说过，写操作通常都是追加到日志中（LSM树，B树的预写式日志）。日志是包含所有数据库写入的仅追加字节序列，主库直接将日志发给从库，就可以建立与主库一模一样的数据结构的副本。

缺点：日志记录的数据非常底层，WAL包含哪些磁盘块中哪些字节发生改变，复制与存储引擎紧密耦合，这使得主库和从库的数据库版本需要一致。若非如此，就可以先升级从库，然后故障切换，从而使数据库软件不停机升级。

逻辑日志复制（基于行）

存储引擎的日志是物理表示，逻辑日志使复制日志从存储引擎内部分离出来。

逻辑日志通常以行未粒度记录序列：

• 插入时，日志包含所有列的新值
• 删除时，日志通过唯一标识，如果没有主键则需要记录列的所有值
• 更新时，日志包含唯一标识和列的新值

修改多行事务会生成多个这样的日志记录，后面跟着一条记录指出事务已提交（MySQL的二进制日志用的就是这种方法）

逻辑日志更容易保持向后兼容，也能更好的被外部应用程序解析，可以更容易将数据库内容发到外部系统（数据变更捕获）

基于触发器的复制

触发器提高了复制的灵活性，我们可以只复制数据的一个子集、复制到不同种类的数据库、解决冲突逻辑。

触发器使得数据库发生数据更改时自动执行程序代码。它将更改记录到一个单独的表中，使用外部程序读取这个表，即可使用业务逻辑处理，以将数据变更复制到另一个系统中。

触发器会使得开销变大，使得复制更容易出错，也存在许多限制。

2 复制延迟问题

当客户端从异步的从库中读取数据时，由于复制延迟问题，主库和从库的数据有可能不一致，同样的语句会可能读出不同的结果。这种不一致只是暂时的，等一段时间从库就会赶上并与主库保持一致，这种效应称为最终一致性。

但是，滞后时间太长会产生一些问题，接下来介绍几种情况和解决方法

读己之写

异步复制时，用户写入后马上查看数据，新数据有可能还没到达副本。这种情况下，我们需要读写一致性，也称读己之写一致性。

如何实现（基于领导者复制系统）：

• 读取用户可能已经修改过的内容时，都从主库读。读取自己的信息时都从主库读，读取别人信息时从从库中读。
• 跟踪上次更新的时间，例如上次编辑完一分钟内，从主库读。
• 客户端记住最近一次写入的时间戳，当发现获取到的数据不够新时，从另一个从库中读取，或者等待从库更新完成。、

注意i：当副本分布在多个数据中心时，复杂性会增加，任何由主库提供服务的请求都必须路由到包含主库的数据中心

当同个用户用不同设备读写时，事情变得更加复杂：

• 记住用户上次更新的时间戳变得困难。
• 副本分布在不同数据中心时，无法保证设备连接会路由到同一数据中心。

单调读

当用户向不同从库进行多次读取，可能会发生时光倒流：用户可能先读到一个更新完的库，然后再读到一个尚未更新的库。

单调读保证这种异常不会发生。这种保证比强一致性弱，但比最终一致性强。

实现：确保单用户总是从同一从库进行读取。可以基于用户ID的散列来选择从库，而不是随机选择。注意，当从库宕机时需要重新路由。

一致性前缀读

假设A和B数据通过不同的客户端发出，且两者存在逻辑关系，此时由于复制延迟问题，A和B可能会在某个库中打乱顺序，这样就违反了因果关系。

例如a发送了A消息给b，b用B消息回答了a，由于复制延迟问题，A消息和B消息在某个从库中被打乱，后来c要去查看群消息中a和b讨论了什么时，A消息和B消息c就看不懂了。

一致前缀读用于防止这种异常：如果一系列写入按照某个顺序发生时，任何人读取这些写入时，也会看见他们以同样的顺序出现。

这是分区数据库中的一个特殊问题，将会在第6章中讨论。

3 多主复制

多领导配置允许多个节点接受写入，同时每个领导者也是其他领导者的追随者。

3.1 多主复制的应用场景

运维多个数据中心

当只有一个数据库，且副本分散在不同的数据中心时，多领导配置可以在每个数据中心都有主库。

多主的优点

• 性能：多主写入时间更短
• 容忍数据中心停机：单主可以使另一个数据中心的追随者成为领导者。多主可以直接切换其他数据中心运行。
• 容忍网络问题：单主配置对于网络连接问题非常敏感

多主的缺点：两个不同数据中心可能会同时修改同一个数据，这样会造成写冲突。

需要离线操作的客户端

当应用程序需要在断网后仍能继续工作时，如果在离线状态下进行任何更改，那么下一次上线时需要与服务器和其他设备同步。

这种情况下，每个设备都有一个充当领导者角色的本地数据库，并且在所有设备上的副本之间同步时，存在异步的多主复制过程。复制延迟取决于什么时候访问互联网，可能是几小时甚至几天。

协同编辑

多个人同时编辑同一份文档时，通常不会将其视为数据库复制问题。当用户进行协作式编辑时，更改立即应用到其本地副本，并异步复制到服务器和编辑同一文档的任何其他用户。

为了保证不发生编辑冲突，应用程序要先取得文档的锁定，即另一个用户提交时，需要等上一个用户提交修改并释放锁定。

3.2 处理写入冲突

多领导者复制的最大问题就是可能发生写冲突

同步与异步冲突检测

单主数据库中，第二个写入会被阻塞并等待第一个写入完成，或者终止第二个写入事务并强制用户重试。而多主配置中，两次的写入都是成功的。

冲突检测同步：等待写入被复制到所有副本，再告诉用户写入成功。但是这样就和单主复制没区别了。

避免冲突

应用程序可以确保同一用户始终路由到同一个数据中心，这样就不会出现冲突问题。

当数据中心出现故障，或者用户跑到离另一个数据中心更近的位置时，不同主库同时写入又有可能出现了。

收敛至一致的状态

单主库按顺序应用写操作：如果同一个字段有多个更新，则最后一个写操作将确定该字段的最终值

多主配置中，写入顺序没有定义，所以两个主库的最终结果可能不同，那么数据将处于数据不一致的状态。收敛使得所有副本必须在所有变更复制完成时收敛至一个相同的值。

实现冲突合并解决有许多种方式：

• 最后写入胜利（LWW）：给每个写入一个唯一的时间戳，挑最高的时间戳的写入作为胜利者，丢弃其他写入。
• 以某种方式将这些值合并，然后连接它们。
• 在保留所有信息的显示数据结构中记录冲突，并编写解决冲突的应用程序代码（可以通过提示用户的方式）。

自定义冲突解决逻辑

大多数多主复制工具允许应用程序编写冲突解决逻辑，代码可以在写或读时执行

• 写时执行：只要数据库系统检测到复制更改日志中存在冲突时调用。
• 读时执行：当检测到冲突时，所有冲突写入被存储。下次读取数据时，将多个版本的数据返回给应用程序，应用程序提示用户或自动解决冲突，然后将结果返回给数据库。

其他冲突

除了写冲突外还有其他更难以发现的冲突

例如商品秒杀问题，必须确保同一件商品只有一个人抢到，同时创建两个订单会发生冲突，因为下单是由两个不同的领导者进行的。

3.3 多主复制拓扑

复制拓扑描述了写入操作从一个节点传播到另一个节点的通信路径。

有两个以上的领导者时，各种不同的拓扑是可能的

• 环形拓扑（MySQL）：每个节点接收上个节点的写入，并转发给另一个节点
• 星型拓扑：一个节点转发给其他所有节点。星型拓扑可以推广到树。
• 全能拓扑：全能拓扑是更密集连接的拓扑结构，

圆形和星型拓扑中，为了防止无限循环，每个节点都需要在复制日志中写入已经通过的节点的标识符，当节点收到含有自己标识符的数据更改时将更改忽略。且当一个节点故障可能会中断消息复制，与之相比，全能拓扑的容错性更好，它允许消息沿着不同的路径传播，避免单点故障。但是，在全能拓扑中，网络连接速度可能使一些复制消息“超过”其他复制消息。（如图）

这是一个因果关系的问题，类似于“前缀一致读”所解决的问题。为了正确的排序，可以使用版本向量技术，本章稍后讨论。

4 无主复制

允许任何副本接收写入。也成为Dynamo风格，关系型数据库一般不用。

实现方式：

• 客户端之间将写入发送到几个副本中
• 由一个协调者节点代表客户端写入（与领导者不同的是，协调者不执行特定的写入顺序）

4.1 当节点故障时写入数据库

无领导配置中，故障切换不存在。如图，客户端并行发送写入到三个副本，其中一个不可用，客户收到两个确定的响应后写入是成功的。

但是，不可用节点的重新连接后它的数据是过时的。为了解决此问题，当客户端从数据库中读数据时，读请求会并行发送到多个节点，客户端用版本号确定哪个值比较新。

读修复和反熵

不可用节点重新连接后需要补上没更新的数据

• 读修复（Read repair）：当客户端并行读取多个节点时，检测陈旧的响应，将新值写入陈旧的副本。此方法适用于频繁读取的值，因为很少读取的值可能会丢失从而降低持久性。
• 反熵过程（Anti-entropy process）：一些数据存储具有后台进程，该进程不断查找副本之间数据的差异，并将缺少的数据添加。

读写的法定人数

副本数量为n时，每次写入需有w个节点确认才能算成功，并且读取时至少查询r个节点。n和w和r满足 w + r > n，这保证你读取的节点中至少有一个新节点，以容忍至多n/2个节点故障。遵循这条公式的读写称为法定人数的读和写。

若少于最低w或r，读或写将返回错误。因为节点不可用

这三个参数通常可以设置，通常n设为奇数，则w=r=(n+1)/2。w和r的数值影响工作负载和持久性。

4.2 仲裁一致性的局限性

即使满足w+r>n，也可能存在返回陈旧值的边缘情况

• 写冲突。可以使用合并并发写入或最后写入胜利来避免。
• 读写同时发生，可能有些副本还未写入，此时不确定返回是否为新值。
• 写操作小于w时，整体判定失败，但并未对成功的副本进行回滚，这导致读取可能读到写入失败的值。
• 有新值的节点失效后，读取了带有旧值的副本恢复时，新值的副本数可能低于w，从而打破法定人数条件。
• 可能出现啊时序（timing）的边缘情况。

4.3 松散法定人数与提示移交

合理配置的法定人数可以使数据库无需故障切换即可容忍个别节点的故障和变慢，因为请求不必等待所有n个节点的响应。这可以应用于需要高可用、低延时、且能够容忍偶尔读到陈旧值的应用场景

然而，网络中断可能导致剩余的可用节点少于需要的节点（w和r），客户端无法到达法定人数。

在大型集群中（节点数量远大于n），网络中断期间客户端可能连接到某些数据库节点，此时应该权衡一下：

• 将错误返回给我们无法达到w或r节点的法定数量的所有请求是否更好？
• 我们是否应该接受写入，然后将它们写入一些可达的节点，但不在n值通常存在的n个节点之间？

松散的法定人数（sloppy quorum）

• 上面第二条就是
• 读写仍需要满足rw，但可能不在一开始指定的n个节点中

提示移交（hinted handoff）

• 网络中断得到解决时，一开始指定的n个节点中的一些节点是陈旧的，那么，不在那一开始的n个节点中但是被临时写入的节点，应该将写入发送给它们

打个比方，松散的法定人数：你没带钥匙所以先在邻居家坐一会儿。提示移交：房子门开了，你邻居让你回家。

松散法定人数能提高写入的可用性：只要有任何w节点可用，数据库就可以接收写入。但这意味着即使满足读写的法定人数，也不能确定读取的某个键是最新值，因为最新值可能临时写入了n之外的节点。

运维多个数据中心

无主复制适用于多数据中心操作，因为它旨在容忍冲突的并发写入，网络中断和延迟尖峰。

无论数据中心如何，每个来自客户端的写入都会发送到所有副本，但客户端通常只等待来自其本地数据中心内的法定节点的确认，从而不会受到跨数据中心链路延迟和中断的影响。对其他数据中心的高延迟写入通常被配置为异步发生。

4.4 检测并发写入

Dynamo风格数据库和多领导复制都会造成写入冲突，同时Dynamo风格在“读修复”或“提示交接”时也可能冲突。

问题在于，由于网络延迟或故障，两个用户同时操作一个数据，可能导致多个副本的同一个数据不一致。如图

客户端A和B并发写入时，由于网络延迟，多个副本的同一个数据不一致。如何避免呢？

最后写入胜利（LWW，丢弃并发写入）

每个副本只需要存储“最近”的值，并允许“更旧”的值被覆盖。

然而，客户端并不知道哪个是“最近”的，所以我们可以为写入附加一个时间戳。

缺点：以持久性为代价，一个key有多个并发写入时，即使他们都报告为成功，也只有一个写入能存活。所以当丢失数据是不可接受的时，不能选择LWW。

“此前发生”的关系和并发

假设有A和B两个操作，那么AB有两类情况，一类是两者存在因果依赖关系，一类是AB并发。

例如：B增加的值是A插入的值，此时B因果依赖于A

而当两个操作都不在另一个之前发生，即两个操作都不知道对方，此时可以说两个操作是并发的。（不是物理时间上的并发）

如果操作并发，则存在需要解决的冲突，我们需要一个算法来判断两个操作是否并发

捕获“此前发生”关系

用于确定两个操作是否并发或具有因果依赖

服务器通过查看版本号来确定两个操作是否是并发的：

• 服务器为每个键保留一个版本号，每次写入键时都增加版本号，并将新版本号与写入的值一起存储。
• 当客户端读取键时，服务器将返回所有未覆盖的值以及最新的版本号。客户端在写入前必须读取。
• 客户端写入键时，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在一起。 （来自写入请求的响应可以像读取一样，返回所有当前值，这使得我们可以像购物车示例那样连接多个写入。）
• 当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或更低版本的所有值（因为它知道它们已经被合并到新的值中），但是它必须保持所有值更高版本号（因为这些值与传入的写入同时发生）。

当一个写入包含前一次读取的版本号时，它会告诉我们写入的是哪一种状态。如果在不包含版本号的情况下进行写操作，则与所有其他写操作并发，因此它不会覆盖任何内容 —— 只会在随后的读取中作为其中一个值返回。

合并同时写入的值

通过让客户端合并并发写入的值来完成。

Riak称这些并发值为兄弟（siblings），所以也称合并兄弟值。本质上和多领导者复制中的冲突相同。

一个项目在删除时留下一个具有适合版本号的标记，以指示合并兄弟时项目已经被删除，这种删除标记称为墓碑。

通常用一些数据结构来自动执行合并。

版本向量

当有多个副本但没有领导者时，使用单个版本号来捕获操作之间的依赖关系，除了对每个键使用版本号之外，每个副本也需要使用版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本中看到的版本号。这个信息指出了要覆盖哪些值，以及保留哪些值作为兄弟。所有副本的版本号集合称为版本向量（version vector） 。当读取值时，版本向量会从数据库副本发送到客户端，并且随后写入值时需要将其发送回数据库。版本向量允许数据库区分覆盖写入和并发写入。

版本向量结构确保从一个副本读取并随后写回到另一个副本是安全的。这样做可能会创建兄弟，但只要兄弟姐妹合并正确，就不会丢失数据。

5 小结

复制可以用于：提高可用性、断开连接的操作、降低延迟（数据放在离用户地理位置更近的地方）、提高可扩展性

复制主要有三种方法：单主复制、多主复制、无主复制

复制延迟会带来一系列问题，解决方式有：写后读、单调读、一致前缀读