赛题背景

POLARDB作为软硬件结合的代表, 充分使用新硬件, 榨干硬件的红利来为用户获取极致的数据性能, 其中在PPOLARDB 的设计中, 我们使用 Optane SSD作为所有热数据的写入缓冲区, 通过kernel bypass的方式, 实现了极致的性能。所以本次比赛就以Optane SSD为背景，参赛者在其基础之上探索实现一种高效的kv存储引擎。

赛题描述

实现一个简化、高效的kv存储引擎，支持Write、Read、Range接口。

程序评测逻辑

评测程序分为2个阶段：

1）Recover正确性评测：

此阶段评测程序会并发写入特定数据（key 8B、value 4KB）同时进行任意次kill -9来模拟进程意外退出（参赛引擎需要保证进程意外退出时数据持久化不丢失），接着重新打开DB，调用Read、Range接口来进行正确性校验

2）性能评测

- 随机写入：64个线程并发随机写入，每个线程使用Write各写100万次随机数据（key 8B、value 4KB）

- 随机读取：64个线程并发随机读取，每个线程各使用Read读取100万次随机数据

- 顺序读取：64个线程并发顺序读取，每个线程各使用Range有序（增序）遍历全量数据2次

注：

2.2阶段会对所有读取的kv校验是否匹配，如不通过则终止，评测失败；

2.3阶段除了对迭代出来每条的kv校验是否匹配外，还会额外校验是否严格递增，如不通过则终止，评测失败。

评测硬件规格

CPU：Intel(R) Xeon(R) CPU E5-2682 v4 @ 2.50GHz x2

内存：C++ 2G Java 3G（Java含评测程序）这里的内存指程序可用的所有内存资源，使用CGROUP命令限制

存储： Intel Opatne 2701（345G、裸盘IOPS 580K、EXT4 IOPS 400K）

赛题分析

这次比赛的硬件阵容可谓是相当豪华了，不论是CPU还是存储硬件，都是价值五位数的神器。64核CPU可以说是几乎不用考虑并发计算性能的问题，但是越高的并发量就意味着线程同步等问题难度的增长，一些在本地4核6核上可以正常运行的程序，在线上就可能出现预料之外的死锁等问题。这次比赛虽然为评测设置了3600秒的超时机制，但想要准确定位和高效调试，还是需要自己在代码中实现一个死锁超时自动exit的机制。至于SSD，借用大佬的一张图：

没错，Intel Optane P系列使用了最新的X3D Point技术，使得SSD的4K随机读取的性能暴涨，达到了60w IOPS，看以后谁还敢叫我牙膏厂。经实测，其顺序写入速度达到55w IOPS，随机读取60w IOPS，顺序读取65w IOPS，这意味着完全不需要考虑操作系统的PageCache机制和复杂的调度优化，直接使用DIO就可以最大化性能。至于赛题中一个比较重要的要求，就是要实现进程意外退出时数据持久化不丢失，这个其实很简单，对Linux比较熟悉或者有参赛经验的同学都知道使用mmap做WAL缓冲区，就可以实现进程被KILL -9之后又操作系统帮我们把未保存的数据Flush到存储设备上。

这样看来，赛题的难点就在于2GB/3GB的内存限制，好在6400w条消息的KEY（8Byte）大约需要488M的内存，如果算上需要保存的偏移量之类的信息（以8Byte计），则最多占用980M左右的内存。这意味着所有的KEY都可以读到内存中，并且还有1G以上的可用空间。或者保证KEY与VALUE在文件位置上的一一映射关系，则可以只存KEY值，从而有1.5G的可支配空间。

架构设计

写入阶段

64个线程并发无锁写入，KEY直接使用mmap一次性分配所有缓冲区，顺序写入缓冲区即可。同时通过KEY前9bit位的值，HASH到512个BUCKET中，每个BUCKET配备256*4096字节的双缓冲区。不论是KEY或VALUE，写入的时候使用atomic<int>获取写入缓冲区的偏移量，写入完成后再将缓冲区的原子计数器加1，如果写满，则使用pwrite接口落盘。其中BUCKET的双缓冲区机制可以保证一个缓冲区在落盘的时候，其他线程仍然可以往另外一个缓冲区里写入，从而避免阻塞。当两个缓冲区都写满时，线程调用sched_yield自旋等待。

随机读阶段

一次性读取所有KEY，然后64线程并发构建索引，如下图所示，所有KEY通过计算前25个bit位的值，散列到2^25个BUCKET中，其中冲突的KEY可以使用链表串联，即使用NEXTKEY指向下一个散列到同BUCKET的KEY。读取的时候，计算KEY的hash值，然后沿着链表查找即可。

顺序读阶段

因为已经将VALUE分配到512个BUCKET，虽然每个桶内是乱序的，但是桶之间是有序的，而且BUCKET大约500M大小，这意味着至少可以同时有两个BUCKET读入内存。所以这其实就是一个单生产者多消费者模型，通过RingBuffer和缓冲区原子计数器就可以实现单线程顺序读（不过这里使用的是自己封装的syscall调用的异步IO读取函数），同时64个线程RangeVisit。

总结

虽然相比自身有了长足的进步，但是和真正的大佬比还是有很大的差距。且不谈毫无争议的冠军Rapids团队（前中间件大赛冠军，曾用一手AVX2向量化技惊四座），0xCC大佬更是在复赛第二天就肝出了跑分415s的代码。彼时我还在纠结应该使用哪种架构，结果错误使用了全顺序写+随机读的方案，导致range阶段速度始终提不上去，整整两周时间在做无用的优化。幸好最后4天突然醒悟，连夜写出Bucket+分片读的方案，勉强保住前20。

其实还有好几个没有来得及尝试的优化点，这里罗列下：

KEY在写入阶段就分成64个BUCKET保存，这样就可以在写入结束后64线程并发排序直接顺序落盘，同时随机读构建hash索引时也可以不使用原子量。

过多的文件描述符会降低IO调度性能，尤其1024是一道坎，具体技术解析参考：

文件描述符file descriptor与inode的相关知识

使用set_affinity设置线程CPU亲核性；

随机读取阶段会有800M左右的空闲内存，可以预读一部分文件作为缓存。

以及通过赛后交流了解到的优化点：

O_NOATIME打开文件读写会稍微快一点，因为·可以避免更新文件时间戳。

内联汇编实现memcpy，以及异或实现字节逆序（这个貌似没什么用）。

sched_yield是并发性能杀手，它会使当前线程让出时间片，并回到调度队列的末尾。

16K小缓冲区写入要快过大于1M的大缓冲区写入（想不通为什么大缓冲区大批量写入反而性能会降低，或许是这会阻塞SSD的调度?还是说SSD本身的读取单元就是以小BLOCK为单位的？看来性能优化真的是一门玄学技术。。。）