数据结构（四）、LSM树（日志结构合并树）

一时失言乱红尘 2023-03-06 05:54 64阅读 0赞

传统关系型数据库大都使用B-Tree或其变体作为存储结构，能够进行高效查找。但保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远，这就可能造成大量的磁盘随机读写。因此对于关系型数据库来说随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了本篇要讲的LSM树。LSM树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能。因此在大数据生态下，很多数据库引擎都是使用LSM树存储引擎。

--------------------

[数据结构（一）、二叉树（BT），二叉查找树（BST），平衡二叉树（AVL树）][BT_BST_AVL]

[数据结构（二）、红黑树（RBT）][RBT]

[数据结构（三）、B树，B+树，B\*树][B_B_B]

**目录**

背景

存储引擎

原理

尾巴

--------------------

# 背景 #

1996年，一篇名为 The Log Structured Merge Tree（LSM-tree）的论文创造性地提出了日志结构合并树（ Log Structured Merge Tree）的概念，该方法既吸收了日志结构方法的优点，又通过将数据文件预排序克服了日志结构方法随机读性能较差的问题。尽管当时 LSM-tree新颖且优势鲜明，但它真正声名鹊起却是在 10年之后的 2006年，那年谷歌的一篇使用了 LSM-tree技术的论文 Bigtable: A Distributed Storage System for Structured Data横空出世，在分布式数据处理领域掀起了一阵旋风，随后两个声名赫赫的大数据开源组件（ 2007年的 HBase与 2008年的 Cassandra，目前两者同为 Apache顶级项目）直接在其思想基础上破茧而出，彻底改变了大数据基础组件的格局，同时也极大地推广了 LSM-tree技术。

LSM树 相比 B+树能提高写性能的本质原因是：无论是磁盘还是SSD，都有随机读写慢，顺序读写快的问题。

![format_png][]

# 存储引擎 #

目前常见的主要的三种存储引擎是：

*  **哈希存储引擎**：哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表就是正确的选择。
 *  **B树存储引擎**：B树的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（如：Mysql）。
 *  **LSM树存储引擎**：和B+树存储引擎一样，支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利就有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。

# 原理 #

LSM树真正发扬光大是从Google的BigTable论文起：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70][]

由图上可以看出，LSM树的读写原理分解下来就是下面几个步骤：

**写请求操作**：

1.  先将数据写入log文件，当内存储中的memtable数据丢失时可以从log文件中恢复。log文件中的数据不会进行排序；
2.  将数据写入内存储中的memtable，若命中数据则更新，否则插入新数据。memtable中的数据会按key值排序，通常使用AVL，红黑树的数据结构进行索引；
3.  当memtable的大小达到一定规模时会将数据连同索引一起写入磁盘，即sstable文件；
4.  memtable的数据持久化sstable中后，log文件中的内容被清空；
5.  后台compaction线程根据策略对sstable文件进行合并，由于sstable内是有序的，合并的过程很快；

**读请求操作**：

1.  查找内存储中的memtable，若命中则返回，否则进行下一步；
2.  在内存储中没有找到数据，就会逆序查找sstable，直到命中数据，由于sstable是有序的，所以查找过程比较高效；

在上面的简要过程中我们可以看出，由于LSM树的增删改操作对于磁盘都是纯粹的append-only操作(追加sstable文件)，因此LSM树相比于B树的写入节点会分裂重平衡更加高效。而在读数据时会依次查找sstable文件，直至查到数据，同时由于在写数据的时候生成的sstable文件过多，读性能会递减，虽然后台会有线程对sstable文件进行合并，但还是会影响到LSM树的读性能。

> **WAL**：在一些基于LSM树的实现中，使用WAL（Write-Ahead Logging）预写日志保证数据完整性，就是上面图中的tablet log；类似于ES的translog：[Elasticsearch核心原理][Elasticsearch]
> 
> **布隆过滤器**：由于sstable文件数量越多，LSM树的读性能就越低，因此在一些LSM树的实现中使用布隆过滤器（bloom filter）来优化读性能。关于布隆过滤器在之前的文章中有过介绍：[布隆过滤器][Link 1]

# 尾巴 #

随着数据爆炸和SSD的出现，越来越多的新兴数据库选择LSM树，比如最近很热的HTAP数据库TiDB、Esgyn 和大数据生态的nosql数据库hbase、Cassandra、RocksDB等等，它对数据的写入性能有很大的提升，同时用LSM树做列存储，数据压缩的效果比行存的B+树也要好很多。由于SSD的存在，随机读性能比B+树也不会差太多。

希望本文对你有帮助，请点个赞鼓励一下作者吧~ 谢谢！

[BT_BST_AVL]: https://blog.csdn.net/wsdc0521/article/details/107676999
[RBT]: https://blog.csdn.net/wsdc0521/article/details/107677009
[B_B_B]: https://blog.csdn.net/wsdc0521/article/details/107800168
[format_png]: /images/20230208/ff4cfd87d16c4a4792e6f9c89bd51ba3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGMwNTIx_size_16_color_FFFFFF_t_70]: /images/20230208/9e85276662f349839191b995d1c8bd1f.png
[Elasticsearch]: https://blog.csdn.net/wsdc0521/article/details/106902807
[Link 1]: https://blog.csdn.net/wsdc0521/article/details/107220367