目录
- 复制的意义（三点）
- 单领导者（同步复制vs异步复制）
- 复制延迟问题
- 多主复制（适应多数据中心，3种冲突处理方案，3种拓扑结构优缺点）
- 无主复制 （2种副本修复办法，Quorum机制，3种写入冲突的解法）
复制的意义
复制意味着在通过网络连接的多台机器上保留相同数据的副本。
他的作用有
- 使得数据与用户在地理上接近（从而减少延迟）
- 即使系统的一部分出现故障，系统也能继续工作（从而提高可用性）
- 扩展可以接受读请求的机器数量（从而提高读取吞吐量）
复制的问题
如果复制中的数据不会随时间而改变，那复制就很简单：将数据复制到每个节点一次就万事大吉。复制的困难之处在于处理复制数据的变更（change）。我们将讨论三种流行的变更复制算法：单领导者（single leader），多领导者（multi leader）和无领导者（leaderless）。几乎所有分布式数据库都使用这三种方法之一。
使用同步复制还是异步复制？如何处理失败的副本？
单领导者（single leader）
领导者负责写，备份负责读log，同步和领导者的写。log 称为复制日志。
同步复制vs异步复制。
follower 1 是同步复制。
follower 2 是异步复制。
同步复制的优点是，从库保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上上找到。
缺点是，如果同步从库没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主库就无法处理写入操作。主库必须阻止所有写入，并等待同步副本再次可用。
异步的优点就是不阻塞主库的写。但是缺点在于从库可能落后主库几分钟或更久；例如：从库正在从故障中恢复，系统在最大容量附近运行，或者如果节点间存在网络问题。
折中策略：
在数据库上启用同步复制，通常意味着其中一个跟随者是同步的，而其他的则是异步的。如果同步从库变得不可用或缓慢，则使一个异步从库同步。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库。 这种配置有时也被称为半同步（semi-synchronous）
新从库如何同步：
拉取主库的一致性快照。
并拉取快照之后发生的所有数据变更。
当从库处理完快照之后积压的数据变更，代表赶上了。
上述方案也适用于从库挂了。恢复之后怎么做
那么主库挂了该如何？
参见我的文集里的paxos那章。
这些问题没有简单的解决方案。因此，即使软件支持自动故障切换，不少运维团队还是更愿意手动执行故障切换。
复制日志的3种实现
- 直接基于语句 (update xxx where xxx)
问题是可能有些函数不是确定的，那么相同语句会跑出不同结果。同时如果基于全局自增的id，则要求这些日志运行的顺序必须严格一致。
- 基于WAL
数据库在写数据前一般都会先往wal日志里写一条记录。这个日志只能被该数据库数据引擎自己解析从而构建出一致的数据。所以问题是这使复制与存储引擎紧密耦合。如果数据库将其存储格式从一个版本更改为另一个版本，通常不可能在主库和从库上运行不同版本的数据库软件。
- 基于逻辑日志（old val, new val, row id) 又称行日志
为了解决上述问题，可以使复制日志从存储引擎内部分离出来。这种复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来。
- 需要自定义的话可以基于触发器来复制，规则自己配。
复制延迟问题
读己之写
解决思路：只有自己能改的，都从主库读。
可以跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。还可以监控从库的复制延迟，防止任向任何滞后超过一分钟到底从库发出查询。
单调读
解决方案是可以基于用户ID的散列来选择副本，而不是随机选择副本。
因果读
确保任何因果相关的写入都写入相同的分区。
对于某些无法高效完成这种操作的应用，还有一些显式跟踪因果依赖关系的算法
多主复制
在单个数据中心内部使用多个主库很少是有意义的，因为好处很少超过复杂性的代价。 但在一些情况下，多活配置是也合理的。
多主复制在多个数据中心的好处：
1.性能更好
2.可以容忍数据中心停机
3.容忍网络问题
尽管多主复制有这些优势，但也有一个很大的缺点：两个不同的数据中心可能会同时修改相同的数据，写冲突是必须解决的
解决方案：
同步与异步冲突检测
处理冲突的最简单的策略就是避免它们
如果应用程序可以确保特定记录的所有写入都通过同一个领导者，那么冲突就不会发生。由于多领导者复制处理的许多实现冲突相当不好，避免冲突是一个经常推荐的方法
3.收敛到一致状态
在单Leader的机制中：如果对同一个字段有多个更新，最后一个写入确定字段的最终值。而在多Leader的机制中，没有定义的写入顺序，因此不清楚最终值应该是什么。所以数据系统必须以收敛的方式解决冲突，这意味着当所有更改都被复制时，所有副本必须到达相同的最终值。可以为每个写操作分配一个唯一的ID（例如，一个时间戳，一个长的随机数，一个UUID或散列的键和值），最高的ID值认为是最终值，这种技术被称为Last Write Win（LWW）。
4.自定义冲突消解的逻辑
最合适的解决冲突的方法可能取决于应用程序，该代码可以在写或读时执行：一旦数据系统检测到复制更改日志中的冲突，它就调用冲突处理程序。或是在应用程序读取的阶段检测到冲突时，会将这些数据的多个版本将返回应用程序。应用程序可以提示用户或自动解决冲突，并将结果写入数据库。（Cassandra与CouchDB就是采取了这种机制）
多Leader机制的复制拓扑
两个Leader进行同步时，拓扑结构十分简单。但是一旦扩展到4,5个Leader，之后多个Leader之间的同步结构又应该是怎么样的呢？（虽然在实践中，很少采用这样的架构）
最一般的拓扑结构是图（c），其中每个节点都将其写入传递给所有的节点。而（a）或（b）采用了环形或星型的结构来减少网络的流量。在环形和星形拓扑中，在到达所有副本之前，写入可能需要经过几个节点。因此，节点需要转发它们从其他节点接收到的数据更改。为了防止无限复制循环，每个节点都被赋予唯一的标识符，并且在复制日志中，每个写入都用它经过的所有节点的标识符标记。当一个节点接收一个带有自己标识符的数据更改时，该数据更改将被忽略，因为节点知道它已经被处理了。
环形和星形结构存在的一个问题是，如果有一个节点失效，会中断其他节点之间的同步消息流，而因为它不允许消息沿着不同的路径传播，造成了单点故障。但是All pass的结构也会带来一些新的问题，由于网络拥塞的原因，各个节点的信息接收顺序不一致，如下图所示：
Client A将行插入到一个Leader 1的表，和Client B在Leader 3之中进行更新。而Leader 2收到了不同顺序的写操作：update操作出现在了insert操作之前。为了正确地排列这些事件，我们可以使用一种称为多版本向量控制（MVCC）的技术。 参加我的分布式系统系列文集里 并发控制 一章。
无主复制
多副本读写
No-Leader机制是怎么样消除Leader这个角色的存在的呢？答案也很简单：多副本读写。接下来我们来看一个栗子：
假设我们在数据系统之中采用了三副本的结构，如下图所示：User 1234 并行地将所有的副本发送给三个存储节点，并且两个节点可以接受副本的写入，但是其中一个节点不在线，所以副本写入失败。所以在三个副本中有两个副本确认写入成功了：在User 1234收到两个OK响应之后，User就认为写入操作是成功的，忽略了一个副本写入失败。（当然，不是简单的就不管这个写入失败了，后续会有修复机制来补齐这个副本的数据）
现在假设User 2345开始读取新写入的数据。由于一个节点写入失败了，所以User 234 可能会得到过期的值作为响应。为了解决这个问题，当User 从数据系统之中读取数据时，它不只是将请求发送到一个副本，而是将读取请求并行地发送到多个副本节点。User可以从不同节点获得不同的响应，即来自其他节点的最新值和另一个节点的过期值。这里通过了版本号用于确定哪个值是更新的值。
副本修复
No-Leader机制导致了数据系统之中可能存在大量过期的值，所以一个节点怎么来修复自身的副本来获取最新值的过程我们就称之为副本修复,No-Leader机制也是通过这样的方式来达到最终一致性的。通常会有这样几种方式：
读修复
当用户并行读取多个节点时，它可以获取到其他过期的值的响应。所以用户会发现其中有些节点拥有过期的值，这时用户可以主动将新值写入该节点。这种方法称之为读修复。
反熵过程（其实是一个物理学概念）
每个数据存储节点都会有一个后台进程，不断的比对自己的副本与其他节点副本的差异，发现自己拥有过期的值之后，会主动修复自己过期的副本。与基于写入顺序日志不同，这种反熵过程不以任何特定的顺序复制写操作，并且在复制数据之前可能会有显著的延迟。
Quorum机制
假设有n个副本，每次写操作必须由w个节点确认为成功，每个读操作读取r个节点。（在上文的例子中，n＝3，w＝2，r＝2）。只要w + r > n，如果读和写操作的总次数大于n，那么读和写操作必然至少有一个副本是相同的，也就是读操作必然可以读到最新写操作的数据。这被我们称之为：Quorum机制，每次读写都需要达到法定人数。
通常 n、w和r通常是可配置的，根据您的需要来修改这些数字。一个常见的选择是使n为奇数（通常为3或5），并设置w＝r＝（n + 1）/ 2 。如下图所示，如果w < n，如果有n - w个节点不可用，我们仍然可以处理写操作。同样的如果r＜n，如果有n - r个节点不可用，我们仍然可以处理读操作。而如果小于所需的w或r节点可用，则写或读操作就会返回错误。
n＝3，w＝2，r＝2，我们可以容忍一个不可用的节点。
n＝5，w＝3，r＝3，我们可以容忍两个不可用的节点。
写入冲突与Quorum机制
同样的Quorum机制的设计本身就可以允许并发读写操作，并容忍网络中断与高峰延迟。但是这也必然会带来一致性问题，我们来看下面这个例子：
如图所示，有两个Client A与B，同时写入关键字X在一个三副本的数据存储系统之中。Node 1接收来自A的写入，但由于网络中断而从未接收来自B的写入。Node 2首先接收来自A的写入，然后接收B写入。而Node 3则是首先接收来自B的写入，然后接收A的写入。Node 2认为X的最终值是B，而其他Node认为最终值是A.
Last Write Win
我们可以为每个写操作附加一个时间戳，选择最大的时间戳作为最新的值，并丢弃任何具有早期时间戳的写操作的值。这种冲突解决算法，称为Last Write Win。这种情况要求每个写操作具有幂等性，否则会出现写丢失的情况，如何能保证不出现依赖的写丢失呢？
合并“happens-before”关系
每当有两个操作A和B时，有三种可能：A发生在B之前，B发生在A之前，A或B是并发的。我们需要的是一个算法，告诉我们两个操作是否并发。如果一个操作在另一个操作之前发生，那么后面的操作应该覆盖前面的操作，但是如果操作是并行的，那么我们需要解决一个冲突。怎么样去捕获并合并“happen-before”的关系呢？可以在服务器节点维护一个版本号，每次写操作时递增版本号，并将新版本号存储在写入的值中。
客户端
当客户端读取一个键时，服务节点会返回所有未被覆盖的值，以及最新版本号。当客户端需要写一个键时，它必须包含从先前读取中的版本号，并且它必须合并它在前面读取中接收到的所有值。
服务器
当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或以下的所有值，因为它知道已经合并到新值，但必须保留所有值具有更高版本号。
版本向量
合并“happen-before"使用一个单一的版本号来捕捉操作之间的依赖关系，但这不足以解决当有多个副本并行写入的情况。相反，我们需要使用每个副本的版本号以及每个键。每个副本在处理写时递增自己的版本号，并跟踪从其他副本中看到的版本号。此信息指示要覆盖哪些值以及作为兄弟版本保存着哪些值。而所有副本的版本号的集合称为版本向量。版本向量从数据节点发送给客户端，所以版本向量让我们可以区分覆盖写与发并行写操作。
