InnoDB和RocksDB存储引擎解析

引言

数据库存储引擎为数据库提供了数据的读（查询）和写（创建、更新、删除）操作，不同的存储引擎提供了不同的存储机制、索引技巧、事务操作等功能。同时，存储的数据达到一定体量，存储引擎性能也是各不相同。本文将围绕InnoDB和LevelDB两种存储引擎，从数据读写应用场景入手分析各自的架构特点、采用的数据结构以及各自的优缺点，并以此作为存储引擎选型的依据。

InnoDB

基本介绍

InnoDB存储引擎支持事务，设计目标用于在线事务处理(OLTP)的应用，作为MySQL数据库最为常用的存储引擎之一。该存储引擎是第一个完整支持ACID事务的MySQL存储引擎，具有行锁设计、MVCC(多版本控制并发)、外键、一致性非锁定读的特点，可以有效利用内存和CPU资源。

体系结构

InnoDB存储引擎架构主要由多个后台处理线程+内存缓冲池+本地磁盘文件构成。如下图所示：

（1）线程划分

• Master Thread: 负责将缓冲池的数据异步刷新到磁盘，保证数据一致性，包括脏页（发生修改的页）刷新、合并插入缓冲、undo页回收等；
• IO Thread: 采用异步IO处理写IO请求，提高数据库性能，分布式read、write、insert buffer、log这四个IO线程；
• Purge Thread: 事务调提交后，undo页可能不再需要，通过Purge Thread线程进行回收；
• Page Cleaner Thread: 为了提升存储引擎性能，将脏页刷新操作独立出来，减轻Master Thread工作量和查询阻塞问题。

（2）内存划分

• 缓冲池：由于CPU速度远高于磁盘读取速度，故采用缓冲池技术提高数据库性能，数据以页的形式组织管理。
  • 缓冲池中页被修改后，通过checkpoint机制刷到磁盘；
  • 缓冲池支持多实例，通过hash方式将页均匀加载到不同实例，提高并发能力；
  • 通过改进的LRU算法管理数据，通过old和new划分，避免偶尔的数据扫描替换掉热点数据；
  • 支持对页的压缩，将原本默认16 KB的页压缩到1 KB、2 KB、4 KB和8 KB。
• 重做日志缓冲：重做日志先写入缓冲，通过一定机制再写入磁盘重做日志文件。重做日志文件记录了存储引擎的事务日志（write ahead log），当发生宕机时用于数据恢复，保证数据完整性。
• 额外内存池：用于缓冲区内部一些其他控制信息或数据结构需要的额外内存。

索引机制

InnoDB存储引擎支持的常见索引有B+树索引、全文索引以及哈希索引（根据表适用情况自适应创建，不对外）。其中，B+树索引是目前关系型数据库中查询最为常用和最为有效的索引。

（1）B+树结构

B+树由二叉查找树->平衡二叉树->B树（多路平衡查找树）演化而来，为基于磁盘或其他存储设备之上的文件系统所需而设计的一种多路平衡查找树。

在B+树中所有记录节点都是按照键值大小顺序放在同一层叶子节点上，由各节点指针进行连接。相对B树来说，非叶子节点上读取一次磁盘可以存放更多的关键词元素，从而降低了IO的读写次数。

（2）关键特性

• 支持范围查询，基于索引节点，定位到叶子节点链表起始点和结束点直接遍历；
• 适合OLTP的场景，根据索引条件过滤出少量数据；
• 任何查询都需要从根节点到叶子节点，路径相同，查询稳定；

（3）B+索引应用

B+索引是B+树在数据库中的实现，在MySQL中分为聚集索引（clustered index）和辅助索引（secondary index）。聚集索引中叶子节点记录了整个表行记录，因此一个表只有一个聚集索引。但是每张表可以多个辅助索引，辅助索引中的叶子节点存储了bookmark，指向行记录在聚集索引中的索引键。

RocksDB

基本介绍

RocksDB是使用C++编写的、LSM结构的、嵌入式KV存储引擎，由Facebook基于LevelDB开发，还借鉴了许多HBase的设计理念。RocksDB依靠大量灵活的配置，使之能针对不同的生产环境进行调优，包括直接使用内存，使用Flash，使用硬盘或者HDFS。支持使用不同的压缩算法，并且有一套完整的工具供生产和调试使用。

体系结构

RocksDB存储引擎是基于LSM（Log Structure Merge Tree）思想实现的，内存结构memtable和immutable memtable，immutable memtable用于flush到磁盘形成SST文件，不同SST、Level之间的merge操作称为compaction。manifest记录了引擎的状态和SST修改快照信息，current标识当前正在使用的manifest（SST生成新的，manifest也会生成新的）。由于RocksDB是基于LevelDB构建，下面给出两个引擎的架构图作为对比。

RocksDB在LevelDB基础上引入列簇的概念，每个ColumnFamily有自己的Memtable， SST文件，所有ColumnFamily共享WAL、Current、Manifest文件。

（1）写入流程

数据写入时，先追加到WAL再写入memtable。memtable写满后转为immutable memtable，等待flush到第0层SST，触发条件后再compaction到第1层SST，依次类推到第N层SST。

flush操作将多个immutable memtable合并排序后，持久化到第0层SST文件中，由于该层SST文件并没有做compaction操作，因此不同SST之间存在key重复。

compaction操作将本层的SST和上一次层的SST进行合并操作，因此第1层以上的SST文件key都是唯一的。

（2）读取流程

读取的顺序为memtable->immutable memtable->level 0 SST->…->level n SST。其中，memtable和immutable memtable采用了跳表特性进行查询，SST文件中有过滤器（布隆过滤器）决定是否包含某个key再加载至内存，基于有序KV进行二分查找。同时，在memtable和SST之上还设置了Block Cache，提高查询性能。

索引机制

RocksDB采用的内存结构memtable和外存结构SST，决定了RocksDB能够支持点查和范围查询。

（1）Memtable

内存中的数据结构，在数据flush到SST之前用来保存数据的，可用于读写。写入数据时首先插入memtable，写满后转为immutable memtable，等待flush到SST中。读取数据时也是优先读取memtable中，数据相对于SST比较新。支持如下两类数据结构：

• Skiplist MemTable：基于skiplist的memtable为读写、随机访问和顺序扫描提供了良好的性能，支持范围查询
• HashSkiplist MemTable：hash和skiplist的结合，按照key的前缀做hash，每个hash桶中都是一个skiplist。单独访问一个key时性能更好，相对于skiplist减少了比较次数，夸多个前缀进行扫描需要复制和排序，范围查询性能也会差一些。

（2）SST

SST是Sorted Sequence Table（排序队列表），是排好序的数据文件。在这些文件里，所有键都按照排序好的顺序组织，一个键或者一个迭代位置可以通过二分查找进行定位，支持两种结构：

• Block-based Table格式：该方式是RocksDB的默认SST格式。内部结构按照块的方式组织，详情见github wiki。

<文件开始>
[data block 1]                                (排好序的KV，二分查找)
[data block 2]
...
[data block N]
[meta block 1: filter block]                  (过滤器)
[meta block 2: stats block]                   (属性)
[meta block 3: compression dictionary block]  (压缩字典)
[meta block 4: range deletion block]          (see section: "range deletion" Meta Block)
...
[meta block K: future extended block]  (后期会添加更多的元数据块)
[metaindex block]                      (元数据索引块，指向多个元数据块位置)
[index block]                          (数据索引块)
    [index block - partition 1]        (按照Key的范围创建的索引)
    [index block - partition 2]
    ...
    [index block - partition N]
    [index block - top-level index]    (先将顶级索引加载到内存，然后按需加载对应分区索引)
[Footer]                               (固定大小; 指定数据索引块的top-level index和元数据索引块)
<文件结束>

• PlainTable格式：RocksDB针对纯内存或低延迟介质上的低查询延迟进行了优化。详情见github wiki。

对比分析

InnoDB属于B树存储引擎，RocksDB属于LSM树存储引擎。存储引擎不同的存储结构、策略，决定了不同的读写应用场景。

（1）B树存储引擎

针对InnoDB，按照页来组织数据，每个页对应B+树的一个节点。读取操作B+树一次检索最多需要h-1次磁盘IO（h为树的高度）。写入操作需要对内存中的B+树进行修改，修改的页超过比率后在持久到磁盘。因此，InnoDB适合写少读多的场景。

（2）LSM树存储引擎

针对RocksDB，LSM结构体现在对数据修改增量保持在内存，达到阈值后将修改操作批量写入磁盘，读取时需要合并磁盘中的历史数据和内存中最近的修改操作。因此，RocksDB的LSM机制牺牲了读的性能，提高了写入的性能，适合写多读少的场景。

参考资料

• 《大规模分布式存储系统·原理解析与架构实战》
• 《MySQL技术内幕 InnoDB存储引擎第2版》
• 从B树、B+树、B*树谈到R树
• RocksDB中文网
• https://github.com/facebook/rocksdb/wiki/
• 看图了解RocksDB