LSM 存储结构：从原理到应用，简单聊聊
如果你对数据库或者存储系统有点兴趣，可能听说过 LSM（Log-Structured Merge-Tree，日志结构合并树）。它是大名鼎鼎的现代存储引擎（如 LevelDB、RocksDB、Cassandra 等）背后的核心数据结构。这篇博客会用尽量通俗的语言，带你搞清楚 LSM 是什么、怎么工作，以及为什么它这么受欢迎。
什么是 LSM？
简单来说，LSM 是一种专门优化写操作的存储结构。传统数据库（比如基于 B+树的结构）在处理写操作时，需要直接找到数据存放的位置，然后修改磁盘上的内容。这种随机写操作在机械硬盘上特别慢，因为磁盘的随机 I/O 性能很差。LSM 的设计思路完全不同：它把写操作变成顺序写，先记下来再说，之后再慢慢整理。
想象一下，你在记笔记。如果每次有新想法都翻到笔记本的某个特定页面去改，很麻烦，对吧？LSM 的做法更像是在笔记本最后加一页，快速写下新内容，等到有空再整理到合适的位置。这就是“日志结构”的核心思想。
LSM 怎么工作？
LSM 的核心组件主要有两个：内存里的部分和磁盘上的部分。让我们一步步拆解它的运作流程。
1. 内存中的 MemTable
当有数据写入（比如新增、修改）时，LSM 不会直接写到磁盘，而是先写到内存里的一个结构，叫做 MemTable（内存表）。MemTable 通常用高效的数据结构实现，比如跳表（Skip List）或者红黑树，这样插入和查询都很快速。
这就像你在小纸条上记东西，速度快，改动方便。
2. 日志文件（WAL）
为了防止宕机丢数据，每次写到 MemTable 之前，LSM 都会先把操作记录到一个磁盘上的日志文件，叫 WAL（Write-Ahead Log，预写日志）。这个日志是顺序写入的，所以非常快。
相当于你记小纸条时，先快速抄到日记本的最后一页，确保不会忘。
3. Immutable MemTable 和 SSTable
当 MemTable 满了，它会变成只读的 Immutable MemTable（不可变内存表），然后后台线程会把它刷到磁盘上，变成 SSTable（Sorted String Table，排序字符串表）。SSTable 是磁盘上的文件，数据按键（Key）排序好，并且不可修改。
这就像你把小纸条上的内容整理好，抄到笔记本的某个章节，再也不改动这部分。
4. 多层结构（Level）
磁盘上的 SSTable 会越来越多。为了管理这些文件，LSM 把它们分成多层（Level 0, Level 1, Level 2…）。每一层的数据量通常比上一层大（比如 10 倍），而且数据是有序的。
当某一层的 SSTable 太多时，LSM 会把它们合并（Merge），去掉重复或过时的数据，生成新的 SSTable，放到下一层。这个过程叫 Compaction（合并压缩）。
有点像你整理笔记，把零散的内容合并成更厚的一章，扔掉没用的草稿。
5. 读操作
读数据时，LSM 先查内存里的 MemTable 和 Immutable MemTable（如果有），再去磁盘上的 SSTable 找。因为 SSTable 是分层的，LSM 会从 Level 0 开始一级级查，利用键的有序性快速定位。虽然读可能需要多查几处，但可以用 Bloom Filter（布隆过滤器）这种技巧加速，判断某个键是否存在于某个 SSTable。
LSM 的优点
- 写性能超高：所有写操作先到内存，再顺序刷盘，避免了随机 I/O。
- 顺序 I/O 友好：日志和 SSTable 都是顺序写入，特别适合机械硬盘和现代 SSD。
- 可扩展性强：通过分层和合并，LSM 能处理海量数据。
LSM 的缺点
- 读性能相对弱：因为数据分散在内存和多层 SSTable，读可能需要多次查询。
- 合并开销：Compaction 过程会占用 CPU 和 I/O，可能会影响系统性能。
- 空间放大：同一键的多个版本可能暂时共存，占用的磁盘空间会比实际数据多。
实际应用场景
LSM 特别适合写多读少的场景。比如：
- 时间序列数据库（如 InfluxDB）：传感器数据不断写入，查询相对少。
- 分布式 KV 存储（如 RocksDB、Cassandra）：需要快速写入和高吞吐量。
- 日志系统：顺序记录事件，偶尔查历史。
总结
LSM 存储结构的核心思路是“先快写，后整理”。它通过内存缓冲、日志保护、分层管理和合并压缩，把随机写变成顺序写，大幅提升了写性能。虽然读操作和空间效率上有些妥协，但现代优化手段（比如 Bloom Filter、缓存）让这些问题变得可控。
如果你是个有一定基础的技术爱好者，希望这篇博客让你对 LSM 有个清晰的认识。简单来说，LSM 就像一个高效的“记事本管理员”：写得快、整理得聪明，用在合适的地方特别强大！