分布式系统-数据复制

数据复制的困难之处在于处理复制数据的变更。几乎所有分布式数据库都使用这三种复制算法：单领导者（single leader），多领导者（multi leader）和无领导者（leaderless）。

领导者与追随者

存储数据库副本的节点称为副本。为了保证副本数据的一致性，最常见的方式是 基于领导者的复制（leader-based replication） （也称 主动/被动（active/passive） 或 主/从（master/slave） 复制）。原理如下：

副本之一被指定为 领导者（leader），也称为 主库（master|primary） 。当客户端要向数据库写入时，它必须将请求发送给领导者，领导者会将新数据写入其本地存储。
其他副本被称为追随者（followers），亦称为只读副本（read replicas），从库（slaves），备库（ sencondaries），热备（hot-standby）。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为复制日志（replication log）记录或变更流（change stream）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照领导者处理的相同顺序应用所有写入。
当客户想要从数据库中读取数据时，它可以向领导者或追随者查询。但只有领导者才能接受写操作（从客户端的角度来看从库都是只读的）。

同步复制和异步复制

下图展示了同步复制和异步复制的区别，follower1是同步复制，2是异步复制。

同步复制的优点是，从库保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上上找到。缺点是，如果同步从库没有响应，主库就无法处理写入操作。主库必须阻止所有写入，并等待同步副本再次可用。

将所有从库都设置为同步的是不切实际的：任何一个节点的中断都会导致整个系统停滞不前。所以，可以令一个跟随者同步，其他异步，当同步从库变慢或不可用，就换一个。这种配置有时也被称为 半同步（semi-synchronous）。

通常情况下，基于领导者的复制都配置为完全异步。这意味着即使已经向客户端确认成功，写入也不能保证 持久（Durable） 。然而，一个完全异步的配置也有优点：即使所有的从库都落后了，主库也可以继续处理写入。

设置新从库

如果要设置一个新的从库（比如增加副本数量等），可能要进行如下步骤：

在某个时刻获取主库的一致性快照（如果可能），而不必锁定整个数据库。
将快照复制到新的从库节点。
从库连接到主库，并拉取快照之后发生的所有数据变更。这要求快照与主库复制日志中的位置精确关联。这个位置在MySQL中称为 二进制日志坐标（binlog coordinates）。
当从库处理完快照之后积压的数据变更，我们说它 赶上（caught up） 了主库。

处理节点宕机

从库失效

从库可以从日志中知道，在发生故障之前处理的最后一个事务。因此，从库可以连接到主库，并请求在从库断开连接时发生的所有数据变更。

主库失效

其中一个从库需要被提升为新的主库，需要重新配置客户端，以将它们的写操作发送给新的主库，其他从库需要开始拉取来自新主库的数据变更。这个过程被称为故障切换（failover）。步骤如下：

确认主库失效。大多数系统只是简单使用 超时（Timeout） ：节点频繁地相互来回传递消息，并且如果一个节点在一段时间内（例如30秒）没有响应，就认为它挂了。
选择一个新的主库。这可以通过选举过程（主库由剩余副本以多数选举产生）来完成，或者可以由之前选定的控制器节点（controller node）来指定新的主库。
重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库。如果老领导回来，可能仍然认为自己是主库，没有意识到其他副本已经让它下台了。系统需要确保老领导认可新领导，成为一个从库。

故障切换出现的问题

如果使用异步复制，则新主库可能没有收到老主库宕机前最后的写入操作。在选出新主库后，如果老主库重新加入集群，新主库在此期间可能会收到冲突的写入，那这些写入该如何处理？最常见的解决方案是简单丢弃老主库未复制的写入，这很可能打破客户对于数据持久性的期望。
如果数据库需要和其他外部存储相协调，那么丢弃写入内容是极其危险的操作。例如在GitHub的一场事故中，一个过时的MySQL从库被提升为主库。数据库使用自增ID作为主键，因为新主库的计数器落后于老主库的计数器，所以新主库重新分配了一些已经被老主库分配掉的ID作为主键。这些主键也在Redis中使用，主键重用使得MySQL和Redis中数据产生不一致，最后导致一些私有数据泄漏到错误的用户手中。
发生某些故障时可能会出现两个节点都以为自己是主库的情况。这种情况称为 **脑裂(split brain)**，非常危险：如果两个主库都可以接受写操作，却没有冲突解决机制，那么数据就可能丢失或损坏。一些系统采取了安全防范措施：当检测到两个主库节点同时存在时会关闭其中一个节点，但设计粗糙的机制可能最后会导致两个节点都被关闭。
主库被宣告死亡之前的正确超时应该怎么配置？在主库失效的情况下，超时时间越长，意味着恢复时间也越长。但是如果超时设置太短，又可能会出现不必要的故障切换。例如，临时负载峰值可能导致节点的响应时间超时，或网络故障可能导致数据包延迟。如果系统已经处于高负载或网络问题的困扰之中，那么不必要的故障切换可能会让情况变得更糟糕。

复制日志的实现

基于语句的复制

就是将sql语句发送给从库，从库需要解析并执行语句，但会出很多问题：如果调用 非确定性函数（nondeterministic） 的语句，可能会在每个副本上生成不同的值，比如NOW()。如果使用了自增列，则必须在每个副本以完全相同的顺序执行他们。

基于语句的复制在5.1版本前的MySQL中使用。因为它相当紧凑，现在有时候也还在用。但现在在默认情况下，如果语句中存在任何不确定性，MySQL会切换到基于行的复制。

传输预写式日志（WAL）

通常都是将写操作追加到日志中：

对于日志结构存储引擎，日志是主要的存储位置。日志段在后台压缩，并进行垃圾回收。
对于覆写单个磁盘块的B树，每次修改都会先写入 预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态。

当从库应用这个日志时，它会建立和主库一模一样数据结构的副本。

逻辑日志复制（基于行）

逻辑日志，比如MySQL的binlog，这种关系数据库的逻辑日志通常是以行的粒度描述对数据库表的写入的记录序列：

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

修改多行的事务会生成多个这样的日志记录，后面跟着一条记录，指出事务已经提交。

由于逻辑日志与存储引擎内部分离，因此可以更容易地保持向后兼容，从而使领导者和跟随者能够运行不同版本的数据库软件甚至不同的存储引擎。对于外部应用程序来说，逻辑日志格式也更容易解析。

复制延迟问题

如果使用异步复制的话，应用程序难免会从从库读到过时的信息，这会导致数据库的不一致。

读己之写

读后一致性的实现方法：

读用户可能已经修改过的内容时，都从主库读；比如某些用户可以修改的信息，读的时候从主库读，但如何判断那些是用户可以修改的信息，是个问题。
跟踪上一次更新时间，比如上一次更新在一分钟内，从主库读，一分钟后读从库。
客户端可以记住最近一次写入的时间戳，系统需要确保从库为该用户提供任何查询时，该时间戳前的变更都已经传播到了本从库中。如果当前从库不够新，则可以从另一个从库读，或者等待从库追赶上来。
如果您的副本分布在多个数据中心，则会增加复杂性。任何需要由领导者提供服务的请求都必须路由到包含主库的数据中心。

单调读

如果用户多次查询的情况下，查的是进度不同的从库，可能出现第二次查询比第一次查询滞后的情况。如图：

单调读取仅意味着如果一个用户顺序地进行多次读取，如果先前读取到较新的数据，后续读取不会得到更旧的数据。

实现单调读取的一种方式是确保每个用户总是从同一个副本进行读取。例如，可以基于用户ID的散列来选择副本，而不是随机选择副本。但是，如果该副本失败，用户的查询将需要重新路由到另一个副本。

一致前缀读

如果数据进行分区存储的话，没个分区都有主从库，那么可能导致这种情况：

一致前缀读（consistent prefix reads）：如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。

一种解决方案是，确保任何因果相关的写入都写入相同的分区。对于某些无法高效完成这种操作的应用，还有一些显式跟踪因果依赖关系的算法。

多主复制

基于领导者的复制模型的自然延伸是允许多个节点接受写入。复制仍然以同样的方式发生：处理写入的每个节点都必须将该数据更改转发给所有其他节点。称之为多领导者配置（也称多主、多活复制）。在这种情况下，每个领导者同时扮演其他领导者的追随者。

多主复制的应用场景

运维多个数据中心

多领导者配置中可以在每个数据中心都有主库。在每个数据中心内使用常规的主从复制；在数据中心之间，每个数据中心的主库都会将其更改复制到其他数据中心的主库中。

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

性能

在单活配置中，每个写入都必须穿过互联网，这可能会增加写入时间，并可能违背了设置多个数据中心的初心。在多活配置中，每个写操作都可以在本地数据中心进行处理，并与其他数据中心异步复制。
容忍数据中心停机

在单主配置中，故障切换可以使另一个数据中心里的追随者成为领导者。在多活配置中，发生故障的数据中心归队时，复制会自动赶上。
容忍网络问题

单主配置对这数据中心间的连接问题非常敏感，因为通过这个连接进行的写操作是同步的。采用异步复制功能的多活配置通常能更好地承受网络问题：临时的网络中断并不会妨碍正在处理的写入。

尽管多主复制有这些优势，但也有一个很大的缺点：两个不同的数据中心可能会同时修改相同的数据，写冲突是必须解决的。

需要离线操作的客户端

多主复制的另一种适用场景是：应用程序在断网之后仍然需要继续工作。

在这种情况下，每个设备都有一个充当领导者的本地数据库，并且在所有设备上的日历副本之间同步时，存在异步的多主复制过程。复制延迟可能是几小时甚至几天，具体取决于何时可以访问互联网。

从架构的角度来看，这种设置实际上与数据中心之间的多领导者复制类似，每个设备都是一个“数据中心”，而它们之间的网络连接是极度不可靠的。实现起来很困难。

处理写入冲突

两个用户如果将各自的更改同步到各自的主库中，这时主库之间的同步就会有冲突。

同步和异步冲突检测

单主数据库中，第二个写入会被阻塞，等待第一个写入完成，或终止第二个写入，强制用户重试。多活配置中，两个写入都是成功的，并且在稍后的时间点仅仅异步地检测到冲突。那时要求用户解决冲突可能为时已晚。

如果使冲突检测同步，即等待写入被复制到所有副本，然后告诉用户写入成功，但这样会丢弃多主复制的主要优点：允许每个副本独立接受写入。

避免冲突

如果应用程序可以确保特定记录的所有写入都通过同一个领导者，那么冲突就不会发生。

但有时需要更改指定的主库，比如数据中心出现故障，需要将流量路由到其他数据中心，冲突避免会中断。

收敛至一致的状态

数据库必须以一种 收敛（convergent） 的方式解决冲突，这意味着所有副本必须在所有变更复制完成时收敛至一个相同的最终值。

实现冲突合并解决有多种途径：

给每个写入一个唯一的ID，挑选最高ID的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为最后写入胜利（LWW, last write wins）。虽然这种方法很流行，但是很容易造成数据丢失。
为每个副本分配一个唯一的ID，ID编号更高的写入具有更高的优先级。这种方法也意味着数据丢失。
以某种方式将这些值合并在一起 - 例如，按字母顺序排序，然后连接它们。
用一种可保留所有信息的显式数据结构来记录冲突，并编写解决冲突的应用程序代码。

自定义冲突解决逻辑

作为解决冲突最合适的方法可能取决于应用程序，大多数多主复制工具允许使用应用程序代码编写冲突解决逻辑。该代码可以在写入或读取时执行：

写时执行

只要数据库系统检测到复制更改日志中存在冲突，就会调用冲突处理程序。

读时执行

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

多主复制拓扑

如果领导者在两个以上，哪如何定义他们的拓扑结构呢？

a和b这两种拓扑的问题是，只要一个节点故障，就可能会中断其他节点之间的复制消息流，导致它们无法通信，直到节点修复。

c这种拓扑的问题是，一些网络链接比其他网络链接更快的情况下，一些复制消息可能“超过”其他复制消息：

无主复制

在一些无领导者的实现中，客户端直接将写入发送到到几个副本中，而另一些情况下，一个 协调者（coordinator） 节点代表客户端进行写入。但与主库数据库不同，协调者不执行特定的写入顺序。我们将会看到，这种设计上的差异对数据库的使用方式有着深远的影响。

当节点故障时写入数据库

无主复制情况下，故障切换是不存在的。比如有三个副本，客户端收到两个副本的确认信息后，认为写入成功，忽略了第三个副本错过写入的事实：

为了解决这个问题，当一个客户端从数据库中读取数据时，它不仅仅发送它的请求到一个副本：读请求也被并行地发送到多个节点。客户可能会从不同的节点获得不同的响应。即来自一个节点的最新值和来自另一个节点的陈旧值。版本号用于确定哪个值更新。

读修复和周期性静默修复

读修复：当发现某个副本有陈旧值，则将新值写回该副本。

周期性静默修复：一些数据存储具有后台进程，该进程不断查找副本之间的数据差异，并将任何缺少的数据从一个副本复制到另一个副本。这个过程不会以特定的顺序复制写入。

读写的法定人数

如果有n个副本，每个写入必须由w节点确认才能被认为是成功的，并且我们必须至少为每个读取查询r个节点。只要$w + r> n$，我们期望在读取时获得最新的值，因为r个读取中至少有一个节点是最新的。遵循这些r值，w值的读写称为法定人数（quorum）的读和写。

法定人数条件$w + r> n$允许系统容忍不可用的节点。如果少于所需的w或r节点可用，则写入或读取将返回错误。

仲裁一致性的局限性

通常，r和w被选为多数（超过 $n/2$ ）节点，因为这确保了$w + r> n$，同时容忍多达$n/2$个节点故障。

较小的w和r虽然更有可能会读取过时的数据，但是这种配置允许更低的延迟和更高的可用性：如果存在网络中断，并且许多副本变得无法访问，则可以继续处理读取和写入的机会更大。只有当可达副本的数量低于w或r时，数据库才分别变得不可用于写入或读取。

即使在$w + r> n$的情况下，也可能存在返回陈旧值的边缘情况。这取决于实现，但可能的情况包括：

如果使用松散的法定人数，w个写入和r个读取落在完全不同的节点上，因此r节点和w之间不再保证有重叠节点。
如果写操作与读操作同时发生，写操作可能仅反映在某些副本上。在这种情况下，不确定读取是返回旧值还是新值。
如果写操作在某些副本上成功，而在其他节点上失败，在小于w个副本上写入成功。所以整体判定写入失败，但整体写入失败并没有在写入成功的副本上回滚。这意味着如果一个写入虽然报告失败，后续的读取仍然可能会读取这次失败写入的值。
如果携带新值的节点失败，需要读取其他带有旧值的副本。并且其数据从带有旧值的副本中恢复，则存储新值的副本数可能会低于w，从而打破法定人数条件。

监控陈旧度

从运维的角度来看，监视你的数据库是否返回最新的结果是很重要的。即使应用可以容忍陈旧的读取，您也需要了解复制的健康状况。如果显著落后，应该提醒您，以便您可以调查原因。

在无领导者复制的系统中，没有固定的写入顺序，这使得监控变得更加困难。

松散法定人数与带提示的接力

一般大型的集群（节点数大于n个），客户端可能连接集群中部分数据库，当网络中断或数据库出问题时，可能客户端连接就小于n了，那么如果将客户端的写入写入到一些别的可达节点，不在客户端本来连接的n个节点间时，写和读仍有成功响应，这就叫松散的法定人数，一旦网络中断解决，代表节点临时接受的节点的任何写入，都发送到适当的“本地”节点，这就是所谓的带提示的接力（hinted handoff）。

松散法定人数对写入可用性的提高特别有用：只要有任何w节点可用，数据库就可以接受写入。然而，这意味着即使当$w + r> n$时，也不能确定读取某个键的最新值，因为最新的值可能已经临时写入了n之外的某些节点。

运维多个数据中心

Cassandra和Voldemort在正常的无主模型中实现了他们的多数据中心支持：副本的数量n包括所有数据中心的节点，在配置中，您可以指定每个数据中心中您想拥有的副本的数量。无论数据中心如何，每个来自客户端的写入都会发送到所有副本，但客户端通常只等待来自其本地数据中心内的法定节点的确认，从而不会受到跨数据中心链路延迟和中断的影响。对其他数据中心的高延迟写入通常被配置为异步发生，尽管配置有一定的灵活性。

检测并发写入

由于可变的网络延迟和部分故障，事件可能在不同的节点以不同的顺序到达：

如果每个节点只要接收到来自客户端的写入请求就简单地覆盖了某个键的值，那么节点就会永久地不一致，如图中的最终获取请求所示：节点2认为 X 的最终值是 B，而其他节点认为值是 A 。

最后写入胜利

即使写入没有自然的排序，我们也可以强制任意排序。例如，可以为每个写入附加一个时间戳，挑选最 “最近” 的最大时间戳，并丢弃具有较早时间戳的任何写入。这种冲突解决算法被称为 最后写入胜利（LWW, last write wins）。

LWW实现了最终收敛的目标，但以持久性为代价：如果同一个Key有多个并发写入，即使它们都被报告为客户端成功（因为它们被写入 w 个副本），但只有一个写入将存活，而其他写入将被静默丢弃。如果丢失数据不可接受，LWW是解决冲突的一个很烂的选择。

如何判断两个操作是否并发

为了简单起见，我们从一个只有一个副本的数据库开始。一旦我们已经制定了如何在单个副本上完成这项工作，我们可以将该方法概括为具有多个副本的无领导者数据库。

两个客户端同时向同一购物车添加项目：

因果依赖关系图：

服务器可以通过查看版本号来确定两个操作是否是并发的——它不需要解释该值本身（因此该值可以是任何数据结构）。该算法的工作原理如下：

服务器为每个主键保留一个版本号，每次写入主键时都增加版本号，并将新版本号与写入的值一起存储。
当客户端读取键时，服务器将返回所有未覆盖的当前值以及最新的版本号。客户端在写入前必须读取。
客户端写入主键时，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在一起。（来自写入请求的响应可以像读取一样，返回所有当前值，这使得我们可以像购物车示例那样连接多个写入。）
当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或更低版本的所有值（因为它知道它们已经被合并到新的值中），但是它必须保持所有值更高版本号（因为这些值与传入的写入同时发生）。

当一个写入包含前一次读取的版本号时，它会告诉我们写入的是哪一种状态。如果在不包含版本号的情况下进行写操作，则与所有其他写操作并发，因此它不会覆盖任何内容 —— 只会在随后的读取中作为其中一个值返回。

合并同时写入的值

上述算法可以保证不会数据丢弃，但客户端必须通过合并并发写入的值来继承旧值。riak称这些并发值是兄弟关系。

上述例子中，最后购物车是将并发值合并和去重来展示的，但如果某个客户端删去了商品，另一个没删去，删去的商品就会出现在最后的合并值中。

为了防止该问题，删除时系统要保留一个对应的版本号来标记这个商品需要在合并时去除。

这个实现挺复杂的，需要设计一个专门的数据结构来自动合并。比如riak支持CRDT的数据结构来高效的自动合并和删除标记。

版本矢量

多个副本同时接受并发希写入时，需要为每个副本和主键定义一个版本号。每个副本处理写入时增加版本号，并跟踪其他副本看到的版本号。所有版本号的集合称为版本矢量。

当读取数据时，数据库副本会返回版本矢量给客户端，在随后写入时需要将版本信息包含在请求发送到数据库。

和单副本例子一样，程序要执行合并操作。版本矢量可以保证从某个副本读取值写入另一个副本，虽然会衍生新的兄弟值，但不会发生数据丢失并可以正确合并所有并发值。