为什么大部分NOSQL数据库选择使用LSM树而非B+树？

文章目录

• LSM Tree
• 架构介绍
• • MemTable
  • Immutable MemTable
  • WAL
  • SSTable
• 核心流程
• • 写入数据
  • 查询数据
  • 段合并（Compaction）
• LSM-Tree VS B+ Teee

LSM Tree

LSM Tree（Log Structured Merge Trees）是一种分层，有序，面向磁盘的复合数据结构，其包括了WAL（Write Ahead Log）、SSTable（Sorted String Table）、MemTable、Immutable MemTable四个部分。LSM Tree是许多key-value 型或日志型数据库所依赖的核心数据结构，例如 BigTable、HBase、Cassandra、LevelDB、SQLite、Scylla、RocksDB等。

其核心架构如下：

LSM Tree核心架构

架构介绍

MemTable

MemTable是在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据，LSM对于具体如何组织有序地组织数据并没有明确的数据结构定义（常用的结构如红黑树、跳表等）。

因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过WAL(Write-ahead logging，预写式日志) 的方式来保证数据的可靠性。

Immutable MemTable

当MemTable达到一定大小后，会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态，它其实就相当于一个只读的MemTable，不再允许数据写入，因此写操作由新的MemTable处理。

Immutable MemTable不会无限占用内存，在后台有一个线程不断地将Immutable MemTable复制到磁盘文件中，然后释放内存空间，而这些写入的硬盘文件，其实就是SSTABLE。

WAL

从前面我们看到，MemTable和Immutable MemTable都存储在内存当中，那如果机器断电或者服务器崩溃，这时不就导致数据永久丢失了吗？为了解决这个问题，LSM引入了WAL（Write Ahead Log，预写日志技术） 技术。

WAL的核心就是预先将数据写入log文件进行备份，同时在处理完成后生成检查点，确保数据不会丢失。其核心流程如下：

1. 内存中的程序在处理数据时，会先讲对数据的修改作为一条记录，顺序写入磁盘的log文件作为备份。
2. 系统会周期性检查内存中的数据是否被处理完，并且生成对应的CheckPoint（检查点） 记录在磁盘中。
3. 当系统崩溃重启时，我们只需要从磁盘中读取出检查点，就能够知道最后一次成功处理的数据在log文件中的位置。紧接着我们只需要把这个位置之后的未被处理的数据从log文件中读取到内存即可。

SSTable

Immutable MemTable持久化到硬盘上之后的结构称为Sorted Strings Table (SSTable)。顾名思义，SSTable保存了排序后的数据（实际上是按照 key 排序的 key-value 对）。每个SSTable可以包含多个存储数据的文件，称为segment，每个segment内部都是有序的，但不同segment 之间没有顺序关系。一个segment一旦生成便不再修改（immutable）。

SSTable示例

介绍完了LSM的核心组成后，下面就来看看其到底如何利用这些结构来完成高性能的写入、查询、合并。

核心流程

写入数据

LSM之所以具有那么高的写性能，原因就是两点：1.顺序写，2.批量写。

由于外部的数据是无序到来，为确保顺序写入，LSM会在内存中利用Memtable（红黑树、跳表）来维护数据，确保数据的有序。同时为了减少随机写入的次数 ，其不会每次都将数据写入到硬盘中，而是当Memtable的数据量达到一定的阈值之后，将其转换为Immutable MemTable的同时会触发其

flush

操作，将所有排好序的数据一次性批量、顺序写入硬盘中，生成一个segment。

数据写入

查询数据

LSM在查找数据时采用的是分层查找的逻辑

1. 首先去内存中查找MemTable和Immutable MemTable
2. 然后再按照顺序依次在磁盘的每一层SSTable文件中去找（从最新层开始查找，越是最近的数据越可能被用户查询）
3. 如果SSTable添加了布隆过滤器索引，则在布隆过滤器中查找key是否存在，由于布隆过滤器具有假阳性，只要找不到，就说明当前SSTable中不存在该数据，仅此直接跳过，减少不必要的磁盘扫描。
4. 由于SSTable本身是有序的，为了避免全表扫描，此时通过将稀疏索引读入内存中，利用二分查找来快速定位key在哪一块数据中。最终只需要读取指定偏移量的数据就可以获取最终的结果。

   

查询数据流程

段合并（Compaction）

随着数据的不断写入，在SSTable中会产生越来越多的的segment，每一个segment都会消耗文件句柄、内存和cpu运行周期。更重要的是，每个查询请求都必须轮流检查每个segment，所以段越多，查询也就越慢。

为了解决这个问题，LSM引入了Compaction机制，其会定期执行合并逻辑，将多个segment合并为一个较大的segment，同时由于每个segment中的数据已经是有序的，因此其只需要通过归并排序的逻辑，就可以高效的完成合并。

段合并

在Compaction的过程中，在之前被标记为删除的数据不会被写入新的segment中，且在合并结束后，所有旧的segment的数据将从硬盘上被彻底删除掉。

LSM-Tree VS B+ Teee

下面给出两者的对比

区别	LSM-Tree	B+ Teee
应用场景	K-V数据库、日志数据库（频繁写）	关系型数据库（频繁读）
写入性能	批量顺序写，且采用追加写（不需更新），写入性能高	单条随机写入，且索引需要更新，写入性能低
查找性能	存在读放大，查询性能低O(N)，经过索引、缓存优化后可以O(LogN)	查找性能极高，O(LogN)
删除与修改	追加写入，标记删除，在compaction阶段才能真正删除	原地更新与删除
存储方式	内存+硬盘	硬盘