MiniLSM概览

MiniLSM源码阅读笔记（一）

背景

迟sir的教学性质的LSM+Rust项目：

• 项目链接：https://github.com/skyzh/mini-lsm
• 教程文档：https://skyzh.github.io/mini-lsm

总体架构

LSM存储引擎一般包括三个部分：

• wal(write-ahead log)：预写日志文件；
• sstable(static string table)：磁盘中分层有序key-value对文件；
• memtable/immutable memtable(后文简称immutable)：内存中有序key-value对结构。

存储引擎一般会提供一下接口：

• Put(key, value)：数据添加或修改；
• Delete(key)：数据删除；
• Get(key)：数据单点查询；
• Scan(range)：数据范围查询；
• Txn()：事务操作。

写流程

写操作主要包括以下四步：

1. 预写日志，将修改保存至key-value对保存至磁盘中的wal中；
2. 将key-value写入memtable，到这一步用户线程操作结束；
3. （后台flush线程）当mem-table满了之后将其冻结成immutable mem-table，然后写入磁盘中的SST中；
4. （后台compact线程）当某一层SST满了之后进行压缩合并至下一层的sstable，以保持LSM-Tree的数据结构。

写操作包括修改和删除操作，其中删除操作实际上就是value为空的修改操作。

读流程

读操作主要包括以下两步：

1. 按照从新到旧的顺序在memtable/immutable中检索；
2. 没找到的话会在磁盘中LSM-Tree的每一层sstable进行检索。

查询操作包括单点查询和范围查询，范围查询的关键是通过单点查询获取其起始边界的位置，然后再该起始点顺序访问。

上述流程只是简单的概括介绍，由于使用了多版本机制实际的读写流程要复杂一些。