复制指在多个节点上存储相同的数据，以降低访问延迟（数据分布在多个地理位置），提高容错性和吞吐量。如果复制的数据一成不变，那么只需要简单地将数据复制到每个节点。然而复制的挑战在于如何处理不断变化的数据（如何保证数据的一致性），下面讨论三种流行的应对复制数据变化的方法：主从复制、多主复制和无主复制。

主从复制

工作原理

主从复制也被称为单主复制，客户端必须将写请求发送给主节点，主节点首先将更改应用到本地，然后再将更改发送给所有从节点。客户端可以将读请求发送给主节点或者从节点。

同步和异步复制

• 同步复制
  • 优点：如果主节点发生故障，则可以在从节点访问到最新数据。
  • 缺点：如果从节点发生故障，则主节点会被阻塞直到从节点复制完成。
• 异步复制
  • 优点：主节点不会被阻塞，系统的吞吐量更大。
  • 缺点：如果主节点发生不可恢复的故障，则所有未被复制到从节点的更改都会丢失。

实践中，通常只将一个从节点设置为同步模式，其他从节点设置为异步模式。如果主节点发生故障，则可以在同步的从节点访问到最新数据；如果同步的从节点发生故障，则可以将另一个异步的从节点升级为同步模式。这种配置方式被称为半同步。

配置新的从节点

当需要提高系统的容错性或者替换失效的从节点时，就需要增加新的从节点。此时如何保证新的从节点和主节点的数据一致？简单地将数据从主节点复制到从节点是不行的，因为数据在不断变化，这样可能会丢失更改。或者可以对数据库加写锁，但是这会违反高可用的设计目标。

实际上，可以在不中断数据库服务的情况下完成新的从节点的配置。步骤如下：对主节点的数据创建一个一致性快照，将此快照复制到从节点，然后从节点向主节点请求快照之后的更改日志（根据快照中的 LSN 确定），获得日志之后重做日志的更改（这个步骤称为追赶）。

处理节点失效

从节点失效：追赶式恢复

如果从节点发生故障，然后顺利重启，或者主从节点之间的网络发生中断，则从节点可以通过向主节点请求故障期间的日志，并且将日志应用到本地来追赶主节点，从而恢复正常状态。

主节点失效：节点切换

如果主节点发生故障，选择某个从节点将其升级为主节点，同时更新客户端的主节点的信息。切换可以手动进行，也可以自动进行。

自动切换的步骤如下：

1. 确认主节点失效（心跳检测）。
2. 选举新的主节点（共识算法）。
3. 重新配置系统使新主节点生效（修改客户端配置以及原主节点上线之后降级为从节点）。

切换过程存在的问题：

• 如果使用了异步复制，并且新的主节点并未和原主节点同步，则原主节点上线之后可能会尝试将未完成复制的更改发送到新的主节点，从而产生冲突。常见的解决方案是将未完成复制的更改丢弃，这会违背持久化的承诺。
• 如果有外部系统依赖于数据库的内容，丢弃数据的方案会产生很严重的问题（可能会导致数据泄露）。
• 在某些故障下，会发生两个节点同时都认为自己是主节点的情况（称为脑裂），这可能会导致数据丢失或者破坏。
• 如何设置合适的超时时间来检测主节点失效。

复制日志的实现

原书中描述的是基于语句的复制，基于预写日志的复制，基于行的逻辑日志的复制等。下面将预写日志改为物理日志，将语句和行归为逻辑日志。之所以这样，是因为根据我所看过的一些资料（包括 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：书上只是简单提了一下，还有很多细节没说。

Least Product

题目

输入长度为 \(n\) 的数组 \(a\)，输出能够使 \(\prod_{i=1}^{n}{a_{i}}\) 最小的最小操作次数。每次操作可以选择数组中的任意元素 \(a_{i}\)，如果 \(a_{i}<0\)，则可以将其改为 \([a_{i},0]\) 中的任意整数，否则可以将其改为 \([0,a_{i}]\) 中的任意整数。

数据范围：\(1\leq n\leq 100\)，\(-10^{9}\leq a_{i}\leq 10^{9}\)。

思路

由于操作只会让所有元素乘积的绝对值变小，所以如果乘积是非正数，则不需要进行操作，否则只需进行一次操作，将任意一个元素改为 \(0\)。

Erase First or Second Letter

题目

输入长度为 \(n\) 的字符串 \(s\)，输出进行任意次操作能够得到的不同非空字符串的个数。每次操作可以删除字符串的第一个字符或者第二个字符。

数据范围：\(1\leq n\leq 10^{5}\)。

思路

• 方法一：枚举剩余字符串的第一个字符下标 \(i\)，对于每个 \(i\) 都可以通过不断删除第二个字符得到 \(n-i\) 个不同的字符串。然后思考什么时候会出现相同的字符串，假设两次枚举的第一个字符分别为 \(i\) 和 \(j\)（\(i<j\)），只有当 \(s_{i}=s_{j}\) 时才有可能出现相同字符串，进一步观察可以发现，对 \(i\) 操作得到的 \(n-i\) 个不同的字符串总是包含对 \(j\) 操作得到的 \(n-j\) 个不同的字符串。所以，假设字符串 \(s\) 中有 \(m\) 个不同的字符，每个字符第一次出现的位置分别为 \(k_{0},k_{1},\dots,k_{m-1}\)，则答案为 \(\sum_{i=0}^{m-1}(n-k_{i})\)。
• 方法二：枚举剩余字符串的第二个字符下标 \(i\)，对于每个 \(i\) 它的贡献为 \([0,i-1]\) 中不同字符的个数。

Watering an Array

题目

输入长度为 \(n\) 的整数数组 \(a\)，长度为 \(k\) 的整数数组 \(v\)，以及整数 \(d\)。输出执行 \(d\) 次操作能够得到的最大分数。有两种类型的操作：

• 假设当前执行第 \(i\) 次操作，则将数组 \(a\) 的前缀 \([a_{1},a_{b_{i}}]\) 都加 \(1\)。其中 \(b_{i}=v_{((i-1)\bmod k)+1}\)。
• 将 \(a_{j}=j\) 的元素个数加到分数中，然后将数组中的所有元素都置为 \(0\)。（下标从 \(1\) 开始）

数据范围：\(1\leq n\leq 2000\)，\(1\leq k\leq 10^{5}\)，\(k\leq d\leq 10^{9}\)，\(0\leq a_{i}\leq n\)，\(1\leq v_{i}\leq n\)。

思路

如果数组 \(a\) 中的元素都为 \(0\)，显然最大分数为 \(\lfloor\frac{d}{2}\rfloor\)，对应的方案为交替执行两种操作。也就是说，解决问题的关键是确定何时第一次将数组 \(a\) 重置。这可以通过枚举实现，但是由于 \(d\) 很大，肯定不能直接枚举范围 \([1,d]\)。进一步观察可以发现，对前缀进行 \(2n\) 次加法，再重置最多得到 \(n\) 分，而先重置再交替执行操作，能够得到的分数大于等于 \(n\)，所以只需要枚举范围 \([1,2n]\)。

Yet Another Inversions Problem

题目

输入长度为 \(n\) 的数组 \(p\)，表示 \([1,2n-1]\) 中所有奇数的一个排列。输入长度为 \(k\) 的数组 \(q\)，表示 \([0,k-1]\) 中所有整数的一个排列。定义长度为 \(nk\) 的数组 \(a\)，对于 \(0\leq i<n\) 和 \(0\leq j<k\)，有 \(a_{i\cdot k+j}=p_{i}\cdot 2^{q_{j}}\)。输出数组 \(a\) 的逆序数，结果对 \(998244353\) 取余。

数据范围：\(1\leq n,k\leq 2\cdot 10^{5}\)，\(1\leq p_{i}\leq 2n-1\)，\(0\leq q_{i}<k\)。

思路

可以将数组看作 \(n\times k\) 的矩阵，逆序数可以分为行内和行间。所有行的行内逆序数都是数组 \(q\) 的逆序数，使用归并排序或者树状数组即可求解，所以难点在如何快速求出行间的逆序数。首先尝试两两枚举所有行，然后观察对于确定的两个行，它们的逆序数有什么特点。由此可以发现，两行之间的逆序数大概是一个等差数列之和，项数和其他边界条件是由 \(p_{i}\) 和 \(p_{j}\) 的大小关系确定的。具体来说，假设 \(p_{i}<p_{j}\)，等差数列是由满足 \(p_{i}\cdot 2^{z}<p_{j}\) 条件的最大的 \(z\) 确定的，确定 \(z\) 需要花费 \(O(\log{n})\) 的时间。从而可以得到时间复杂度为 \(O(n^{2}\log{n}+k\log{k})\) 的朴素解法。（总是假设 \(i<j\)）

下面解释等差数列是如何得到的，假设 \(p_{i}\cdot 2^{z}<p_{j}\)（\(z\geq0\)），将对应的两行合并之后可以得到如下序列：

要求逆序数，可以通过对每个 \(p_{i}\) 项前面有多少个 \(p_{j}\) 项计数，然后求和得到。可以发现，\(p_{i}\cdot 2^{z+1}\) 前面有 \(1\) 个 \(p_{j}\) 项，\(p_{i}\cdot 2^{z+2}\) 前面有 \(2\) 个 \(p_{j}\) 项，\(p_{i}\cdot 2^{k-1}\) 前面有 \(k-1-z\) 个 \(p_{j}\) 项。得到逆序数为 \(\frac{(k-z)(k-1-z)}{2}\)。

同理，假设 \(p_{j}\cdot 2^{z}<p_{i}\)（\(z\geq0\)），将对应的两行合并之后可以得到如下序列：

可以发现，\(p_{i}\cdot 2^{k-z-1}\) 到 \(p_{i}\cdot 2^{k-1}\) 的逆序数都为 \(k\)，总和为 \(k(z+1)\)。剩余部分的逆序数构成首项为 \(z+1\)，尾项为 \(k-1\)，公差为 \(1\) 的等差数列，总和为 \(\frac{(k+z)(k-1-z)}{2}\)。得到逆序数为 \(\frac{(k+z)(k-1-z)}{2}+k(z+1)\)。

如何降低时间复杂度？通过上述分析，可以知道对于任意 \(p_{i}\) 和 \(p_{j}\)，它们之间的逆序数是由 \(z\) 决定的。也就是说，如果给定 \(p_{i}\) 和 \(z\)（\(z\) 为任意整数），对于任意满足 \(p_{i}\cdot 2^{z}<p_{j}<p_{i}\cdot 2^{z+1}\) 条件的 \(p_{j}\) 来说，\(p_{i}\) 和 \(p_{j}\) 之间的逆序数都是相同的。注意，当 \(z<0\) 时，对不等式变形得到 \(p_{i}\cdot 2^{-1}<p_{j}\cdot 2^{-z-1}<p_{i}\)，此时的 \(z\) 和上面逆序数公式中的 \(z\) 不同，并且需要处理整数除法的舍入问题（存在一些边界情况）。

要快速求出区间中 \(p_{j}\) 的个数，可以使用树状数组/线段树，从而可以得到 \(O(n\log{\min(\log{n},k)}+k\log{k})\) 的解决方案。外层循环枚举 \(p_{i}\)（倒序遍历数组 \(p\)，因为之前的讨论都基于 \(i<j\) 的假设），内层循环枚举 \(z\)（大小由 \(n\) 和 \(k\) 限制），然后使用树状数组求区间和，之后可以 \(O(1)\) 时间内计算出该区间的 \(p_{j}\) 和当前枚举的 \(p_{i}\) 之间的逆序数。

PS：还有另一种写法，只需要对树状数组的前缀求和，而不是区间求和，写起来好像更简单，但是没看懂。好难，溜了。

移除栅栏得到的正方形田地的最大面积

题目

输入整数 \(m\) 和 \(n\)，表示宽为 \(m\) 长为 \(n\) 的矩形，左上角为 \((1,1)\)，右下角为 \((m,n)\)。输入长度分别为 \(p\) 和 \(q\) 的数组 \(a\) 和 \(b\)，数组 \(a\) 中的数对矩形水平分割，数组 \(b\) 中的数对矩形垂直分割。输出从数组 \(a\) 和 \(b\) 中移除任意个数，所能够形成的最大正方形面积，结果对 \(10^{9}+7\) 取余。

数据范围：\(3\leq m,n\leq 10^{9}\)，\(1\leq p,q\leq 600\)，\(1<a_{i}<m\)，\(1<b_{i}<n\)。

思路

首先考虑对于宽来说，能够表示的长度是多少。显然，可以通过二重循环枚举出所有可能的长度。将宽能够表示的长度放入哈希表，然后同样使用二重循环枚举长能够表示的长度（假设当前枚举到长度 \(x\)），如果该长度在哈希表中，则说明可以形成长度为 \(x\) 的正方形。最后输出最大值即可。

转换字符串的最小成本 II

题目

输入长度为 \(n\) 的字符串 \(source\) 和 \(target\)，以及长度为 \(m\) 的字符串数组 \(original\)、\(changed\) 和 \(cost\)。其中 \(cost[i]\) 表示将字符串 \(original[i]\) 替换为 \(changed[i]\) 的成本。输出将 \(source\) 转换为 \(target\) 所需的最小成本，如果无法转换则输出 \(-1\)。任意两个替换操作所替换的区间要么相同，要么不相交。

数据范围：\(1\leq n\leq 1000\)，\(1\leq m\leq 100\)，\(1\leq \operatorname{len}(original[i])=\operatorname{len}(changed[i])\leq n\)。

思路

首先使用哈希表将 \(original\) 和 \(changed\) 数组中的字符串映射为数字，每个数字都作为图中的一个顶点。对于每个下标 \(i\)，建立一条从顶点 \(original[i]\) 到顶点 \(changed[i]\) 的边，然后使用 Floyd 算法求出多源最短路径。最后使用动态规划，定义 \(dp[i+1]\) 为对 \(source\) 的前缀 \([0,i]\) 做替换使其和 \(target\) 的前缀 \([0,i]\) 相等，所需的最小代价。注意，外层循环枚举前缀的右端点 \(i\)，内层循环枚举 \(original\) 数组，总时间复杂度为 \(O(m^{3}+n^{2}m)\)。使用字典树会更快，参考灵神题解。