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