复制

复制主要指通过互联网络在多台机器上保存相同数据的副本。 通过数据复制方案，人们通常希望达到以下目的：

低延迟：使数据在地理位置上更接近用户，从而降低访问延迟
高可用：当部分组件出现故障，系统依然可以继续工作，从而提高可用性。
可拓展：扩展至多台机器以同时提供数据访问服务，从而提高读吞量。

主流的三种流行的复制数据变化的方法是：主从复制、多主节点复制和无主节点复制。

主从复制

每个保存数据库完整数据集的节点称之为副本。而每当有数据写入时，所有的副本需要随之更新，否则就会出现数据不一致的问题。最常见的解决方案就是主从复制，如下图：

其工作原理如下：

指定某一个节点为主节点。当用户写数据库时，必须将写请求首先发送给主节点，主节点首先将新数据写入本地存储。
其他节点则全部称为从节点。主节点把新数据写入本地存储后，然后将数据更改作为复制的日志或更改流发送给所有从节点。每个从节点获得更改日志之后将其应用到本地，且严格保持与主节点相同的写入顺序。
客户端从数据库中读数据时，可以在主节点或者从节点上执行查询。只有主节点才可以接受写请求，从客户端的角度来看，从节点都是只读的。

同步复制与异步复制

复制非常重要的一个设计选项是同步复制还是异步复制。

同步复制：
- 优点：一旦向用户确认，从节点可以明确保证完成了与主节点的更新同步，数据已经处于最新版本。万一主节点发生故障，总是可以在从节点继续访问最新的数据。
- 缺点：如果同步的从节点无法完成确认，写入就不能视为成功。主节点会阻塞其后所有的写操作，直到同步副本确认完成。因此任何一个同步节点的中断都会导致整个系统更新停滞不前。
异步复制
- 优点：不管从节点上数据多么滞后，主节点总是可以继续响应写请求，系统的吞吐性能更好。
- 缺点：如果主节点发生失败且不可恢复，则所有尚未复制到从节点的写请求都会丢失。这意味着即使向客户端确认了写操作，却还是无法保证数据的持久化。

在实际使用中有时还会采用半同步的设计方案。即某个从节点是同步的，而其他节点则是异步模式。万一同步的从节点变得不可用或性能下降，则将另一个异步的从节点提升为同步模式。这样可以保证至少有两个节点（即主节点和一个同步从节点）拥有最新的数据副本。

新增节点

如果需要增加副本数以提高容错能力，或者替换失败的副本，就需要考虑增加新的从节点。但如何确保新的从节点和主节点保持数据一致呢？

主要操作步骤如下：

在某个时间点对主节点的数据副本产生一个一致性快照，这样避免长时间锁定整个数据库。
将此快照拷贝到新的从节点。
从节点连接到主节点并请求快照点之后所发生的数据更改日志。
获得日志之后，从节点来应用这些快照点之后所有数据变更。
不断重复上述过程。

节点失效的处理

从节点失效

从节点的本地磁盘上都保存了副本收到的数据变更日志。如果从节点发生崩溃，然后顺利重启，或者主从节点之间的网络发生暂时中断（闪断），则恢复比较容易，根据副本的复制日志，从节点可以知道在发生故障之前所处理的最后一笔事务，然后连接到主节点，并请求自那笔事务之后中断期间内所有的数据变更。在收到这些数据变更日志之后，将其应用到本地来追赶主节点。之后就和正常情况样持续接收来自主节点数据流的变化。

主节点失效

处理主节点故障的情况则比较棘手：选择某个从节点将其提升为主节点。这样之后的写请求会发送给新的主节点，然后其他从节点要接受来自新的主节点上的变更数据，这一过程称之为故障转移。

故障转移可以手动进行，例如通知管理员主节点发生失效，采取必要的步骤来创建新的主节点。或者以自动方式进行切换。自动切换的步骤通常如下：

确认主节点失效。大多数系统都采用了基于超时的机制。节点间频繁地互相发生发送心跳存活消息，如果发现某一个节点在一段比较长时间内（例如 30s）没有响应，即认为该节点发生失效。
选举新的主节点。可以通过选举的方式（超过多数的节点达成共识）来选举新的主节点，或者由之前选定的某控制节点来指定新的主节点。候选节点最好与原主节点的数据差异最小，这样可以最小化数据丢失的风险。
重新配置系统使新主节点生效。 客户端现在需要将写请求发送给新的主节点。如果原主节点之后重新上线，这时系统要确保原主节点降级为从节点，并让其认可新的主节点。

复制日志的实现

基于语句的复制

主节点记录所执行的每个写请求（操作语句）并将该操作语句作为日志发送给从节点。 对于关系数据库，这意味着每个 INSERT、UPDATE、 DELETE 语句都会转发给从节点，并且每个从节点都会分析井执行这些 SQL 语句。

但这种复制方式有一些不适用的场景：

任何调用非确定性函数的语句，如 NOW() 获取当前时间，或 RAND() 获取一个随机数等，可能会在不同的副本上产生不同的值。
如果语句中使用了自增列，或者依赖于数据库的现有数据（例如，UPDATE ... WHERE <某些条件>），则所有副本必须按照完全相同的顺序执行，否则可能会带来不同的结果。进而，如果有多个同时并发执行的事务时，会有很大的限制。
有副作用的语句（例如，触发器、存储过程、用户定义的函数等），可能会在不同的副本上产生不同的副作用。

基于预写日志传输

对于常见的磁盘数据结构，通常每个写操作都是以追加写的方式写入到日志中：

对于日志结构存储引擎，日志是主要的存储方式。日志段在后台压缩井支持垃圾回收。
对于采用覆盖写磁盘的 B 树结构，每次修改会预先写入日志，如系统发生崩溃，通过索引更新的方式迅速恢复到此前一致状态。

所有对数据库写入的字节序列都被记入日志。因此可以使用完全相同的日志在另一个节点上构建副本：将日志入磁盘之后，主节点通过网络将其发送给从节点。从节点收到日志进行处理，建立和主节点内容完全相同的数据副本。

其主要缺点是日志描述的数据结果非常底层。 WAL 包含了哪些磁盘块的哪些字节发生改变，诸如此类的细节。这使得复制方案和存储引擎紧密耦合。如果数据库的存储格式从一个版本改为另一个版本，那么系统通常无法支持主从节点上运行不同版本的软件。

基于行的逻辑日志复制

复制和存储采用不同的日志格式，这样使得复制与存储逻辑剥离。这种复制日志称为逻辑日志，以区分物理存储引擎的数据表示。

关系数据库的逻辑日志通常是指一系列记录来描述数据表行级别的写请求：

对于行插入，日志包含所有相关列的新值。
对于行删除，日志里有足够的信息来唯一标识已删除的行，通常是靠主键，但如果表上没有定义主键，就需要记录所有列的旧值。
对于行更新，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少包含所有已更新列的新值）。

由于逻辑日志与存储引擎逻辑解耦，因此可以更容易地保持向后兼容，从而使主从节点能够运行不同版本的软件甚至是不同的存储引擎。对于外部应用程序来说，逻辑日志格式也更容易解析。

基于触发器的复制

触发器支持注册自己的应用层代码，使得当数据库系统发生数据更改（写事务）时自动执行上述自定义代码。通过触发器技术，可以将数据更改记录到一个单独的表中，然后外部处理逻辑访问该表，实施必要的自定义应用层逻辑，例如将数据更改复制到另一个系统。

基于触发器的复制通常比其他复制方式开销更高，也比数据库内置复制更容易出错，或者暴露一些限制。然而，其高度灵活性仍有用武之地。

复制滞后问题

写后读一致性

对于分布式数据库来说，提交新数据须发送到主节点，但是当用户读取数据，数据可能来自从节点，这就会带来一个问题。当用户在写入不久时查看数据，则新数据可能尚未到达从节点。对用户来讲，看起来似乎是刚刚提交的数据丢失了，如下图所示：

对于这种情况，就需要引入写后读一致性（也称读写一致性）。 其保证如果用户重新加载页面，他们总能看到自己最近提交的更新。但对其他用户则没有任何保证，这些用户的更新可能会在稍后才能刷新看到。

单调读

如下图所示。假定用户 2345 从不同副本进行了多次完全相同的读取，第一次首先查询到了一个相对来说正常的节点，该节点接收到了用户 1234 发布的内容，并将其返回给了用户 2345。而当网页再次刷新，用户 2345 再次进行查询，此时又路由到了一个相对来说较为滞后的节点，这时由于其还未来得及同步用户 1234 的数据，就导致了其返回了一个空结果。对于用户 2345 来说，此时他看到了最新内容之后又看到了过期的内容，好像时间被回拨了一样。

单调读可以确保不会发生这种异常。这是一个介于强一致性与最终一致性的保证。其保证了当读取数据时，如果某个用户依次进行多次读取，则他绝不会看到回滚现象，即在读取较新值之后又发生读旧值的情况。

实现单调读的一种方式是，确保每个用户总是从固定的同一副本执行读取（而不同的用户可以从不同的副本读取）。例如，基于用户 ID 的哈希的方法而不是随机选择副本。但如果该副本发生失效，则用户的查询必须重新路由到另一个副本。

前缀一致读

如果数据库总是以相同的顺序写入，则读取总是看到一致的序列，不会发生这种反常。然而，在许多分布式数据库中，不同的分区独立运行，因此不存在全局写入顺序。这就导致当用户从数据库中读数据时，可能会看到数据库的某部分旧值和另一部分新值。

为了防止这种异常问题，就需要引入一种保证：前缀一致读。其保证了对于一系列按照某个顺序发生的写请求，那么读取这些内容时也会按照当时写入的顺序。

比较常见的实现方案是确保任何具有因果顺序关系的写入都交给一个分区来完成。但由于其性能不佳，如今通常使用一些新的算法来显式追踪事件因果关系。

多主节点复制

主从复制并不是完美的，其存在单点问题：系统只有一个主节点，而所有的写入都必须经由主节点 。如果由于某种原因，例如与主节点之间的网络中断而导致主节点无法连接，主从复制方案就会影响所有的写入操作。

如果要改进这个策略，就可以对主从复制模型进行自然的扩展。即配置多个主节点，每个主节点都可以接受写操作，处理写的每个主节点都必须将该数据更改转发到所有其他节点。这就是多主节点复制。此时，每个主节点同时扮演其他主节点的从节点。

处理写冲突

多主复制的最大问题是可能发生写冲突。而通常采用下面三种方法来处理。

避免冲突

而处理冲突最理想的策略是避免发生冲突 ，即如果应用层可以保证对特定记录的写请求总是通过同一个主节点，这样就不会发生写冲突。

例如，在一个应用系统中，用户需要更新自己的数据，那么我们确保特定用户的更新请求总是路由到特定的数据中心，并在该数据中心的主节点上进行读/写。但是，有时可能需要改变事先指定的主节点，例如由于该数据中心发生故障，不得不将流量重新路由到其他数据中心，此时，冲突避免方式不再有效，必须有措施来处理同时写入冲突的可能性。

收敛于一致状态

当多个主节点写入数据发生冲突时，所有的复制模型至少应该确保数据在所有副本中最终状态一定是一致的。因此，数据库必须以一种收敛趋同的方式来解决冲突，这就意味着当所有更改最终被复制、同步之后，所有副本的最终值是相同。

收敛的冲突解决有以下几种方式：

给每个写入分配唯一 ID。 例如时间戳、足够长的随机数，UUID 或者基于 K-V 的哈希值，挑选最高 ID 的写入作为胜利者，并将其他写入丢弃。
为每个副本分配一个唯一的 ID，并制定规则。 例如序号高的副本写入始终优先于序号低的副本。
以某种方式将这些值合并在一起。 例如，按字母顺序排序，然后拼接在一起。
利用预定义好的格式来记录和保留冲突相关的所有信息，然后依靠应用层的逻辑，事后解决冲突。

自定义冲突解决逻辑

解决冲突最合适的方式可能还是依靠应用层，所以大多数多主节点复制模型都有工具让用户编写应用代码来解决冲突。可以在写入时或在读取时执行这些代码逻辑：

在写入时执行：只要数据库系统在复制变更日志时检测到冲突，就会调用应用层的冲突处理程序。
在读取时执行：当检测到冲突时，所有冲突写入值都会暂时保存下来。当下一次读取数据时，会将数据的多个版本读返回给应用层。应用层可能会提示用户或自动解决冲突，井将最后处理好的结果返回到数据库。

拓扑结构

拓扑结构描述了写请求从一个节点传播到其他节点的通信路径。 常见的拓扑结构如下图：

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

在环形和星形拓扑中，写请求需要通过多个节点才能到达所有的副本，即中间节点需要转发从其他节点收到的数据变更。为防止无限循环，每个节点需要赋予一个唯一标识符，在复制日志中的每个写请求都标记了已通过的节点标识符。如果某个节点收到了包含自身标识符的数据更改，表明该请求已经被处理过，因此会忽略变更请求，避免重复转发。

环形和星形拓扑的问题是，如果某一个节点发生了故障，在修复之前，会影响其他节点之间复制日志的转发。可以采用重新配置拓扑结构的方法暂时排除掉故障节点。

全链接拓扑也存在一些问题。主要是存在某些网络链路比其他链路更快的情况（例如由于不同网络拥塞），从而导致复制日志之间的覆盖。为了使得日志消息正确有序，可以使用一种称为版本向量的技术。

无主节点复制

无主节点复制模型采用了另一种方案，其选择放弃主节点，允许任何副本直接接受来自客户端的写请求。

节点失效处理

对于有主复制模型来说，当节点失效后，其会通过主从切换、从节点追赶等方式来进行修复。但是对于无主模型来说，并没有这样的切换机制。

对于无主模型，其解决节点失效的方法如下：当一个客户端从数据库中读取数据时，它不是向一个副本发送请求，而是并行地发送到多个副本。客户端可能会得到不同节点的不同响应，包括某些节点的新值和某些节点的旧值。可以采用版本号来确定哪个值更新。

读修复与反熵

复制模型应确保所有数据最终复制到所有的副本。当一个失效的节点重新上线之后，它如何赶上中间错过的那些写请求呢？

Dynamo 风格的数据存储系统经常使用以下两种机制：

读修复：当客户端并行读取多个副本时，可以检测到过期的返回值，然后将新值写入到该副本。
反熵：后台进程不断查找副本之间数据的差异，将任何缺少的数据从一个副本复制到另一个副本。

读写的quorum

如果有 n 个副本，写入需要 w 个节点确认，读取必须至少查询 r 个节点，则只要满足 w + r > n ，读取的节点中一定会包含最新值。（成功写入的节点集合和读取的节点集合必然有重合，这样读取的节点中至少有一个具有最新值）。满足上述这些 r、w 值的读/写操作被称之为法定票数读或法定票数写。也可以认为 r 和 w 是用于判定读、写是否有效的最低票数。

在 Dynamo 风格的数据库中，**参数 n、w 和 r 通常是可配置的。一个常见的选择是设置 n 为奇数，w = r = (n + 1) / 2 。**通常会根据具体的业务场景来灵活配置。

仲裁条件 w + r > n 定义了系统可容忍的失效节点数，如下所示：

当 w < n ，如果一个节点不可用，仍然可以处理写入。
当 r < n ，如果一个节点不可用，仍然可以处理读取。
例如 n = 5，w = 3，r = 3。则可以容忍两个不可用的节点。
读取和写入操作总是并行发送到所有的 n 个副本。参数 r 和参数 w 只是决定要等待的节点数。即有多少个节点需要返回结果，我们才能判断出结果的正确性。

如果可用节点数小于所需的 w 或 r，则写入或读取就会返回错误。

检查并发写

Dynamo 风格的数据库允许多个客户端对相同的主键同时发起写操作，即使采用严格的 quorum 机制也可能会发生写冲突。这与多主节复制类似，此外，由于读时修复或者数据回传也会导致并发写冲突。

由于网络延迟不稳定或者局部失效，请求在不同的节点上可能会呈现不同的顺序。如果节点每当收到新的写请求时就简单地覆盖原有的主键，那么这些节点将永久无法达成一致。

下面就来介绍一下数据库内部如何进行冲突处理，保证副本收敛于相同的内容，从而达到最终一致性。

最后写入获胜（LWW算法）

一种实现最终收敛的方方法是，每个副本总是保存最新值，允许覆盖并丢弃旧值。 那么，假定每个写请求都最终同步到所有副本，只要有一个明确的方法来确定哪个写入是最新的，副本可以最终收敛到相同的值。但问题又来了，对于并发的写入，我们无法确定他们的顺序。

即使无法确定写请求的自然顺序，我们也可以强制对其排序。附加为每一个写请求附加一个时间戳，然后选择最新的时间戳，丢弃较早时间戳的写入。这个冲突解决算能被称为最后写入获胜（LWW, last write wins）

LWW 可以达成最终一致，但代价是牺牲数据持久性。如果同一个主键有多个并发写，即使这些并发写都向客户端报告成功（因为完成了写入 w 个副本），但最后只有一个写入值会存活下来，其他的将被系统默默丢弃。

在某些场景下，由于 LWW 会导致数据的覆盖和丢失，所以它并不是一个好的选择。要确保 LWW 安全无副作用的唯一方法是：只写入一次然后写入值视为不可变，这样就避免了对同一主键的并发（覆盖）写。

Happens-before关系和并发

如何判断两个操作是否是并发呢？通常如果两个操作同时发生，则称之为并发，然而事实上，操作是否在时间上重叠并不重要，由于分布式系统中复杂的时钟同步问题，现实当中，我们很难严格确定它们是否同时发生。为了更好的定义并发性，我们并不依赖确切的发生时间，即不管物理的时机如何，如果两个操作并不需要意识到对方，我们即可称它们是并发操作。

如果 B 知道 A，或者 B 依赖于 A，或者以某种方式在 A 的基础上构建，则称操作 A 在操作 B 之前发生。这是定义何为并发的关键。事实上，我们也可以简单地说，如果两个操作都不在另一个之前发生（或者两者都不知道对方） ，那么操作是并发的。

确定前后关系

服务器判断操作是否并发的依据主要依靠对比版本号 ，而并不需要解释新旧值本身（值可以是任何数据结构）。算法的工作流程如下：

服务器为每个主键维护一个版本号，每当主键新值写入时递增版本号，井将新版本号与写入的值一起保存。
当客户端读取主键时，服务器将返回所有（未被覆盖的）当前值以及最新的版本号。且要求写之前，客户必须先发送读请求。
客户端写主键，写请求必须包含之前读到的版本号、读到的值和新值合并后的集合。写请求的响应可以像读操作一样会返回所有当前值，这样就可以一步步链接起多个写入的值。
当服务器收到带有特定版本号的写入时，覆盖该版本号或更低版本的所有值（因为知道这些值已经被合并到新传入的值集合中），但必须保存更高版本号的所有值（因为这些值与当前的写操作属于并发）。

当写请求包含了前一次读取的版本号时，意味着修改的是基于以前的状态。如果一个写请求没有包含版本号，它将与所有其他写入同时进行，不会覆盖任何已有值，其传入的值将包含在后续读请求的返回值列表当中。

合并同时写入的值

如果多个操作并发发生，则客户端必须通过合并并发写入的值来继承旧值。

版本矢量

所有副本的版本号集合称为版本矢量。 当读取数据时，数据库副本会返回版本矢量给客户端，而在随后写入时需要将版本信息包含在请求当中一起发送到数据库。版本矢量技术使数据库可以区分究竟应该覆盖写还是保留并发值。

版本矢量可以保证从某一个副本读取值然后写入到另一个副本，而这些值可能会导致在其他副本上衍生出来新的“兄弟”值，但至少不会发生数据丢失且可以正确合并所有并发值。