【数据挖掘】RocksDB结构介绍

引言： 前一篇文章已经介绍过，TIDB的核心存储机制为RocksDB，而RocksDB是一个基于日志结构归并树（LSM树）的KV数据存储引擎。那么RocksDB的系统结构究竟如何？他又相较于前辈LevelDB有了何种优化呢？

01

简介

Rocksdb是由facebook基于leveldb开发的，一套基于LSM树结构的数据存储引擎。针对SSD做过相应的特殊化优化处理，能够高速吞吐PB级的数据，又有极高的IO效率。

02

框架

与其他的LSM树结构的KV数据库基本一致，RocksDB也分为了内存区和磁盘区两个部分。下图为RocksDB的基本结构图。

如图所示，RocksDB的主要部分有：

①ColunFamily（CF）：列族，与HBase中的CF类似，由于将相同类的KV对进行分类存储；

② Memtable：数据内存表，上层写入的数据将被直接写入到此表；

③Immutable Memtable：不可变的内存表，在Memtable达到预设阈值时自动转变为Immutable Memtable，开始flush操作；

④ WAL： Write-Ahead Logging，预写日志，用于数据出错恢复；

⑤SST：磁盘存储数据模块。

03

Column Family

其中CF是RocksDB基于leveldb进行扩充的部分。CF的作用在于将不同类型的数据KV对进行区分开，对数据集进行逻辑上的划分，这能够较好地保证数据独立性。

每个CF中可以简单理解为一个LevelDB，每个CF都包含一个MemTable和多个Immutable Memtable，也有独立的Flush机制，但与LevelDB不同的是，CF之间共享同一个WAL，以保证数据的一致性，避免写不同的WAL出现数据错乱的情况。

04

写数据机制

在RocksDB中，与levelDB不同的是，Rocksdb的写流程时可以并行进行。数据在进行写入到数据库中时，首先会构建相应Writer结构，在通过BatchGroup线程完成调度。

现有的写机制主要有两种:

① 一组数据均有作为Leader的Writer写入，即单线程模式，Leader首先写入WAL后，再写入数据到Memtable中；

②作为Leader的Writer写完WAL后，通知其他Writer，Writer接到Leader的信号后开始并行完成自己的数据写入到Memtable中。

05

管道机制

对于多组数据的写入，正常情况下的写入流程为两个WriteGroup依次写入数据，完成数据写入。RocksDB针对这种情况提供了一种Pipeline Write机制，将写数据的流程转化为流水线的形式，提升写数据效率。

正常的写流程分为写WAL和写Memtable。两个写流程串行时，写开销为2*(Twal+Tmem),而如图的流水线形式能够减少第二次的写WAL的开销。实测管道功能的开启能够带来将近20%的性能提升。

06

Flush机制

一个LSM树结构的存储系统flush操作和compact操作时必不可少的部分。当内存中的memtable数据达到阈值大小时将触发flush机制。对于leveldb，整个系统中只有一个memtable，在该memtable满时，将转变为immutable memtable，同时生成一个新的memtable接受上层的写操作，同时将immutable memtable中的数据转变为SSTable结构，写入到磁盘。而Rocksdb相较于leveldb最大的不同点在于，他的memtable数量不只是一个，他一个memtable满时，系统会直接使用新的memtable来接受数据写入，而不会像leveldb一样等待其转变为immutable memTable，如何再生成一个新的memtable。简而言之就是时刻有空的memtable在准备，而不是需要新的memtable才去构建。

如图为rocksdb的flush源码结构，memtable在满时，转变为immutable memTable，随即加入到待flush的链表中，后台flush线程依次处理将其进行转换为SSTable形式，写入到磁盘中的LSM树第0层。

07

Compaction机制

LSM树结构的Compaction机制基本大同小异，RocksDB相较于leveldb所多的有两点：

1.Compaction与Flush不同线程

Compaction与flush采用不同的线程，可以完成这两个流程的异步化处理，这也是采用多个memtable 导致了，这样子flush线程能够更高效率的完成数据写入，而compaction可以对队列上的数据完成合并操作，异步化能够流水线形式的执行任务，提升性能。

2. SubCompaction

对于LSM树磁盘层的L0层，由于其特殊性，导致了同层的数据块有相应的key值重叠的部分，所以在做每次compaction操作中，很大可能涉及到了整层的数据，这会导致一个compaction涉及的数据量巨大，从而阻塞了compaction下层的执行流程，因此，针对这种情况，Rocksdb提供了subCompaction技术，将一个大的compaction扩展为多个小的子合并过程，完成插入操作，流程图如图所示。

08

总结

总的来说，Rocksdb基于leveldb主要做了三个方面的改动：

① CF，划分数据逻辑分区

②并行化，多线程，提高吞吐率

③多memtable以及队列化，为多线程提供条件

这些特征使得rocksb在leveldb的基础上，拥有了质的提升，也解决了leveldb的一大痛点，compaction时性能停滞的问题，是一个非常大的性能进步。目前更多的研究也集中于对于memtable的结构以及如何降低LSM树的层次上，后续有空的话，我将带来关于降低LSM树层次的论文框架的简介说明。

往期推荐