LSM Tree

日志结构合并树(Log-Structured Merge-Tree)

前言

大多 NoSQL 数据库核心思想都是基于LSM Tree 的存储模型来做的，只是具体的实现不同。包括 LevelDB，HBase，
Google BigTable，Cassandra，InfluxDB ，携程 SessionDB，Facebook rocksdb 等。

LSM树，即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构，
它更多是一种数据结构的设计思想。

由来

讲 LSM 树之前，需要提下三种基本的存储引擎，这样才能清楚 LSM 树的由来。

哈希存储引擎: 是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表就非常适合。代表性的数据库有：Redis，Memcache，以及存储系统Bitcask。
B树存储引擎是B树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库(MySQL)。
LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。

当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。

从技术角度: 由于磁盘的(磁柱、磁盘、磁道、磁头)结构与B树结构的特点,导致传统B树索引存在着随机写效率的上限挑战，所以当在那些索引插入频率远大于查询频率的应用场景下，如历史记录表和日志文件来说，B树索引显得捉襟见肘了。

1. B树随机写特点

一个BTree，对于在没有缓存的Case情况下, 一个随机写分为两步进行：

从磁盘Load目标块节点到内存，
修改它并写回磁盘。

所以BTree在对于随机key值下的平均“blind-write”操作需要两次IO操作，其限定了BTree的随机写吞吐量。

为什么B+树会慢

从原理来说，B+树在查询过程中应该是不会慢的，但如果数据插入比较无序的时候，比如先插入5 然后10000然后3然后800 这样跨度很大的数据的时候，就需要先“找到这个数据应该被插入的位置”，然后插入数据。
这个查找到位置的过程，如果非常离散，那么就意味着每次查找的时候，他的叶子节点都不在内存中，这时候就必须使用磁盘寻道时间来进行查找了。更新基本与插入是相同的。

既然随机写相对昂贵的，LSM采用“有序map的数据分层与延迟写”(all sorted-map write-deferral)的策略而代替立即写的操作；同时为了避免数据层数的过多造成对读的性能的伤害，数据层级之间会周期性地触发自顶向下地进行合并的操作。

LSM Tree采取了什么样的方式来优化这个问题呢?

简单来说，就是放弃磁盘读性能来换取写的顺序性。

存储模型

1. WAL

在设计数据库的时候经常被使用，当插入一条数据时，数据先顺序写入 WAL 文件中，
之后插入到内存中的 MemTable 中。
这样就保证了数据的持久化，不会丢失数据，并且都是顺序写，速度很快。
当程序挂掉重启时，可以从 WAL 文件中重新恢复内存中的 MemTable。

2. MemTable

MemTable 对应的就是 WAL 文件，是该文件内容在内存中的存储结构，
通常用 SkipList 来实现。MemTable 提供了 k-v 数据的写入、删除以及读取的操作接口。
其内部将 k-v 对按照 key 值有序存储，这样方便之后快速序列化到 SSTable 文件中，仍然保持数据的有序性。

3. Immutable Memtable

顾名思义，Immutable Memtable 就是在内存中只读的 MemTable，由于内存是有限的，通常我们会设置一个阀值，当 MemTable 占用的内存达到阀值后就自动转换为 Immutable Memtable，Immutable Memtable 和 MemTable 的区别就是它是只读的，系统此时会生成新的 MemTable 供写操作继续写入。

之所以要使用 Immutable Memtable，就是为了避免将 MemTable 中的内容序列化到磁盘中时会阻塞写操作。

4. SSTable

SSTable 就是 MemTable 中的数据在磁盘上的有序存储，其内部数据是根据 key 从小到大排列的。通常为了加快查找的速度，需要在 SSTable 中加入数据索引，可以快读定位到指定的 k-v 数据。

常用操作的实现

1. 写入

在 LSM Tree 中，写入操作是相当快速的，只需要在 WAL 文件中顺序写入当次操作的内容，成功之后将该 k-v 数据写入 MemTable 中即可。尽管做了一次磁盘 IO，但是由于是顺序追加写入操作，效率相对来说很高，并不会导致写入速度的降低。数据写入 MemTable 中其实就是往 SkipList 中插入一条数据，过程也相当简单快速。

2. 更新

更新操作其实并不真正存在，和写入一个 k-v 数据没有什么不同，只是在读取的时候，会从 Level0 层的 SSTable 文件开始查找数据，数据在低层的 SSTable 文件中必然比高层的文件中要新，所以总能读取到最新的那条数据。也就是说此时在整个 LSM Tree 中可能会同时存在多个 key 值相同的数据，只有在之后合并 SSTable 文件的时候，才会将旧的值删除。

3. 删除

删除一条记录的操作比较特殊，并不立即将数据从文件中删除，而是记录下对这个 key 的删除操作标记，同插入操作相同，插入操作插入的是 k-v 值，而删除操作插入的是 k-del 标记，只有当合并 SSTable 文件时才会真正的删除。

4. 合并

Compaction。当数据不断从 Immutable Memtable 序列化到磁盘上的 SSTable 文件中时，SSTable 文件的数量就不断增加，而且其中可能有很多更新和删除操作并不立即对文件进行操作，而只是存储一个操作记录，这就造成了整个 LSM Tree 中可能有大量相同 key 值的数据，占据了磁盘空间。

为了节省磁盘空间占用，控制 SSTable 文件数量，需要将多个 SSTable 文件进行合并，生成一个新的 SSTable 文件。比如说有 5 个 10 行的 SSTable 文件要合并成 1 个 50 行的 SSTable 文件，但是其中可能有 key 值重复的数据，我们只需要保留其中最新的一条即可，这个时候新生成的 SSTable 可能只有 40 行记录。

5. 读取

LSM Tree 的读取效率并不高，当需要读取指定 key 的数据时，先在内存中的 MemTable 和 Immutable MemTable 中查找，如果没有找到，则继续从 Level 0 层开始，找不到就从更高层的 SSTable 文件中查找，如果查找失败，说明整个 LSM Tree 中都不存在这个 key 的数据。如果中间在任何一个地方找到这个 key 的数据，那么按照这个路径找到的数据都是最新的。

6. 优化读取

因为这样的读取效率非常差，通常会进行一些优化，例如 LevelDB 中的 Mainfest 文件，这个文件记录了 SSTable 文件的一些关键信息，例如 Level 层数，文件名，最小 key 值，最大 key 值等，这个文件通常不会太大，可以放入内存中，可以帮助快速定位到要查询的 SSTable 文件，避免频繁读取。

另外一个经常使用的方法是布隆解析器(Bloom filter)，布隆解析器是一个使用内存判断文件是否包含一个关键字的有效方法。

总结

总的来说就是通过将大量的随机写转换为顺序写，从而极大地提升了数据写入的性能，虽然与此同时牺牲了部分读的性能。

只适合存储 key 值有序且写入大于读取的数据，或者读取操作通常是 key 值连续的数据。

B树和LSM树最主要的区别在于他们的结构和如何利用硬件，特别是磁盘。

LSM Tree 的思想非常实用，将随机写转换为顺序写来大幅提高写入操作的性能，但是牺牲了部分读的性能。

由于时间序列数据库的特性，运用 LSM Tree 的算法非常合适。持续写入数据量大，数据和时间相关，编码到 key 值中很容易使 key 值有序。读取操作相对来说较少，而且通常不是读取单个 key 的值，而是一段时间范围内的数据，这样就把 LSM Tree 读取性能差的劣势缩小了，反而由于数据在 SSTable 中是按照 key 值顺序排列，读取大块连续的数据时效率也很高。

1
2
3

作者：fatedier 
本文出处：http://blog.fatedier.com/2016/06/15/learn-lsm-tree/ 
文章版权归本人所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文链接，否则保留追究法律责任的权利。

参考链接

前言

由来