共计 4588 个字符，预计需要花费 12 分钟才能阅读完成。
LSM Tree（Log-structured merge-tree）广泛应用在 HBase，TiDB 等诸多数据库和存储引擎上，咱们先来看一下它的一些利用：
这么牛 X 的名单，你不想理解下 LSM Tree 吗？装 X 之前，咱们先来理解一些基本概念。
设计数据存储系统可能须要思考的一些问题有：ACID，RUM（Read,Write,Memory）。
ACID
ACID 置信小伙伴都被面试官问过，我想简略探讨的一点是：如何 长久化数据 能力保证数据写入的 事务性 和 读写性能？
事务性可简略了解为：1. 数据必须长久化。2. 一次数据的写入返回给用户 写入胜利就肯定胜利，失败就肯定失败。
读写性能可简略了解为：一次读 或 一次写 须要的 IO 次数，因为拜访速率：CPU>> 内存 >>SSD/ 磁盘。
对于单机存储，最简略的形式当然是：写一条就长久化一条，读一条就遍历一遍所有数据，而后返回。当然没人这么干，在内存中咱们都还晓得用个 HashMap 呢。
拿 Mysql InnoDB 举例子：读性能体现在数据的索引在磁盘上次要用 B + 树来保障。写性能体现在使用 WAL 机制 来防止每次写都去更新 B + 树上的全量索引和数据内容，而是通过 redo log 记录下来每次写的增量内容，程序将 redo log 写入磁盘。同时在内存中记录下来本次写入应该在 B + 树上更新的脏页数据，而后在肯定条件下触发脏页的刷盘。
redo log 是数据增删改的实时增量数据，程序写入保障了写性能和事务性。磁盘上的 B + 树是数据增删改的全量数据，通过定时脏页刷盘保障这份数据的完整性。
这里的问题是：尽管通过 WAL 机制，进步了写入性能，然而依然防止不了脏页数据定时刷盘的随机 IO 写入。因为数据在磁盘上是以 block 为单位存储的（比方 4K，16K）, 如果你更新了 Order 表一条数据，又更新了 Product 表一条数据，脏页刷盘时，这两条数据在磁盘上的 block 地位可能差了十万八千里，就变成了随机 IO 的写入。
RUM
RUM（Read,Write,Memory）相似分布式畛域的 CAP 定理。如果想得到三者中的两者性能，必须以就义第三者的性能为代价。掂量这三者的性能指标有：读放大、写放大、空间放大。
读放大：是指每次查问读取磁盘的次数。如果每次查问须要查问 5 个 page (或 block)，则读放大是 5.
写放大：是指数据写入存储设备的量和数据写入数据库的量之比。如果用户写入数据库的大小是 10MB，而理论写入磁盘的大小是 30MB，则写放大是 3. 另外 SSD 的写入次数是无限的，写放大会缩小 SSD 的寿命。
空间放大：是指数据在存储设备的总量和数据在数据库的总量之比。如果用户往数据库上存 10MB，而数据库理论在磁盘上用了 100MB 去存，则空间放大就是 10.
通常，数据结构能够最多优化这其中的两者，如 B + 树有更少的读放大，LSM Tree 有更少的写放大。
上面咱们将介绍 LSM Tree 的构造，它是如何解决 B+ 树中“全量数据的随机写入”问题的；在 RUM 问题上，又该如何优化 LSM Tree。
为什么要有 LSM Tree
LSM Tree（Log-structured merge-tree）起源于 1996 年的一篇论文：The log-structured merge-tree (LSM-tree)。过后的背景是：为一张数据增长很快的历史数据表设计一种存储构造，使得它可能解决：在内存不足，磁盘随机 IO 太慢下的重大写入性能问题。
如果咱们先后批改两条数据，那么在脏数据块落盘时，不是一条条随机写入，而是以一个脏块批量落盘时，就能解决 B+ 树中“全量数据的随机写入”问题了。
所以大佬设计了这么一种构造：
Ck tree 是一个有序的树状构造，数据的写入流转从 C0 tree 内存开始，一直被合并到磁盘上的更大容量的 Ck tree 上。这种形式写入是程序写的，增删改操作都是 append。
这样一次 I / O 能够进行多条数据的写入，从而充分利用每一次写 I /O。
merge 所做的事件有：当上一棵树容量有余时，1. 将上棵树中要删除的数据删除掉，进行 GC 回收。2. 合并数据的最新版本，使得 Ck tree 不会适度收缩。
这种初始构造存在的问题有：随着数据量的增大，merge 吃力，没有好的索引构造，读放大重大。古代的 LSM Tree 构造如下：
MemTable：是 LSM Tree 在内存中还未刷盘的写入数据，这外面的数据能够批改。是一个有序的树状构造，如 RocksDB 中的跳表。
SSTable（Sorted String Table）：是一个键是有序的，存储字符串模式键值对的磁盘文件。当 SSTable 太大时，能够将其划分为多个 block；咱们须要通过 下图中的 Index 记录下来每个 block 的起始地位，那么就能够构建每个 SSTable 的稠密索引。这样在读 SSTable 前，通过 Index 构造就晓得要读取的数据块磁盘地位了。
LSM Tree 读数据
读数据 包含点读和范畴读，咱们离开探讨。假如 LSM Tree 中的 key 为[0-99]，
点读：是指精确地取出一条数据，如 get(23), 则其示意图为：
依照图中标示的程序，会先读取内存，在从 Level0 顺次往高层读取，直到找到 key=23 的数据。
范畴读：是指读取一个范畴内的数据，如读取 [23-40] 内的所有数据（select * from t where key >= 23 && key <=40),
则须要做的是在每一层 SSTable 找到这个范畴内的第一个 block, 而后遍历 block 块的数据，直到不合乎范畴条件。
ReadOnly MemTable：如 RocksDB，在 MemTable 和 Level0 数据之间还有一个内存的 ReadOnly MemTable 构造。它是 LSM Tree 在内存中还未刷盘的写入数据，这外面的数据不能够批改。是当 MemTable 达到一定量须要刷到 SSTable 时，由 MemTable 残缺 copy 下来的。这样可防止从 MemTable 间接刷到 SSTable 时的并发竞争问题。
LSM Tree 写数据
在 LSM Tree 写入数据时，咱们把 ReadOnly MemTable 画上，示意图如下：
当有写申请时，数据会先写入 MemTable, 同时写入 WAL Log；当 MemTable 空间有余时，触发 ReadOnly MemTable copy, 同时写入 WAL Log；而后刷新到磁盘 Level0 的 SSTable 中。当低层 SSTable 空间有余时，一直通过 Compaction 和高层 SSTable 进行 Merge。
LSM Tree 合并策略
LSM Tree 有两种合并策略，Tiering 和 Leveling。咱们看图谈话：
Tiering的特点是：每层可能有 N 个重叠的 sorted runs，当上一层的 sorted runs 要 merge 下来时，不会和以后层重叠的 sorted runs 马上合并，而是等到以后层空间有余时，才会合并，而后再 merge 到下一层。
Tiering 这种策略能够减小写放大，然而以读放大和空间放大为代价。
Leveling的特点是：每层只有一个 sorted run，当上一层的 sorted run 要 merge 下来时，会马上和以后层的 sorted run 合并。
Leveling 这种策略能够减小读放大和空间放大，但以写放大为代价。
LSM Tree 的优化
参考资料 [2-4] 中的大佬们提到了不少优化形式，我这里从读，合并方面简要总结下 LSM Tree 的优化。
点读的优化
只管咱们能够通过 SSTable 的内存 block 稠密索引构造简略判断 key 是否可能存在于 block 中，但如上 get(23)，如果 level1 读不到，仍须要往下读 level2,level3。（因为数据是依照增删改的工夫程序一层层往着落盘的，如果一个 key 不存在低 level 中，可能存在于更早的高 level 中）。这样的点读 IO 次数较多，读放大重大。
布隆过滤器
对于准确查问，hash 的工夫复杂度为 O(1)，那么能够通过布隆过滤器来优化。咱们只须要查问时先过一遍布隆过滤器，就能排除掉肯定不存在的 key 了，防止不必要的 IO 查问。
布隆过滤器：是通过 hash 算法来判断一个 key 是否存在于某个汇合中，布隆过滤器通常是一个 bit 数组，用针对一个 key 屡次 hash 算法确定的多个 bit 值来示意 key 是否存在。多个 bit 值全为 1，则示意 key 可能存在，否则不存在。益处是多个 bit 值通常比间接存储一个存在的 key 占用空间小，省内存。
分层布隆过滤器
上述布隆过滤器是假如每层数据都应用雷同的布隆过滤器来进行过滤，而数据随着层数的减少通常是指数级增长的，如果使低层的数据应用更准确的布隆过滤器（所需 bit 数更多，然而精确度更高）, 高层的数据应用略微不那么准确的布隆过滤器，则整体点查的效率将进步。参考资料【3】中 Monkey 做了上述优化，即便随着数据量和层数的增大，点查仍能放弃在一个稳固的工夫内。
范畴读的优化
Hash 的有余就是无奈反对范畴查问索引，优化形式有：
并行查问
因为读数据不存在竞争问题，能够并行读每层的数据，缩短整体查问工夫，然而这种形式理论并没有缩短 IO 次数。
前缀布隆过滤器
前缀布隆过滤器是以 key 的前缀来 Hash 构建布隆过滤器，而不是 key 自身的值。这样能够起到过滤 like Monica* 这样的查问条件作用。RocksDB 有做此优化。
合并的优化
下面提到了两种合并策略 Tiering 和 Leveling。Tiering 能够减小写放大，Leveling 能够减小读放大和空间放大。参考资料【3】中提到了数据库所采纳的合并策略走势如下：
随着数据量的增大，整条曲线会上移。优化的重点在于：如何联合两种合并策略，使曲线整体下移。
Lazy Leveling
参考资料【3】中 Dostoevsky 采纳了一种 Lazy Leveling 的策略：它是对低层数据采纳 Tiering 合并策略，对高层数据采纳 Leveling 合并策略。从而衡量了读写性能。
RUM 的取舍
RUM 的取舍和衡量相似于分布式畛域的 CAP，在特定的场景采纳适宜的优化伎俩能力使整体性能最优。参考资料【3】中的大佬还提到了 Fluid Merge 策略。233 酱示意虽过了眼瘾，但仍是个 CRUD 渣渣。
对于 RUM 的优化，233 酱最初放一张图，心愿对你我有所启发。
后记
LSM Tree 是这两年始终听到的名词，然而始终没有花工夫搞懂它。233 酱趁这次机会现学现卖，对其有了更深一步的理解。
对本文内容感兴趣的小伙伴可进一步浏览参考资料，如果文中有谬误或者不了解的中央也欢送小伙伴们和我交换斧正。
另外，如果感觉有播种也请帮忙 四连【关注，点赞，再看，转发】 反对一下 233 酱，谢谢～
参考资料：
[1].https://kernelmaker.github.io/lsm-tree
[2].https://www.youtube.com/watch?v=aKAJMd0iKtI
[3].https://www.youtube.com/watch?v=b6SI8VbcT4w
[4].https://www.bilibili.com/video/BV1fb411x7zz?from=search&seid=8679886514280300283
[5].https://tikv.github.io/deep-dive-tikv/key-value-engine/B-Tree-vs-Log-Structured-Merge-Tree.html
