亚军Rollbacked作品解析

缘起

TaurusDB 是华为云自主研发的最新一代云原生分布式数据库，完全兼容 MySQL8.0，采用计算与存储分离、日志即数据的架构设计，支持 1 写 15 读，性能达到原生 MySQL 的 7 倍。Taurus 构建在共享分布式存储上，存储空间最高达 128T，能跨 AZ 部署，具有可靠、高性能、易伸缩等特性。

华为云 TaurusDB 性能挑战赛是由华为云主办的数据库领域顶级赛事，大赛将综合科研教学成果及商业领域需求，探索数据库领域的技术问题的可行性，为需求方和开发者提供联接的桥梁；并联合合作伙伴，搭建一个技术交流、人才培养、机遇共创数据库开发者平台和生态。

听起来很激动人心吧，关键是奖金也很多, 同时还能刷脸！ 最早是听一个同事说起的，恰好本人的工作也是“新一代数据库”开发，看着这么多人工智能的比赛不能参加，只能后悔自己选错了专业，但是机会来了，终于有自己擅长的领域了，心想不能错过这次机会，一边默默加了收藏。

比赛内容一句话概括，就是实现一个 kvstore，初赛是单机引擎，复赛要求存储计算分离，并且 kv 都是定长的，如果通用性做得好，可以直接用作块存储。

题目

初赛和复赛稍有区别，这里只说复赛的题目。存储引擎 K，V 都是定长的，key 8bytes， value 4K bytes。测试分为三轮：第一轮，16 个线程写，每个线程写 400 万次；第二轮，16 个线程读，每个线程按顺序读取 400 万次；第三轮，16 个线程读，每个线程逆序读取 400 万次。第三轮的逆序是局部随机，总体逆序，也即在 10M 的数据范围内随机读，然后以 10M 为单位逆序推进。成绩就是看总时间，时间越短越好。

前面已经说过，初赛要实现的是单机引擎，复赛要实现的是存储计算分离的引擎，最大的限制是计算节点不能持久化任何数据。

预选赛

不得不说，华为可真会玩，这次预选赛竟然还要做题，并且是必须要学习他们的资料才能通过的题目，题目包括数据库的基本常识，但是也有产品介绍，经过深夜两个小时的学习，我算是第一次知道了这么多种不同的产品究竟是干嘛的。第一次答题还错了一道，以防万一，又做了一遍，这次错了两道，算了不玩了，95 分也够了，睡觉去。但是心里总是不舒服，究竟是哪错了，又看了一遍，原来是幻读的理解这道题错了。

初赛

不出意外，预选赛顺利通过，初赛就开始写代码了，初赛只要写的差不多就可以晋级复赛。当然任何一个程序员都不会满足刚好够用的状态，因此正常能想到的优化都加上了：比如 Direct IO, 多文件做数据分区，引入写 buffer，比较频繁修改元数据，读取使用自己实现的 page cache，以免 4K 读不能打满磁盘带宽。

复赛

复赛要求存储计算分离, 我认真做了一些分析，同时也对他们的硬件做了测试。分析下来，这个比赛比拼的点和我平时在工作中要追求的还是很不一样的。平时无论做什么系统，都是在延迟差不多的情况下，把吞吐量做高，这次比赛最关键的一个点是：延迟第一，延迟是最重要的。特别是写的阶段，因为并发只有 16，想通过聚合换吞吐量都不好使了。

考虑持久化方法：

• 4K恰好能对齐IO，所以key和value要分开存储, 想使用rocksdb之类的存储引擎即使不被禁止也是没有竞争力的。

• value非常随机，基本不用考虑压缩，就算有一点点好处，实现起来也太复杂了。

考虑如何优化 IO：

• SSD的IO吞吐量高于4K * iops, 不管是读还是写，IO聚合是必须的。

• 单文件会遇到文件系统瓶颈，需要多文件, 也即要对数据做partition。

• 关于同步IO还是异步IO的选择, 因为延迟优先，所以应该选同步IO。

考虑网络框架：

• 首先，我直接放弃考虑任何已有的网络框架，因为这是benchmark， 再小的开销也是开销，都会让程序变慢。

• 其次，实际上任何 IO multiplexing 的框架都会造成额外的延迟，不仅复杂，也是得不偿失的。

综上，我决定就使用最简单的阻塞式 IO 来做 socket 通信。

总体设计

计算节点和存储节点分工, 关键就是索引维护在哪？经过思考, 决定索引维护在计算节点。索引的内容是：key -> <file_id, pos>，索引在计算节点的内存中维护为 hash 表。

因为 build 索引大概需要 400ms，写入再读取 index 比重新构建一遍 index 时间还长, 所以索引不需要持久化，这其实是一个反直觉的决定。计算节点在发送第一个读请求之前，会从存储节点把所有写入的 key 和 pos 发送过来, 然后由计算节点构造索引。

存储节点起 16 个线程，listen 在 16 个不同的端口。计算节点也会有 16 个线程，每个计算节点的线程只会连接一个存储节点的端口，从而和一个存储节点线程通信。

写入请求：

1 写入过程不同的线程完全独立，每个线程负责一部分数据。

2 请求发到存储节点后由接受请求的线程写入。

读取过程：

1 读取过程每个存储线程会读取任意一个线程写入的数据。

2 由计算节点指定要读取哪个分区的数据。

即写请求发到哪个存储线程，就由哪个存储线程写入，每个存储线程实际上就对应了一个数据分区。读请求发到一个存储线程，它可能要跨线程读取其它分区的数据。

存储文件

存储节点把数据分为 16 个 partition，每个 partition 由一个线程负责写入。每个 partition 共三个文件，之所以有三个文件是因为首先 key 和 value 要分开存储，这就要用两个文件。其次为了优化写，额外引入了文件做写入 buffer。

文件命名规则如下, 以第一个分区为例：

• 00.k：保存写入的key，fallocate 4M * 8B， mmap到内存。

• 00.v：保存写入的value，fallocate 4M * 4K， DIO读写。

• 00.b：用作写入buffer，fallocate 16K buffer + 4K 元数据，mmap到内存。

写入原子性

先写 key 和 value，再更新 key count。key count 改成功，则写成功；否则写失败，下次重启进程当作这次写没发生过。换句话说，key count 改成功实际上表示这次写入 commit 成功。

key count 记录在 00.k 的第一个 8 字节, 如前所诉, 00.k 是 mmap 到内存的，所以更新 key count 是没有什么代价的。

value 先记录到写 buffer 里，然后批量刷到 00.v 文件。

key file 内容如下：

value file 内容如下：

buffer file 内容如下:

write buffer 也是 mmap 到内存的， 前 64K 记录数据。紧跟 64K 的 8 个字节记录 flushed pos。因为 mmap 必须以 page 为单位，所以实际内存占用 64K + 4K。它实际上是一个 mmap 持久化的 ring buffer。Ring Buffer 的元数据包括 filled pos 和 flushed pos。filled pos 由 key count 可以算出来, 所以不需要单独再记。

build index

build index 实际上是构造一个 key -> offset 的 hash 表。要在 400ms 内完成 build index，难点是如何并行：基本思路是把 key 做 partition，每个 partition 内独立构造 hash。这本质上是一个 MapReduce 的过程。

map 阶段：并行划分 range，16 个线程，每个线程负责处理一个 key 文件。

reduce 阶段：并行构造 hash，16 个线程，每个线程处理一个 range。

线程同步：第二阶段开始之前要等第一全部完成，也即两个 Stage 之间是个 Barrier，这个同步过程和 map reduce 的 shuffle 是类似的。

读取 cache 的实现

cache 是 value 的镜像，value 文件分成了 16 个，cache 也对应分成 16 组。因为顺序和热点访问模式对 cache 都很友好，cache 不需要特别大，每一组 cache 大小为 64M。

为了应对热点读，cache 的最小单元设为 16M，借用 CPU cache 的术语，我把它叫 cache line，这是一个很大的值。cache 的内存因为是定长的，所以通过 mmap 一次申请好，不需要动态分配。cache 的索引本质是一个 hash，但是不用解决冲突, 用 file offset 直接计算得到索引的下标。

对 16 组 cache 中的每一组来说，有 4 个 cache line, 每个 cache line 有三种状态，用一个 uint32_t 表示：

1 Invalid: UINT32_MAX

2 Locked: UINT32_MAX - 1

3 Valid: file_offset »12

cache line 的状态被叫做 indexStat，它被单独记在另外一个小数组里。

读取不用加锁，使用 double check 即可:

1 读取之前检查 IndexStat 有效，并且 offset 和我要读取的内容匹配。

2 拷贝 cache line 的内容到私有 buffer。

3 拷贝完 cache line 的内容后再检查 IndexStat 是否发生过变化, 如果 indexStat 没有变化过，则说明我们拷贝的 cache line 内容是对的。

为了让上述 double check 生效, 更新 cache 的线程需要在写入之前把 indexStat 改为 Locked，更新完成后再把 indexStat 改为有效值。

网络通信

关于网络框架还有一个问题，就是是否有必要用 UDP，犹豫之下，觉得 UDP 还是会更复杂，稳妥起见，选择了 TCP。后来得知在测试环境里 UDP 是不同的，也就释然了。

但是 TCP 看起来开箱即用，用起来却暗藏机关，至少要调整以下三个参数：

1 tcp_nodelay

2 tcp_quickack

3 send/recv buf

最后为了规避 TCP 的流控，我们要避免另外两个坑：

1 避免发送太快，超过交换机的队列长度，从而导致丢包，因为 TCP 的工作方式就是，只要你给它数据，它就会不停的加大发送窗口，直到发生丢包，然后触发限流。要避免这种情况，本质是要限制 TCP 的连接数， 因为只要连接数限制住了，发送窗口总长度也就限制住了。

2 避免 TCP“冷却”之后重新进入慢启动状态，如果有 root 权限，是可以通过 sysctl 关闭 slow start 的，但是我们没法控制系统参数，这就要求我们一个连接最好要不停的发包，不要停下来。

有人定义了 packet 格式，而我遵循一切从简的原则，没有实现通常 RPC 要有的功能：

1 没有定义 pcode，因为整个通信过程就只有读和写两种 request，每一个 socket 只用来发送一种类型的 request，如果要发送不同的 request，只需要切换 socket 即可。

2 没有实现序列化，因为 request 很简单，只需要把结构体直接发送到 socket 即可。

细节决定性能

细节也就是很多关于性能的小点：

1 首先关于文件 IO：同步 IO 比异步 IO 延迟要小; open 的时候加入 O_NOATIME 避免读取操作也修改元数据

2 其次关于内存分配：分配完内后提前触发 page fault 至少可以让性能更稳定，如果不能提高性能的话；分配内存可以尝试 hugepage, 失败之后再使用 4K page; mmap 的内存可以不用清零

3 最后关于 CPU, 绑核，通用可以让延迟更稳定, 理论上对性能是有提升的。

正确性测试

如前所属，我基本上是一切从简，但即使如此，提交了好多次，都通不过正确性测试。为了排查问题，专门写了一个随机的验证程序，确实发现了一个 readv 之后更新 iovec 的 bug，还有一处 cache 的 bug。 事后看来，在这个测试上花的时间非常值得，否则我可能到最后都没有成绩。

总结

这次比赛感觉有点像马拉松，听完大家的分享，感觉每个人的时间都比较有限，大家都是争分夺秒，每个人都有一些优化没来得及试。本人最大的一个遗憾是读预取没有实现，另外一个是写的过程中网络和 IO 并行化做的不好。

最后听了第一名的方案，深有体会，要想拿到最好的成绩，需要把写和读分开考虑，同时把网络传输和本地 IO 分开考虑。

单纯从工程上说，我的代码有一些特有的风格, 简单来说就是总爱重复造轮子，不愿意引入依赖：

1 没有用 pthread mutex/cond，全部用 atomic ops + futex

2 没有 spin，等待的地方都有睡眠和唤醒机制

另外，本人虽然工作中用 C++，但是我情愿用 plain old C，所以我很少用高级 C++特性。

如果未来还做这种系统实现的比赛，希望有可以利用 RDMA 的和 NVM 的比赛，毕竟，新硬件总是有更多的可能。当然比赛的设置要考虑引入更多自由度，这样会更加有趣。

本文转载自 HW 云数据库。