背景

2022 年 10 月，2022 TiDB Hackathon Possibility at Scale 成功举办。

作为暑期实习在贵司事务组的 intern，在对 TiKV 的 codebase 有一定了解后，我兴致勃勃地拉了实验室的同学报名参加了此次 Hackathon，并且最终拿到了产品组的最佳校园奖，虽然没有拿到更大的奖项，但已经玩得十分开心了。

非常感谢 Hackathon 期间队友，mentor，组织者和评委对我们组的帮助和认可。

本文将简单介绍我们组的工作和思考以做回顾。

以下是我们项目的一些相关资料，欢迎点击了解：

• 代码
• RFC
• 答辩视频

注：本文仅代表个人看法。

工作

本小节将沿着答辩 PPT 的思路介绍我们的工作。

我们的名字是热点清零队。我们的项目是无畏写热点，我们希望能够解决 TiKV 写热点问题的最后一公里。

我们的团队成员均来自清华大学软件学院。今年 hackathon 的主题是探索 scale 的可能性，我们的主要工作是解决热点 Region 在单机多核上的扩展性问题。在极致场景下我们提升了 TiDB 接近 1.2 倍的吞吐。

从用户视角来看，写热点问题会给他们带来多少困扰呢？比如某用户就提出，批量写场景下 TiKV 的 CPU/IO 都没用满，但写入依然很慢，这些现象给用户带来了不便和困扰。我们统计了 AskTug 论坛上写满 tag 帖子的原因分布，大致如右上图所示，可以看到写热点问题占比第一。

那现在的 TiDB 是如何解决热点问题的呢？其整体思路都是通过划分 region 来均匀承担负载，从而能够扩展。如右图所示，理想情况下随着 region 的分裂，热点会被稀释，进而线性扩展起来。然而，在当前上层数据分片的语义下，对于聚簇索引，唯一自增索引等场景，写热点问题难以避免。

当分裂 region 不能均分负载时，实际情况会如右上图所示，尽管分裂出了多的 region，但写热点始终集中在个别 region 上。在这种场景下，往往会遇到单节点存算资源并没有被充分利用的情况。其实不论上层怎么去分裂 region，单 region 热点始终是写热点问题的最后一公里，无法回避。

那让我们看看在 TiKV 中单 region 的执行路径。总体来说是需要在 StorePool 中进行 commit，在 ApplyPool 中进行 apply。然而在现有的实现中，不论是 StorePool 的持久化还是 ApplyPool 的写 memtable，并行度都是 1，因而不具备在单机上的扩展性。

那如果我们想要在单机上扩展热点 region，那可以从存储资源和计算资源两个方面来入手。对于存储资源，可以利用 IO 并行来提高吞吐，比如将单 region 不同批的日志用异步 IO 并行化处理，去年的 TPC 项目已经做过尝试，取得了不错的效果。对于计算资源，理论上也可以采用多核并行来提高吞吐，这也是我们的尝试，即去做 Parallel Apply

Parallel Apply 的整体思路是将无依赖的日志并行处理，从而提升整体吞吐。2018 年 VLDB 和 2021 年 JOS 已经对 Parallel Apply 的可行性和正确性进行了证明。

那在 TiKV 上落地 Parallel Apply 会有哪些难点呢？我们主要遇到了 4 个问题，比如如何保证依赖顺序的正确性，数据正确性，语义正确性和 index 正确性等等，以下分别进行介绍

我们的整体思路是在 ApplyPool 以外额外引入一个 ParallelApplyPool，并在 StorePool 中判断路由，进而使得单 region 的日志存在并行的可能性。同时在实现过程中，为了避免锁导致的线程切换，我们的共享状态均使用了原子变量。

对于刚刚提到的难点，我们简单介绍一下解决方案。

对于如何保证具有依赖的日志执行顺序正确？在 Leader 侧和在 Follower 侧需要有不同的处理方案。

• 在 Leader 侧，得益于上层事务语义的约束，我们不需要引入依赖检测结果便可以无约束的并行 apply 普通日志，因为他们的 key 范围必定不会重叠。
• 在 Follower 侧，最简单可以串行执行来保证正确性，更进一步也可以考虑基于拓扑排序的依赖检测机制来并行 apply 日志从而满足依赖关系。

对于如何保证 leader 切换或重启时数据依然正确？我们则很简单的使用了 Raft 的 term 变量，当且仅当日志的 term 为当前 term 时才考虑路由到 ParallelApplyPool 并行处理。这样的机制保证了 Leader 切换或者节点重启时系统不会将本不能并行处理的日志并行化处理，从而导致数据不一致。

对于如何保证 admin 等特殊日志的执行依然符合串行语义？即在 admin 日志执行之前其前面的所有日志均需要已经执行，在 admin 之后的日志执行前必须保证该 admin 日志已经执行。这个具体实现非常复杂，简单来说，我们在 Parallel Apply Pool 和 ApplyPool 中用原子变量共享了一些状态，对于单 region，StorePool 会将无冲突的普通日志在 Parallel ApplyPool 中并行执行，当出现 admin 日志时，当 StorePool 未感知到其执行完时，所有的日志都会被路由到 ApplyPool 中串行执行，当 admin 日志的 apply 结果返回 StorePool 后，之后的普通日志可以被继续路由到 Parallel Apply Pool 中并行执行。在...