深入浅出LSM-Tree (1) - 核心原理

引言

当前很多数据库底层数据存储结构都用了LSM-Tree，例如LevelDB、RocksDB、HBase、TiDB、OceanBase等。LSM-Tree到底有啥魅力，下面让我们去揭秘。本系列主要介绍LSM-Tree原理和关键技术点，最后用LSM-Tress 实现一个mini KV数据库。

参考论文

https://www.cs.umb.edu/~poneil/lsmtree.pdf

https://link.springer.com/article/10.1007/s00778-019-00555-y

LSM-Tree是什么

LSM-Tree 名称 Log-Structured Merge-Tree 日志结构合并树，其实这个数据结构的核心重点在于日志结构合并，和tree的关系并不是很大。LSM-Tree 通常没有一种固定死的实现方式，主要是体现在数据存储结构的一种实现思想。LSM-Tree的核心思想将数据按层级组织（内存 + 多级磁盘组件），通过批量合并操作将内存中的新数据逐步刷写到磁盘，以降低随机写磁盘的开销，被广泛应用于写密集型（Write-intensive）的数据库。

LSM-Tree 的历史背景

通常索引结构有两种更新策略：就地更新(In-place)和异地更新(Out-of-place)。就地更新结构（例如 B+ 树）会直接覆盖旧记录以存储新的更新。例如，在上图 中，为了将键 k1 关联的值从 v1 更新为 v4，需要直接修改索引条目 (k1, v1) 以应用此更新。这些结构通常针对读取进行了优化，因为只存储每条记录的最新版本。然而，这种设计会牺牲写入性能，因为更新会产生随机 I/O。此外，索引页可能会因更新和删除而碎片化，从而降低空间利用率。

相比之下，异地更新结构（例如 LSM 树）总是将更新存储到新位置，而不是覆盖旧条目。例如，在上图中，更新 (k1, v4) 被存储到新位置，而不是直接更新旧条目 (k1, v1)。这种设计提高了写入性能，因为它可以利用顺序 I/O 来处理写入操作。它还可以通过不覆盖旧数据来简化恢复过程。然而，这种设计的主要问题是，由于一条记录可能存储在多个位置中的任意一个，因此读取性能会有所损失。此外，这些结构通常需要单独的数据合并（compaction）过程来持续提高存储和查询效率。

LSM-Tree的核心结构设计

LSM-tree 设计由内存和磁盘两层数据结构组合而成。内存中的部分称为MemTable，磁盘中的部分称为SSTable(Sorted String Table)。

MemTable 通常用平衡排序树、跳表(SkipList)、红黑树等有序的数据结构，方便顺序从内存写到磁盘

SSTable 本质是排序好后 appendonly 写到磁盘上的文件

LSM-Tree 的基本操作流程

Memtable我们用SkipList来实现，如果SkipList不熟悉可以先看之前的文章介绍 SkipList

插入操作

LSM-Tress 的插入操作相对简单，直接写到内存表Memtable就行了。如果内存中存在则更新value，

不用关心数据是否在磁盘中存在，如果磁盘中存在以最新的为准，后续的compaction也会做合并

删除操作

LSM-Tree的删除操作不会直接删除数据，而是通过标记位来删除。不管数据存不存在，数据在哪里，都等同于往内存表中插入一条标记删除的记录

更新操作

LSM-Tree 的操作等同于插入操作，如果数据存在内存表中则更新，不用管磁盘数据是否存在

查询操作

LSM-Tree的查询操作会先从内存表查询，如果找到则返回，如果内存表中没有，则会从磁盘中的最上层Level0开始到Leveln往下找，直到找到为止。极端情况下，如果数据不在LSM-Tree中，则需要把整个表扫一遍，这代价是非常大的，可以通过布隆过滤器和稀疏索引来优化，后面会介绍到

总结

LSM-Tree的写操作都是在内存中完成，写效率是非常高。读操作极端情况下会导致全表扫描。有什么办法可以提高查询效率？先思考一下，下文会介绍工业中针对LSM-Tree的读写优化和本文没介绍的compaction。

欢迎关注微信公众号【笑傲码湖】