Facebook 内部都在用的存储引擎，LSM 凭什么能硬扛亿级写入流量？

2025-08-21
新疆
本文字数：3038 字
阅读完需：约 10 分钟

RocksDB LSM 树

RocksDB 是 Meta (Facebook) 开源的高性能持久化键值存储库，源于 Google 的 LevelDB，并针对 SSD 和服务器工作负载进行了深度优化。它广泛应用于需要处理海量数据（亿级甚至更高）并要求高写入吞吐的场景。RocksDB 以 kv 对集合的形式存储数据， key 和 value 是任意长度的字节数组（byte array）。RocksDB 提供了几个用于操作 kv 集合的函数底层接口：

// 插入新的键值对或更新已有键值对put(key, value)// 将新值与给定键的原值进行合并merge(key, value)// 从集合中删除键值对delete(key)// 通过点查来获取 key 所关联的 valueget(key)// 通过迭代器进行范围扫描——找到特定的key，并按顺序访问该key后续的键值对iterator.seek(key_prefix); iterator.value(); iterator.next()

复制代码

LSM 树

RocksDB 的核心数据结构被称为日志结构合并树（Log Structured Merge Tree，LSM Tree）。LSM 树是一种专为写密集型工作负载设计的数据结构，其思想最早由 O'Neil 等人在 1996 年的同名论文提出被大家所知。在 2000 年左右，谷歌发布了大名鼎鼎的"三驾马车"的论文，分别是 Google File System(2003 年)，MapReduce（2004 年），BigTable（2006 年）。其中在 “BigTable” 的论文中很多很酷的方面之一就是它所使用的文件组织方式，这个方法的名字叫 LSM 树。

如上图所示，LSM 树有以下四个重要组成部分。1）MemTable（内存表）：MemTable 是在内存中的数据结构，用于保存最近更新的数据，会按照 Key 有序地组织这些数据，LSM 树未明确定义有序组织的数据结构，例如 RocksDB 使用平衡二叉树来保证内存中 key 的有序。2）Immutable MemTable（不可变内存表）：Immutable MemTable 是将转 MemTable 变为 SSTable 的一种中间状态。写操作由新的 MemTable 处理，在转存过程中不阻塞数据更新操作。3）WAL：因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过预写式日志（Write-ahead logging，WAL）的方式来保证数据的可靠性。WAL 是一个只允许追加（Append Only）的文件，包含一组更改记录序列。每个记录包含键值对、记录类型（Put / Merge / Delete）和校验和（checksum）。与 MemTable 不同，在 WAL 中，记录不按 key 有序，而是按照请求到来的顺序被追加到 WAL 中。WAL 是顺序写的，速度很快。若系统崩溃，可通过 WAL 恢复 MemTable 中的数据。4）SSTable（Sorted String Table，有序字符串表）：SSTable 是一种拥有持久化，有序且不可变的的键值存储结构，它的 key 和 value 都是任意的字节数组，并且了提供了按指定 key 查找和指定范围的 key 区间迭代遍历的功能。SSTable 内部包含了一系列可配置大小的 Block 块，典型的大小是 64KB。与 WAL 的记录类似，每个数据块中都包含用于检测数据是否损坏的校验和。每次从硬盘读取数据时，LSM 树都会使用这些校验和进行校验。当一个 SSTable 被打开的时候，存储在 SSTable 尾部的 index 会被加载到内存，然后根据 key 在内存 index 里面进行一个二分查找，查到该 key 对应的硬盘的 offset 之后，然后去硬盘把相应的块数据读取出来。

数据写入

写入一个<Key, Value>时，LSM 树的写入顺序是：1）写操作记录到 WAL（顺序写）。2）写操作插入到内存中的 MemTable（有序插入）。3）当 MemTable 写满，转换为 Immutable MemTable，同时创建新的 MemTable 和 WAL 文件接收新写入。4）后台线程将 Immutable MemTable 的数据顺序写入磁盘，生成一个新的 SSTable 文件，通常放在 Level-0 层。5）刷盘完成后，对应的 WAL 文件可以被安全删除。所有磁盘写入（WAL 和 SSTable）都是顺序的，极大地提高了写入吞吐。MemTable 的默认大小为 64 MB。 LSM 树定期把内存写满的 MemTable 转变为 Immutable MemTable ，并从内存持久化到硬盘。一旦刷盘（flush）完成，Immutable MemTable 和相应的 WAL 就会被丢弃。LSM 树写入新的 WAL、MemTable。每次刷盘都会在 Level 0 层上产生一个新的 SSTable 文件。该文件一旦写入硬盘后，就不再会修改。有序性使得 MemTable 刷盘时更高效，因为可以直接按顺序迭代键值对顺序写入硬盘。将随机写变为顺序写是 LSM 树的核心设计之一。

数据删除

对于需要删除的数据，LSM 树采用一个特殊的标志位，称为墓碑（tombstone），删除一条数据就是把它的值置为墓碑。如果查询当前数据，返回的是空值。因此，删除操作的本质是覆盖写，而不是清除一条数据，墓碑会在合并机制中被清理掉，于是置为墓碑的数据在新的 SSTable 中将不复存在。

合并机制

由于 SSTable 不可修改，更新和删除操作实际上是写入新的记录（更新是新版本，删除是打上“墓碑”标记 Tombstone）。这样的设计虽然大大提高了写性能，但同时也会带来一些问题。1）空间放大 (Space Amplification)：磁盘上可能存在同一 Key 的多个版本或已删除的“墓碑”，占用额外空间。2）读放大 (Read Amplification)：查询一个 Key 时，可能需要从 MemTable 查起，然后逐层（从新到旧）查找多个 SSTable，直到找到该 Key 或确认不存在。3）写放大 (Write Amplification)：实际写入磁盘的数据量远大于用户写入的数据量，因为数据在合并过程中会被多次重写。合并 (Compaction)机制是 LSM 树维持性能和控制放大的关键：后台线程定期将不同层级（Level）的 SSTable 进行合并。合并过程会读取多个旧 SSTable，将它们的有序键值对归并排序，丢弃被覆盖的旧值和已删除的墓碑，然后将结果写入新的 SSTable（通常到下一层）。通过这种方式，减少 SSTable 数量（降低读放大）、回收无效数据占用的空间（降低空间放大）。然而合并本身是 I/O 密集型操作，会产生写放大，消耗处理器和磁盘带宽。RocksDB 提供不同的合并策略，如：Leveled Compaction (分层合并)：将数据组织成多个层（L0, L1, L2...）。L0 的 SSTable 可能有重叠的 Key 范围，L1 及以上层 SSTable 的 Key 范围通常不重叠。合并时，从 Ln 层选择一个 SSTable，与 Ln+1 层中 Key 范围重叠的 SSTable 进行合并。这种策略读放大较小，但写放大可能较高。Tiered Compaction (分级合并，也称 Universal Compaction)：将 SSTable 按大小或时间分组，组内合并，或将多个小 SSTable 合并成一个大 SSTable。写放大较低，但读放大可能较高。 RocksDB 允许用户根据应用特性选择和配置合并策略，以在读、写、空间放大之间取得平衡。

数据查询

查询一个 Key 时，LSM 树的查找顺序是：1）Active MemTable。2）Immutable MemTable。3）SSTables on Level-0 （可能有多个，Key 范围可能重叠，需逐个查）。4）SSTables on Level-1, Level-2, ..., Level-N（每层内 Key 范围不重叠或部分不重叠，可快速定位）。LSM 树在内存中对每个 SSTable 维护一个稀疏索引（Sparse index）。稀疏索引是指将有序数据切分成（固定大小的）块，仅对各个块开头的一条数据做索引。与之相对的是全量索引（Dense index），即对全部数据编制索引，比如 MySQL 采用 B+树作为索引结构。有稀疏索引之后，可以先在索引表中使用二分查找快速定位某个 key 位于 SSTable 哪一小块数据中，这样仅从硬盘中读取这一块数据即可获得最终查询结果，此时加载的数据量仅仅是整个 SSTable 的一小部分，因此 I/O 代价较小。然而当要查询的结果在 SSTable 中不存在时，将不得不依次扫描完所有的层级 SSTable，这是最差的一种情况。因此，为加速查询，特别是查询不存在的 Key，每个 SSTable 通常会关联一个布隆过滤器（Bloom Filter）。查询时先查布隆过滤器，若告知 Key“肯定不存在”，则可直接跳过该 SSTable 的实际读取，显著减少不必要的 I/O。布隆过滤器有一定假阳性率（可能误报“存在”），但绝无假阴性（不会漏报）。