PolarDB 数据库性能大赛总结

PolarDB 数据库性能大赛总结

几个月前龙先生告诉我有这么个比赛,于是便和龙先生、虎先生一起参加了。结果不算差但还是挺遗憾的,距离前十只差 5 名,不过还是学到了很多东西,以后可能也会用上不少。

下面零零碎碎地讲一下从头开始的思路吧。

题目是什么

首先是官网上写的这个样子:

https://tianchi.aliyun.com/programming/introduction.htm?spm=5176.11165268.5678.1.145c3314rNfUam&raceId=231689

实现一个支持的操作非常简单的 kv 数据库,保证 key 长度为 8 byte,value 长度为 4KB。测评过程通过无数次提交大致确定为:

初赛分为两个阶段:正确性测试和随机读写性能测试

正确性测试:全程只有一个线程负责访问数据库。使用 Open 获取数据库实例,调用 Write 写入 128w 条数据,随后使用 kill -9 杀死这个线程。然后再 Open 一次,读取 64w 次,并检验键值是否匹配。

随机读写性能测试:虽然说是可能有读有写,但实际上也分为两个阶段。第一个阶段只写,写完 6400w 条数据后 delete 掉数据库,然后再第二个阶段再 Open 一次, 完成 6400w 次读。

复赛在初赛的两阶段测试后分别添加了(每个线程)两次全量顺序读。在 Write 之后会再 delete 一次数据库。

从零开始的 kv 数据库比赛

3 个人之前都从来没有接触过这些东西,于是预热赛时了解了一些常见的 kv 数据库实现,看了看 levelDB 的源码,也学习了一下 Log-Structured-Merge Tree 之类的东西。LSM 的设计是相当精妙的,用一部分的写放大换来了从随机写到顺序写的飞跃性提升。具体的文章很多,这里也不想再讲一遍。

所以我们决定,先写一遍 LSM 。所有的 value 全部储存在单独的文件中,数据库里只保存 value 对应的 index。

虽然有现成的大量资源, LSM 本身的复杂度还是不低的,尤其是两种 compaction 的实现,花了不少时间 debug。提交后,我们获得了我们遇到的第一个障碍:

Out of memory

这不对啊,我们从头到尾基本没在内存里存过东西啊,2m 的日志一满就会被 dump 出去,理论上根本没有什么内存占用。

泄露了吗?有可能。于是掏出 valgrind 开始跑,大的泄露倒没找到,也就找到一点零星的加起来没多少的未释放的内存。修了后顺便加上了隔一段时间朝 /proc/self/status 瞅一眼的 log,发现内存占用跟着 compaction 调用一次加几十兆。

这也太坑爹了吧,看了看 compaction 时使用的 std::vector<polar_race::record, std::allocator> ,感觉有点不妙,便换成了 malloc/free 写的 allocator 。本地测试时内存占用稍微下去了一点,而且由于跑的很慢,看上去增加的也很慢,涨了一点信心又交了几发

还是炸。注意到 minor-compaction 的发生相当频繁,遂不再进行 minor-compaction 而直接在 major compaction 的时候 dump 出这些数据(从这里就已经有开始抛弃 LSM 的迹象了)。仍然炸

佛了,全部重写!(其实并没有)。想了想所有日志实际上只有 768m,加上 compaction 导致的写放大一共也不会超过 1g,不如一次性全部分配出去,文件的 dump 就直接使用开启时分配好的内存即可。

然后就跑出了第一个通过的提交:896 秒

第一个 Breakthrough

896 秒是什么概念?读写大概都在 500M/s 的水准,非常慢。64 个线程强行同步成单线程的程序对数据进行写入,当然会慢。龙先生考虑到(通过测试得出)数据的分布非常均匀,于是直接在我们当前的实现上套了一层 Dispatcher

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Dispatcher: public Engine {
ArcDB* db[WORKER_COUNT];

explicit Dispatcher(const std::string& path) {
FileManager::create_dir(path);
for (int i = 0; i < WORKER_COUNT; i++) {
auto db_path = path + "/" + std::to_string(i);
db[i] = new ArcDB(db_path);
}
}

RetCode Write(const PolarString& key, const PolarString& value) override {
auto k = str_to_key(key.data());
auto choice = k / KEY_DIVIDER;
return db[choice]->Write(key, value);
}
// omitted
}

思路很简单,就是分桶,使数据均匀地散落到各个桶中。有 64 个线程在调用 DispatcherWrite ,所以即使阻塞了也只会阻塞当前的桶,不会对其它线程产生很大的影响。这次提交获得了 374 秒的成绩。

在这过后不久我们重构了第一版的代码。针对评测机制,我们 assert 在写之后不会有读操作,所有的数据直接 append 而不需要考虑查找效率问题;在数据库启动时检查数据是否有序,并在这个时候进行排序。这一些常数优化、调参提升到了 329。

第二个 Breakthrough

使用 Dispatcher 确实能够提升很大一部分的效率,但它并没有解决关键性的问题:不必要的阻塞依然存在着。

所以必须在 worker 上做文章。目前每个 worker 使用一个日志文件,所有的写请求过来都需要拿到日志锁完成同步。于是我们可以使用多日志文件轮流储存:根据键分配好对应的初始日志文件,然后试图拿对应的日志锁,没拿到就试下一个。

1
2
3
4
5
6
7
auto addr = index_to_addr[i];
off64_t off = addr.index * VALUE_SIZE;
auto rd_cur = i % VALUE_RD_FILE_COUNT;
while (!read_mutex[addr.cur][rd_cur].try_lock()) {
rd_cur = (rd_cur + 1) % VALUE_RD_FILE_COUNT;
read_mis_times++;
}

效果显著,获得了 245 的成绩,但直到初赛结束,也没有能做出更大的提升,最终成绩为 241.19s / 45名

找到 IO 的极限

初赛最开始的时候实现了 range,然而发现评测并没有调用 range 于是就没有维护了。当时的 range 思路仍然是跟着 levelDB 走的,使用一个文件迭代器,完成多路归并。在本地检查了一下正确性问题之后就提交了,结果超时了(时限是 3600s)。稍微想了一下发现:顺序读部分需要读取的数据量是随机读部分的 128 倍!如果用随机读的速度的话得要 3 个小时,根本扛不住。

稍微分析一下顺序读部分干了什么:64 个线程在做同样的事情,对每个线程的 visitor 而言需要访问 6400w 组数据,总计 256g * 128 = 32t 的数据。然而事实上对于一次 64 线程的全量顺序读,我们只需要从磁盘读取一次,让它们同时访问从磁盘中获取的数据即可。

除去储存所有 record 所需的 768m 和一些其它的零碎的内存开销,我们还有大约 1g 多一点的空间可以用作缓存。一个朴素的想法就是:64 个线程去获取缓存块的名额,获取到的线程负责处理文件 IO,将数据从磁盘转移到内存,在任务处理结束后设置相应的原子量;没能获取的线程把所需的缓存块引用计数加一,并自旋等待工作线程从磁盘获取阶段结束,在 visit 结束后将相应缓存块的引用计数减一,引用计数归 0 时释放这一块缓存并使下一个工作线程获取这一块缓存。当然可能出现“所有的非工作线程还没能完全调用引用计数增加就有线程 visit 结束并使引用计数归 0”的情况,不过考虑到每次 visit 也是相当耗时的操作,这种情况也不一定非常常见

下面是这一段逻辑对应的代码(加了注释),看起来非常的复杂(确实很复杂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
RetCode Range(const PolarString& s_lower, const PolarString& s_upper, Visitor& visitor) override {
int pos_r = 0;
int pos_work = -1;
int pos_free = -1;
_buckets[pos_r].range_acquire();
// total BUCKET_NUM buckets
while (pos_r < BUCKET_NUM) {
if (_buckets[pos_r].range_ready()) { // buffer is ready
_buckets[pos_r].range(visitor);
_buckets[pos_r].range_release(); // decrease ref count
pos_r++; // read next buffer
if (pos_r < BUCKET_NUM) _buckets[pos_r].range_acquire(); // acquire next buffer
} else {
// this thread is not working
if (pos_work == -1) {
// which position this thread can get
pos_work = work_frontier.fetch_add(1);
// the position wait for
pos_free = (int) (pos_work - work_buffer_count);
}
// check buffer ready and free the last one
if (pos_free >= 0 && !_buckets[pos_free % BUCKET_NUM].range_free()) {
range_miss_time++;
continue;
}
// buffer is ready and get work
_buckets[pos_work % BUCKET_NUM].range_work(_value_manager);
if (pos_work % 1000 == 0) {
slog(std::string("a ") + std::to_string(pos_work) + " " + std::to_string(Self::getMemMB()));
}
pos_work = -1;
}
}
return kSucc;
}

在榜上不到 10 个人的情况下这份代码跑出了 468 秒的成绩,排第二,当时感觉拿钱有希望了(差点信了)。

而 0xCC 两个小时写的代码跑了 420 秒。

随后我们又重构了一次。通过 range 开始时一段时间内访问到 range 的线程个数确定引用计数的大小,开启一个单独的工作线程专门负责读取磁盘数据,worker 在读完数据后会设置它自己的引用计数为总线程数,当引用计数归 0 时,worker 释放空间,提交一个信号量 (就是 sem 那一套 API) 唤醒调度线程。调用 range 的 64 个线程会在引用计数因为 worker 结束而改变之前一直自旋。

这次重构没有带来效率提升(其实带来了),但代码可读性明显提高。

review 了一下代码发现龙先生把 worker 线程的 work 调度设为了阻塞形式,然而实际上并不需要;而且我们已经有通过原子量实现的线程同步了,所以在分派任务时根本不需要等待它的返回,直接 std::thread 一把梭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::thread([&] {
db[0].work(refc);
plog("work 0");
}).detach();
std::thread([&] {
db[1].work(refc);
plog("work 1");
}).detach();
for (auto i = 2; i < WORKER_COUNT; i++) {
ValueManager::sem.wait();
CoDB* dbi = db + i;
std::thread([=] {
dbi->work(refc);
plog(std::string("work ") + std::to_string(i));
}).detach();
}

直接跑到了 440 秒

第三个 Breakthrough

使用了 mmap with MAP_POPULATE 代替手动开辟的内存。MAP_POPULATE 这个 flag 会使 mmap 出来的空间通过预读的方式准备好页表。普通的 mmap 分配内存非常快,但是在访问的过程中会频繁的引起缺页异常,而 POPULATE 的空间会在准备时处理好这些问题。虽然启动时会带来一定的效率开销,但整体是省下了后期均摊的缺页异常带来的性能损失。range 时会频繁的读取/写入我们的 buffer 空间,所以这一部分的性能是非常重要的

进一步提升了 read,write 和 range 的效率,使成绩达到了 428 秒。

没有 Breakthrough 了

速度已经开始接近极限,只能一点一点的扣

  1. 启动

我们之前的启动非常耗时,因为读完数据进来之后还要进行排序和分桶。但排序的结果在数据库被杀掉之后就没了。我们可以在几个阶段之间对结果进行排序,并记录下分桶的信息,这样在下一次 open 的时候只需要读取我们上一次 dump 出的元信息而不需要手动进行运算。

  1. 优化内存结构

集中处理所有的大块内存分配,根据测试场景判断当前的分配模式

  1. 一些边角优化

循环结构优化、添加 unlikelylikely 手动提供分支预测信息,fadvise madvise 为操作系统提供文件/内存访问模式,prefetch 优化获取速度等等

本来指望最后一天能再做出一些突破,可测评系统已经繁忙到提交一次需要等待数个小时才能获取反馈的程度了,在无法获取宝贵的评测信息的情况下,再想往前抖一点已经是非常困难的事情了。

最终 419.12 秒,排名 15 / 1653

总结

一些取得成绩的关键

  1. 减少无意义的阻塞
  2. 使用 DIO, pread , POPULATE,mmap 等提升 IO 速度
  3. 并行耗时长的操作,比如排序等
  4. 减少冗余计算,利用好已有的信息
  5. 使自旋线程休眠防止其影响 IO 速度
  6. 针对硬件进行优化
  7. 通过合理的 benchmark 获取理想的硬件性能

或许能改进的地方

  1. 让线程绑定核心: setaffinity
  2. 使用 AVX 等特殊指令集优化 memset 等操作
  3. 优化代码结构(玄学)
  4. 不知道

最后

非常感谢龙先生和虎先生这一个半月的付出,带我打比赛。

也非常感谢阿里云提供的这次机会和一条还没寄到的 T 恤,学到了很多东西,也认识了很多厉害的人。

有好心人问会开源吗,这得问龙先生

得开始找工作了