我在上篇文章 Apache Pulsar 的架构设计 中介绍了 Pulsar 存算拆散的架构，其中 broker 只负责计算，由 BookKeeper 负责底层的存储，我还画了这样一张图阐明 BookKeeper 读写拆散的设计：

然而再深究上来，memtable具体是以怎么的格局长久化到磁盘上的呢？又是用什么算法高效查找一条音讯的呢？

通过学习相干材料，我发现 Apache BookKeeper 底层存储引擎用的是 Facebook 开源的 RocksDB，而 RocksDB 又是基于 Google 开源的 LevelDB 革新的，而 LevelDB 的外围是一个叫做 LSM 树（Log Structured Merge Tree）的构造。

LevelDB 整个库的代码只有几百 KB，所以我去钻研了 LSM 树的代码实现，总结了这篇文章，带你理解 LSM 树的设计原理。

什么是 LSM 树呢？如果说到 B+ 树大家应该不生疏，像 MySQL 这样的关系型数据库底层个别用 B+ 树结构来存储数据。LSM 树其实就是另一种存储数据的构造，常见于日志存储系统中。

首先，咱们先来聊聊存储系统。

正如前文 学习数据结构和算法的框架思维 所说，所有数据结构从根本上讲都是增删查改，但在具体实现上，磁盘数据结构和内存数据结构会有比拟大的差别。

内存数据结构你间接 new 一个进去就行了，不必关怀这个构造在内存中是如何布局的，这些都由操作系统和编程语言代劳了。

但磁盘就不一样，思考到计磁盘读取的操作效率绝对比拟低，且每次只能读取固定大小的磁盘数据，你要本人设计数据的存储布局，规定每个字节存什么信息，而后基于你设计的存储布局实现增删查改的 API，比拟干燥琐碎。

比如说，学过 MySQL 的话应该比拟相熟 B+ 树结构，但你必定不容易看懂 B+ 树的代码。因为 B+ 树是磁盘数据结构，尽管原理上能够了解为 BST 的加强版，但思考到数据文件格式的设计，真正的代码实现非常复杂。

所以一般来说，咱们理解磁盘数据结构的原理，理解各个操作的工夫复杂度就能够了，没必要特地纠结它的具体实现。

数据可变 vs 数据不可变

存储构造能够粗略分为两类：数据可变的和数据不可变的。所谓可变，就是说曾经插入的数据还能够原地进行批改，不可变就是说曾经插入的数据就不能再批改了。

B 树是数据可变的代表构造（B+ 树等衍生构造都归为 B 树一族）。你就想想 BST 吧，数据存在节点上，咱们能够随便插入、删除、批改 BST 中的节点。

B 树的实践增删查改性能和 BST 一样都是 logN，但 B 树的理论写入效率并不是特地高：

一方面是因为 B 树须要决裂合并等操作保障整棵树的平衡性，这外面波及很多磁盘随机读写的操作，性能会比拟差；另一方面思考到并发场景，批改 B 树结构时须要比较复杂的锁机制保障并发平安，也会肯定水平影响效率。

综上，B 树的难点在于平衡性保护和并发管制，个别用在读多写少的场景。

LSM 树是数据不可变的代表构造。你只能在尾部追加新数据，不能批改之前曾经插入的数据。

如果不能批改以前的数据，是不是就不能提供删、查、改的操作 API 呢？其实是能够的。

咱们只须要提供set(key, val)和get(key)两个 API 即可。查问操作靠get(key)，增删改操作都能够由set(key, val)实现：

如果set的key不存在就是新增键值对，如果曾经存在，就是更新键值对；如果把val设置为一个非凡值（比方 null）就能够代表key被删掉了（墓碑机制）。

那么我对某个键key做了一系列操作后，我只有找到最近一次的操作，就能晓得这个键以后的值是多少了。

从磁盘的角度来说，在尾部追加的写入效率十分高，因为不须要像 B 树那样保护简单的树形构造嘛。但代价就是，查找效率必定比拟低，因为只能通过线性遍历去查找操作记录。

前面我会讲讲真正的 LSM 树如何针对读场景进行优化，但再怎么优化，必定也达不到 B 树的读取效率。

同时，LSM 树还有一个显著弊病就是存在空间放大。在 B 树中一个键值对就占用一个节点，我更新这个键 100 次，它还是只占用一个节点。但在 LSM 树中，如果我更新一个键 100 次，就相当于写入了 100 条数据，会耗费更多空间。

前面会讲到，这个问题的解决方案是压实（compact），把操作序列中生效的历史操作打消掉，只保留最近的操作记录。

综上，LSM 树的难点在于 compact 操作和读取数据时的效率优化，个别用在写多读少的场景。

有序 vs 无序

能够说，存储构造的有序水平间接决定了该类构造的读写性能下限。有序度越高，读性能越强，但相应的，保护有序性的老本也越高，写入性能也就会越差。

你看 B 树，作为 BST 的加强版，实际上是保护了所有数据的有序性，读取性能必然腾飞，但写入性能你也别抱太大心愿。

LSM 树不可能向 B 树那样保护所有数据的有序性，但能够保护部分数据的有序性，从而肯定水平晋升读性能。

LSM 树的设计

就我的了解，LSM 树其实不是一种数据结构，而是一种存储计划。这外面波及三个重要的数据组件：memtable，log，SSTable，正如我在 Apache Pulsar 的架构设计 中画的这幅图：

其中Journal就是log，Entry Log就是若干SSTable的汇合，叫法不同罢了。

memtable是红黑树或者跳表这样的有序内存数据结构，起到缓存和排序的作用，把新写入的数据依照键的大小进行排序。当memtable达到肯定大小之后，会被转化成SSTable格局刷入磁盘长久化存储。

SSTable（Sorted String Table）说白了就是一个非凡格局的文件，其中的数据依照键的大小排列，你能够把它类比成一个有序数组。而 LSM 树，说白了就是若干SSTable的汇合。

log文件记录操作日志，在数据写入memtable的同时也会刷盘写入到log文件，作用是数据恢复。比方在memtable中的数据还没转化成SSTable长久化到磁盘时，如果忽然断电，那么memtable外面的数据都会失落，但有log文件在，就能够复原这些数据。当然，等memtable中的数据胜利转化成SSTable落盘之后，log文件中对应的操作日志就没必要存在了，能够被删除。

LSM 树的set写入过程并不简单：写入log和memtable，最初转化成一个SSTable长久化到磁盘就行了。

最要害的应该是读取和 compact 的过程：SSTable要如何组织，能力疾速get到一个key对应的val呢？如何定期对所有 SSTable 做 compact 瘦身呢？

其实有多种计划，其中比拟罕用的计划是依照层级组织SSTable：

图中每个绿色方块代表一个SSTable，若干个SSTable形成一层，总共有若干层，每层可能包容的SSTable数量下限顺次递增。

新刷入的SSTable在第 0 层，如果某一层的SSTable个数超过下限，则会触发 compact 操作，依照SSTable的键区间从该层和下一层选出若干SSTable合并成一个更大的SSTable，挪动下一层：

每个SSTable就好比一个有序数组/链表，多个SSTable的合并就是前文 链表双指针技巧汇总 中合并多个有序链表的逻辑。

这样，越靠下层的数据越新，越靠上层的数据越旧，且算法保障同一层的若干SSTable的key不存在重叠：

那么假如给一个指标键key27，咱们只须要从上到下遍历层，并在每一层中应用 二分查找算法 找到键区间蕴含key27的SSTable，而后用布隆过滤器疾速判断一下key27是否存在这个SSTable中。

如果存在，因为SSTable中的键也是有序的，能够再次使用 二分查找算法 找到键对应的值。

这样，借助 LSM 树的层级构造和SSTable的有序性，就能利用二分搜寻晋升查找效率，防止线性查找键值对。

以上就是本文的全部内容，如果你对 LSM 树的更多实现细节感兴趣，欢送和我探讨。举荐一些学习材料：

LevelDB 的代码仓库：https://github.com/google/lev...

RocksDB 的 wiki：https://github.com/facebook/r...

《数据库系统底细》《精通 LevelDB》这两本书也不错。

更多高质量干货文章，请关注我的微信公众号：labuladong