从 LSM-Tree 原理到 OceanBase 存储架构实践在前面的文章中我们提到OceanBase 和 TiDB 这两款主流分布式数据库并没有沿用传统的 HEAP 或 B 树存储引擎而是选择了LSM-Tree架构。事实上LSM-Tree近年来在业界颇受欢迎——无论是大数据领域的 HBase、Cassandra还是 LevelDB、LuceneES 的底层引擎或是分布式NewSQL领域的 OceanBase 、TDSQL 新敏态存储现名 TDSQL Boundless以及 TiDB 底层的存储RocksDB都采用了LSM-Tree作为核心存储引擎。这期文章我们就以 OceanBase 为例来深入聊聊LSM-Tree的设计原理与工程实践。1. LSM-Tree1. LSM-Tree1.1 概念LSM 树Log-Structured Merge-tree日志结构合并树是一种专为高吞吐写操作设计的持久化存储数据结构。它并不是一棵具体的物理树而是一种将内存数据结构与磁盘文件系统结合的多层存储架构思想。传统数据库如 MySQL InnoDB采用的 B 树依赖“就地更新In-place Update在面对海量写入时会导致大量的磁盘随机 I/O。LSM 树的核心思路是将随机写转换为顺序追加写Append-only以此榨干机械硬盘和 SSD 的极限写入带宽。1.2 LSM 树的核心架构组件LSM 树将存储层分为内存组件与磁盘组件两部分1. 内存层MemoryWAL预写日志 所有写操作在进入内存前会先以顺序追加的方式写入磁盘上的 WAL 文件用于崩溃恢复。这一机制是几乎所有数据库的共性设计——只要内存的成本仍远高于磁盘WAL 就不会退出历史舞台。WAL 只为内存中的 MemTable提供崩溃恢复担保MemTable刷盘生成SSTable后对应的 WAL 即可整块物理删除。InnoDB的Redo Log为内存中的 Buffer Pool​ 提供崩溃恢复担保以固定大小循环覆盖使用崩溃恢复时Redo Log需要与磁盘上 B 树旧页的 LSN 进行比对校验将未落盘的数据页恢复到一致状态。两者的本质差异在于LSM-Tree 的 WAL 是一次性消费而 InnoDB 的 Redo Log 是循环复用。MemTable内存表驻留在内存中的有序数据结构通常基于跳表SkipList或红黑树实现负责直接处理所有的数据写入。在LSM-Tree的设计哲学中MemTable将所有修改、更新、删除操作在逻辑上统一转化为了“插入”操作。由于数据操作全程在内存中完成无需磁盘 I/O因此能够提供极致的写入与读取性能。InnoDB的写入需要先定位到Buffer Pool中的目标数据页对记录进行原地更新修改现有行或标记删除 purge 线程后续异步清理。这意味着 InnoDB 的写入路径上伴随着数据页的查找、加锁与可能的页分裂且脏页最终需要随机刷回磁盘。MemTable的 一切皆插入​ 规避了原地修改的复杂性将所有的写压力转化为内存中的顺序/随机插入再异步批量落盘这也是LSM-Tree写入吞吐通常高于 B 树的核心原因。Immutable MemTable冻结内存表由于内存空间有限当MemTable达到大小阈值后系统会触发冻结Freeze机制当前MemTable被切换为只读状态Immutable MemTable同时系统会立刻开一个新的MemTable继续接收新数据。LSM-Tree的“写冻结、后台刷”的设计巧妙地将原本需要同步等待的磁盘落盘操作转化为了后台线程的异步 Flush 任务从而彻底解耦了用户写入与磁盘 I/O保证了写入的低延迟。InnoDB依赖Checkpoint 机制​ 来推进刷脏页当Buffer Pool中脏页比例过高或Redo Log空间即将写满时后台线程会将脏页随机刷回磁盘 B 树中。虽然 InnoDB 也尽力将刷盘异步化但脏页的随机写特性以及 Checkpoint 推进不及时时可能触发的前台线程同步刷脏Sharp Checkpoint都会对写入延迟造成抖动为此Innodb引入了Fuzzy Checkpoint、组提交等机制。2. 磁盘层DiskSSTableSorted String Table排序字符串表磁盘上的不可变文件。内部记录按Key升序排列并包含索引块Index Block和布隆过滤器Bloom Filter以支持高效的点查与范围扫描。一旦生成SSTable永不修改后续的更新和删除只是往新的SSTable中追加记录并通过Compaction机制在后台异步回收旧版本数据和墓碑。SSTable 是写后即只读的任何修改都不会触碰已有文件而是写入新的 SSTable这彻底消除了随机写和原地更新的复杂性。代价则是需要后台Compaction来回收空间。Multi-Level分层组织SSTable 在磁盘上按层级Level 0, Level 1, Level 2…存放层级越高存储的数据量越大且数据整体呈冷→热分布——L0 靠近写入端数据最新、最热越往下层数据越旧、越冷。每一层内的SSTable文件之间Key范围互不重叠L0 除外且层间容量通常呈十倍递增如 RocksDB 的 10 倍放大策略形成天然的漏斗结构。1.3 LSM-Tree 的优点1. 极致的写入吞吐量转随机写为顺序写LSM-Tree采用追加写机制。所有写操作插入、更新、删除先写入内存的MemTable满后异步顺序批量刷盘生成SSTable彻底消除了写入时的随机 I/O 。2. 超高的数据压缩比与空间利用率磁盘上的 SSTable 是完全只读且不可变Immutable的且内部数据按 Key 严格排序。静态文件的特性使其非常适合进行高效的前缀压缩、字典编码或通用压缩如ZSTD、Snappy显著节省磁盘存储成本。3. 高并发下的无锁/轻量锁写入内存写入通常采用无锁或轻量锁的数据结构如跳表SkipList避免了传统 B 树在并发修改时复杂的锁竞争如树结构调整时的Latch Crabbing锁机制并发写入吞吐极高。4. 对 SSD 硬件寿命友好LSM-Tree通过内存缓冲与后台合并将小块写入整合成大块连续写入极大地减少了 SSD 的物理擦除次数显著延长硬件寿命。1.4 LSM-Tree 的缺点发现 LSM 树优点太多了那它有什么缺点呢1. 读放大问题表现当读取一个数据Key时如果该数据不在内存中系统可能需要依次检索 Level 0 到 Level N 的多个SSTable文件才能找到最新版本的数据。缓解方案引入布隆过滤器Bloom Filter快速判断 Key 是否存在于某文件以及使用Block Cache缓存频繁读取的数据块。2. 写放大与 CPU/IO 抖动表现数据虽然最初是顺序写落盘但后台的 Compaction合并进程会不断地把旧 SSTable 读取出来、排序合并后重新写回磁盘。一个数据在生命周期内可能会被重复写入磁盘多次。后果当后台 Compaction 压力过大时会抢占磁盘 I/O 和 CPU 资源导致前台业务写入产生明显的延迟抖动。3. 空间放大问题Space Amplification表现由于采用追加写更新和删除操作只是追加一条带新版本号或墓碑标记Tombstone的记录旧版本数据和被删数据依然保存在磁盘上。后果在后台 Compaction 完成清理之前这些“垃圾数据”会暂时占用额外的磁盘空间。4. 范围查询Range Scan性能相对较弱表现检索某段区间的数据如WHERE id BETWEEN 100 AND 200时由于相同范围的数据可能分散在不同的SSTable文件中系统需要对多个SSTable进行归并排序相比 B 树在单一连续页上的顺序扫描效率稍逊一筹。2. OceanBase 的存储架构OceanBase的LSM-Tree存储架构设计核心在于解决传统LSM-Tree“读放大” 与 “写放大” 的天然矛盾结合了内存数据库的高性能与LSM-Tree的高吞吐特性。2.1 设计原则OceanBase 采用准内存与读写分离的设计原则写数据追加更新所有的更新、插入和删除操作均不直接修改磁盘上的原始数据而是作为增量记录追加写入内存MemTable。写路径先写 WAL 保证持久性再写入MemTable。读数据多版本融合查询时需要将磁盘中的静态基线数据Base SSTable与内存/磁盘中的动态增量数据MemTable/SSTable进行多版本合并。为了解决LSM-Tree读路径过长和读放大严重的问题OceanBase建立了多级缓存架构KVCacheBloomFilter Cache 建立在磁盘宏块Macro Block上的布隆过滤器缓存拦截并提高空查询的效率防止无用 I/O。Row Cache直接缓存热点数据行如果这行数据很热Row Cache直接把这一行缓存在内存中。GET 操作点查命中 Row Cache 可直接返回跳过复杂的 LSM 树多版本归并过程。Block Cache缓存从磁盘读取并解压后的热点数据微块Micro Block减少磁盘数据解压带来的 CPU 消耗。Block Index Cache缓存热点微块的索引加速微块数据的访问。Fuse Row Cache缓存“熔合结果”行的快照点数据即使内存和磁盘都有缓存每次读都要把“磁盘基线页”和“内存增量段”拉出来现场做一次重组FuseCPU 消耗极高。Fuse Row Cache熔合行缓存直接把重组好之后的、最终形态的那一行数据缓存在内存里。只要这行数据后续没有新的写入下一次点查直接拿走最终快照绕过了LSM-Tree复杂的合并读取流程。2.2 动态数据和静态数据1. MemTable动态数据结构MemTable是LSM-Tree中增量数据在写内存中的组织形式每个分区对应一个MemTable。插入、更新、删除时数据写入内存块由BTree和Hash Table双索引指向对应数据指针。传统的 LSM-Tree如 RocksDB在 MemTable 中通常只采用单一的跳表SkipList。跳表虽然能够以O(log⁡N)O(\log N)O(logN)的复杂度同时支持插入、点查和范围扫描但在极高并发的 OLTP 场景下存在两大局限点查性能不极致点查根据 Key 获取 Value在跳表中仍需O(log⁡N)O(\log N)O(logN)的指针跳转远不如 Hash 索引的O(1)O(1)O(1)。CPU 缓存命中率低跳表节点零散分布在内存中频繁的指针追溯对 CPU Cache 极其不友好。在此架构下内存中的 MemTable 被拆分为数据存储区与索引区Hash Table哈希索引—— 极致的点查加速 (O(1)O(1)O(1))作用专门服务于SELECT * FROM t WHERE id 123或UPDATE/DELETE这类基于主键/唯一索引的点查与更新操作。原理将 Key 进行 Hash 映射直接定位到槽位指针直接指向数据区中的最新行版本。避免了树形结构的层层比较将点查延迟降低到物理极限。BTree B 树索引—— 高效的范围扫描 (O(log⁡N)O(\log N)O(logN))作用专门服务于WHERE id 100 AND id 200或ORDER BY这类范围查询与归并合并Compaction操作。原理BTree 的叶子节点之间天然有序且节点连续相比 SkipList对 CPU Cache 更友好。范围查询时通过 BTree 快速定位到起始 Key随后沿着叶子节点顺序遍历指针即可。Data Heap / Block真实行数据区存储内容存放实际的 Key-Value、多版本控制信息MVCC 的事务时间戳/版本号以及修改标记如 Tombstone 墓碑。解耦设计索引节点不直接嵌套完整数据只保存指向数据区的 64 位内存指针。这种“索引与数据分离”的设计使得构建双索引的开销被降至最低。数据结构优点缺点BTree数据按主键有序适合范围查询。单行查找需进行大量主键比较理论性能比 Hash Table 慢。Hash Table可根据主键快速定位到行适合单行点查。不适合范围查询。2. SSTableSSTable是 LSMTree 架构中表数据在磁盘中的存储形式。当数据从内存落盘写入到SSTable后应用程序对数据的修改将不会改变已经落盘的数据版本。OceanBase的磁盘层摒弃了传统文件系统离散分配页面的方式将SSTable划分为两级物理结构宏块Macro Block尺寸固定为 2 MB。作用磁盘空间分配与物理 I/O 的基本单位。OceanBase采用类似“文件系统”的连续块分配模式管理更高效基本消除了磁盘碎片。微块Micro Block尺寸默认为 16 KB 左右可变长。作用数据编码Encoding与通用物理压缩Compression的基本单位也是内存 Block Cache 载入的基本粒度。优势查询时仅需解压命中的 16 KB 微块而不需要读取整块 2 MB 宏块极大节省了 CPU 与内存。2.3 分层转储与合并机制磁盘层的数据由转储Minor Compaction和合并Major Compaction动态生成分为三种主要形态Mini SSTableL0 层来源内存中的 Active MemTable 冻结为 Frozen MemTable 后写盘生成该过程称为Mini Compaction转储。特点写入速度极快数据未做深度重排与重压缩保留了全量增量数据版本L0 层允许存在多个 Mini SSTable。Minor SSTableL1 层来源L0 层的多个 Mini SSTable 归并为一个 Minor SSTable该过程称为Minor Compaction。特点消除多份 Mini SSTable 之间的冗余中间版本降低读路径上的 SSTable 层数通常只有一个 Minor SSTable。Major SSTableL2 层 - 基线数据来源由 Minor SSTable 与原 L2 层的 Major SSTable 进行全量归并生成。用来存放基线数据由Major Compaction合并产生。特点包含了表的完整静态数据应用自研的行列混存编码如字典、RLE 等与高级物理压缩算法是数据压缩比最高的层级。回顾完OceanBase的存储架构LSM-Tree之所以在现代分布式数据库中取代传统的 B 树主要是针对其天然的“读放大”和“写放大”短板在工程层面** 进行了如下突破内存端抛弃传统SkipList采用“BTree Hash Table”双索引兼顾极致的点查与范围扫描缓存端引入Fuse Row Cache熔合行缓存避免每次点查都现场重组基线与增量数据磁盘端采用“2 MB 宏块 16 KB 微块”的两级连续分配架构配合低峰期的每日大合并Major Compaction有效理顺了 LSM-Tree 在高并发 OLTP 场景下的读写性能。这里是《实战派K8SDB》更多干货敬请关注公众号。如果本文对你有所帮助欢迎点赞、推荐和转发也欢迎关注后续文章一起考证、一起学习 Oceanbase 分布式数据库。