前言
数据副本（Replication），指的是相同的数据在不同的机器上拷贝多份，原因有以下几点：
- 使数据在地理上离用户的距离更近，以降低延迟
- 允许在部分数据丢失时，系统仍然能够继续工作，提升可用性
- 通过对提供读请求的机器进行水平扩展，提高读请求的吞吐量
在本章的讨论中，我们假设每台机器有完整的数据拷贝，关于数据分区的话题会在下一章讨论。
数据的多副本拷贝，如果数据在写入后就不会改变，那只要将数据拷贝到其他机器，一次就完成了。但多副本的难点在于数据时刻在更新的，需要将数据实时更新到副本数据上。这里有三种主流的节点间关系的模型：single-leader，multi-leader，leaderless。
这三种模型都有各自的优点和缺点，前两节将主要介绍single-leader模型，最后会介绍multi-leader和leaderless。
Leaders和Followers
数据库中的每个数据副本为一个replica，如果保证所有replica的数据都是一致的？这就需要每次数据库的写入都作用到所有的replica上。最常见的解决方案就是leader-based模型，也称为active/passive或者master-slave，它的工作方式如下：
- 数据库的写入都发送到leader节点，leader将新数据写入到本地存储；
- leader将数据更新通过日志或者流的方式，发送给其他followers，followers根据接收到的信息，按相同的顺序执行写入操作。
- 客户端在读取数据时，可以读取leader或者任何一个follower。写请求只会发送给leader。
使用这种方式更新数据副本的系统包括有：
- 关系型数据库：PostgreSQL、MySQL、SQL Server等；
- 非关系型数据库：MongoDB、RethinkDB、Espresso等；
- 消息队列：Kafka、RabbitMQ。
同步复制和异步复制
关于数据复制的一个很重要的细节，就是复制的过程是同步还是异步的：
- 同步复制：leader等待所有follower都确认写入操作完成，才将更新后的数据返回到客户端。同步复制的好处是保证所有节点的数据都更新完成且是一致的，缺点是如果某follower节点由于节点崩溃、网络原因等没有返回确认到leader，会导致写请求无法处理，leader必须后续所有的写请求并等待。
- 异步复制：leader将写入操作发送给follower后，不等待follower确认完成，就将新数据返回到客户端。异步复制的好处是follower的故障不会阻塞leader处理后续的写请求，缺点是一旦leader出现故障，所有没有复制的消息将会丢失，也就是无法保证数据的可靠性。
以下两张图分别为Leader-based模型的示意图和时序图，在数据更新的过程中，客户端发起了一个查询请求：
此外还有一种称为半同步的复制策略，该策略中有一个follower是同步的，其他follower是异步的，因此可以保证至少有两个节点的写入操作执行完成，在一定程度上兼顾了同步复制和异步复制各自的优缺点。
添加新的Follower
这一小节讨论的是扩展性的问题。在需要增加replica的数量、或者替换故障节点时，需要在集群中添加新的follower。此时如何保证新的follower能够拥有leader数据的正确副本呢？考虑到数据库中的数据是不断更新的，只是简单的拷贝数据到新的follower是不行的，因为在拷贝的不同时刻数据的状态是不一致的，拷贝后的结果也将是错误的。
- 正确的数据拷贝流程如下：
- 在某个确定的时间点，建立leader数据的镜像，甚至可以在数据库不加锁的情况下完成，很多数据库都支持该功能；
- 将此镜像拷贝到新的follower节点；
- follower从leader中获取从镜像点到最新点的所有数据更新。这需要leader将此镜像点和数据更新日志的某点关联，在PostgreSQL中称为log sequence number，MySQL中称为binlog coordinates；
- 当follower处理完所有数据更新后，该follower追上了进度，可以处理leader后续的写请求了。
处理节点故障
这一小节讨论的是可用性的问题。如何在节点故障时，系统仍可以正常运行，我们看下leader-based模型下的follower和leader在故障时应该如何处理。
- Follower故障：Catch-up recovery
Follower故障的原因主要有：follower崩溃、重启，或者follower和leader的网络连接中断。由于在leader上记录了所有数据更新的日志，follower在连接到leader后，可以重新执行之前由于故障而未执行的数据更新，追赶到最新的进度并接收此后的所有数据更新。
- Leader故障：Failover，故障转移
当leader故障时，一个follower会被升级为新的leader，客户端将写请求发送到新的leader，新leader将数据更新发送给其他的follower，该过程称为failover。通常该过程的步骤如下：
- 发现节点故障：一般采用心跳机制，一个节点在规定时间内没有响应则认为出现了故障；
- 选择新的leader：由选举控制节点发起选举流程，通常是数据更新最快的节点当选为新的leader；
- 使用新的leader重新配合系统：客户端发送写请求到新的leader，如果旧的leader恢复，也需要承认新的leader节点。
这种failover的方式可能存在两个问题：
- 如果使用异步复制，新的leader可能未接收到旧的leader所有的写请求，那么当旧的leader恢复后，可能会出现写请求的冲突。最常用的解决方式是，旧的leader所有未被复制的写请求被丢弃，这可能会违反一些客户端的可用性要求。
- 当此数据库与其他数据库协同工作时，丢弃写请求可能会很危险。比如MySQL使用自增id作为每行的主键，当leader出现故障时，follower的进度比leader晚，会出现重复使用之前用过的主键；而如果主键作为Redis的key使用，可能会导致数据的错乱。
- 在某些出错情况下，系统可能出现脑裂，也即是有两个节点都认为自己是leader，它们同时接收客户端的请求，可能会导致数据丢失或出错。这时需要一个机制，当系统出现两个leader时，停止其中一个leader。
- 如何判断leader故障，需要设置一个合理的超时时间。如果时间太长的话，系统恢复的时间会很长，如果太短的话，可能导致很多不必要的failover。
复制日志记录的实现
- Statement-based replication
leader记录每个执行的写请求(statement)到日志中，然后将日志发送给follower。follower解析并执行这些SQL表达式，就像这些命令是从客户端接收到的一样。
这听起来是很合理的，但在实现中有以下可能存在的问题：
- 表达式中可能存在不确定的函数，比如NOW()或者RANDOM()，不同的副本产生不同的值；
- 表达式可能使用一些自增列，或者依赖数据库中的已有顺序，这样就要求每个副本必须以相同的顺序执行这些表达式；
- 表达式可能存在一些负效应，比如触发器、存储程序或者用户定义函数，导致在每个副本有不同的负效应。
即使可以有一些方案来解决以上的问题，比如将不确定的值变为确定的，但statement-based的方法仍然较少被使用。
- Write-ahead log（WAL）shipping
在第三章，我们讨论过SSTables、LSM-Trees和B-tree，这些方法同样可以用于数据库的数据复制。leader将所有数据块的字节变化写在日志中，并发送给follower。follower处理这些日志，从而构建和leader完全相同的数据。
该方法的主要缺点是，数据复制的过程和存储引擎相关联，如果更新一种存储引擎，leader和follower的数据将无法同步，这就导致数据库的版本不能不停机升级。
- Logical（基于行）log replication
Logical replication的目的是解决上面WAL中的复制日志和存储引擎耦合的问题。logical replication的名字就是为了和存储引擎的physical区分开的。
logical replication的实现方式是数据库记录表的行级写入记录：
- 行插入：日志中包含所有列的值；
- 行删除：采用主键标识被删的行，如果没有主键则使用所有列的值；
- 行更新：标识方式和行删除相同，同时包括更新行的所有列的值。
MySQL的binlog使用的就是这种方式。这种方式可以实现复制日志记录和存储引擎的解耦，从而可以实现数据库版本的不停机更新。
- Trigger-based replication
由用户自己实现的应用程序代码，当数据更新时，触发代码完成用户指定的复制操作。该方法的灵活性是最好的。
