1. 主从复制

工作原理：

指定某个副本为主副本（主节点），写请求先发送给主副本，并写入本地存储
其它副本为从副本（从节点），主副本写入存储后，将数据更改发给所有从副本，从副本将其应用到本地，顺序与主副本严格一致
客户端可从主和从副本读，但只能向主副本写

1.1. 同步/异步复制

同步复制：一旦向用户确认，从节点保证完成了与主节点的更新同步；但从节点无法完成确认，写入不能成功，引起阻塞。（通常只开启一个节点的同步，其它是异步的）

异步复制：主节点奔溃则导致未复制的请求丢失，即使向用户确认了写操作（复制滞后）。但系统吞吐性更好。

1.2. 配置新的从节点

在不锁定数据库条件下（不违反高可用），可以：

某个时间点对主节点的副本生成一个一致性快照
将快照拷贝到新的从节点
从节点向主节点请求快照点之后所发生的数据更改日志
获取日志后，应用快照点后的变更（即追赶复制），之后可以继续处理主节点的新的变化

1.3. 处理节点失效

1.3.1. 从节点失效——追赶复制

根据副本日志，从节点直到故障前最后一个事务，然后请求主节点之后的变更，应用变更来追赶主节点。

1.3.2. 主节点失效——节点切换

从某个从节点中选择一个作为主节点，客户端也需要更新。

自动切换的流程通常为：

确认主节点失效，通常使用超时机制（心跳）
选举新的主节点，可通过选举达成共识或之前主节点指定的方式
重新配置使新的主节点生效，并更新客户端

但仍然充满变数：异步复制的数据丢失/不一致，脑裂，如何检测失效等

1.4. 复制日志的实现

1.4.1. 基于语句的复制

最简单的情况，主节点把所有请求的语句作为日志直接发给从节点。

但语句对系统有副作用的时候，并不合适。

1.4.2. 基于预写日志(WAL)传输

对于大多数事务数据库，会有预写日志，直接把日志发给从节点，根据日志可让从节点构建相同的副本。

缺点：WAL描述数据过于底层，导致复制方案和存储引擎紧耦合（升级的时候会有麻烦）。

1.4.3. 基于行的逻辑日志复制

关系日志的逻辑日志：包含一系列记录，描述数据表行级别的写请求

行插入：日志包含所有相关列的值
行删除：若有唯一标识（通常为主键），则使用唯一标识；否则记录所有列的旧值
行更新：对应行的唯一标识以及所有列/已更新列的新值

它和存储引擎解耦，容易保持向后兼容，且易于解析。

1.4.4. 基于触发器的复制

将复制交给应用上层触发，更加有灵活性，但开销更大，且易出错。

2. 复制滞后

最终一致性：（异步）主从复制下，从节点会滞后于主节点，读请求在不同节点上的结果会暂时的不同，但最终会一致。

滞后时间过长，会出现很多的问题。

2.1. Read-After-Write/Read-Your-Write

Q：客户端写入数据后，在从节点上读不到数据。

A：实现Read-after-write/Read-your-write（两个是一样的）一致性，保证某个用户重复读，总能看到自己最近提交的更新，但对其它用户不保证。

实现：

若用户访问可能修改的内容，从主节点读取；否则，可从从节点读取
跟踪最新时间，在一段时间内只能从主节点读取；监控复制滞后程度，避免从滞后时间过长的从节点上读取
客户端可记录最近的更新时间戳（逻辑或实际的），附带到请求中，系统可确保提供读服务的节点上至少包含该时间戳的更新
若副本分布在多个数据中心，必须把请求路由到主节点所在的数据中心

2.2. Monotonic Reads

Q：客户端写入数据，先向从节点1读，读到数据，而再向从节点2读，读不到数据（由于滞后），似乎被回滚

A：实现Monotonic reads一致性，某个用户多次读取，永远读不到比之前读到的数据更旧的值

实现：确保每个用户总在一个固定的副本上读取（不同用户可在不同的副本上读取），如基于用户ID进行散列

Monotonic Write: 服务端（所有相关节点）和客户端的写顺序必须相同

2.3. Consistent Prefix Reads

Q：不同用户的写入（按顺序）$W_1, W_2$分布到不同分区，由于复制滞后，观察者从不同分区的从节点读取内容，观察到的顺序可能相反，即先读到$W_2$，然后才是$W_1$（在有因果顺序的时候，往往是错的）

A：实现Consistent prefix reads一致性，即保证：对于一系列按照某个顺序发生的写请求，读取这些内容的时候也要按照写入的顺序

实现：

有因果或其它顺序要求的写入，都交给一个分区（效率低）
利用算法追踪因果关系（后面叙述）

2.4. 复制滞后的解决方案

在最终一致性系统中，若滞后来带严重的问题时，可考虑：

使用更强的一致性，如Read-after-write
使用分布式事务

3. 多主复制

主从复制的缺点：写只能经过一个主节点，主节点挂掉会对写入造成巨大影响

多主复制：多个主节点可以接收写操作，后面的操作类似（可能还需要冲突解决的模块），而主节点可作为其它节点的从节点

3.1. 适用场景

3.1.1. 多数据中心

多主复制和主从复制的区别：

	多主复制	主从复制
性能	写请求可路由到最近的数据中心，延迟小	写请求必须路由到主节点的数据中心，延迟大
容忍数据中心失效	每个数据中心独立运行，故障的数据中心恢复后即可更新到最新状态	必须切换数据中心，将一个从节点提升为主节点，然后恢复
容忍网络问题	异步复制采用的多，依赖网络小	同步复制采用的多，更依赖网络

而缺点有：

多主产生写入冲突（最大的问题）
与其它数据库功能交互时会有副作用

3.1.2. 离线客户端操作

当终端与网络断开时，也得可用。这时终端充当主节点，然后在所有终端上异步同步这些多个主节点的副本。协作编辑也可以是一个类似的例子。

它们都会遇到写入冲突的问题。

3.2. 处理写入冲突

3.2.1. 避免冲突

最简单的策略，即应用层让特定请求总是通过一个主节点。（最极端的情况即主从复制）

3.2.2. 收敛于一致状态

数据库在多主节点上必须以一种收敛于趋同的方式解决冲突，即更改被复制、同步后，所有副本最终值一样。方式可以有：

给请求赋上ID（如时间戳），挑选ID最大的写入，其它丢弃。（时间戳下，为最后写入者获胜。数据易丢失，缓存系统中适用）
每个副本赋上唯一ID，制定规则规定写入顺序（如ID高先写，但数据易丢失）
以某种方式将这些值合并
记录和保留冲突信息，依靠上层逻辑解决冲突

3.2.3. 自定义冲突解决逻辑（依赖上层）

最好的方式。大多数多主复制模型都提供这种方式，可在：

写入时执行：写入时，根据日志和规则解决冲突，通常在后台进行，不能提醒用户
读取时执行：读取时，所有的冲突值（前提要保留所有的冲突值）返回给应用层，让应用层决定，最后将结果返回到数据库

3.2.4. 自动冲突解决

如通过：

无冲突的复制数据类型（CRDT），可以由多个用户同时编辑，并内置合理的方式解决冲突
可合并的持久数据结构。类似于git，跟踪变更历史，提出三向合并（CRDT是双向合并）
操作转换，一种冲突解决算法

3.3. 拓扑结构

复制的拓扑结构描述了一个写请求传播到其它节点的路径，包括：环形、星型、全部-全部型。

前两种，当路径上某个节点失效，会影响其它节点的复制转发。因此，需要有多条路径可选。

最后一种，有网络开销大以及复制日志的覆盖（顺序问题，覆盖了前面的更改）问题。

4. 无主复制

允许任何副本直接接收客户端的写入。

实现方式：

客户端直接将写入（并行）发送到多副本
有一个协调者代表客户端进行写入，但不维护写入顺序

4.1. 节点失效后的写入

写入：并行向所有副本写入，成功比例达到一定值后即可认为成功

读取：并行向所有副本发送读请求，采用最新版本号的数据

这样较少节点失效时，也能读写新数据

4.1.1 读修复 & 反熵 —— 失效节点再上线后的追赶

读修复：读取频繁场景下，客户端读取到多个副本，取最新，并将新值写入到旧副本上

反熵：后台进程不断查找不同副本之间的差异，将缺少的数据从一个副本复制到另一个副本，但有明显的同步滞后

4.1.2. 读写quorum（严格）

假定总共有$n$个副本，写入至少需要$w$个节点（从那$n$个节点中）的确认，读至少查询$r$个节点（从那$n$个节点中）并得到结果，则只需要$w + r > n$，就能保证读取一定包含最新值。

这里读写操作必须作用到设定好的$n$个副本/节点上

以上为（严格）法定票数读写，若不满足票数条件，客户端可直接返回错误，提示集群不可用。

通常$n$为奇数，$w = r = \frac {(n + 1)}{2}$

4.2. Quorum一致性和局限性

$w + r > n$下也可能返回旧值，情况可能为（通常在最终一致性情况下）：

若采用sloppy quorum，写操作$w$与读操作$r$可能不重叠，造成读取旧值
两个写同时发送，无法明确顺序，唯一安全的方法是合并（机器时间戳不行）
写和读同时发生，写可能只在一部分副本完成，读取的内容不确定（实际的$w’ < w$并和$r$不重合）
和上条类似，若一部分写入成功，一部分写入失败，总数小于$w$，成功副本上不回滚，则读可能是新值也可能是旧值
若具有新值节点失效，恢复时来自旧值（这是可能的，如通过读恢复），则总的新值副本会小于$w$，打破了判定条件
一切正常情况下也会有边界情况

4.2.1. 监控旧值

主从复制：数据库导出复制滞后的指标（可通过日志执行偏移量），集成到监控模块

无主复制：由于没有固定的写入顺序（写入到不同副本的），监控更加困难，若只支持读时修复，则旧值的落后程度没有上限。因此没有很普及。

4.2.2. 宽松quorum和数据回传

宽松的读写仲裁：读写仍然满足$w + r > n$条件，但是读写操作包含了并不在之前指定的$n$个节点（即将请求暂存到另一个不在$n$个指定节点集合的节点）。

它大大提高写可用性（只要有$w$个节点可用即可），但在$w + r > n$下不能保证读到新值（新值可能在$n$个节点之外的某个节点），因此需要数据回传，将新值传回$n$个指定节点（回传未结束，就不保证读到新值）。

4.2.3. 多数据中心

无主复制也可以应用到多个数据中心的场景。

4.3. 检测并发写

4.3.1. Happens-Before关系和并发

并发：两个操作都不在（或不知道在）另一个操作前发生

若$A$操作与$B$操作有先后关系，则使用覆盖；否则$A$与$B$为并发，需要解决冲突，见3.2节。

4.3.2. 确定先后关系

主要依赖版本号，算法工作流程为：

服务器为每个主键维护一个版本号$v$，每次写入新值，$v = v + 1$, 并将其保存
客户端读取时，服务器返回所有当前值以及最新版本号$v$，且要求客户端写之前，必须先读
客户端写入时，请求包含之前的版本号$v$，读到的值和新值的合并值$V_r \cup V_{new}$。响应可像读操作一样，返回所有当前值

若无版本号，则认为写请求与其它写请求并发。传入值会在后续读请求的返回值中，用于合并并发写入
服务器受到特定版本号的写入时，覆盖该版本号以及更低版本的所有值，但必须保留更高版本号的所有值

上述算法可保证数据丢失，但是并发操作时，客户端必须合并并发写入，以继承旧值（因此可设计专门的数据结构执行合并，如CRDT）

对于删除操作，删除操作需要添加一个对应的版本号，作为标记，表明这个删除是否在合并时被应用上去（即墓碑）

4.3.3. 版本矢量

在无主复制的多副本场景下，每个副本都要创建一个版本矢量（类似于矢量时钟，之前的整理中详细说明过），写入时增加自己的版本号，并跟踪其它副本的版本号。通过它决定并发操作时，哪些需要覆盖，哪些需要保留。

和之前单副本一样，读时返回版本矢量，写入时将版本信息稍带到请求中给数据库，但依旧需要执行合并操作，不过不会丢失数据