缘起

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云数据库。

创作场景

亚军 Rollbacked 作品解析