TiDB Hackathon 项目白皮书—LotusDB
团队成员
roseduan:就职于哔哩哔哩分布式存储团队,开源爱好者,开源项目 rosedb、lotusdb 开发者,分布式存储发烧友
南风:开源项目 lotusdb 开发者,北京大学研究生在读,喜欢学习和 coding,对数据库开发很感兴趣,期待大家共同进步
项目介绍
LotusDB 是一个 Go 语言实现的单机 kv 存储引擎,兼备 LSM 和 B+ Tree 的优点,读写速度快、读放大和空间放大极低。
我们希望提供一个强有力的存储引擎,使 lotusdb 成为 TiDB 中 Pebble 的替代品,以及 TiKV 中除了 RocksDB 的新选择。
背景 &动机
在目前的单机存储引擎产品中,LSM Tree 派系的产品独秀一枝,其中以 RocksDB 最为流行,应用最为广泛。在顺序 IO 的保证下,写性能较高,但由于存在多级 SSTable,查询的性能会受到影响。并且追加写的特征,虽然最大限度的发挥了顺序 IO 的优势,但也随之带来了严重的读写放大问题。我们可以认为 LSM 是 Write Friendly 的。
与 LSM Tree 对应的常见的存储模型是 B+ 树,它的特点是原地更新,不会存在 compaction,数据全部存储在了 B+ 树叶子节点当中,读性能稳定。我们可以认为 B+ 树是 Read Friendly 的。
基于以上思路,我们想结合 LSM 和 B+ Tree 的优势,尽量降低读写放大、空间放大问题,以及减少 compaction 带来的 CPU 和磁盘消耗。
况且,在实际的生产环境中,自己维护一个可控、性能优异、简洁的存储引擎,比掌握一个庞大的开源项目(RocksDB)更加可靠,出现了问题更加容易定位和解决,例如 cockroachdb 使用自研的 Pebble 替换掉了 RocksDB,这有助于 TiDB 这样的数据库产品进行快速迭代更新。
项目设计
我们的设计源于两篇 USENIX 论文,分别是: USENIX FAST`19 中的 SLM-DB 和 USENIX FAST`16 中的 Wisckey。
LotusDB 的设计细节如下:
1、仍然像 LSM 那样,维护一个 WAL 日志,以及内存 MemTable 和 Immutable MemTable,对于写请求,和 LSM 完全一致,先写 WAL 日志,再更新 MemTable。
2、MemTable 写满之后,需要 Flush 到磁盘当中,这里和 LSM 处理不一样:我们将 Flush 到磁盘中的数据放到 B+ Tree 当中。为了降低 B+ Tree 带来的写放大,我们采取了两个方案:
写入 B+ Tree 的数据尽量采取批次 Flush,避免多次随机 IO 写入
B+ Tree 只存储索引和小 value 信息,对于大 value,我们采用 kv 分离的方式,将 value 单独存储在日志中
3、对于读请求,流程是这样的:内存 MemTable -> 内存 Immutable MemTable -> 磁盘 B+ Tree -> Value Log。
在这种设计下,我们总结出如下优点:
对于用户的写请求(写 WAL + MemTable),仍然是 append only 的方式,因此是顺序 IO,Throughput 得到保证,延续了 LSM 特有的写性能优势
读请求,先读内存中的 MemTable 和 Immutable MemTable,再读磁盘中的 B+ Tree 和 Value Log,由于 B+ Tree 有稳定的读性能,因此读放大降低。并且得益于 B+ Tree 有序的数据组织方式,范围扫描数据非常的高效
除了 value log,其他组件无需进行 compact,虽说 B+ Tree 仍然存在一定的空间浪费,但由于是原地更新,无效的数据比 LSM 少很多,空间放大降低。
基于以上描述,LotusDB 的架构设计图如下:
维护的基本组件如下:
WAL:预写日志,预防内存崩溃
MemTable:内存中的数据结构(一般为跳表),设定一个阈值,写满后关闭
Immutable MemTable:不可变的 MemTable,等待被后台线程 Flush 到磁盘当中
bolt:磁盘索引数据管理,我们使用了 BoltDB,采用 B+ 树模型。如果 value 的大小没超过设置的阈值,则 value 也存放到 B+ 树中
Value Log:追加写 value 日志,用于 kv 分离,如果超过了设定的 value 大小阈值,则会将 value 存放到日志中
功能模块
在本次 Hackathon 中,我们预计开发的基本功能如下:
KV 整体管理,对外接口
Column Family 支持
Memtable
WAL 日志
磁盘数据管理(B+ 树)
Value Log
ps. 后续会加上更加丰富的功能,例如事务、MemTable 的多种数据结构选择、Value Log Compaction 等。
考虑到 TiKV 是基于 rust 进行开发的,如果我们在 Go 语言版本的 LotusDB 中验证方案可行的话,后续会基于 rust 重新构建,让 TiKV 可以无语言转换开销接入 LotusDB。
测试用例
测试结果是 Hackathon 的重要部分,因此我们主要的测试 case 如下。
选择的竞品:
Badger
Pebble
BoltDB
RocksDB
测试的主要 case:
1、放大问题
读放大
写放大
空间放大
2、延迟问题
随机读延迟
顺序读延迟
随机写延迟
顺序写延迟
针对不同的 value size 进行测试:1kb、4kb、16kb、64kb、128kb
大 value:1mb、2mb、4mb
3、吞吐问题
4、资源消耗问题
CPU 使用率
内存使用率
磁盘空间
5、YCSB 工具测试:
版权声明: 本文为 InfoQ 作者【roseduan】的原创文章。
原文链接:【http://xie.infoq.cn/article/1dce30ddb054ba123a072ae6b】。文章转载请联系作者。
评论