关于源码分析:TiKV-源码解析系列文章二十一Region-Merge-源码解析

Region Merge 是 Range 相邻的两个的 Region 合并的过程，咱们把一个 Region 称为 Source Region，另一个称为 Target Region，在 Merge 过程完结后，Target Region 治理的 Range 会扩充到 Source Region 的局部，Source Region 则被删除。

在上一篇 Region Split 源码解析 的结尾，咱们提到了与其绝对的 Region Merge 的复杂性。

因为两个 Region 属于不同的 Raft group，与 Region Split，Raft Snapshot 的相互作用，再加上网络隔离带来的影响，无疑有更大的复杂度。

本文接下来将会解开 Region Merge 的神秘面纱。

Merge 的设计需要

咱们心愿 Merge 的设计可能满足以下几个需要：

1. 不依附 PD 在 Merge 期间不发动其余的调度满足正确性
2. 不会因为网络隔离或者宕机引发正确性问题
3. 只有参加 Merge 的 TiKV 中 Majority 存活且能相互通信，Merge 能够持续或者回滚，不会被阻塞住（跟 Raft 保障可用性的要求统一）
4. 不对 Split/Conf Change 加额定条件限度（出于性能思考）
5. 尽量减少搬迁数据的开销
6. 尽量减少 Merge 期间服务不可用的工夫

接下来咱们来看一下 TiKV 的 Merge 是怎么一一满足这些需要的。

Merge 的触发

与 Split 和 Conf Change 相似，PD 负责发起者。然而与 Split 不同的是，Merge 的触发齐全是由 PD 判断的：

1. 如果 Region 的大小大于 max-merge-region-size（默认 20MB）或者 key 数量大于 max-merge-region-keys（默认 200000）不会触发 Merge。
2. 对于新 Split 的 Region 在一段时间内 split-merge-interval（默认 1h）不会触发 Merge。
3. 确保 Source Region 与 Target Region 的所有 Peer 都存在，该信息是通过 Region Leader 上报 PD 取得。
4. 还有一些其余的触发条件，这些属于外部机制，超出了本文的范畴。

PD 在决定某个 Source Region 须要 Merge 到相邻的 Target Region 之后，之后会通过 Conf Change 把它们的 Peer 对齐到雷同的 TiKV 上，再给该 Region 发送申请触发 Merge。

Merge 的流程

PD 发送给 Source Region Leader 的申请中会带上 Target Region 的 Region 信息。该 Leader 收到申请后，会 Propose 一条 PrepareMerge，在真正 Propose 之前，须要查看如下几项是否满足：

1. 本地的 Target Region 的 Epoch 跟 Region 信息中的统一（Epoch 的含意可参考 Region Split 源码解析），如果统一，查看是否是范畴相邻 Region，是否所有对应 Peer 都在雷同的 Store 上，代码见 PeerFsmDelegate check_merge_proposal。
2. 所有 Follower 落后的日志数目小于 merge-max-log-gap（默认 10）

   a. 前面步骤中有补日志的操作，须要管制落后日志的数量。

3. 从所有 Follower 上最小的 commit index 对应的日志到以后最初一条日志之间没有如下的 cmd（Leader 会保护所有 Follower 已知的 commit index）

   a. CompactLog，为了保障前面取日志的时候，日志还存在。

   b. Split/Merge/Conf Change，为了缩小网络隔离时候的简单状况，在后文解说网络隔离的时候会具体阐明。

2，3 代码见 Peer pre_propose_prepare_merge。

如果以上几项均满足，该 PrepareMerge 能够真正被 Propose 了，反之则会疏忽该申请。

message PrepareMergeRequest {
    uint64 min_index = 1;
    metapb.Region target = 2;
}

其中 min_index 代表的是所有 Follower 中最小的 match index，target 存的是 PD 发送过去的 Target Region 信息。

在 PrepareMerge 被 Propose 之后，之后的 Proposal 在 Apply 的时候会因为 Epoch 被跳过，也就是说，这个时候 Source Region 不能服务读写申请了。

接下来看 PrepareMerge 被 Commit 后 Apply 的代码 ApplyDelegate exec_prepare_merge：

• 批改 RegionLocalState 中 PeerState 为 Merging。
• 批改 RegionLocalState 中 MergeState，存入 min_index，target，commit 信息，其中 commit 为 PrepareMerge 对应的 index。

enum PeerState {
    Normal = 0;
    Applying = 1;
    Tombstone = 2;
    Merging = 3;
}
message MergeState {
    uint64 min_index = 1;
    metapb.Region target = 2;
    uint64 commit = 3;
}
message RegionLocalState {
    PeerState state = 1;
    metapb.Region region = 2;
    MergeState merge_state = 3;
}

随后每一个 Source Peer 都会定时触发 merge tick，代码见 PeerFsmDelegate on_check_merge:

1. 比拟本地 Target Peer 与 MergeState 中的 target 的 Epoch

   a. 若本地没有 Target Peer 或者前者大，这里存在两种可能性

   • PD 在期间对 Target Region 发动了调度申请（Split，Merge，Conf Change）。
   • Merge 胜利了，然而本地的 Target Peer 在某些状况下不须要本地的 Source Peer 去 Apply CommitMerge。比方 Target Region 在 Merge 之后又进行了 Split，而本地的 Target Peer 又通过 Snapshot 复原（与 Source Peer 的 Range 没有重叠），这种状况下 Source Peer 与 Target Peer 就会同时存在，又比方本地的 Target Peer 在随后通过 Conf Change 被移除了，然而因为被隔离了，被移除的时候没有 Apply 完所有日志（也就没有 Apply CommitMerge）。

   为了辨别这两种状况，这里应用了一个奇妙的解法：如果有 Quorum 的 Source Peer 都发现了本地没有 Target Peer 或者 Epoch 更大，然而本人还依然存在，则阐明肯定是状况 1 了（反之则持续期待），此时必须得 Rollback，代码见 PeerFsmDelegate on_check_merge。Rollback 的过程比较简单，只需 Propose 一条 RollbackMerge，期待 Apply 之后，Source Region 即可从新复原服务。

   b. 若前者小，阐明本地还未追上，持续期待。

   c. 若相等则下一步。

2. 给本地的 Target Peer Propose 一条 CommitMerge。

   message CommitMergeRequest {
       metapb.Region source = 1;
       uint64 commit = 2;
       repeated eraftpb.Entry entries = 3;
   }

   其中 source 是 Source Region 的信息，commit 是 MergeState 中的 commit，entries 是 index 从 MergeState 中的 min_index + 1 到 commit 的 Raft Log。

小伙伴们必定会好奇为什么 CommitMerge 不只发给 Target Region 的 Leader？这其实是为了简化实现，因为定时给本地的发就不须要思考 Target Region 的 Leader 是否切换了以及网络是否隔离的问题了。

• 非 Leader 的 Peer 收到后会静默抛弃，而 Leader 这里不必放心屡次 Propose 的问题，Apply CommitMerge 会让 Epoch 中的 version 减少，所以在之后带有雷同 Epoch 的 Proposal 都会被跳过。

接下来 Merge 的重心就转移到 Target Region 上了。

咱们来看 Target Region Apply CommitMerge 的中央，代码见 ApplyDelegate exec_commit_merge：

1. 因为 Source Region 的日志可能不够，为了让数据统一，咱们先发送 CommitMerge 中的 entries 给 Source Region，期待它把日志补全并且全副 Apply 完

   • 因为牵扯到并发逻辑解决，具体流程较简单，感兴趣的小伙伴可参见 exec_commit_merge 的函数正文自行浏览源码。
2. 批改 Source Region 的 Peer 状态为 Tombstone。
3. 扩充 Target Region 的 Range 范畴，批改 Epoch 的 version 为 max(source_version, target_version) + 1。

至此，Merge 的过程曾经实现了，原 Source Region 范畴内的数据当初由 Target Region 提供读写服务。

Merge/Split 对 Raft 算法的影响

家喻户晓，依据 Raft 算法自身依赖的复制状态机实践，Apply 日志是不能存在条件的，换句话说，对于任何参与者来说，只有领有雷同的日志，Apply 完之后就应该达成统一的状态。

然而咱们回顾上文的 Merge 流程，认真的小伙伴们会发现一个 Merge 胜利的重要性质：

性质 1：Target Peer 在 Apply CommitMerge 的时候，本地肯定存在对应的 Source Peer。

这是因为 Merge 的流程设计上想尽量减少开销，在 CommitMerge 中只存有很少一部分的日志，而绝大多数的数据只能依附本地的 Source Peer。

• 试想如果咱们让 CommitMerge 中带上 Source Region 的所有数据，这个问题就不复存在了

满足性质 1 也就意味着只有参加 Merge 过程的 Target Peer 能力 Apply CommitMerge，所以这里对 Raft 算法的影响点就集中在了 Conf Change 上。

raft-rs 中的 Configuration Change (简称 Conf Change) 算法移植自 etcd/raft。该算法有两种模式，single membership change 和 joint consensus，在 Raft 论文中均有形容，然而对于 Configuration 何时失效，etcd/raft 的实现的与 Raft 论文中形容的有很大的不同。Raft 论文中形容的是在收到后就失效，而 etcd/raft 则是在 Apply 之后才失效。探讨两种形式的优缺点超出了本文的范畴，不过对于 TiKV 的 Split/Merge 的实现来说，etcd/raft 的形式升高了实现的复杂度。

假如 CommitMerge 能胜利 Apply，即不会被 Epoch 的查看所跳过，那么阐明在它 Propose 的时候，那些在它之前还未 Apply 的 Proposal 里均不存在批改 Epoch 的操作，也不会有 Conf Change 的操作，所以这个时候只有在 Propose 的时候冀望的那些 Target Peer 会 Apply CommitMerge。

而对于在 CommitMerge 之后的 Conf Change 来说，失效是期待 Apply 之后，此时 CommitMerge 曾经 Apply 完了。假如有新增 Peer，为了满足性质 1，Leader 须要保障收回的 Snapshot 至多得是 Apply 了 CommitMerge 之后的。

Split 有相似的条件，只有参加 Split 过程的 Peer 能力 Apply BatchSplit。同样是依附这三点来保障这一条件：1. Epoch 查看 2. Conf Change 在 Apply 之后失效 3. 新 Snapshot 得是 Apply 了 BatchSplit 之后的。

TiKV 对于保障 Snapshot 的实现比较简单，在生成 snapshot 之后，比照一下它的 Epoch 中的 conf_ver 和以后的 conf_ver，如果前者小就要从新生成。这样能够保障生成的 Snapshot 的 index 肯定大于等于最初一条 Apply 的 Conf Change 的 index，所以也就大于上述情况中的 CommitMerge 或者 BatchSplit 的 index，间接保障了以上的条件。（代码见 PeerStorage validate_snap）

隔离的复原问题

接下来咱们来思考隔离的复原问题。这里的隔离不仅指的是网络隔离，宕机也能够认为是一种隔离，两者须要思考的复原问题是等价的。

如果还能够通过追日志复原，那么就与失常流程没有区别。剩下的状况就是被 Conf Change 移除了，或者通过 Snapshot 复原，这里咱们次要探讨通过 Snapshot 复原的问题。

回顾 Merge 流程在一开始 Propose PrepareMerge 之前的查看条件 3

• 查看从所有 Source Region 的 Follower 上最小的 commit index 对应的日志到以后最初一条日志之间是否没有 CompactLog/Split/Merge/Conf Change。

据此，可推出性质 2：Snapshot 不必思考屡次笼罩的 Merge 的状况，即 A merge to B，B merge to C（当然 A merge to B，C merge to B 的状况还是须要思考的）。

这一性质很好证实，如果某个隔离的 TiKV 上有 A B C 三个 Region 的 Peer，被隔离时，A merge to B 能够胜利，然而 B merge to C 会被上述的查看条件 3 给挡住。

有了该性质之后，Snapshot 只须要在 Apply 前删除那些要 Merge 给本人的 Source Peer 即可。然而删除这些 Source Peer 并不能轻易删，必须要确保之后 Apply Snapshot 不会失败能力删。这里暗藏着一个违反性质 1 的陷阱，发送 Snapshot 并不意味着之后肯定都会发 Snapshot，因为可能只有 Leader 把日志给 Compact 了，能够结构一种状况在 Leader 给某 Peer 发送 Snapshot 之后，之后的 Leader 依然给它发送日志，如果此时 Source Peer 曾经被删除，那就无奈 Apply CommitMerge 了，违反性质 1。

• 如何结构的问题就留给读者解答了。

在 TiKV 的实现中是先查看该 Snapshot 是否在删除 Source Peer 之后范畴不抵触（代码见 PeerFsmDelegate check_snapshot），而后在暂停 Source Peer 运行之后，对 Source Peer RegionLocalState 中的 PeerState 设置为 Tombstone，Target Peer RegionLocalState 中的 PeerState 设置为 Applying（代码见 PeerStorage apply_snapshot），并且应用 WriteBatch 原子的写入来解决该问题。

• 如果在写入之后宕机，重启后，Source Peer 状态是 Tombstone 会清理残余的数据，Target Peer 状态是 Applying 会持续 Apply Snapshot。

Merge 对租约的影响

在 Region Split 源码解析 中提到 Split 对于 Leader 的租约是有影响的，相似的，Merge 对于租约也有影响。

Target Region 在 CommitMerge 之后，Target Leader 就能失常的解决 Source Region 范畴局部的读写申请了，因为 Source Leader 和 Target Leader 并不一定在一台 TiKV 上，Source Leader 到底要何时让租约过期才是正确的呢？

正确的工夫是在 Source Leader 得悉 PrepareMerge 曾经 commit 并且筹备播送该 commit 的音讯之前（代码见 Peer on_leader_commit_idx_changed）。这是因为在其余的 Source Peer 收到该 commit 音讯之后很短时间内，Merge 的过程可能曾经胜利了，并且 Target Leader 也曾经实现了 Source Region 范畴内新的写申请。此时若 Source Leader 依然持有租约持续服务读申请，就会返回旧数据，从而违反线性一致性。

Merge 对 Split 的影响

在 Region Split 源码解析 中的 Split 实现章节咱们讲到在 Apply Split 的时候会对每个新的 Region 创立元数据。这里存在一个荫蔽的前提：Split 中的新 Region 肯定是第一次呈现在本地的。如果该前提被突破，Split 时写入新 Region 的元数据就可能笼罩掉正在运行中的新 Region 的元数据，影响正确性。

该前提在只有 Split 的状况下是能够保障的，因为范畴重叠，新 Region 是无奈提前被创立进去的。然而因为 Merge 的存在，新 Region 可能会“逃脱”原 Region 的范畴，从而违反该前提。

举个例子：
Region A 要 Split，新 Region 为 C，然而在 TiKV 1 上的 Region A 因为某种原因，运行迟缓，始终没有 Apply Split。

注：* 代表空

此时进行了 Conf Change。Region C 和 A 各自都移除了 TiKV 1 上的 Peer，也在 TiKV 4 上减少了 Peer。

Region C 进行了 2 次 Merge 以及 Split 之后，再次进行 Conf Change，移除了 TiKV 4 上的 Peer，在 TiKV 1 上减少 Peer。

此时曾经突破前提了，在 TiKV 1 上，Region C 曾经在 Region A Apply Split 之前呈现了。

能够发现该问题的触发并不容易，这是因为一些实现细节的起因，比方 Split 之后原 Region 的地位以及 Merge 在 Propose PrepareMerge 时的查看条件等等。

因为创立新 Peer 与 Apply Split 是在不同的线程，波及到并发逻辑，解决该问题的实现细节比较复杂，这里就不详述了，感兴趣的小伙伴可自行浏览源码。

总结

咱们来回顾一下之前提到的设计需要：

1. 不依附 PD 在 Merge 期间不发动其余的调度满足正确性

   • 满足，如果 PD 在 Merge 期间进行调度，Merge 会 Rollback

2. 不会因为网络隔离或者宕机引发正确性问题

   • 满足

3. 只有参加 Merge 的 TiKV 中 Majority 存活且能相互通信，Merge 能够持续或者回滚，不会被阻塞住（跟 Raft 保障可用性的要求统一）

   • 满足

4. 不对 Split/Conf Change 加额定条件限度（出于性能思考）

   • 满足

5. 尽量减少搬迁数据的开销

   • 在 PD 搬迁正本之后，Merge 带来的额定数据仅只有一小部分日志

6. 尽量减少 Merge 期间服务不可用的工夫

   • Target Region 无服务不可用工夫
   • Source Region 服务不可用工夫如下

   • PD 会抉择较冷的 Region 作为 Source Region，所以一般来说这个代价是可忍受的

总的来说，TiKV 的 Region Merge 的设计根本达成了指标。

从全文来看，Region Merge 的设计上对原始 Raft 算法有肯定的批改，有诸多的实现细节问题，再加上与其余性能的相互影响，简单的隔离复原问题等等，这所有也使它成为 TiKV 中最为简单的性能之一。因为篇幅所限，本文次要帮忙读者理清 Region Merge 的主体设计思路，更多的细节就留给感兴趣的读者们自行浏览源码了。

至此 TiKV 源码浏览就临时告一段落了，TiKV 依然还在一直的演变倒退，朝着更稳，更快，更牢靠的方向后退。心愿小伙伴们可能继续关注 TiKV，退出咱们的 slack 频道参加探讨或者提 issue 和 pr。