这篇文章是ddia第五章的阅读笔记。
0x00 Pre
前面的部分都是在一台机器上。
出于一些原因，需要将数据复制到多台机器上：
- 就近部署：降低延迟；
- 高可用性：一台出故障系统仍可用；
- 高吞吐量：多台机器可以提高吞吐量。
一个假设，一份副本足以存储在一台机器上。
如果副本过大，就需要分片了。
好的，为了达到复制的目的，应该怎么做呢？会有什么问题呢？该怎么解决呢？
0x01 主节点与从节点
有三种复制的方式：主从复制、多主节点复制和无主节点复制。
首先看看主从复制。基本过程如下：
- 指定一个主节点。写请求都在这个节点上进行；
- 其他副本都是从节点，主节点把数据写入本地之后将数据更改作为复制日志发送给从节点。从节点根据日志进行更新，和主节点保持一致；
- 所有的从节点只处理读请求。
主从复制是一种很常见的复制方式。不仅关系型数据库在用，好多NoSQL数据库也在用，比如MongoDB等。
1.1 同步复制与异步复制
问题来了，主节点和从节点之间的更新，是同步复制呢还是异步复制？
下图展示了这两种方案：
同步复制的优点很明显，一旦确认成功那么数据已经处于最新版本；不过也有缺点，就是如果其他节点没有成功那么就需要等待。
实际使用中，如果数据库启用了同步复制，通常意味着其中某一个从节点是同步的，其余的从节点是异步的。
这就是半同步（semi-synchronous）。
还可以是全异步模式，如果这个时候主节点失败且不可恢复，那么所有尚未复制到从节点的写请求都会丢失。但是全异步模式下主节点可以处理更多的写请求，系统的吞吐量大。
还有一种方式是链式复制（chain replication）。
1.2 配置新的从节点
添加新的从节点的步骤如下：
- 在某个时间点对数据副本生成一个一致性快照，可以避免长时间锁定数据库。对于MySQL，需要使用innobackupex；
- 将快照复制到新的从节点；
- 从节点向主节点请求快照之后的更新日志。这个位置在MySQL中叫做binlog coordinates；
- 从节点获取日志后应用更新，来追上主节点。然后就可以继续处理数据变化了。
1.3 处理失效节点
任何时候任何节点都有可能出现问题。
我们需要做到的是，尽管个别节点会出现中断，但要保持系统总体的持续运行，并尽可能减小节点中断带来的影响。
1.3.1 从节点失效：Catch-up recovery
和添加新的从节点类似，如果一个从节点失效并顺利重启的话，可以知道自己的更新日志的位置，然后向主节点请求之后的日志，根据这些日志更新数据来追上主节点即可。
1.3.2 主节点失效：Failover
主节点失效了就复杂了。需要选一个从节点作为主节点，客户端新的写请求需要发送到新的主节点，然后其他的从节点从这个新的主节点接收变更日志。
可以手动也可以自动切换主节点。自动切换过程如下：
- 确认主节点失效。通常可以使用心跳检测来确认；
- 选举新的主节点。这是一个共识问题（consensus problem）；
- 使新主节点生效。写请求发送给新的主节点。
不过切换过程中可能会有很多问题：
- 如果使用心跳检测来确认主节点失效的话，那么多长时间合适呢？太长意味着系统恢复时间长，太短意味着可能频繁的切换；
- 如果使用异步复制，且失效前新的主节点没有接收到原主节点的数据，切换之后原主节点重新上线并加入集群，那么就有可能发生冲突。一个简单的办法就是丢弃原主节点未完成复制的数据，造成数据丢失；
- 如果简单的丢弃数据，就会有严重的问题。尤其在mysql+redis的系统中，数据不一致可能会导致严重的问题；
- 可能会发生，新旧主节点都认为自己是主节点（split brain），需要强制关闭一个主节点。
这些问题都挺复杂，包括节点失效（node failures）、网络不可靠（unreliable networks）、副本一致性（replia consistency）、持久性（durability）、可用性（availability）和延迟（latency）等，以及之间的平衡。
1.4 复制日志的实现
复制日志如何实现？
1.4.1 基于语句的复制
最简单的，是直接将语句同步给从节点，然后从节点按照接收的顺序执行一遍。
不过这个问题有点大，比如一些语句有非确定性函数NOW()等，就会不一致。
基本上不使用这种方式。
1.4.2 基于预写日志（WAL）传输
不管是日志结构存储引擎还是使用Btree结构的存储引擎，都会将数据库写入的字节序列写入日志。
因此可以将这个日志发送给从节点，来进行数据更新。
不过这个预写日志的缺点是数据非常底层，和存储引擎紧密耦合。
也不推荐使用。
1.4.3 基于行的逻辑日志复制
和预写日志类似，但是数据格式和存储逻辑剥离，这就是逻辑日志（logical log）。
每一行的数据变更都可以记入日志，从节点就可以根据这个日志进行数据更新。
在mysql中，配置为基于行的复制时，binlog就是使用的这种方式。
1.4.4 基于触发器的复制
还可以使用触发器和存储过程。
不过这个开销有点高，也不推荐。
0x02 复制滞后问题
主从复制下，所有的写请求都在主节点上，从节点只处理读请求。
这个方式适用读密集的负载，比如web应用。创建多个从节点，就可以提高系统的吞吐量。
不过这样只能使用异步复制，不然一个节点失败就会导致整个系统无法写入。
如果使用异步复制，虽然可以达到最终一致性（eventual consistency），也会有各种复制滞后问题。
2.1 读自己的写
写入不久即查看数据，复制没有完成，看起来没有写成功：
这里需要写后读一致性（read-after-write consistency）或读写一致性（read-your-writes consistency）。
这个一致性保证，如果用户重新加载页面，总能看到自己最近提交的更新；但对其他用户没有任何保证，这些更新其他用户可能过会才能看到。
解决方式：
- 如果访问可能会被更新的内容，从主节点读；否则在从节点读。这需要应用程序层面上有一些逻辑需要知道哪些可能被修改。比如个人主页的信息只能所有者更新，所以所有者在主节点上读，其他人在从节点上读就可以了；
- 如果几乎所有的内容都可能被所有人更新，那么上面的方式就不行了了。不然读请求也都到主节点上去了。这个时候可以追踪最近更新的时间，比如最近更新在一分钟内，那么在主节点上读，否则在从节点上读。同时还可以监控从节点的复制滞后程度，避免在过于滞后的从节点上读；
- 客户端还可以记录最近更新时间戳，并附带在请求上。服务器需要保证副本至少包含这个时间戳的更新。如果不够新，可以交给更新的副本来处理。这个相当于版本（version）。
如果涉及到多个设备，那么可能需要跨设备的写后读一致性（cross-device read-after-write consistency）。
2.2 单调读
如果两个同样的读操作被路由到了两个复制状态不一致的机器上，那么就会出现数据向后回滚的情况：
用户2345先看到了用户1234的评论，然后又看不到了，还以为是删除了。
这需要单调读一致性（monotonic reads），比强一致性弱，比最终一致性强的保证。它保证，如果用户进行多次读取，那么不会出现回滚现象。
解决方式：确保同一个用户总是从固定的副本上读取，不同的用户可以在不同的副本上读取。
2.3 前缀一致读
在分区数据库中有一种特殊的问题：
一个诡异的现象，但不合逻辑。
这需要前缀一致性（consistent prefix reads）。就是说，对于一系列按照某个顺序发生的写请求，那么读取这些内容时也会按照写入的顺序。
一个方案是具有因果顺序的写入都交给一个分区，但实现效率低。
不过现在有算法来追踪事件因果关系。
0x03 多主节点复制
单主节点的一个缺点就是主节点只有一个，所有写请求都到主节点上。
自然的扩展就是多个主节点。复制的流程类似，不过，每个主节点还是其他主节点的从节点：
在一个数据中心内部使用多主节点没啥意义，过于复杂。
可以在多个数据中心使用多主节点复制，每个数据中心一个主节点。
还可以对需要离线操作的客户端使用多主节点复制，其中每个客户端都是一个主节点。
进而，多人协作编辑也可以使用多主节点复制，虽然不是数据库复制，但也很类似。
3.1 处理写冲突
在每个主节点都写入成功的情况下，可能会发生冲突：
最理想的处理冲突的方式就是避免冲突。
比如，特定记录的修改路由到特定的主节点来处理。
不过也有问题，万一那个特定的主节点不可用了呢。
那么冲突就不可避免了，不过，需要达到一种最终状态是一致的。
一些方式：
- 最后写入的覆盖之前的，这样会有数据丢失；
- 为每个副本分配一个ID，不同的ID有不同的优先级，高优先级的副本优先于低优先级的副本。这也会有数据丢失；
- 使用某种方式将冲突的数据合并在一起展示；
- 使用预先定义好的格式来将冲突数据保存起来，在应用层上处理。
冲突最好在应用层处理。不过也有一些自动解决冲突的方案：
- 无冲突的复制数据类型（Conflict-free Replicated Datatypes, CRDT）;
- 可合并的持久数据结构（Mergeable persistent data）；
- 操作转换（Operational transformation）。
3.2 拓扑结构
多个主节点之间需要将各自的更新传送到其他的主节点。
那么传递的路径就有多种方式了：
mysql只支持环形拓扑。
环形和星形拓扑的一个问题是，其中的一个节点出现问题会影响整个系统的复制日志转发。
全连接拓扑的问题是，会出现复制日志覆盖的情况：
和前面的前缀一致性类似，这里有因果关系问题。可以使用版本向量（version vector）。
0x04 无主节点复制
前面的都是有主节点的。那么还可以没有主节点。
这样客户端直接将写请求发送到多个副本。
这对数据库的使用有很大的影响。
4.1 节点失效时写入数据库
如下图的情况：
三个副本中只有两个写入成功，那么也可以认为写入成功。
之后失效的节点重新上线，就可能读到过期的数据。
不过可以向多个副本发送读请求，这样可以收到多个结果，然后根据每个结果的版本号来确定哪个结果是新的。
4.1.1 读修复与反熵
这样就会有问题，集群中的数据不一致。
为了解决这个问题，可以有两种方案：
- 读修复（Read repair）：读取的时候如果发现旧数据，那么就用新数据来更新；
- 反熵（Anti-entropy process）：启动一个后台进程不断查找数据差异，并进行更新。
读修复适合频繁读取的场景，不过如果一些数据很少被访问的话就可能很久得不到更新，降低了写的持久性。
4.1.2 读写Quorum
这里给出一个一般性法则，对于有n个副本的集群，至少需要多个副本读写成功才算成功。
如果有n个副本，写入需要w个节点确认，读取必须至少查询r个节点，需要满足 w + r > n。
一般来说n都是某个奇数，然后w=r=(n+1)/2（向上舍入）。
4.2 Quorum一致性的局限
w+r>n保证了可以读到一个最新值：
还可以将w和r设置为较小的数字，这样可以降低延迟，不过有可能读不到最新的值。
即使在w+r>n的情况下，也可能存在返回旧值的边界条件：
- 使用了sloppy quorum，写操作的w节点和读取的r节点没有重合；
- 如果两个写操作同时发生，可以合并处理。如果简单保留最后写入成功的值的话，会有数据丢失；
- 读写同时发生，写操作可能仅在一部分副本上发生，还是可能读到旧值；
- 写成功数小于w，整体视为写失败，但是如果成功的副本不回滚的话，会读取到不应该存在的新值；
- 如果有新值的节点失效后以旧值恢复，那么就破坏了之前的判定条件。
总之，情况很复杂。
4.3 Sloppy Quorums and Hinted Handoff
n副本的集群中读写只需要r和w个有响应即可。对于需要高可用和低延迟的场景来说，还可以降低r和w的值。
网络不总是那么靠谱。如果一个客户端能连接到的副本少于w，但是对其它客户端来说没问题，那么这个倒霉的客户端写入的话该怎么办呢？
- 无法到达w，直接返回错误；
- 接收写请求，将数据写入到n个节点之外的可访问节点。
后一个就是Sloppy Quorum。
等网络问题没了，就把数据从临时的节点发送到原始节点上，叫做数据回传（Hinted Handoff）。
这样可以提高可用性，即使达不到写入所需的w个节点，但只要有可访问的w个节点就可以（包括不是集群中的节点）。
这样，即使满足w+r>n，也可能读取到旧数据。
注意，Sloppy Quorum不是传统意义上的Quorum。
4.4 检测并发写
多个客户端同时写的话，就可能会发生冲突，即使使用严格的Quorum机制。此外，读修复和数据回传的时候也可能发生冲突。
比如：
- 节点1收到A的写请求，但是没有收到B的写请求；
- 节点2先收到A后收到B的写请求；
- 节点3和节点2相反。
如果只是简单的覆盖的话，那么这些节点就达不成一致。
这里更详细地看冲突处理。
4.4.1 最后写入者获胜
Last Write Wins，后写入的覆盖之前的。
LWW通过牺牲数据持久性为代价来达到最终收敛的目标。
4.4.2 Happens-before和并发
happens-before和并发是不同的，对于happens-before来说，后面的写可以覆盖前面的，但是对于并发来说，就不能简单的覆盖。
由于时间问题，并不能仅仅依靠是否时间戳上差不多来定义并发。
如果两个操作并不需要意识到对方，就可以认为是并发操作，即使两者的操作有一定的时间间隔。
4.4.3 确定前后关系
通过下面这个例子来看如何确定前后关系以及并发：
上面的流程可以通过下图来展示：
服务器判断操作是否并发的依据是对比版本号。流程如下：
- 服务器对每一个主键维护一个版本号，每次主键写入的时候将版本号加一，和新值一起保存；
- 客户端读取时，服务器返回所有未被覆盖的值以及最新的版本号。客户端在写之前必须先读；
- 客户端写时，必须附带前一次读时服务器返回的版本号，同时将读到的值和新值合并一起发给服务器；写请求的响应和读一样；
- 服务器收到带有特定版本号的写请求时，覆盖该版本号或更低版本号的所有值，但必须保留更高版本号的所有值。
4.4.4 合并同时写入的值
在多个操作并发发生时，客户端需要将并发写入的值合并。
对于删除的数据不能简单地删除，应该使用一个删除标记。
还可以使用一些专门的数据结构来自动执行合并，比如CRDT。
4.4.5 版本矢量
前面的例子只有一个副本，将情况扩展到多个副本算法类似。
不过需要对每个副本的每个主键都维护一个版本号，构成版本向量（version vector）。
还有一个概念叫做版本时钟（version clocks）。
