数据复制
复制指在多个节点上存储相同的数据，以降低访问延迟（数据分布在多个地理位置），提高容错性和吞吐量。如果复制的数据一成不变，那么只需要简单地将数据复制到每个节点。然而复制的挑战在于如何处理不断变化的数据（如何保证数据的一致性），下面讨论三种流行的应对复制数据变化的方法：主从复制、多主复制和无主复制。
主从复制
工作原理
主从复制也被称为单主复制，客户端必须将写请求发送给主节点，主节点首先将更改应用到本地，然后再将更改发送给所有从节点。客户端可以将读请求发送给主节点或者从节点。
同步和异步复制
- 同步复制
- 优点：如果主节点发生故障，则可以在从节点访问到最新数据。
- 缺点：如果从节点发生故障，则主节点会被阻塞直到从节点复制完成。
- 异步复制
- 优点：主节点不会被阻塞，系统的吞吐量更大。
- 缺点：如果主节点发生不可恢复的故障，则所有未被复制到从节点的更改都会丢失。
实践中，通常只将一个从节点设置为同步模式，其他从节点设置为异步模式。如果主节点发生故障，则可以在同步的从节点访问到最新数据；如果同步的从节点发生故障，则可以将另一个异步的从节点升级为同步模式。这种配置方式被称为半同步。
配置新的从节点
当需要提高系统的容错性或者替换失效的从节点时，就需要增加新的从节点。此时如何保证新的从节点和主节点的数据一致？简单地将数据从主节点复制到从节点是不行的，因为数据在不断变化，这样可能会丢失更改。或者可以对数据库加写锁，但是这会违反高可用的设计目标。
实际上，可以在不中断数据库服务的情况下完成新的从节点的配置。步骤如下：对主节点的数据创建一个一致性快照，将此快照复制到从节点，然后从节点向主节点请求快照之后的更改日志（根据快照中的 LSN 确定），获得日志之后重做日志的更改（这个步骤称为追赶）。
处理节点失效
从节点失效：追赶式恢复
如果从节点发生故障，然后顺利重启，或者主从节点之间的网络发生中断，则从节点可以通过向主节点请求故障期间的日志，并且将日志应用到本地来追赶主节点，从而恢复正常状态。
主节点失效：节点切换
如果主节点发生故障，选择某个从节点将其升级为主节点，同时更新客户端的主节点的信息。切换可以手动进行，也可以自动进行。
自动切换的步骤如下：
- 确认主节点失效（心跳检测）。
- 选举新的主节点（共识算法）。
- 重新配置系统使新主节点生效（修改客户端配置以及原主节点上线之后降级为从节点）。
切换过程存在的问题：
- 如果使用了异步复制，并且新的主节点并未和原主节点同步，则原主节点上线之后可能会尝试将未完成复制的更改发送到新的主节点，从而产生冲突。常见的解决方案是将未完成复制的更改丢弃，这会违背持久化的承诺。
- 如果有外部系统依赖于数据库的内容，丢弃数据的方案会产生很严重的问题（可能会导致数据泄露）。
- 在某些故障下，会发生两个节点同时都认为自己是主节点的情况（称为脑裂），这可能会导致数据丢失或者破坏。
- 如何设置合适的超时时间来检测主节点失效。
复制日志的实现
原书中描述的是基于语句的复制，基于预写日志的复制，基于行的逻辑日志的复制等。下面将预写日志改为物理日志，将语句和行归为逻辑日志。之所以这样，是因为根据我所看过的一些资料（包括 CMU-15445）都将语句归为逻辑日志，而基于行的复制根据书上的说法，它和存储引擎解耦，同时书上也称其为基于行的逻辑日志的复制，所以我将两者都归为逻辑日志。而把预写日志改为物理日志，是因为书上说预写日志描述的是数据的字节级更改，按照这个说法，明显是预写日志的物理日志模式（CMU-15445 中描述了预写日志的三个日志模式：物理日志，逻辑日志，混合日志）。
基于物理日志的复制
解释：主节点将物理日志发送给从节点。
缺点：由于物理日志描述的是数据的字节级更改，这种复制方案和存储引擎紧密耦合，此时主从节点必须使用相同版本的存储引擎。所以在进行数据库升级时，只能首先将主从节点停机，再进行升级。如果复制方案允许从节点的版本比主节点更高，则可以首先将从节点升级，然后将从节点作为新的主节点，从而实现不停机升级。
基于逻辑日志的复制
解释：分为基于语句的复制和基于行的复制，主节点将逻辑日志（和物理存储引擎解耦的日志格式）发送给从节点。
缺点：如果使用基于语句的复制，则某些语句可能在不同节点产生不同的执行结果。例如：语句使用非确定性函数（NOW，RAND），语句依赖于数据库现有数据，有副作用的语句（触发器、存储过程、用户定义的函数）。
优点：主从节点可以运行不同版本的存储引擎，甚至是不同的存储引擎。对于外部应用程序，逻辑日志格式也更容易解析。
基于触发器的复制
解释：之前的复制都是由 DBMS 实现的，但在某些情况下可能需要更高的灵活性，这时需要将复制交给应用程序实现。一种方法是让应用程序读取数据库日志从而获取数据更改，另一种方法是使用触发器和存储过程，当发生数据更改时自动执行存储过程，将数据更改记录到单独的表中，应用程序通过访问该表来获取数据更改。
分析：此复制方式开销更高，也更容易出错或者暴露一些限制，但是具有更高的灵活性。
复制滞后问题
如果使用异步复制，则会出现主节点和从节点的数据不一致的情况，这种不一致只是暂时的状态。如果停止写数据库，则从节点最终会追赶上主节点，这被称为最终一致性。虽然主从节点最终会保持一致，但是暂时的不一致会引发各种问题，下面将讨论相关问题和解决方案。
写后读
问题：用户写入数据之后立即读取这些数据，如果读请求被发送给滞后的从节点，则用户看不到刚才写入的数据。
解决：此时，我们需要保证写后读一致性（也称为读写一致性），该一致性要求用户能够立即看到自己最近写入的数据，但是不保证其他用户能够立即看到这些数据。系统可以通过跟踪用户最近写入的时间戳，来保证将读请求发送给包含对应数据的节点。
单调读
问题：用户执行两次相同的查询，对应的读请求分别被路由两个不同的从节点，并且第二次查询访问的从节点比第一次查询访问的从节点更滞后。这会导致用户首先看到新数据，然后看到旧数据，就好像数据被回滚一样。
解决：此时，我们需要保证单调读一致性，该一致性要求用户进行多次读取时，不会先读到新数据再读到旧数据，即读取的数据对应的时间戳是单调递增的。系统可以总是将同一用户的读请求路由到同一个节点来保证单调读。
前缀读
问题：存在因果关系的数据被划分到不同的分区，用户在读取数据时可能会先看到果后看到因。
解决：此时，我们需要保证前缀读一致性，该一致性要求按照写入数据的顺序读取数据。对于未分区的单主数据库而言，数据总是按照因果关系的顺序写入数据库[1]，在读取数据时也总是按照因果关系的顺序读取，因此不会发生该异常。但是，如果数据被划分到不同分区，不同分区独立运行，无法保证分区之间的从节点按照因果关系的顺序写入数据[2]，此时将会发生异常。简单的想法是在复制日志中记录时间戳，但是由于存在时钟偏差问题，该方法不可行。一种解决方案是将具有因果关系的写入都交给一个分区完成，但是这样做的效率很低。另一种解决方案是使用版本向量技术跟踪因果关系，这将在无主复制的检测并发写中进行讨论。PS：这部分是按照我的理解描述的，可能存在错误。
多主复制
工作原理
系统中包含多个主节点，每个主节点都可以接收写请求，并且需要将更改发送给其他主节点和自己的从节点。
使用场景
多数据中心：为了容忍数据中心级别的故障或者使数据库更接近用户，可以把数据库的副本存储在多个数据中心。如果使用主从复制，主节点只能存在于某个数据中心，所有写请求都必须经过该数据中心。如果使用多主复制，则可以为每个数据中心设置一个主节点，在数据中心内部使用主从复制，主节点之间通常使用异步复制进行同步。
多主复制相比主从复制在多数据中心场景下的优势：写入延迟更低，对网络性能的依赖更低，能够容忍数据中心失效。缺点是，如果使用异步复制，多个主节点同时更改相同的数据时会产生写冲突。
处理写冲突
冲突检测
如果使用异步复制，那么多个主节点可以同时更改相同的数据，并且只能在稍后的复制过程中检测到冲突。
如果使用同步复制，每次只能进行一个写请求，无法发挥多个主节点的优势，那还不如直接使用主从复制。
冲突避免
可以在应用层保证对相同数据的写请求路由到相同的数据中心，但是在某些时候需要改变事先指定的数据中心，例如在数据中心故障或者用户移动到其他位置导致离某个数据中心更近时，写请求将会被路由到其他数据中心。
冲突解决
可能的解决方式如下：
- 为每个写请求分配唯一的 ID（时间戳、随机数、UUID、哈希值），然后按照某种规则选择特定的写请求。
- 为每个节点分配唯一的 ID，然后按照某种规则确定优先级。
- 将多个写入的值合并。
- 保存冲突信息，然后在应用层解决冲突。
在应用层解决冲突是最合理的方式，可以在写入时调用用户定义的冲突处理程序解决，还可以保留多个写入值，然后在读取时调用程序或者通知用户解决。还有一些自动解决冲突的方法，包括使用无冲突的复制数据类型（CRDT）、可合并的持久数据结构、操作转换算法。
拓扑结构
复制的拓扑结构描述了写日志从一个节点传播到其他节点的通信路径，包括全部至全部型拓扑（完全图）、环形拓扑、星形拓扑等。在环形和星形拓扑中，写日志需要经过多个节点才能传播到所有节点，为了避免循环复制（自己的写日志被传播给自己，然后又进行一轮传播），在复制日志中都会记录已传播节点的标识符。
星形和环形拓扑的问题是单点故障会影响写日志的传播，这可以通过在故障时重新配置拓扑结构解决。而全部至全部型拓扑的问题是在传播时写日志的因果顺序无法保证（参考复制滞后问题中的前缀读）。
无主复制
工作原理
客户端并行地将写请求发送给多个节点，如果得到多数节点的确认，则认为写入成功。读取时也是并行地从多个节点上读取数据，此时可能得到多个不同的值（由于复制滞后），系统会使用某种机制确定新值以及更新旧值。
读修复和反熵
当节点失效之后重新上线，可以使用以下两种机制进行追赶。
读修复
解释：客户端并行读取多个节点，获取的数据中包含版本号，以判断数据的新旧，同时会更新包含旧数据的节点。
分析：该方法适合读密集的场景，不然包含旧数据的节点得不到更新。
反熵
解释：使用后台进程检测节点之间数据的差异，然后将新数据复制到包含旧数据的节点。
分析：和基于主节点的复制不同，此过程不保证按照特定的顺序复制数据，并且会引入明显的滞后。
读写仲裁（quorum）
如果有 \(n\) 个节点参与仲裁，写入时需要得到 \(w\) 个节点的确认，读取时至少查询 \(r\) 个节点，则只要 \(w+r>n\)，读取的节点中就一定会包含最新值。满足该条件的读/写操作被称为仲裁读/写（或者法定票数读/写），可以将 \(w\) 和 \(r\) 看作是确认读/写操作是否有效的最低票数。
通常会将 \(n\) 设置为奇数，将 \(w\) 和 \(r\) 设置为 \(\frac{n+1}{2}\)。当然也可以根据实际情况做调整，例如对于读多写少的负载，设置 \(w=n\) 和 \(r=1\) 比较合适，这样读取速度很快，但是只要有一个节点失效就会导致仲裁写失败。
通常读/写请求总是并行发送给所有节点，参数 \(w\) 和 \(r\) 只是决定要等待的节点数。如果可用的节点数小于 \(w\) 或 \(r\)，则读/写操作就会返回错误。
也可以将 \(w\) 和 \(r\) 设置为较小的值，使得 \(w+r\leq n\)，不满足仲裁条件。此时可能读取到的值都是旧值，但是可用获得更低的延迟和更高的可用性。即使在 \(w+r>n\) 的情况下，也可能存在只读取到旧值的边界条件。
如果需要更高的容错性，可用使用宽松的读写仲裁：写入和读取仍需要 \(w\) 和 \(r\) 个节点确认，但是可以利用 \(n\) 个节点之外的其它节点（参与仲裁的节点数量为 \(n\)，集群中的节点数量大于 \(n\)）。例如，当 \(n\) 个节点中的多数节点失效时，客户端会向额外的节点发送读/写请求，当失效节点重新上线时，将额外节点中的新值复制到这些滞后的节点。
检测并发写
和多主复制类似，无主复制同样存在写冲突。在多主复制的处理写冲突中介绍过，可以为每个写请求分配一个时间戳，然后选择保留时间戳最大的写请求，这被称为最后写入者获胜（last write wins，LWW）。LWW 可以实现最终一致性，代价是牺牲数据的持久性，因为小于最大时间戳的并发写入都会被覆盖，由于时钟偏差，该算法甚至可能覆盖非并发写入。是否使用该算法依据实际场景而定，例如在缓存系统中覆盖是可以接受的，则可以使用该算法。
我们可以使用版本向量技术来判断两个写操作是否并发。如果一个写操作发生在另一个写操作之前（依赖关系/因果关系），则后面的写操作可以覆盖前面的写操作。如果是并发的，就需要处理写冲突问题。算法的工作流程见书上，本质上就是通过在写之前读，来获取数据的当前值以及版本向量（该数据在所有节点上的版本号的集合），之后的写操作只会覆盖服务器中低版本的数据，从而并发写（高版本）的数据得到保留。PS：书上只是简单提了一下，还有很多细节没说。