一文总结存储引擎和相关资料分享

存储引擎（storage engine），有时候也称数据库引擎（database engine）。用于支撑数据库管理系统（DBMS）底层的 CRUD。当然，这里的数据库，不仅是关系数据库，还有各种 NoSQL 数据库，比如 KV 存储、文档型数据库、图数据库等等。比如 ，[TiDB](https://github.com/pingcap/tidb) 底层用的 [RocksDB](https://github.com/facebook/rocksdb)，[Etcd](https://github.com/etcd-io/etcd) 底层用的是 [BoltDB](https://github.com/boltdb/bolt)，[MongoDB](https://www.mongodb.com/) 底层用的是 [wiredTiger](https://www.mongodb.com/docs/manual/core/wiredtiger/)。

概述

存储引擎本质上就负责两件事：数据存储和数据读写。前者关注，如何以最小代价安全的存储数据，会涉及到存储格式设计、数据压缩和数据加密、数据冗余等技术。后者关注，如何提供高性能的读写，包括尽可能低的延迟，尽可能高的吞吐。但我们都知道，在系统设计时，不可能既要又要，只能根据实际情况做取舍。

常用的用于衡量存储引擎的两个指标有：**存储放大**和**读写（IO）放大**。可以从这个方向来考虑这两个指标，就是我们将存储引擎当做白盒，真实的存储和读写，与我们将其当做黑盒，外部给到的存储和读写，之间的比值。以存储放大为例，如果用户写入一份数据，由于存储引擎的设计（比如垃圾和数据冗余的存在），最终在磁盘上会产生 N 份数据，则称其存储放大为 N。

存储引擎在设计上分为[两个流派](https://ddia.qtmuniao.com/#/ch03)：日志追加流（log-structured）和原地修改流（update-in-place）。前者代表数据结构是 LSM-Tree，工业界的实现有 LevelDB、RocksDB 等。后者代表数据结构是 B-Tree，工业界的实现有 WiredTiger、BoltDB 等等。

最后，从用户接口（user interface）上来说，存储引擎一般都提供最简单的 KV 接口，上层 DBMS 再根据需求，封装出关系接口、文档接口或者图接口等等。


Log-Structured

所谓日志结构，就是指在向存储引擎写入数据时，直接向数据文件追加。然后当数据文件到达一定尺寸之后，就会另起一个文件。至于相同 key ，后写入的如何覆盖先写入的？可以在内存中维护一个 key → data file + offset 哈希表，只需要修改哈希表相应 key 的指向即可。这种 log-structure 与哈希表的比较简单的组合，称为 Bitcask，对应论文是：https://riak.com/assets/bitcask-intro.pdf

LSM-Tree ，全称 Log-Structured Merge-Tree ，论文是 https://www.cs.umb.edu/~poneil/lsmtree.pdf 。 在 Bitcask 基础上，常见的 Log-Structured Merge-Tree 实现，比如 LevelDB，有以下优化：

• 内存中的索引结构更加复杂，通常用跳表或者平衡树，称作 MemTable（内存表）。
• 磁盘上的数据内容变成有序，由内存数据结构顺序写入而来，称作 SSTable（有序字符串表）。
• 写数据先写内存，而非直接写数据文件。为了避免宕机丢数据，引入了写前日志（WAL）。
• 后台会自动对已有的有序数据文件（SST）进行多路归并，以回收空间。
• 为了增加数据命中率，减少磁盘访问，做了 LRUCache。
• 为了避免不必要的 SST 访问，使用 Bloom Filter 。
  

LeveDB 可以参考的资料有：

• 一本很凝练的小册子 leveldb handbook：https://leveldb-handbook.readthedocs.io/zh/latest/
• LevelDB github 仓库文档：https://github.com/google/leveldb/tree/main/doc
• 我的一些数据结构解析文章：https://www.qtmuniao.com/categories/源码阅读/leveldb/
  

RocksDB 在 LeveDB 的基础上，又做了大量的工程优化。如：

• 在接口上，提供多了 Column Family 的支持、 AtomicOP 支持等等
• 在性能上，增加了并行 Compact、前缀过滤、更多的调优参数等等
  

其中的优化细节，可以参考其博客：https://rocksdb.org/blog/ 。
由于其众多优化，也因此成为了很多数据库的底层存储引擎，比如 TiDB，CockroachDB，MyRocks 等等。

TiDB 一些关于 rocksdb 的博客：
https://cn.pingcap.com/blog/?tag=RocksDB
https://github.com/pingcap/blog/blob/master/rocksdb-in-tikv.md

CRDB 关于 rocksdb 的博客：
https://www.cockroachlabs.com/blog/cockroachdb-on-rocksd/
https://www.cockroachlabs.com/blog/pebble-rocksdb-kv-store/

其中 Pebble 是 CRDB 在 RocksDB 基础上，用 go 重写的，并增加了分区等优化。

业界比较有名的对 LSM-Tree 的优化还有 Wisckey，将 KV 分开存储：https://www.usenix.org/system/fi ... ast16-papers-lu.pdf
我写过一篇解析文章：https://www.qtmuniao.com/2020/03/19/wisckey/

未完待续，欢迎关注我的系统专栏：https://xiaobot.net/p/system-thinking。

如果觉得对你有帮助的话，求米求米~