开源单机存储引擎之 LSMTree

由于工作相关和个人兴趣，之前收集、调研了不少开源的单机存储引擎——精力有限，有些仔细研究过代码，有些只简单浏览和看看文档。整理此文，方便以后参考。

LSMTree^[1] 是最近几年非常流行的存储引擎，全称是 log-structured merge-tree。

LSMTree 是一种写优化（牺牲读性能）的数据结构。网上关于 LSMTree 的资料很多，这里不多言。

LevelDB^[2]

LevelDB 是我最早接触的 LSMTree 存储引擎，也是曾经学习最深入的。

我觉得它最大的特点就是——“精巧”：

1. 核心代码量只有区区 2 万多行，走读甚至精读一遍代码都花不了太多时间。
2. 实现上，倾向于通用性、简单性，而不是性能。这点对只有 C++ 基础的初学者非常友好。
3. 最新版的代码已经用 C++11 简单重构了一遍。

关于 LevelDB，网上的资料汗牛充栋。我之前也写过一系列 LevelDB 的源码解析文章，这里毛遂自荐一下：LevelDB 完全解析（点击跳转），建议搭配官方代码进行品尝。

RocksDB^[3]

RocksDB 应该是当下最流行的 LSMTree 存储引擎。它是从一个 LevelDB 的 fork 开始的，一路发展过来，加入了许多性能优化和新功能，具体可以参考 RocksDB 的 wiki^[4] 和 RocksDB 的官方博客^[5]。

相比 LevelDB，目前的 RocksDB 要复杂许多，要人肉阅读所有代码逻辑估计有点压力也没必要，建议带着问题去看看 RocksDB 的实现。

另外，MyRocks^[6] 是一个基于 RocksDB 的 MySQL 存储引擎。

Badger^[7]

Badger 是一个 Go 语言实现的 LSMTree 存储引擎。

相比 RocksDB，它最大的特点是基于论文 WiscKey: Separating Keys from Values in SSD-conscious Storage^[8]，实现了键值分离，有效减小了写放大。

Pebble^[9]

Pebble 是著名的 NewSQL 项目 CockroachDB^[10] 的存储引擎。CockroachDB 最开始使用的是 RocksDB（Why we built CockroachDB on top of RocksDB^[11]），后来因为某些原因（Introducing Pebble: A RocksDB Inspired Key-Value Store Written in Go^[12]）替换成 pebble。

Pebble 可以认为是 CockroachDB 为自己量身定制（主要是简化，当然也包含一些优化，参考：Pebble vs RocksDB: Implementation Differences^[13]）的 RocksDB，用 Go 语言编写（CockroachDB 也是用 Go 语言编写的）。

TerarkDB^[14]

TerarkDB 是一个基于 RocksDB 开发的存储引擎，主要是优化了长尾延迟、吞吐量和压缩率。

TerarkDB 并没有大刀阔斧地修改 RocksDB，其最大的特点是实现了一种新的 SST 存储结构 TerarkZipTable^[15]，其特点是拥有极高的压缩率（当然，消耗的 CPU 也会高一些）。

参考资料