LSM 树:结构及其原理浅析(LevelDB)

LSM 介绍

LSM (Log Structured-Merge Tree)是一种“攒攒再写”的结构,相比于 B+tree 写入性能更好,读取性能更烂。前人之述备矣,我们直接进入正题。主要以 LevelDB 为例。

操作机制

在讲内存结构之前,说一下操作机制。虽然头一次看会有点晕,但是你必须前后对照,两个一起看,不然看不清楚。

写入

注意:所有结构其内部的数据都是有序的

  1. 写入时,先写日志(WAL)

  2. 然后写 MemTable

    1. 如果 MemTable 达到阈值,则转换为 Immutable MemTable,并准备转移到磁盘成为 SSTable

    2. 如果 SSTable 过多,则合并为更简练的 SSTable

由于只进行一个日志写和 MemTable 写就返回给用户,写性能比 InnoDB 好得多。

预写式日志(Write-ahead logging,WAL):即在所有操作提交前写日志。典型的如 InnoDB 用日志文件组存放 Checkpoint 和 redo log,而 LevelDB 只是简单地 Append 到 Log 文件日志。这是 LSM 树数据库防止断电丢数的最主要机制。

删除

删除实际上就是追加标记。也就是说,并不会在记录原本的位置标记删除,而是用一条新的日志标记删除

更新

更新实际上还是追加,只不过新的值更靠后。

读取

读取会以 Key=UserKey+Seq 作为索引,依次从 MemTable、Immutable MemTable、SSTable 从后往前查找,第一次找到(无论是找到值还是删除标记)就返回。

另外需要一提的是,程序并不会傻傻地顺序回溯,实际上每个 SSTable 和 MemTable 一样都是有序结构。因此可以利用二分加速查询索引。

然而,最糟糕的情况下,这个 Key 根本不存在,那么无论你 SSTable 有多大都会全扫一遍。这是灾难性的,被称为“读放大”,因此 Level DB 通过这几种方式减轻伤害:

  1. Cache

    1. TableCache:从 SSTable 到对应的索引块和元数据块的映射。

    2. BlockCache:从 SSTable 文件号到 TableAndFile 对象的映射。缓存解压后的数据块。

    3. 原理都是 LRU,即双链表配合哈希表。LevelDB 的 LRU 对多线程做了优化,可以分片上锁。

  2. BloomFilter:

    1. 引入:常用位图实现。传统位图的思路是,存在,就给对应位置标 1. 但这样无法适应大数据,会导致巨大的位图。

    2. 介绍:BloomFilter 利用哈希函数,初始为 0,SSTable 插入值后,对值进行散列然后将 Bloom 数组对应位置(超长的取余数)标 1. 从而实现:有限空间下大概率猜中存不存在

    3. 假阳性问题:明明不存在,却以为存在。

  3. 压缩合并

我记得自己前几个月去面 PingCAP,面试官让我半小时写一个细粒度锁的线程安全 LRU 缓存。最后毫无悬念挂了。回来一看,原来就是 LevelDB 实现的这种,核心就是LRU 缓存分片,从而可以对局部加锁。当然即便知道原理,我也起码得一两天才能写出来。可能还有更简洁的实现,欢迎留言。

顺带提一下:除了读放大,还有写放大,就是说为了向硬盘写入 512B,硬盘内部可能实际上得先读出 4KB 然后和写入的新数据合并,再把这 4KB 写入。导致实际上写入的数据量远大于我们所以为的。

另外还有空间放大,主要是 LSM 树通过追加标记状态迁移,因此会残存大量失效的历史状态,造成空间浪费。

内部:压缩

从抽象的角度,甚至可以把写入和删除都看作是对 K,V 压栈,而读取就是从栈顶向历史回溯,找到第一个匹配K,V

因此这种“屏蔽”效应会导致可能有大量的历史失效,这些历史数据会被后台线程在压缩(合并过程)清理。每次进行 Compaction,Level DB 就会创建一个新版本

为了性能的考虑,当文件较大时,可能真实行记录不会和 Key 存放在一起,而存放在一起的是 Offset,然后根据 Offset 再去精准读取具体的记录数据。

错误恢复

错误恢复时:

  1. 读取CURRENT文件,获取最新的 MANIFEST 文件名,从而找到最新 MANIFEST 文件。

  2. 里面的日志是 VersionEdit 格式,使用 VersionEdit::DecodeFrom 解析,然后按照日志创建 version 并恢复(Finalize)

  3. 恢复的过程就是按日志写 SSTable。

存储结构

内存结构

内存中有 MemTable 和 Immutable MemTable。

MemTable

MemTable 是 KV 表。因此可以用 AVL,B 树,RB 树,跳表实现。LevelDB、elasticsearch 用的就是跳表。反正对外就暴露哈希表接口。

跳表:跳表是一种非常简单的链状二分搜索结构,期望时间复杂度 $O(\log n)$ ,最坏 $O(n)$

Immutable Memtable

Immutable Memtable 是定格后的 MemTable。定格,是因为和 MemTable 内容完全一样,只不过不能再写入了,但是内容一样不代表结构一样,Immutable Memtable 由于要落盘,会采用更适合顺序读的结构存放。

它也是跳表结构。

磁盘结构

Log

日志文件。通过追加写入,类似 InnoDB 的 Redolog。

当 Log 超过 1MB 时,会创建新的 MemTable 以及新的 Log 文件。而旧的 MemTable 变成不可变,被后台线程 Dump 到 SSTable 文件。每条日志一个 LSN(Sequence),单调递增。

SSTable

SSTable(sort-string table,排序字节串表)是磁盘中的结构。具体来说并不是一个文件,而是一系列有层级的文件。具体来说,LevelDB 的 SSTable 从 Level 0 到 Level N 分为多层。每一层包含多个 SST 文件。

文件内数据有序(并且不是树,而是线性排列的,非常直白的 K,V 序列)。

实际上论文没有规定你怎么实现的有序,此处以 LevelDB 为例。

Level 0 SST 由Immutable Dump 产生。>= Level 1 的 SST 通过归并顺序写产生。没有真正的删除,只有标记删除。

如果一个 Level 的大小超过限制,就会合并到 Next Level,一般来说 Level 越高大小上界越高。

注:此处的文件内记录的顺序是主键顺序,不是时间顺序。

需要注意的是,Level 0 的 SSTable 文件,其 Key 范围可能有交集(比如一个是 ad,另一个是 cg),所以需要合并。由于 Level 0 到 Level 1 的过程中完成了合并,对于 Level > 0 的不会重合。

为什么会重合呢?

这是因为 Level DB 有小压缩(minor compaction)和大压缩(major compaction)之分。

小压缩:遍历 Immutable SkipList,从小到大排列,得到 Level 0 SSTable。而各次导出自然会可能重叠。

大压缩:如果剩余层级也有重叠,查找起来必然极其低效,所以会进行消除重叠的压缩合并。如果你刷题经验丰富,会见过“合并K个有序链表”这种题,实际上就和大压缩很像。就是针对有重叠线性文件的多路归并排序。

Manifset-[:num:]

这是元数据文件。记录 Level DB 的元信息,例如 Comparator,SSTable 的层级信息,最小最大记录 Key。

每次 Level DB 启动,会产生一个 CURRENT 文件,表示使用中的 Manifest.

Manifest 格式和 Log 一致,记录了启动以来的所有状态迁移。以 VersionEdit 形式写入

参考

CppGuide/articles/leveldb源码分析 at master · balloonwj/CppGuide

庖丁解LevelDB之概览 | CatKang的博客

LevelDB设计与实现_AndersCloud的博客-CSDN博客

布隆过滤器 — leveldb-handbook 文档

对论文感兴趣可以看:【Paper笔记】The Log structured Merge-Tree(LSM-Tree) ·