TaurusDB 挑战赛系列六:优胜奖 wangkai 作品解析

阅读数:33 2019 年 12 月 16 日 15:53

TaurusDB挑战赛系列六:优胜奖wangkai作品解析

评测程序分为 2 个阶段

正确性评测

此阶段评测程序会并发写入随机数据(key 8B、value4KB),写入数据过程中进行任意次进程意外退出测试,引擎需要保证异常中止不影响已经写入的数据正确性。

异常中止后,重启引擎,验证已经写入数据正确性和完整性,并继续写入数据,重复此过程直至数据写入完毕。

只有通过此阶段测试才会进入下一阶段测试。

性能评测

随机写入:16 个线程并发随机写入,每个线程使用 Set 各写 400 万次随机数据(key 8B、value4KB)。

顺序读取:16 个线程并发按照写入顺序逐一读取,每个线程各使用 Get 读取 400 万次随机数据。

热点读取:16 个线程并发读取,每个线程按照写入顺序热点分区,随机读取 400 万次数据,读取范围覆盖全部写入数据。热点的逻辑为:按照数据的写入顺序按 10MB 数据粒度分区,分区逆序推进,在每个 10MB 数据分区内随机读取,随机读取次数会增加约 10%。

评测环境

计算节点:内存占用不得超过 4G(CPP), 5G(JAVA),不得写入和读取磁盘空间。

存储节点:内存占用不得超过 2G(C++),3G(JAVA),磁盘占用不得超过 320G。

注:后台将 CPU 统一限制为 16 核。

语言限定
CPP & Java,一起排名

赛题分析

拿到赛题后首先我们对赛题已知条件做下分析:

  • 数据总量为 4M16(64M) 条数据
    Key 数据总量为 64M
    8(B),索引可以完全加载到内存

  • 定长 Key(8B) 和 Value(4KB)
    极大简化索引构建和写入缓存设计

  • 读取分为顺序和逆序遍历 (10M 内随机)
    可以考虑使用 LRU 作为缓存策略

  • kill -9 保证数据不丢
    需使用 mmap 保证数据最终落盘

  • 因为我们比系统更了解程序的缓存策略
    读写考虑使用 DirectIO+ 自管理缓存

计算存储分离
可把存储节点当作一块磁盘对外提供 read, write 接口,把索引构建及索引查找放到计算节点

因为 DB 是分布式的

应考虑使用大块网络传输来减少 rtt 带来的性能损耗可以看出此次大赛的核心考察点是计算存储分离,因为计算量不大,存储介质性能又非常强悍,程序的瓶颈可能是在网络层面,如何高效利用网络是本次比赛重点思考内容。

程序设计

1 功能设计

首先要考虑的是功能评测,即保证 kill -9 数据不丢,因为一个程序只有功能正确才能谈性能,保证 kill-9 数据不丢有两种方式,第一种是来一条数据写一次盘,每条数据都即时落盘,这个方式虽然可以保证数据不丢,但是性能堪忧,好在操作系统给我们提供了另一种方式 mmap(memory mapping),通过 mmap 可以将文件直接映射到 user 内存区,user 可以直接操作这块内存,程序可以通过主动(force)或者被动(程序结束或崩溃)方式将内存中的数据持久到磁盘,这个过程不经过 kernel 内存区,省去一次内存拷贝,同时也保证了数据安全。

保证了存储节点数据不丢后下面要考虑在有网络传输的情况下数据不丢,如果允许数据丢失则可以使用异步 io 方式传输数据,但是要保证数据不丢则计算机点需要一直阻塞直到存储节点数据落盘并返回 ack 后计算节点 set 方法才能返回,这样网络模型为 PING/PONG 模型。

2 文件分布设计

因为程序是多实例数据库,实例之间互不干扰,这里没有对数据进行分片操作,其实换一个角度看我们可以把每个实例看作一个数据库分片,因为分片的目的是为了让分片之间互不干扰,提高程序并行能力,每个实例 (分片) 内的写操作都比较简单,采用追加写的方式。

每个实例包含 3 个文件:
MergeIO(mmap):merge io
索引文件 (mmap):Key 实际存储文件
数据文件:Value 实际存储文件

TaurusDB挑战赛系列六:优胜奖wangkai作品解析

写入 Value 时先写入 MergeIO 文件,Merge 满后批量写入数据文件,即使程序被 kill,也可以从 MergeIO 文件恢复 Value 数据。

这里感谢一下徐靖峰 (岛风) 同学开源的 kdio(java 操作 DirectIO 的库)

3 索引设计

数组二分查找:构建索引时需要排序,单点查询对 cpu 分支预测不友好,但是方便进行范围
LongIntMap(开放寻址法):可以动态构建索引,单点查询可快速定位(key 冲突量不大时),难以范围查询
因为这里考虑只有单点 get 没有范围查询,所以用了 LongIntMap

4 读取设计

读取采用 LRU 算法对数据进行缓存读取,每个 LRU Item 包含 4M Value 数据 (1K 个 Value,参数可调) 每个实例包含 14 个 LRUItem,包含 4M(总消息数)/1K 个空 Item,比如说通过 Key 找到 Index 为 1,对 1 取模得到缓存位置 0,因为缓存已存在则直接使用 item.get(), 如果 Index 为 1024,因为缓存不存在,则根据缓存最后访问时间找到需要失效的缓存,通过 read 方法从存储节点读取该缓存的内容,然后 get 出结果。

TaurusDB挑战赛系列六:优胜奖wangkai作品解析
5 网络传输设计

存储节点:存储节点采用 Epoll EventLoop 模式,节点启动 16 条线程,计算节点与存储节点 tcp 连接均匀分布在 16 条线程上,后面数据交互均在固定线程完成,充分利用多核优势。

计算节点:计算节点采用 bio 方式与存储节点建立连接,计算节点与存储节点交互均采用 req/res 阻塞模式交互。计算节点从存储节点 read 数据时,存储节点 dio 读取的数据直接使用 ByteBuf.wrap,没有内存拷贝 (程序层面),直接发送给计算节点。

连接建立后开启 tcp_nodelay 以减少网络延迟。

在比赛结束最后一天之前计算节点一直用的 nio 开发,写入耗时始终在 719 秒往上,因为一直觉得虽然 nio 在发送接收时与 set/get 线程有 cpu 切换,但是这些切换耗时与网络 rtt 相比应该不算什么,可事实总是在啪啪啪打脸,最后一天(其实也就写好两三天的样子,java 环境最后几天才好,(/□ ))把 nio 改写成 bio 传输,写入时间从 725 降到 560 左右(不确定是否是因为 cpu 切换导致),总结一下就是不能搞经验主义,一定要 benchmark everything。

可探索的改进

一般情况下我们使用 nio 都是将其 fd 绑定到某个 event loop 上,该 event loop 监听该 fd 的事件,这里其实我们可以改变 nio 使用方式,在 set/get 当前线程监听 fd 事件来读写数据,由 set/get 线程充当 event loop,可能会有一个不错的提升。

感想

第一次参加数据库相关的比赛,收获颇多,对数据库相关知识有了初步的了解,也学到了其他选手不错的分享,同时也非常感谢举办方举办这次比赛,给选手提供一个展示和学习的平台,预祝比赛越办越好。

本文转载自 HW 云数据库公众号。

原文链接: https://mp.weixin.qq.com/s/msuvyEjIVsqa6I8PbPZpZQ

评论

发布