一个自制简易数据库 KxDB

背景

启发自一位富裕的女同事推荐的 CMU-15-445: CMU 的数据库系统课程,于是改头换脸地实现。

设计初衷:

  1. 实现高性能的存储引擎,减少内存复制延迟,以及实现更深入的 I/O 性能优化,
  2. 实现查询引擎,希望基于 KV 实现出复杂的查询优化场景,
  3. 使用 Lustre 类似的并行文件系统,并发对文件块进行查询(解决 LSM 树过分依赖 Compaction 来减少随机 I/O),
  4. 最终实现分布式,这是个大坑。

存储层框架

LSM 树

在写入时,LSM 树假设了磁盘文件数据的写入是有序的,如果输入数据无序,则会使用内存的有序数据结构,如跳表、红黑树(本设计采用红黑树),在一定量后溢写到磁盘。溢写发生时,对有序数据建立类似 B+ 树的一维空间索引,由于此时输入数据有序,索引的建立也是顺顺利利,不像 B+ 树添加/删除数据时候还需要覆盖索引改动的数据块 。

但有一个不好处理(不太优雅)的点,客户端 Scan Memstore 的红黑树时,是有状态的(也就是每次遍历一点点,然后再从上次遍历的数据再往后遍历),这需要遍历时候至少需要分阶段上锁或者无锁,而不能一直锁住直至所有遍历完成,但写入 Memstore 时,红黑树的结构可能一直在变更,所以查询上次进度需要重新从根开始计算,并且可能需要分阶段上锁,每遍历一个阶段的数据,上锁然后复制数据出来返回给客户端。

在读取时,由于文件内部有序,直接使用多路归并排序,也就是用一个二叉堆拾取数据即可。

Buffer Pool / Block Cache

采用朴素的 LRU,但是由于在 C++ 上实现,需要手动释放内存,因此需要考虑标记 LRU Cache 的数据块是否可释放,evict 驱逐时候把未能释放的块放到待 GC 集合保留,当数据块再次被使用时,可直接拉回 LRU Cache 中,而如果数据块未被再次使用并触发了释放操作,数据块将释放并从待 GC 集合中删除。

这样可避免同一份数据,被各种操作复制多次使用。

Bloom Filter

在 256KB 块上对 131072(128K) 个 rowkeys 进行 BKDRHash + DEKHash + FNVHash + APHash + JSHash 哈希取样,测试结果准确率在 99.85% 左右。

但 Bloom Filter 目前只针对点查有效,范围查就凉了,未来可以考虑优化(配合线段树区间查询?但似乎作用不大);还有它的数学概率分析公式实在没搞懂,挖坑日后再研究。

WAL 与 MVVC

暂未实现,但并不复杂,日后待更吧。

实现代码

基础实现:https://github.com/akiasprin/KxDB

参考资料

  1. https://www.jianshu.com/nb/36265841
  2. https://www.bilibili.com/video/av39731185?from=search&amp%3Bseid=15982257803189242166

2 Replies to “一个自制简易数据库 KxDB”

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注