今天几乎所有需要"疯狂写入"的数据库——Cassandra、HBase、RocksDB、LevelDB、InfluxDB，甚至 Kafka 的存储引擎思路——都绕不开一篇诞生于 1996 年、当年几乎没人注意的冷门论文。
它没有炫技的算法，也没有华丽的证明，作者甚至不是搞分布式系统出身的人。三十年后，它却几乎重新定义了"写多读少"系统的存储方式。它就是LSM Tree——Log-Structured Merge-Tree。
一个被写入压垮的时代
时间回到 1990 年代初。那是关系数据库如日中天的年代，Oracle、Sybase、Informix 这些厂商都在打磨同一件事：B 树索引。从 IBM 的 System R 到后来的 MySQL InnoDB，B 树统治了几乎所有磁盘数据库。
但有一类系统开始感到吃力：写入密集型系统。
90 年代的电信计费系统、银行流水记录、早期的传感器采集系统，特征高度一致：
- 数据几乎只追加，很少更新；
- 写入量巨大，且要求持续、稳定；
- 读取相对较少，或者可以接受一点延迟；
- 存储介质是机械硬盘，寻道是最贵的操作。
这里有一个当时工程师心知肚明、却很少被系统性解决的痛点：机械硬盘的随机写代价极高。磁头要在盘片上来回移动寻找目标扇区，一次随机 IO 可能是顺序 IO 的成百上千倍慢。
而 B 树的更新，恰恰天生是随机的——一条记录改了，就要去磁盘上对应的那个页面原地修改。
旧方案为什么绕不过去
数据库厂商当时的做法，是不断优化缓存、优化预读、优化磁盘调度算法，本质上是在"讨好"随机 IO，而不是"消灭"它。
真正提出问题的，是在贝尔实验室系统工作过、后来转向数据库研究的 Patrick O'Neil。他和合作者 Edward Cheng、Dieter Gawlick、Elizabeth O'Neil 注意到一个现象：如果一个系统的写入负载持续高企，那么无论 B 树怎么调优，它终究要为每一次写付出一次随机 IO 的代价。这不是实现问题，是结构性问题。
B 树的设计初衷，是让任意一条记录的查找都能在 O(log n) 的磁盘 IO 次数内完成。这个设计对读非常友好——树的每一层都对应固定的磁盘页面，随手一查就能定位。但代价是：每次插入或更新，都可能触发一次原地修改，甚至一次页分裂。在写入频繁的场景下，磁头要不停地在盘片各处"跳来跳去"，效率断崖式下跌。
当年的工程师并非没意识到这一点，他们用了各种缓解手段：写缓冲区、延迟刷盘、批量提交。但这些都是在掩盖问题，而不是改变问题的本质——数据落盘的顺序，仍然由业务逻辑的写入顺序决定，而不是由磁盘最舒服的方式决定。
哈希表在内存里效率很高，但一旦涉及持久化到磁盘，同样面临"如何有序地、批量地落盘"这个老问题。跳表解决的是内存中有序结构的并发和实现简单性问题，本质上也没有回答"磁盘写入模式"这件事。
其实业内已经有"只追加写日志"的思路，用于崩溃恢复，也就是 WAL。日志文件写入是纯顺序的，磁盘友好。但日志天生的问题是：它只管写，不管查——你要查一条记录，理论上得从头到尾扫一遍日志，这在读多的场景下是灾难。
于是问题变成了：能不能让数据写入像日志一样顺序，同时又能像索引一样被高效查询？
把随机写移出关键路径
1996 年，Patrick O'Neil、Edward Cheng、Dieter Gawlick 和 Elizabeth O'Neil 在《Acta Informatica》发表了论文《The Log-Structured Merge-Tree (LSM-Tree)》。
他们的洞察非常朴素，却极具颠覆性：与其追求每一次写入都立刻组织成最终形态的索引结构，不如把写入攒起来，先顺序地扔到磁盘，再通过后台"合并"的方式，把这些零散的数据逐步整理成有序的整体。
具体来说，LSM Tree 把存储分成了层级：
- 最新写入的数据先进入内存中的一个有序结构，后来的实现常用跳表或红黑树，这部分叫MemTable
- 当内存结构长到一定大小，就整体、顺序地刷写到磁盘上，形成一个不可变的有序文件，这部分叫SSTable
- 磁盘上会积累越来越多的 SSTable，后台有一个合并进程，持续地把多个 SSTable 合并成更大、更有序的文件，顺便清理掉过期或被覆盖的数据。
这个设计的精妙之处在于：所有对磁盘的写操作，无论是刷写 MemTable 还是合并 SSTable，都是顺序写。随机写被彻底移出了关键路径，取而代之的是查询时可能需要多查几个文件——但这个代价可以通过布隆过滤器、索引块等手段大幅压低。
这篇论文在发表当年几乎没有激起太大水花。它更像是一篇工程笔记式的理论总结，而不是一鸣惊人的突破。
十年后，工业界独立走到了同一个结论
真正让它被全世界知道的，是十年后的两篇工业界论文：Google 的 Bigtable（2006）和随后的 LevelDB，以及 Amazon 的 Dynamo（2007）。
Google 的工程师们在设计 Bigtable 时，独立地走向了与 O'Neil 几乎一致的结论，并第一次把 LSM Tree 的思想在超大规模系统中验证成功。
不需要贴太多代码，只看一件事：为什么查询一条记录，要按照"内存 → 最新 SSTable → 更老的 SSTable"的顺序去找？
以 LevelDB / RocksDB 的思路举例，一次 Get(key) 的核心逻辑大致是：
- 先查 MemTable，也就是最新写入、还没落盘的数据；
- 再查 Immutable MemTable，也就是正在被刷盘的旧内存表；
- 再依次查磁盘上各层 SSTable，从最新的层开始。
为什么是这个顺序？因为 LSM Tree 允许同一个 key 出现在多个地方——你更新一条记录，并不是去磁盘上找到它原地覆盖，而是简单地把新版本追加写入。所以，"最新的数据在哪里，就先查哪里"，一旦找到就立刻返回，这样保证了正确性，也保证了大多数情况下不需要扫描全部层级。
从 1996 年那篇无人问津的论文，到今天写入密集型系统的默认选择，LSM Tree 走的是一条很典型的路：先被结构性问题逼出来，再被工业界的大规模实践验证，最后成为基础设施里那个没人提起、却处处都在的名字。
热门跟贴