乐趣区

关于golang:LotusDB-设计与实现1-基本概念

LotusDB 是一个全新的 KV 存储引擎,Github 地址:https://github.com/flower-corp/lotusdb,心愿大家多多反对呀,点个 star 或者参加进来!

LotusDB 是一个基于 LSM Tree 进行设计,并联合 B+ 树劣势的单机 KV 存储引擎,读写性能稳固、疾速。

在传统的 LSM Tree 架构中,增删数据均是追加有序写入到 SST 文件中,雷同的 key 对应的数据可能存在多份,须要通过简单的 compaction 策略来进行空间回收,这同时带来了空间放大和写放大问题。

LSM Tree 在磁盘上保护多级 SSTable 文件,在数据读取时,须要逐层扫描文件来查找指定的数据,最坏状况下须要扫描每一层的 SSTable,读性能不稳固。

和 LSM Tree 绝对应的,另一种常见的数据存储模型是 B+ Tree,B+ 树因为有着很好的适配磁盘页的个性,在数据库存储引擎中广泛应用,例如最为人熟知的 Mysql 的 InnoDB 引擎。

B+ Tree 将数据保护在树最底层叶子节点中,读性能比较稳定,然而数据的插入和更新均是随机 IO 进行写入,导致 B+ Tree 的写性能绝对较低。

咱们晓得,LSM 存储模型诞生于 HDD(机械硬盘)时代,HDD 的随机和程序读写速度差异微小,所以 LSM 的设计最大限度的施展了程序 IO 的劣势,所有的数据先到内存 buffer 里缓存,而后批量有序写入到文件中。然而随着存储硬件的更新迭代,磁盘的随机和程序读写差异变小了,在一些介质中,程序和随机读写甚至没有太大的差异。

LSM Tree 针对程序 IO 的一些设计就会显得过于简单,导致整个零碎难以实现和管制(如果你相熟 rocksdb 的话,就会深有体会)。

自行设计一个零碎的底层存储引擎,比把握一个简单的我的项目要更加容易,呈现了相干的问题也更容易定位和解决,这也是为什么 cockroach 采纳自研的 Pebble 存储引擎代替 rocksdb,而 LotusDB 就是一个这样能够轻易学习和把握的存储引擎,因为它简洁、直观且高效。

LotusDB 的整体架构图如下:

LotusDB 依然保留了 LSM Tree 中的写流程,因为这可能最大限度的保障写入数据的持久性以及写吞吐,所以在磁盘上保护了 WAL 日志,新写入的数据先追加到 WAL 中保证数据不失落,而后再写入到内存中。
内存中保护了多个跳表构造,最新的跳表叫做 active memtable,一个 memtable 写满之后,会变为 immutable memtable,即不可变的 memtable,其不能接管新的写入,并且期待被后盾线程 flush 到磁盘中。

Flush 的时候,数据索引信息会被寄存到 B+ 树中,而 value 会被独自寄存到 Value Log 中,value log 的构造相似于 WAL,数据写入都是采纳日志追加,只不过 value log 会有一个阈值,写满之后会关上一个新的 value log,因而 value log 是存在多个的。

须要留神的是,B+ Tree 应该尽量存储新的存储介质中,例如固态硬盘,因为后面提到过 B+ 树是随机写入,如果应用传统机械硬盘的话,写性能受限制,写放大重大,Flush 可能会是一个瓶颈。

这就是 LotusDB 的整体实现,在这种实现下,咱们来看看根本的数据读写流程是什么样的。
写一个 key/value:后面说过了,和 LSM 模型完全一致,先将 key/value 封装成一条日志追加到 WAL 中,而后将 k/v 写入到内存的 active memtable。
依据 key 读一个 value:先在内存当中的 active memtable 和 immutable memtable 中顺次查找,如果找到间接返回。否则阐明 value 可能在磁盘中,就从 B+ 树获取 key 的索引信息,索引信息是一个二元组 <fid, offset>,标识 value 位于 value log 中具体哪个文件,以及文件中的地位,而后间接依据这个索引信息到 value log 文件中获取 value 即可。

最初再来总结下 LotusDB 架构的长处,简略演绎大略有如下几点:
1、写数据流程和传统 LSM 模型完全一致,保障了程序 IO 的高吞吐,以及数据持久性
2、 读性能相较于原生 LSM 模型更加稳固,读放大升高,因为引入了 B+ 树,得益于 B+ 树稳固的读性能,整体的读取效率会更加可控
3、 齐全去除了 LSM Tree 模型中的多级 SSTable,没有了 SSTable 的保护,并且采纳已有的 B+ 树实现(BoltDB),大大降低了零碎的复杂性
4、Compaction 对存储介质的损耗升高,LotusDB 中只有 value log 存在 Compaction;原生 LSM 不仅 SSTable 须要 Compaction,并且如果进行了 kv 拆散的话,value log 也同样须要 Compaction
5、 读写流程简洁直观,没有 bloom filter、block cache 等


LotusDB Github 地址:https://github.com/flower-corp/lotusdb

退出移动版