“本文来自天池优秀选手yche，他针对落幕不久的第一届POLARDB数据库性能大赛两道赛题：实现一个简化、高效的kv存储引擎，支持Write、Read以及Range接口，整理了一套详细的比赛攻略，小天今天把这套冠军整理的baseline分享出来，希望有更多的天池小宝贝们盘下这波分享，下届POLARDB数据库性能大赛稳得飞起哟~”
△第一届POLARDB数据库性能大赛排名
一、比赛攻略
注意：详细代码和答辩PPT下载请查看Github仓库 http://t.cn/EMlV8Pk
Rapids团队成员: CheYulin, SunShixuan, WangLipeng。
1. 赛题介绍
评测程序分为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校验是否匹配外，还会额外校验是否严格递增，如不通过则终止，评测失败。
2. 最终线上效果
进程耗时
顺序读取中，在内存并发读取visit总时间大概在105-110秒，吞吐量: 284.1-296.2 GB/s 。
进程启动间隔(波动不大，取其中一次作为样本)
历史最佳成绩离理论历史最佳成绩累加差了0.69 seconds； 这应该是与机器读写性能波动有关，其中写性能波动最大。
二、赛题背景分析及理解
1. 赛题注意点
Recover正确性评测要求: 每次Write调用都要将数据至少写入到page-cache。
每个阶段开始，DB Engine都会被重新打开； 每个阶段进行中， 只有读取或者写入中的一种情况发生； 每一阶段结束，page cache会被清空(清空page cache的时间占用总时间)。
对于复赛的顺序读取，recovery阶段使用单线程，并且只遍历全量数据1次，选手需要做相应处理。
评测中， Key-Value大小都是固定的， Key可用64bit无符号整数表示，并且分布均匀。
评测中，允许使用的最大内存2GB (不计评测程序内存占用)；各子阶段会有固定的64线程随机写入或随机读取或顺序读取。
2. 赛题分析
傲腾存储特征
为达到磁盘的峰值吞吐量， 需要保证iostat中的两个关键参数avgrq-sz(扇区个数，一般每个扇区512B)和avgqu-sz(IO队列长度) 处于合适大小。 并且每个request有最大大小，不能设置太大，具体可以查看blockdev --getmaxsect /dev/sda(/dev/sda为查看的设备)。
随机读写只要有合适大小块(avgrq-sz)，保证足够IO队列长度(avgqu-sz)就可以达到接近顺序读写的效果。
顺序读取通过128KB大小请求,QD=8可以达到2595-2605 MB/s左右。
随机读取4KB大小请求, QD=20+可以达到2290 MB/s左右，波动很小。
随机写入16KB大小请求, QD=20+可以达到2180-2200 MB/s。
注意点
随机写入：保证iostat中的合适大小的avgrq-sz(通过实验测得 mmap buffer 16KB比较优)， 保证avgqu-sz(handle tail threads)，至少需要QD=8(实验中测得8,16,32都差不多)，通过写文件时候系统的同步(锁)。
随机读取：保证iostat中的合适大小的avgqu-sz(handle tail threads)。
顺序读取：保证iostat中的合适avgrq-sz和avgqu-sz。做好充分的overlap-io和内存访问(100-110秒左右)。
三阶段是独立进行的(无混合的读写操作)，因此评测不要求索引支持O(logn)或更低复杂度的动态插入。
三、核心思路
每一阶段结束，page cache会被清空。 因此，整体设计中除了内存映射文件(meta-file, key/val buffer files), 其他文件操作都通过DirectIO。
1.储存和索引设计
文件设计
Key和Value都使用write-ahead-log方式，顺序append到相应位置，并通过一个meta文件记录相应记录个数。
Value大小固定为4KB，因此在设计索引时候可以不存Value长度， 并且可以将偏移量直接除以4KB来减少空间占用。
Key大小固定为8B， 根据PolarString定义, Key可以被转化为64bit-Big-Endian无符号整数表示， Key分布比较随机，因此可按Key分Bucket来设计存储结构, 来支持并发恢复索引。
可以将Key-Value在写入时候一一对应，这样就不用写偏移量，而通过顺序遍历write-ahead-log恢复出来。
索引设计
评测中不要求索引支持O(logn)或更低复杂度的动态插入，因此采用 bucket + sorted array 的方案； 按照Key的Big-Endian无符号整数高位分bucket，每个Bucekt内采用根据Bucket内偏移比较的sorted array； 通过计算bucket id 和 branchless-lower-bound加跳过重复支持value in-bucket offset查询。
并行索引构建(0.2秒，throughput = 488.28125MB/0.2s = 2441.4 MB/s)，每个线程分配一些buckets， 因为每个bucket的大小均匀所以workload balanced，多bucket使得sort时间可以忽略， 此外sort还和io overlap在一起。
写入相关的文件设计
写入buffer必须使用文件作为backend的(通过mmap)，来保证正确性。
考虑到range时候顺序读盘更快，写入时候同一bucket写在同一区域。
2.文件设计
key/value write-ahead logs 各32个(一个文件里面分bucket, bucket id相邻的在文件中相邻)。
meta-file, mmap key buffer file, mmap value buffer file各1个, slice成BUCKET_NUM的views (e.g. 1024)。
文件整体设计分为三部分: (1) K-V-Log文件, (2) Meta-Count文件, (3) Key/Value Buffer文件。
2.1 K-V Log文件
key-value的对应: 逻辑上, key-value被写到一个的相同bucket, 对应到相同的in-bucket offset, 通过write-ahead追加到对应的log文件。 我们把8-byte-key通过big-endian转化出uint64_t类型的整数key。
对应从key到bucket_id的计算如下代码所示：
inline uint32_t get_par_bucket_id(uint64_t key) {
return static_cast<uint32_t >((key >> (64 - BUCKET_DIGITS)) & 0xffffffu);
}逻辑上的bucket到实际中的文件, 通过下面的函数算出, 在设计中, 我们让相邻的value buckets被group到同一个value log file, 来为range查询顺序读服务。
inline pair<uint32_t, uint64_t> get_key_fid_foff(uint32_t bucket_id, uint32_t bucket_off) {
constexpr uint32_t BUCKET_NUM_PER_FILE = (BUCKET_NUM / KEY_FILE_NUM);
uint32_t fid = bucket_id / BUCKET_NUM_PER_FILE;
uint64_t foff = MAX_KEY_BUCKET_SIZE * (bucket_id % BUCKET_NUM_PER_FILE) + bucket_off;
return make_pair(fid, foff * sizeof(uint64_t));
}
inline pair<uint32_t, uint64_t> get_value_fid_foff(uint32_t bucket_id, uint32_t bucket_off) {
// Buckets 0,1,2,3... grouped together.
constexpr uint32_t BUCKET_NUM_PER_FILE = (BUCKET_NUM / VAL_FILE_NUM);
uint32_t fid = bucket_id / BUCKET_NUM_PER_FILE;
uint64_t foff = MAX_VAL_BUCKET_SIZE * (bucket_id % BUCKET_NUM_PER_FILE) + bucket_off;
return make_pair(fid, foff * VALUE_SIZE);
}最终设计中, 我们采用了32个value文件和32个key文件。 这是因为多线程写入同一文件时候可以有一定的同步作用(有写入锁的存在), 来缓解最后剩下tail threads打不满IO的情况。 此外，文件过多容易触发Linux操作系统的bug，从DirectIO进入BufferIO, 即使已经标志flag设置了O_DIRECT.
2.2 Meta-Count 文件
meta-count文件用来记录每个bucket中现在write-ahead进行到第几个in-bucket位置了, 该文件通过内存映射的方式, 来通过操作对应数组mmap_meta_cnt_， 记录每个bucket写入write-ahead-entry个数。
// Meta.
meta_cnt_file_dp_ = open(meta_file_path.c_str(), O_RDWR | O_CREAT, FILE_PRIVILEGE);
ftruncate(meta_cnt_file_dp_, sizeof(uint32_t) * BUCKET_NUM);
mmap_meta_cnt_ = (uint32_t *) mmap(nullptr, sizeof(uint32_t) * (BUCKET_NUM),
PROT_READ | PROT_WRITE, MAP_SHARED, meta_cnt_file_dp_, 0);
memset(mmap_meta_cnt_, 0, sizeof(uint32_t) * (BUCKET_NUM));2.3. Key/Value Buffer 文件
buffer files用来在写入时候进行对每个bucket-entries的buffer (通过内存映射文件得到aligned buffer, 来具备kill-9容错功能). 一个bucket对应相应的key-buffer和value-buffer; 所有的key-buffers从一个key-buffer文件内存映射出来; 同理所有的val-buffers从一个val-buffer文件映射出来。
我们给出一个Value Buffer文件的示例, Key Buffer文件相关的设计与之类似。
// Value Buffers. (To be sliced into BUCKET_NUM slices)
value_buffer_file_dp_ = open(value_buffers_file_path.c_str(), O_RDWR | O_CREAT, FILE_PRIVILEGE);
if (value_buffer_file_dp_ < 0) {
log_info("valbuf err info: %s", strerror(errno));
exit(-1);
}
ftruncate(value_buffer_file_dp_, tmp_buffer_value_file_size);
mmap_value_aligned_buffer_ = (char *) mmap(nullptr, tmp_buffer_value_file_size, \
PROT_READ | PROT_WRITE, MAP_SHARED, value_buffer_file_dp_, 0);
for (int i = 0; i < BUCKET_NUM; i++) {
mmap_value_aligned_buffer_view_[i] =
mmap_value_aligned_buffer_ + VALUE_SIZE * TMP_VALUE_BUFFER_SIZE * i;
}
在设计中, 我们使用了16KB value buffer 和 4KB key buffer, 分别整除VALUE_SIZE和sizeof(uint64_t)。 我们选择较小的buffer是为了让IO尽可能快地均衡地被打出去(不要有很少的线程最后还在打IO以致于打不满), value buffer不选择更小是为了防止sys-cpu过高影响性能，并且我们对磁盘的benchmark显示16KB是一个比较优的值。
3.写入阶段思路
清空page cache占用总时间，傲腾存储iops和throughput都高， 因此使用DirectIO绕过page cache手动管理缓冲和写盘。
写入时候先对bucket加锁，将Key/Value一一对应，分别写入这个bucket对应的key-mmap-buffer和value-mmap-buffer， 在buffer满的时候写入log文件。
4.随机和顺序读取阶段设计思路
随机读取
做最小粒度的同步。奇数和偶数线程同步，来保证64线程间较小的读取进度差别和稳定的queue-depth（24左右）。
尝试了读8KB，并进行缓存置换，命中率不高：2%；这说明通过读更大block-size来优化随机读取不可行。
顺序读取
流水线设计：io部分(io协调者， io线程)，通过set-affinity减少numa结点间的切换；内存读取部分(64threads)同步读一个bucket与下一块bucket的io overlap在一起。
每块buffer为一个读取单位，io协调者通过提交任务给io线程打到合适avgrq-sz和avgqu-sz，从而打满IO throughput，详见io协调者。
流水线使用2块buffer滚动。
在多次全量遍历中，偶数次次遍历重用奇数次的前几块buffer(块数通过程序中的KEEP_REUSE_BUFFER_NUM指定，作为cache)。
5. 容错(K/V Buffer Files Flush)的思路
大体思路: 我们通过ParallelFlushTmp并行flush key, value buffers; 该函数在写入阶段的析构函数调用(如果进行到对应代码), 否则在读取阶段构建index前会调用。
优化: 我们通过ftruncate对应文件长度为0表示所有buckets对应的需要flush的buffers已经Flush出去了, 避免重复的Flush. 相应逻辑在FlushTmpFiles函数中。
由于文章篇幅较长，代码较多，所以小天将部分代码和作者的比赛经验放在下篇分享，后天见哦~
