关于数据库:TiKV-源码解析系列文章二十Region-Split-源码解析

在学习了之前的几篇 raft-rs, raftstore 相干文章之后（如 Raft Propose 的 Commit 和 Apply 情景剖析，Raftstore 概览等），raft-rs 以及 raftstore 的流程大家应该根本理解了。其中 raft-rs 解决的是单个 Raft group（即单个 Region）的问题，raftstore 解决的是多个 Raft group（即多个 Region）的问题。Split 和 Merge 则是 raftstore 多个 Raft group 所独有的操作。TiKV 中的 Split 能把一个 Region 决裂成多个 Region，Merge 则能把 Range 相邻的 2 个 Region 合成一个 Region。本文接下来要介绍的是 Split 的源码。

Region epoch

message RegionEpoch {
    // Conf change version, auto increment when add or remove peer
    uint64 conf_ver = 1;
    // Region version, auto increment when split or merge
    uint64 version = 2;
}

咱们先从 region epoch 讲起，下面是它的 protobuf 定义，在之前的源码分享文章中提到过，它的实质就是两个版本号，更新规定如下：

1. 配置变更的时候，conf_ver + 1。
2. Split 的时候，原 region 与新 region 的 version 均等于原 region 的 version + 新 region 个数。
3. Merge 的时候，两个 region 的 version 均等于这两个 region 的 version 最大值 + 1。

2 和 3 两个规定能够推出一个乏味的论断：如果两个 Region 领有的范畴有重叠，只需比拟两者的 version 即可确认两者之间的历史先后顺序，version 大的意味着更新，不存在相等的状况。

证实比较简单，因为范畴只在 Split 和 Merge 的时候才会扭转，而每一次的 Split 和 Merge 都会更新影响到的范畴里 Region 的 version，并且更新到比原范畴中的 version 更大，对于一段范畴来说，不论它属于哪个 Region，它所在 Region 的 version 肯定是严格枯燥递增的。

PD 应用了这个规定去判断范畴重叠的不同 Region 的新旧。

每条 Proposal 都会在提出的时候带上 PeerFsm 的 Region epoch，在利用的时候查看该 Region epoch 的合法性，如果不非法就跳过。

上图所示，新 Proposal 的 Region epoch 是利用了 Applied Index 那条 Proposal 之后失去的，如果在 Applied Index + 1 到 Last Index 之间的 Proposal 有批改 Region Epoch 的操作，新 Proposal 就有可能会在利用的时候被跳过。

列举两个被跳过的状况，其余的可参照代码 store::util::check_region_epoch：

1. 非 Admin Request，Proposal 中的 version 与以后的不相等。
2. Split，Merge 的 Request，Proposal 中的 Region epoch 与以后的不相等。

Split 触发

Split 触发的条件大体分两种：

1. PD 触发
2. TiKV 每个 Region 自行定时查看触发

PD 触发次要是指定哪些 key 去 Split，Split Region 应用文档 中的性能就是利用 PD 触发实现的。

每个 Region 每隔 split-region-check-tick-interval（默认 10s）就会触发一次 Split 查看，代码见 PeerFsmDelegate::on_split_region_check_tick，以下几个状况不触发查看

• 有查看工作正在进行；
• 数据增量小于阈值；
• 以后正在生成 snapshot 中并且触发次数小于定值。如果频繁 Split，会导致生成的 snapshot 可能因为 version 与以后不统一被抛弃，然而也不能始终不 Split，故设置了触发下限。

触发查看后，会发送工作至 split_checker_worker，工作运行时调用 split_checker.rs 中函数 Runner::check_split。

1. 调用 coprocessor::new_split_checker_host 获取 SplitCheckerHost，获取时会对每一个注册过的 split_check_observers 调用 add_checker，若满足触发阈值则会把它的 split_check退出 SplitCheckerHost::checkers 中，如果 checkers 为空则完结查看。（值得一提的是，这里的 coprocessor 并不是指的是计算下推的那个 coprocessor，而是观测 raftstore 事件，给内部提供事件触发的 coprocessor，它的存在能够很好的缩小内部观测事件对 raftstore 代码的侵入）
2. 获取 policy，这里的 policy 只有两种，别离是 SCAN 和 APPROXIMATE，即扫描和取近似，遍历 split_checker 调用它们的 policy，只有有一个给出的 policy 是取近似，那么最终的后果就是取近似，反之则是扫描。
3. 获取 Split key。

   a. 若 policy 为扫描，调用 scan_split_keys，扫描读出该 Region 范畴大 Column Family 的所有数据，对于每一对 KV，调用每个 split_checker 的 on_kv 计算 Split key，扫描实现后遍历 split_checker 的 split_keys 返回第一个不为空的后果。因为须要扫描存储的数据，这个策略会引入额定的 I/O。

   b. 若为取近似，调用 approximate_split_keys，遍历 split_checker 的 approximate_split_keys，返回第一个不为空的后果。这是通过 RocksDB 的 property 来实现的，简直没有额定的 I/O 被引入，因此性能上是更优的策略。

4. 发送 CasualMessage::SplitRegion 给这个 Region。

SplitCheckerHost 只是聚合了split_check 的后果，具体实现还是在这些 split_check 中，它们均实现了 SplitChecker trait，由上文的流程叙述也都提到了这些函数。

pub trait SplitChecker<E> {
    /// Hook to call for every kv scanned during split.
    ///
    /// Return true to abort scan early.
    fn on_kv(&mut self, _: &mut ObserverContext<'_>, _: &KeyEntry) -> bool {false}

    /// Get the desired split keys.
    fn split_keys(&mut self) -> Vec<Vec<u8>>;

    /// Get approximate split keys without scan.
    fn approximate_split_keys(&mut self, _: &Region, _: &E) -> Result<Vec<Vec<u8>>> {Ok(vec![])
    }

    /// Get split policy.
    fn policy(&self) -> CheckPolicy;
}

split_check 有以下几种：

1. 查看 Region 的总或者近似 Size，代码位于 size.rs。
2. 查看 Region 的总或者近似 Key 数量是否超过阈值，代码位于 key.rs。
3. 依据 Key 范畴二分 Split，代码位于 half.rs，除了上文讲的 PD 指定 key 来 Split，这种形式也是由 PD 触发的，目前只有通过 pd-ctl 和 tikv-ctl 的命令来手动触发。
4. 依据  Key 所属 Table 前缀 Split，代码位于 table.rs，配置默认敞开。

因为篇幅所限，具体的实现细节可参阅代码。

Split 实现

Split 的实现绝对简略，总的来说，Split 这个操作被当做一条 Proposal 通过 Raft 达成共识，而后各自的 Peer 别离执行 Split。

讲一下具体的流程。

在触发 Split 之后，触发方会发送一条 CasualMessage::SplitRegion 给这个 Region，解决代码见 PeerFsmDelegate::on_prepare_split_region，除了须要查看是否是 leader，还需查看 version 是否有变动，如有变动就回绝触发 Split。

查看胜利后，发送一条 RPC 向 PD 申请调配一些新的 ID，蕴含所有新 Region 的 ID 以及它所有的 Peer ID，等到 PD 回复后，结构一个类型为 AdminCmdType::BatchSplit 的 Proposal 提给该 Peer。代码在 pd_worker 下的 handle_ask_batch_split。

之后的流程就如 Raft Propose 的 Commit 和 Apply 情景剖析 所形容的那样，如上文所述，在利用前会判断 Region epoch 的合法性，如果不非法就须要跳过。假如它没有被跳过，接下来看这条 Proposal 利用的中央 ApplyDelegate::exec_batch_split。

1. 更新原 Region 的 version，新 Region 的 epoch 继承原 Region 的 epoch。
2. right_derive 为 true 的，原 Region 要决裂到右侧，为 false 则反之，顺次设置每个 Region 的 start key 与 end key。
3. 对每个 Split 进去的新 Region 调用 write_peer_state 与 write_initial_apply_state 创立元数据。

在利用实现之后，ApplyFsm 会发送 PeerMsg::ApplyRes 给 PeerFsm, PeerFsm 解决的代码在 PeerFsmDelegate::on_ready_split_region

1. 如果是 leader，上报 PD 本人以及新 Region 的 meta 信息（蕴含范畴，Region epoch 等等一系列信息）。
2. 顺次创立新 Region 的 PeerFsm 和 ApplyFsm，做一些注册的工作。
3. 更新 PeerFsm 的 Region epoch。

须要留神的是，如果在利用实现落盘后宕机，这部分的工作能在重启后复原。其实所有日志利用的设计都须要满足这个准则。

到这里 Split 的工作就实现了，等到原 Region 大多数的 Peer 都实现了 Split 的工作后，新 Region 就能够胜利选出 leader 并且提供服务了。

Split 过程中的一致性

在各机器时钟偏移不超过肯定范畴的前提下，某个 Region 的 Leader 持有 Raft 租约能保障这段时间不会产生其余 term 更大的 Leader，基于这个保障，应用租约能够提供 线性一致性 的本地读取性能，具体实现能够参考上一篇源码阅读文章。

然而在 Split 过程中，原 Region 持有的租约并不能保障这一点。

假如 3 个正本，思考如下状况：Split Proposal 在 2 个 Follower 上曾经利用实现，同时 Leader 上还没有利用（因为 apply 是异步的，Follower 上的利用进度可能超过 Leader）。

Split 之后原 Region 的范畴放大，其余的范畴属于新 Region，而新 Region 存活的 Peer 个数曾经超过了 Raft 所要求的大多数正本，故能够正当的发动选举并产生 Leader，并且失常服务读写申请。此时原 Region Leader 依然还未利用 Split Proposal，如果因为持有租约持续服务原范畴的读申请，就会毁坏 线性一致性。

TiKV 解决形式是在 Split 期间不续约租约。办法是记录最初一条 Split Proposal 的 index last_committed_split_idx, 记录地位见 Peer::handle_raft_ready_append。只需判断 last_committed_split_idx 是否大于 applied_index 即可得悉是否在 Split 期间(Peer::is_splitting)。

浏览过 Peer::handle_raft_ready_append 中记录 last_committed_split_idx 的小伙伴应该能留神这里并没有让租约立马生效，仅仅设置 index 阻止下次续约。换句话说，在 Split 期间的那次租约工夫内是能够让原 Region 的 Leader 提供本地读取性能的。依据后面的剖析，这样做貌似是不合理的。

起因非常乏味，对于原 Region 非 Leader 的 Peer 来说，它创立新 Region 的 Peer 是不能立马发动选举的，得期待一个 Raft 的选举超时工夫，而对于原 Region 是 Leader 的 Peer 来说，新 Region 的 Peer 能够立马发动选举。Raft 的超时选举工夫是要比租约工夫长的，这是保障租约正确性的前提。所以在 Split 期间的那次租约工夫内，在其余 TiKV 上的新 Region Peer 就算创立进去了，也不会发动选举，因而保障了不会有新数据写入，故在原 Region 上读取不会毁坏 线性一致性。

总结

Region Split 的根底流程比较简单，简略来说就是依赖原 Region 的 Raft 提供的牢靠复制性能实现的，而与此绝对的 Region Merge 因为两个 Region 属于不同的 Raft group，与 Region Split，Raft Snapshot 的相互作用，再加上网络隔离带来的影响，无疑有更大的复杂度。在之后的源码阅读文章中咱们会持续解说 Region Merge，敬请期待！