LSM Tree

LSM Tree：Log-Structured Merge Tree，日志结构合并树。是一种频繁写性能很高的数据结构。

LSM Tree将写入操作与合并操作分离，数据首先写入磁盘中的日志文件（WAL），随后写入内存缓存，内存中的数据是有序的，通常使用的方式如跳表、红黑树等。内存中的数据按照策略刷新至磁盘，由于内存中的数据有序，存储至磁盘中的数据也是有序的，相较于随机写，顺序写提高了性能。磁盘中的数据根据策略进行合并，删除旧的数据，避免数据持续增长，同时提高了查询性能。

存储结构

• WAL：当有新的 key-value需要写入时，首先将其追加到顺序写的日志文件（WAL）中，因为WAL中的数据与当前内存中的KV数据一致，可以利用WAL文件恢复上一次程序的运行状态。当immutable memtable中的内容写入SSTable后，删除WAL文件，重新创建一个空的WAL文件（此处根据实际情况实现）；
• memtable：内存中的数据结构，保证存储数据有序，通常使用跳表、红黑树等，leveldb中使用的跳表；
• immutable memtable：内存中的数据结构，不可修改的表，memtable中的key数据达到一定的阈值时，memtable变为immutable memtable，然后创建一个新的memtable。引入immutable memtable可以有效避免 memtable 的读写冲突竞争，从而避免阻塞，提高系统性能；
• Minor Compact：
  • 将immutable memtable的数据写入磁盘的流程，在Level 0生成一个新的SSTable；
  • 当某个 Level 中的 SSTable 文件数量或容量达到阈值时，会触发该 Level 文件和下一个 Level 文件的合并操作，这个过程会生成新的SSTable文件删除旧的SSTable文件；
• SSTable：数据持久化到磁盘后的数据结构，保存的是排序后的数据。每个SSTable包含多个存储数据的文件，成为segment，每个segment内部是有序的，由于是追加写，不用的SSTable可能存在相同的key；

数据写入

数据写入的流程如下：

1. 写入日志文件（Write-Ahead Log, WAL）

当有新的 key-value需要写入时，首先将其追加到顺序写的日志文件中。这个操作称为预写日志（Write-Ahead Logging），用于系统崩溃时数据的还原，保证了数据的一致性和可靠性。

2. 写入Memtable

将新的key-value写入内存中的数据结构，数据结构通常为跳表或红黑树，保证了数据的有序性。数据读取时有限读取Memtable，如Memtable中存在，可以迅速响应，提高了读取性能。

3. Memtable to SSTable

当内存中写入的数量达到一定的阈值时，将内存中的数据写入到磁盘的SStable的segmnet中，此过程写入的数据是有序的。

4. SSTable的合并

SSTable可以根据一定的策略进行合并，如时间、文件大小或其他条件，合并操作过程中，消除重复的key和已经删除的key，生成新的SSTable文件。

数据读取

1. 查询memtable，如查询不到，查询mmutable memtable；
2. 查询mmutable memtable，如查询不到，查询SSTable；
3. 查询SSTable；

查询SSTable时，通常从最新的segment扫描，扫描全部segment直至查询到对应数据。当扫描某个特定的segment时，由于该segment内部的数据是有序的，因此可以使用二分查找的方式，在O(logn)的时间内得到查询结果。但对于二分查找来说，要么一次性把数据全部读入内存，要么在每次二分时都消耗一次磁盘 IO，当 segment 非常大时，这两种情况的代价都非常高。通常使用稀疏索引的方式优化查询策略。

稀疏索引

上图为kafka利用稀疏索引查询的机制。

稀疏索引的原理是将数据切分成多个小块，以多个小块作为一个单位，由于数据有序性，仅需将每个单位开头的数据作为索引即可。

有了稀疏索引，我们可以现在索引表中利用二分法快速定位要查询的key在哪个数据块中，仅从磁盘中读取这一小块数据即可获取查询结果，IO代价较小。

稀疏索引虽然提高了查询性能，但是当查询结果不在SSTable中时，我们不得不扫描完所有的segment，针对这种情况，通常使用布隆过滤器解决该问题。

布隆过滤器是一种空间效率极高的算法，能够快速地检测一条数据是否在数据集中存在。我们只需要在写入每条数据之前先在布隆过滤器中登记一下，在查询时即可断定某条数据是否缺失。

布隆过滤器的内部依赖于哈希算法，当检测某一条数据是否见过时，有一定概率出现假阳性（False Positive），但一定不会出现假阴性（False Negative）。也就是说，当布隆过滤器认为一条数据出现过，那么该条数据很可能出现过；但如果布隆过滤器认为一条数据没出现过，那么该条数据一定没出现过。这种特性刚好与此处的需求相契合，即检验某条数据是否缺失。

文件合并

文件合并的目的主要是控制存储数据大小，LSM Tree可以按照一定的策略执行文件合并，合并后的旧数据会被删除，合并后的新数据是有序的，合并过程中会消除重复键、删除键以及更新过期键。

数据删除

LSM tree设计一个特殊的标志位，称为 tombstone（墓碑），删除一条数据就是把它的 value 置为tombstone，如上图所示，在执行文件合并时被删除的数据在合并过程中被清除掉。

合并过程中如存在重复的key，通常根据key的时间戳或其他合并策略决定保留哪个版本的数据。

优缺点

• 具有较高的写入性能和压缩存储，适用于写多读少或写入速度较快的场景。通过将写入操作集中在内存和顺序写的日志文件中，可以获得较高的写入吞吐量。查询性能也较好，通过内存缓存和有序的SSTable文件，可以快速定位和检索键值对。
• 合并操作可能会引起较长的停顿时间，对于实时性要求较高的系统可能会有影响。

总结

• LSM Tree具有较高的写入性能，主要通过写入内存和磁盘顺序写实现；
• 写入数据时，先将数据写入内存，当内存达到一定大小时，将内存中的数据一次性顺序写入(flush)磁盘，生成SSTable中一个segment，segment内部数据也是有序的；
• 读取数据时，先查找布隆过滤器，如查询不到直接返回key不存在，如存在，继续查询稀疏索引表；
• 查找稀疏索引表，根据查询到的范围从磁盘读取数据，进而利用二分法读取获取最终结果；
• Segment过多的情况下，会导致写性能下降，通过文件合并操作，消除重复键、删除键以及更新过期键，避免产生大量的segment文件，达到了数据压缩的目的，同时也提高了查询效率；

参考：

https://zhuanlan.zhihu.com/p/640477369

https://hzhu212.github.io/posts/2d7c5edb

https://cloud.tencent.com/developer/article/2011084