复制的难点在于处理复制数据的变更
复制时的权衡：使用同步复制还是异步复制？如何处理失败的副本？

领导者与追随者

多副本问题：如何确保数据都落在了所有副本上--基于领导者的复制（主从复制）
主从复制原理

• 领导者将新数据写入本地存储时，会将数据变更发送给所有追随者，称为复制日志或变更流
• 每个追随者从领导者拉取日志，并相应更新其他数据库副本，按照领导者处理的相同顺序应用所有写入
• 写数据：领导者；读数据：领导者或追随者
  热备：能接受客户端读请求的副本
  温备：追随领导者，不处理客户端的任何查询
  

同步复制与异步复制

同步复制的速度：从库可能落后主库几分钟或更久，例如：从库正在从故障中恢复，系统在最大容量附近运行，或者节点之间存在网络问题

• 同步复制优点：从库保证有与主库一致的最新数据副本
• 同步复制缺点：如果从库没有响应，主库无法处理写入操作。主库必须组织所有写入，等待从库再次可用
  半同步：一个主库与从库同步，其他从库异步。保证至少两个节点拥有最新的数据副本
  主从同步：完全异步，但写入不能保证持久，因为主库同步从库前可能发生主库宕机。【链式复制：同步复制的变体，可以解决】

设置新从库

• 获取主库的快照
• 将快照复制到新从库节点
• 从库连接到主库，并拉去快照后的所有数据变更。要求快照与主库复制日志中的位置精确关联，比如MySQL中的binlog
• 从库处理完快照之后积压的数据变更，可以继续处理主库产生的数据变化了

处理节点宕机

目标：即使个别节点失效，也能保持整个系统运行

• 从库失效：从库恢复后，从日志中获得发生故障前最后一个事务，连接到主库，请求从从库断开连接时发生的所有数据变更
• 主库失效：故障切换

复制日志的实现

基于语句的复制

主库记录下它执行的每个写入请求（语句（statement））并将该语句日志发送给其从库。
存在问题：

• 任何调用 非确定性函数（nondeterministic） 的语句，可能会在每个副本上生成不同的值。比如 NOW(), RAND()
• 如果语句使用了自增列（auto increment），或者依赖于数据库中的现有数据（例如，UPDATE ... WHERE <某些条件>），则必须在每个副本上按照完全相同的顺序执行它们，否则可能会产生不同的效果。影响并发
• 有副作用的语句（例如，触发器，存储过程，用户定义的函数）可能会在每个副本上产生不同的副作用，除非副作用是绝对确定的

传输预写式日志WAL

对于覆写单个磁盘块的B树，每次修改都会先写入 预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态

• 日志都是包含所有数据库写入的仅追加字节序列。可以使用完全相同的日志在另一个节点上构建副本：除了将日志写入磁盘之外，主库还可以通过网络将其发送给其从库
• 当从库应用这个日志时，它会建立和主库一模一样数据结构的副本
• 日志记录的数据非常底层，因此主从库需要运行相同版本的数据库软件
• 运维时如果升级软件版本，有可能会要求停机

逻辑日志复制（基于行）

复制和存储引擎使用不同的日志格式，复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来

• 关系型数据库通常以行作为粒度描述数据库写入的记录序列
  • 对于插入的行，日志包含所有列的新值
  • 对于删除的行，日志包含足够的信息来唯一标识已删除的行。通常是主键，或者所有列的旧值
  • 对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列（至少是更新列）的新值
• 修改多行，会生成多个这样的记录，后面跟着事务已提交的记录--MySQL使用此方法
• 优点
  • 逻辑日志与存储引擎分离，方便向后兼容。可以让领导者和跟随者运行不同版本的数据库软件
  • 对于外部应用，逻辑日志也更容易解析。比如复制到数据仓库，或者自定义索引和缓存。被称为数据变更捕获

基于触发器的复制

复制延迟问题

• 异步复制时，如果从库落后，并提供了读，可能导致同时对主从库执行查询，得到不同结果
• 异步复制特性：最终一致性

读己之写一致性

用户在提交数据后，总会看到自己提交的任何更新，其他用户可能稍后看到。保证用户自己的输入被正确保存

• 写后读，走主库，比如主库读取自己档案，从库读取其他用户档案
• 如果应用中大部分内容被用户编辑，上述方案无效。可以指定更新后的时间窗口，比如上次更新的一分钟内从主库读。
• 客户端记录最近一次写入的时间戳，从库提供查询时，保证该时间戳前的变更都已经传播到了本从库；否则从另外的从库读，或者等待从库追赶上来
• 如果副本在多个数据中心，比较复杂。任何需要从领导者提供服务的请求，都必须路由到包含主库的数据中心。

用户跨设备同时发出请求，情况更为复杂

• 记录更新时间戳变得更困难。元数据需要一个中心存储
• 不同设备可能路由到不同的数据中心。如果你的方法需要读主库，就需要把同一用户的请求路由到同一个数据中心

单调读

时光倒流：用户顺序进行多次读取，路由到了进度不同的从库。先看到的数据突然消失

• 单调读：确保同一用户总是从同一副本读，可以通过对用户ID哈希的方式进行路由

一致性前缀读

分区/分片数据库问题：不同分区之间独立，不存在全局写入顺序。可能出现一系列事件前后顺序不一致问题（用户从从库中读取数据时，可能看到数据库某些部分处于就状态，某些处于新状态）。比如回答可能在提问前发生

• 一致性前缀读：任何因果相关的写入都写入相同分区

多主复制

• 基于领导者复制的主要缺点：只有一个主库，所有的写入都要通过它
• 多个领导者的复制：允许多个节点接受写入，复制仍然是转发给所有其他节点。每个领导者也是其他领导者的追随者

多主复制应用场景

运维多个数据中心

基于领导者的复制设置，主库必须位于其中一个数据中心，且所有写入都必须经过该数据中心
多领导者配置中可以在每个数据中心都有主库。每个数据中心内使用常规主从复制；数据中间，每个数据中心的主库都会将其更改复制到其他数据中心的主库

运维多个数据中心时，单主和多主的比较

性能

• 单主配置：每个写入都得穿过互联网，进入主库所在的数据中心。会增大写入时间
• 多主配置每个写操作都可以在本地数据中心进行处理，与其他数据中心异步复制。感觉到性能更好。

容忍数据中心停机

• 单主配置：如果主库所在的数据中心发生故障，必须让另一个数据中心的追随者成为主领导者
• 多主配置：每个数据中心都可以独立于其他数据中心继续运行。若发生故障的数据中心归队，复制会自动赶上

容忍网络问题

• 单主配置：单主配置对网络连接问题非常敏感，因为写是同步的，数据中心之间网络不如数据中心内的本地网络可靠
• 多主配置：异步复制的多主配置更好地承受网络问题

多主复制缺点：两个数据中心可能修改相同内容，写冲突必须避免

需要离线操作的客户端

例如手机、笔记本的日历等，无论是否联网，都需要随时能查看会议，并且如果在离线情况下做任何更改，设备上线时需要与服务器和其他设备同步

• 每个设备都有一个充当领导者的本地数据库（接受写请求），在所有设备的日历副本之间同步时，存在异步的多主复制过程，复制延迟取决于何时访问互联网
• 相当于每个设备都是一个数据中心

协同编辑

• 一个用户编辑文档时，所做的更改将立即应用到其他副本，并异步复制到服务器和编辑同一文档的任何其他用户
• 如果想要不发生编辑冲突，则应用程序需要先将文档锁定，然后用户才能进行编辑；如果另一用户想编辑，必须等待第一个用户提交修改并释放锁定。这种协作模式相当于主从复制模型下在主节点上执行事务操作
• 为了加速写作，可编辑的粒度需要非常小（例如单个按键，甚至全程无锁）

处理些写入冲突

多主复制最大的问题：写冲突

同步与异步冲突检测

• 单主数据库：第二个写入被阻塞，等第一个写入完成，或被终止
• 多主复制：两个写入都成功，稍后的时间点仅仅异步检测到冲突
• 如果想冲突检测同步-即等待写入被复制到所有副本，然后再告诉用户写入成功，但是这失去了多主复制优势

避免冲突

• 避免冲突：应用程序确保特定记录的所有写入都通过同一个领导者
• 但是如果数据中心故障，需要把流量重新路由，就会导致冲突避免会中断，必须处理不同主库同时写入的可能性

收敛至一致的状态

• 最后写入胜利LWW：给每个写入一个唯一的ID，挑选最高ID的写入作为胜利者，并丢弃其他写入，但容易导致数据丢失
• 以某种方式将值合并在一起：例如，按字母顺序排序，然后连接，上图得到的结果可能是B/C
• 在保留所有信息的显示数据结构中记录冲突，并编写解决冲突的应用程序代码（也许通过提示用户的方式）。

自定义冲突解决逻辑

写时执行

数据库检测到复制更改日志中存在冲突，调用冲突处理程序

读时执行

检测到冲突时，所有冲突写入被存储。下次读取数据时，会将多个版本的数据返回给应用程序。应用程序可能提示用户或自动解决冲突，并将结果写回数据库

• 冲突解决适用于单个行或文档层面，而不是整个事务。如果有一个事务会原子性的进行几次不同的写入，则对于冲突解决而言，每个写入仍需分开单独考虑

多主复制拓扑

• 复制拓扑：描述谢图从一个节点传播到另一个节点的通信路径
• 两个以上的领导者，拓扑很多样，其中MySQL仅支持环形拓扑
  
• 防止无限复制循环：因为圆形和星型拓扑，节点需要转发从其他节点收到的数据更改。每个节点都有唯一的标识符，在复制日志中，每个写入都标记了所有已经过的节点的标识符
• 多主拓扑结构的问题：
  • 一个节点故障，可能中断其他节点之间的复制消息流
  • 拓扑结构可以重新配置，但需要手动操作
  • 全部到全部的容错性更好，避免单点故障，但可能因为网络问题导致消息顺序错乱--通过版本向量技术解决
    

无主复制

无主复制：客户端直接写入到几个副本中；或者协调者节点代表客户端进行写入，但协调者不执行特定的写入顺序

节点故障时写入数据库

无助复制时，如果节点发生故障，客户端的写请求并行发送给所有副本，节点故障的副本错过写入，在后续恢复之后客户端的读请求，可能将旧值作为响应--通过将读请求并行发送到多个节点解决，版本号用于确定哪个值更新

读修复和反熵

故障节点重新联机后，如果赶上它错过的写入？

读修复

客户端并行读取多个节点时，可以检测到旧值，将新值写回，适合读多场景

反熵过程

一些数据库存储具有后台进程，该进程不断查找副本之间的数据差异，将任何缺少的数据从一个副本复制到另一个副本，但复制可能存在显著延迟

读写的法定人数

假定有n个读本，每个写入必须有w个节点确认才能被认为是成功的，并且必须至少为每个读取查询r个节点

• 只要\(w + r > n\),就可以在读取时获取最新的值
• w值的读写称为法定人数的读写
• 常见选择使n为奇数（通常为3或5），并设置\(w = r = (n - 1) / 2\)（向上取整）
• 根据需要更改，例如\(w = n\) 和\(r = 1\)就是和读多写少场景，这样读速度更快，但是会一个失败节点导致所有数据写入失败

仲裁条件\(w + r > n\)允许系统容忍不可用的节点

• 如果\(w <n\)，如果节点不可用，我们仍然可以处理写入
• 如果\(r <n\)，如果节点不可用，我们仍然可以处理读取
• 对于\(n = 3，w = 2，r = 2\)，我们可以容忍一个不可用的节点
• 对于\(n = 5，w = 3，r = 3\)，我们可以容忍两个不可用的节点
• 通常，读取和写入操作始终并行发送到所有n个副本。 参数w和r决定我们等待多少个节点，即在我们认为读或写成功之前，有多少个节点需要报告成功

仲裁一致性的局限性

但是，即使在 \(w + r> n\) 的情况下，也可能存在返回陈旧值的边缘情况。

• 如果使用了宽松的法定人数，w 个写入和 r 个读取落在完全不同的节点上，r节点和w节点之间不再保证有重叠节点
• 两个写入同时发生，不清楚哪一个先发生
• 写操作和读操作同时发生，写操作可能仅反映在某些副本上。通过合并并发写入，如果根据时间戳选出胜利者，则由于时钟偏差可能导致写入丢失
• 读写同时发生，写操作可能仅反应在某些副本，这时读取结果不确定是旧值还是新值
• 写操作在某些副本上成功，而在其他节点上失败，在小于w个副本上写入成功，整体写失败，但是写成功的副本没有回滚，后续读可能读取到这次失败的值
• 如果携带新值的节点失败，需要读取其他带有旧值的副本，并且其数据从带有旧值得副本中恢复，存储新值得副本数低于w，打破法定人数条件
• 即使一切工作正常，有时也会不幸地出现关于时序（timing） 的边缘情况

不要把 w 和 r 当做绝对的保证，应该看做是概率。
强有力的保证需要事务和共识

监控陈旧度

• 基于领导者的复制，数据库会公开复制滞后得度量标准，可以做监控
• 无领导复制中，没有固定的写入顺序，监控困难

宽松法定人数与提示移交

• 问题：网络中断导致剩余可用节点可能少于w或r，客户端达不到法定人数
• 权衡
  • 对于所有无法打到w或r节点法定人数的请求，是否返回错误是更好的？
  • 或者是否应该接受写入，然后将它们写入一些可达的节点，但不在这些值通常所存在的n个节点上--宽松的法定人数
• 大型集群中，节点数量明显多于n个，写和读仍然需要w和r个成功的响应，但是不来自指定的n个节点
• 提示移交：网络中断得到解决时，另一个节点临时接收的一个节点的任何写入都被发送到适当的“主”节点
  优点：提高了写入可用性：任何w个节点可用，数据库就可以接受写入
  缺点：即使当\(w + r> n\)时，也不能确定读取某个键的最新值，因为最新的值可能已经临时写入了n之外的某些节点

运维多个数据中心

• 无助复制也适用于多数据中心操作，因为它旨在容忍冲突的并发写入，网络中断和延迟尖峰
• 无论数据中心如何，每个来自客户端的写入都会发送到所有副本，但客户端通常只等待来自其本地数据中心内的法定节点的确认，从而不会受到跨数据中心链路延迟和中断的影响
• 对其他数据中心的高延迟写入通常被配置为异步发生，尽管配置有一定的灵活性

检测并发写入

• 无主复制，允许多个客户端同时写入相同的key，会冲突
• 读修改和提示移交期间可能也发生冲突
  

最后写入胜利（丢弃并发写入）

• 方法：最后写入胜利
• 优点：实现了最终收敛的目标
• 缺点：以持久性为代价，会丢失数据，甚至可能会删除不是并发的写入
• 使用场景：唯一安全的方法，即每一个键只写入一次，然后视为不变，避免并发更新

“此前发生”的关系和并发

• 需要一个算法知道两个操作是否并发，如果一个操作再另一个操作之前，后操作直接覆盖早操作，如果是并发的需要解决冲突

捕获“此前发生”关系

服务器可以通过查看版本号来确定两个操作是否并发的，算法原理

• 服务器为美俄key保留一个版本号，每次写入key时都增加版本号，并将新版本号与写入的值一起存储
• 当客户端读取key时，服务器将返回所有未覆盖的值以及最新的版本号，客户端在写入前必须读取
• 客户端在写入Key时，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在一起。（针对写入请求的响应可以像读取请求一样，返回所有当前值，这使得我们可以像购物车示例那样将多个写入串联起来）
• 当服务器接收到具有特定版本号的写入时，可以覆盖该版本号或更低版本的所有值，但是必须用最高的版本号来保存所有的值

当一个写入包含前一次读取的版本号时，会告诉我们的写入是基于之前的哪一种状态

合并同时写入的值

• 优点：没有数据被无声的丢弃
• 缺点：客户端需要额外的工作
• 合并并发值问题：当多个操作并发发生，客户端需合并并发写入的值（称其为兄弟值），简单按版本号或时间戳选择一个值会丢失数据，以购物车为例可采用集合求并等更合理方法，但涉及删除操作时需用 “墓碑” 标记已删除项目，还可利用如 Riak 的数据类型支持的 CRDT 等数据结构自动合并兄弟值。

版本向量

• 版本向量概念：在有多个副本但无领导者时，除对每个键使用版本号外，每个副本处理写入时增加自己的版本号并跟踪其他副本的版本号，所有副本的版本号集合称为版本向量
• 版本向量作用：版本向量从数据库副本发送到客户端再发回数据库，可区分覆盖写入和并发写入，确保从一个副本读取并写回到另一个副本时安全，虽可能产生兄弟值，但正确合并就不会丢失数据。
• 与矢量时钟关系：版本向量有时也被称为矢量时钟，虽不完全相同，但在比较副本状态时，版本向量是正确的数据结构。