分布式数据复制

一、The Basic

1.1 Replication Methods

1.1.1 同步复制

写操作复制到从库之后才返回。

这里隐藏着一个一致性问题：数据变更需要在多个节点上同时对外可见。

但是在现实中：

1. 写操作在各个节点上，谁先生效呢？或者，如何避免脏读？（Kafka 使用 HW 水位值来避免脏读，Kafka 副本备份机制）
2. 写操作不一定都能成功执行，例如硬盘空间不足导致执行失败。是不是要有分布式事务来保证？

因此同步复制在实现的过程中有时需要借鉴一些事务的原理或者借助某种一致性（consensus）算法来保证一致性（consistency）。

下面我们来看一个比较特殊的同步复制实现。

1.1.2 链式复制（Chain Replication）

ChainReplication（Object Storage on CRAQ: High-throughput chain replication for read-mostly workloads）是同步复制的一种。

一个集群中有多条链，一条链由多个节点组成。一个链式结构如下图：

写操作只能在头结点进行，并且按链复制到尾结点。只有尾结点写成功了，头结点的写请求才返回（Committed）。读操作可以在任意结点进行，因此为了达到一致性，CR 在使用 MVCC（Multi-Version Concurrent Control）的同时，还有其独特的方法：

初始所有的节点都保存数据 V1。对于新的写操作 V2，节点并不直接用 V2 覆盖 V1，而是将 V1 和 V2 并存。如果节点的读操作发现有多个版本的数据，先去尾节点询问它所保存的数据的最新版本。如果 V2 的变化已经复制到尾结点了，说明写操作 V2 已经 Commit，这时就可以将 V2 返回给客户端。否则的话还是返回旧版本的数据 V1。

那么什么时候才能删除旧版本 V1 呢？注意到写操作是从头结点链式复制到尾结点，那么写操作的结果（ACK）就是从尾结点链式传递到头结点。每个结点收到下一个结点的 ACK 时，就可以删除旧版本的数据了。

链式复制和主从复制很像，例如写操作都是单向的复制（Paxos 和 Viewstamped Replication 都有可能产生双向复制）以及没有用到任何分布式一致性协议等。当一条链只有 2 个节点时（HEAD 和 TAIL），链式复制看起来和主从复制没有什么不同。然而如果有多于 2 个节点时，链式复制和主从复制就有很大区别了：

1. 链式复制的每个节点（除了尾结点）都会产生写复制操作，而主从复制的写复制操作集中在主节点，这样就增加了主节点的负担；
2. 主从复制要想提供强一致性（consistency），一般都会用上分布式一致性（consensus）算法；而链式复制由于写复制的顺序性，更容易实现强一致性。

当然链式复制也有缺点，就是写操作相比主从复制要慢。链式复制的写复制不能并行，只能沿着链传递。实现上可以有一些优化，例如利用 Multicast 来节省写复制和 ACK 的时间；或者是将写复制 batch（pipeline）化。但是两者本质上还是 Serial VS Parallel。

1.1.3 异步复制

写操作在主库成功后直接返回。大部分的数据库都支持这种模式。

1.1.4 半同步复制

一部分从库与主库保持同步复制，另一部分从库与主库使用异步复制。

MySQL 支持半同步复制。在 5.7 版本中，新增了一个真正的不丢数据的半同步复制方法，Loss-Less Semisync。

写操作首先在主库上做好准备，而后直到确认相应的 binlog 复制到从库之后，才在主库上生效（对客户端可见）。

1.2 Replication In Practice: The Log

实现主从复制的通常方法是日志（Replication Log）。常见有以下4种：

1.2.1 Statement-based Replication

这是最简单的复制方法。Leader 把每个写请求记录到日志中，复制到 Replica；Replica 直接重新执行这些写请求。这种复制方法有以下几个缺点：

1. 如果写请求调用了非确定性的函数，例如 MySQL 的获取时间函数 NOW() 或者产生随机数函数 RAND()，那么这些函数返回的结果就有可能不同。从而造成了 Leader 和 Replica 之间的数据不一致；
2. 写请求在 Replica 的“重放”必须与 Leade r完全一致，否则就可能产生不一致的结果。例如，MySQL 中两条写操作同时依赖自增 ID，那么这两条写操作在从库的执行顺序必须与主库相同。这种顺序性的要求就限制了复制过程的吞吐量和速度。
3. 如果写操作有side-effect，那么还是有可能造成不一致（除非side-effect是确定性的）。例如 Redis 在 2.8 版本对expire命令的复制，就有可能造成 key 在主从库之间的过期时间不同。

这种复制方法也有优点，就是 Replication Log 可以非常小，方便传输。例如，执行一条影响 100 行的update语句，如果使用 Statement-based Replication，那么体现在 Replication Log 中可能就是一行；而如果使用 Row-based Replication，那么 Replication Log 可能会有 100 行。

MySQL 在 5.1 版本之前使用这种复制模式。现在，MySQL 默认使用的复制模式是 Row-based Replication。

1.2.2 Write-ahead log (WAL) shipping

某些数据库在 apply 变更之前，先把变更写入一个日志，这个日志就是 Write-ahead log（WAL）。WAL shipping 就是把 Leader 的 WAL 直接发送给 Replica，从而 Replica 可以构建出与 Leader 一模一样的数据集。注意这种方式和 Statement-based Replication 有一个根本的不同之处，在于 WAL 并不是写请求（Statement），而是相对底层的，数据库内部的变更。所以上文讨论的 Statement-based Replication 的缺点不适用于 WAL shipping。

WAL shipping 有自己的缺点，就是日志格式和数据库底层存储引擎密切相关。一旦数据库所使用的存储引擎发生了变化，例如从 B-Tree 变更为 LSM-Tree，WAL 通常不可能适应（PS：Statement-based Replication 就没有这个问题）。

PostgreSQL使用这种复制方式。

1.2.3 Logical (row-based) log replication

如果把上文提及的 WAL 抽象一下，制定一个与底层存储引擎无关的数据变更日志格式，再复制这个日志，不就可以避免 WAL shipping 的缺点了吗？Logical log replication 正是基于这种想法。例如 MySQL 就在行（row）层面上的做了抽象：

1. 对于一条新插入的行，Logical Log 包含了所有列（column）的数据；
2. 对于被删除的一行，Logical Log含有足够的信息来唯一定位这一行；
3. 对于被更新的一行，Logical Log 除了含有足够的信息来唯一定位这一行以外，还包含了更新的数据。

这种复制方式还带来了其他好处，就是我们可以独立解析 Logical Log，“伪装”成一个 Replica，将数据另做它用。例如阿里巴巴的 MySQL 异步复制工具 Canal，或者 Facebook 的 Wormhole。

1.2.4 Trigger-based Replication

这种复制方式其实可以认为是独立于数据库之外的一种方式。这种方式允许业务代码来决定具体的复制逻辑。例如 MySQL 的 Trigger，我们可以在触发时自己将数据写到其他地方。

二、The Dynamo-style

我们讨论的复制方式都是基于一个“主从复制”的概念，即数据库的不同节点各有角色（主或从），数据变更的复制操作由主节点或从节点发起，最终达到主从之间的数据一致。

2007年，亚马逊发布了著名的 Dynamo 论文Dynamo: Amazon's Highly Available Key-value Store，使一种特殊的“复制”方式引起了广泛关注：Leaderless Replication。使用 Leaderless Replication 的数据库集群中，各节点没有主从之分，都是独立的。在这种数据库中，数据一致性并不是最重要的，最重要的是集群的可用性。（相当于在 CP 和 AP 中选择了 AP。）

Riak，Cassandra 和 Voldemort 是3个受 Dynamo 启发的，使用了 Leaderless Replication 的开源数据库，所以这一类数据库也被称为Dynamo-style数据库。

2.1 quorum-write and quorum-read

在 Leaderless 的数据库集群中，客户端把读写请求直接（或通过一个 coordinator proxy 间接）发往多个节点，通过合并多个节点的执行结果来判断此次请求成功与否。于是我们有了第一个问题：如何判断读写请求是否成功？

在一个有 n 个节点的数据库集群中，我们把读写请求同时发往所有节点。我们定义“w”为写操作成功的节点数，“r”为读操作成功的节点数；只要 w + r > n，我们就能确定集群中至少有1个节点是在读操作时返回了最新数据的，因为读操作的节点集合和写操作的节点集合必然有交集：

我们称满足在至少 w 个节点执行成功的写操作为“quorum-write”，在至少 r 个节点执行成功的读操作为“quorum-read”。只要客户端（或 coordinator proxy）发现此次操作是quorum-write 或 quorum-read，那么它就可以判断此次操作成功了。

注意：quorum 不等于 majority（n / 2 + 1），只要满足读操作成功集合和写操作成功集合有交集即可。通常选取 quorum = majority，是因为这样选择在满足 w + r > n 时，还可以容忍至多 n / 2 个节点失败。在上图的例子中，n = 5，w = r = 3，但是我们可以使 w = r = 2，同时加上条件“读或写必须在节点3上执行成功”。这样也可以形成 quorum-write 和 quorum-read。

在 dynamo-style 的数据库中，w 和 r 一般是可以调整的。例如在读多写少的场景中，我们可以设置 w = n，r = 1。这样做使得读操作在实现时可以随机选择任意一个节点，保证了读操作的快速；缺点也是很显然的：写操作必须在所有节点上生效，因此任何一个节点不可用都会造成写操作失败（quorum-write 失败）。

2.2 read-repair and anti-entropy

在 quorum-write 中，w可以小于 n。这就意味着某些节点的数据并不一定是最新的，例如当一个节点刚刚从不可用中恢复时。为了保证数据的一致性，dynamo-style 的数据库一般有两种方法：

2.2.1 read-repair

当客户端在 quorum-read 中读取到了旧的数据时，它可以把更新的数据写回包含旧数据的节点中。如下图：

user2345 的读操作返回后，发现 Replica3 返回了旧的数据（version = 6）。于是 user2345 随后向 Replica3 发起一次写请求，把新数据（version = 7）写入。

2.2.2 anti-entropy

这种方式是指数据库集群中另有一个独立进程，不断地比较各节点中数据的一致性并修复。

read-repair 适用于读操作比较频繁的数据。如果读操作不频繁，含有旧数据的节点就迟迟无法更新；这个时候我们就需要 anti-entropy，使得读操作即使不发生，我们也能保障数据的一致。所以这两种方式通常需要结合起来进行。

2.3 strict-quorum and sloppy-quorum

我们提到的以 quorum-read 和 quorum-write 来判断读写是否成功的方式，通常被称为“strict-quorum”。在 Leaderless 数据库集群中，可用性通常是最优先的目标；而 strict-quorum 有时并不能达到最高的可用性。例如在发生了网络分区的情况下，某些客户端只能连通一部分（不包含 w 或 r 的）数据库节点，从而无法形成 quorum-read 或 quorum-write，造成读或写失败。

在实际的数据库集群中，数据通常是分片（sharding）存储的。因此上面提到的 n 并不一定是集群中的总节点数。例如一个集群有5个节点 ABCDE，用户1的数据按分片规则保存在节点 ABC 上，那么 n = 3，w 和 r 在 ABC 3个节点中选出。

结合数据分片存储的特性，为了提高可用性，我们可以使用“sloppy-quorum”：w 和 r 可以在 n 个节点之外选取。换言之，在一个总节点数为 m（大于 n）的集群中，w 和 r 可以在 m 中任意选取，而不必只能限制在 n 个节点之内。使用上文的例子，m = 5，n = 3，w = r = 2，当节点 B 或 C 不可用时，用户1的数据可以写到 D 或 E，从而保证了可用性。

但是当 B 或 C 恢复后，quorum 只能在 ABC 当中选取，写到 DE 的数据岂不是相当于丢失了吗？为了解决这个问题，我们有“hinted-handoff”：用户1的数据在写入节点 D 或 E 时，会额外加上一些信息指明这些数据是本应该被写入 B 或 C 的；当 BC 恢复时，DE 会把用户1的数据写回 BC。

sloppy-quorum 加上 hinted-handoff，最大程度地保障了数据库的可用性，但是也进一步增大了数据不一致的可能性。而这种选择也正是适合 dynamo-style 数据库的特性：choose "AP" over "CP"。

三、The Lag Problem

异步复制作为一种最常见的复制方式，我们有必要知道异步复制所引起的一些数据一致性方面的问题。异步复制是写操作在主库上生效后，立刻返回给客户端；相应的数据变更随后异步复制到从库。因此这里有一个主从库之间数据不一致的时间窗口，或者说Replication Lag。如果客户端没有意识到这个 Replication Lag 的存在，并加以防范的话，很容易引发各种问题。

下面我们讨论3种因为 Replication Lag 的存在导致数据不一致，可能产生的问题和解决方法。

3.1 read-your-writes

read-your-writes consistency 是单用户的写操作的结果需要立刻对其后续的读操作可见。注意这里重点是读取自己所做的变更，其他用户所做的变更不需要立即可见。

如图，用户在主库插入一条记录。在这条记录还没复制到从库之前，就向从库发起了读请求；读请求返回空。这在用户看来，就是他刚刚插入的记录丢失了。

解决方法可以是在用户向主库的写操作完成之后，一段时间（大于主从同步延迟）内，所有依赖该写操作的读操作都请求主库。

3.2 monotonic-reads

monotonic-reads（单调读）consistency 是指用户不会读取到“回退（backwards in time）”的数据。

例如上图，用户 B 在从库1上已经读取到了用户 A 插入的动态，接着又重新发起一次相同的请求；新的请求在从库2上被执行，而从库2此时还没有复制到用户A插入的动态，因此从库2给用户B返回空。这在用户 B 看来，就是读的数据丢失或者回退了。

要获得单调读的一致性，可以将用户的 session 和读取的从库做一个绑定。例如用户 A 只读从库1，用户 B 只读从库2，从而避免从库之间数据不一致带来的非单调读。

我们在使用多个从库时，要特别小心保证单调读一致性。

3.3 consistent prefix reads

这种不一致常见于数据被分片了的数据库中。每个数据分片有独立的主从，独立的 Replication Lag；因此，当多个有先后顺序（或因果关系）的写操作分散到不同的分片中时，读操作（或观察者）可能读取（观察）到不同顺序的数据变更，从而违背了写操作的先后顺序（因果关系）。

如上图，用户A顺序插入两条动态，写到两个分片当中；用户 B 监听（subscribe）A 的动态变更。由于两个分片的主从复制延迟时间不同，B 有可能看到 A 的错误顺序的动态。

consistent prefix 意味着读操作观察到之前的（“prefix”）数据变更顺序必须和写操作顺序是一致的（“consistent”）。因此我们可以把需要顺序生效或者有因果关系的写操作都放在同一个数据分片中，从而提供 consistent prefix read。

参考链接

• Distributing Data: Replication(1) -- The Basic
• Distributing Data: Replication(2) -- The Dynamo-style
• Distributing Data: Replication(3) -- The Lag Problem
• 分布式系统下如何进行数据复制？(上)
• 分布式系统下如何进行数据复制？(下)