存储系统中的算法：LSM树设计原理
我在上篇文章 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 树其实就是另一种存储数据的结构，常见于日志存储系统中。
首先，我们先来聊聊存储系统。
内存数据结构 vs 磁盘数据结构
正如前文 学习数据结构和算法的框架思维 所说，一切数据结构从根本上讲都是增删查改，但在具体实现上，磁盘数据结构和内存数据结构会有比较大的差异。
内存数据结构你直接 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：
https://github.com/facebook/rocksdb/wiki/leveled-compaction
图中每个绿色方块代表一个sstable，若干个sstable构成一层，总共有若干层，每层能够容纳的sstable数量上限依次递增。
新刷入的sstable在第 0 层，如果某一层的sstable个数超过上限，则会触发 compact 操作，从该层选出若干sstable合并成一个更大的sstable，移动下一层：
https://github.com/facebook/rocksdb/wiki/leveled-compaction
每个sstable就好比一个有序数组/链表，多个sstable的合并就是前文 链表双指针技巧汇总 中合并多个有序链表的逻辑。
这样，越靠上层的数据越新，越靠下层的数据越旧，且算法保证同一层的若干sstable的key不存在重叠：
https://github.com/facebook/rocksdb/wiki/leveled-compaction
那么假设给一个目标键key27，我们只需要从上到下遍历层，并在每一层中使用 二分查找算法 找到键区间包含key27的sstable，然后用布隆过滤器快速判断一下key27是否不存在这个sstable中。如果可能存在，由于sstable中的键也是有序的，可以再次运用 二分查找算法 在sstable中找到键对应的值。
这样，借助 lsm 树的层级结构和sstable的有序性，就能利用二分搜索提升查找效率，避免线性查找键值对。
以上就是本文的全部内容，lsm 树的设计思路比较易于理解，但实现起来还有不少细节，如果你对具体实现感兴趣，我可以推荐一些学习资料：
leveldb 的代码仓库：
https://github.com/google/leveldb/issues
rocksdb 的 wiki：
https://github.com/facebook/rocksdb/wiki
区块链与物联网之间会发生什么
监视器技术固定刷新率和gsync选择哪个 监视器刷新率越高越好吗
超高速相机在科研界的地位有多高
北一半导体工厂和分立器件加工项目落户牡丹江穆棱经济开发区
典型的DRC案例介绍
存储系统中的算法：LSM树设计原理
瑞昱网通行业芯片应用简介
LHAASO 如何探测暗物质?
赋能演艺新高度 Vivitek(丽讯) DU9900Z工程投影机重磅亮相
怎样制作Arduino天线
完全自主型仿人机器人成为首个参加RoboCup的仿人机器人
国内晶圆厂积极参与MPW流片
锰基电极材料在水系钠离子电池中的研究进展
消息称苹果与比亚迪、宁德时代因造车项目合作谈崩
最受欢迎的几个无线标准
英特尔发布双屏平板电脑，将会引领个人电脑未来？
紫晶存储业绩亮眼 国产存储想取代市场尚需资本支持
电磁阀控制器，让智能灌溉更得心应手！
电池难颠覆 快速充电上演一场大戏
贝叶斯优化是干什么的(原理解读)
但是再深究下去，memtable具体是以怎样的格式持久化到磁盘上的呢？又是用什么算法高效查找一条消息的呢？
通过学习相关资料，我发现 apache bookkeeper 底层存储引擎用的是 facebook 开源的 rocksdb，而 rocksdb 又是基于 google 开源的 leveldb 改造的，而 leveldb 的核心是一个叫做 lsm 树（log structured merge tree）的结构。
leveldb 整个库的代码只有几百 kb，所以我去研究了 lsm 树的代码实现，总结了这篇文章，带你了解 lsm 树的设计原理。
什么是 lsm 树呢？如果说到 b+ 树大家应该不陌生，像 mysql 这样的关系型数据库底层一般用 b+ 树结构来存储数据。lsm 树其实就是另一种存储数据的结构，常见于日志存储系统中。
首先，我们先来聊聊存储系统。
内存数据结构 vs 磁盘数据结构
正如前文 学习数据结构和算法的框架思维 所说，一切数据结构从根本上讲都是增删查改，但在具体实现上，磁盘数据结构和内存数据结构会有比较大的差异。
内存数据结构你直接 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：
https://github.com/facebook/rocksdb/wiki/leveled-compaction
图中每个绿色方块代表一个sstable，若干个sstable构成一层，总共有若干层，每层能够容纳的sstable数量上限依次递增。
新刷入的sstable在第 0 层，如果某一层的sstable个数超过上限，则会触发 compact 操作，从该层选出若干sstable合并成一个更大的sstable，移动下一层：
https://github.com/facebook/rocksdb/wiki/leveled-compaction
每个sstable就好比一个有序数组/链表，多个sstable的合并就是前文 链表双指针技巧汇总 中合并多个有序链表的逻辑。
这样，越靠上层的数据越新，越靠下层的数据越旧，且算法保证同一层的若干sstable的key不存在重叠：
https://github.com/facebook/rocksdb/wiki/leveled-compaction
那么假设给一个目标键key27，我们只需要从上到下遍历层，并在每一层中使用 二分查找算法 找到键区间包含key27的sstable，然后用布隆过滤器快速判断一下key27是否不存在这个sstable中。如果可能存在，由于sstable中的键也是有序的，可以再次运用 二分查找算法 在sstable中找到键对应的值。
这样，借助 lsm 树的层级结构和sstable的有序性，就能利用二分搜索提升查找效率，避免线性查找键值对。
以上就是本文的全部内容，lsm 树的设计思路比较易于理解，但实现起来还有不少细节，如果你对具体实现感兴趣，我可以推荐一些学习资料：
leveldb 的代码仓库：
https://github.com/google/leveldb/issues
rocksdb 的 wiki：
https://github.com/facebook/rocksdb/wiki
区块链与物联网之间会发生什么
监视器技术固定刷新率和gsync选择哪个 监视器刷新率越高越好吗
超高速相机在科研界的地位有多高
北一半导体工厂和分立器件加工项目落户牡丹江穆棱经济开发区
典型的DRC案例介绍
存储系统中的算法：LSM树设计原理
瑞昱网通行业芯片应用简介
LHAASO 如何探测暗物质?
赋能演艺新高度 Vivitek(丽讯) DU9900Z工程投影机重磅亮相
怎样制作Arduino天线
完全自主型仿人机器人成为首个参加RoboCup的仿人机器人
国内晶圆厂积极参与MPW流片
锰基电极材料在水系钠离子电池中的研究进展
消息称苹果与比亚迪、宁德时代因造车项目合作谈崩
最受欢迎的几个无线标准
英特尔发布双屏平板电脑，将会引领个人电脑未来？
紫晶存储业绩亮眼 国产存储想取代市场尚需资本支持
电磁阀控制器，让智能灌溉更得心应手！
电池难颠覆 快速充电上演一场大戏
贝叶斯优化是干什么的(原理解读)