RocksDB源码分析-接口下的数据结构

RocksDB是非常流行的KV数据库,是LSM-Tree数据库的典型代表,很多分布式数据库NewSQL、图数据库都使用RocksDB作为底层存储引擎,RocksDB在稳定性和性能等方面都比较出色。

HugeGraph图数据库底层也支持RocksDB作为后端存储引擎,HugeGraph使用的是Java语言,RocksDB是C++语言编写,幸好官方提供了Java JNI接口可直接使用。RocksDB的功能非常聚焦,可以简单理解为其提供一个个Map来存取键值对,所以核心接口基本就是put、get、scan等,使用起来还是比较简单。不过简单的接口下面,蕴含了非常复杂的内部结构,本文对其接口下的几个核心结构进行分析。

最频繁使用的RocksDB接口:

  • RocksDB:数据库实例,所有操作的入口

  • ColumnFamilyHandle:CF描述符,类似文件描述符,可简单理解为Map的指针

  • RocksIterator:查询迭代器,scan查询的操作接口

 

先看几个问题:

  1. Iterator、ColumnFamilyHandle 背后的是怎么把 MemTable、ImmMemTable、Manifest、SST 等组织起来的?

  2. 要查找某个 CF 中指定key范围的值,如何定位到某个文件的某个位置?

  3. Iterator 的生命周期如何管理?在 CF close 之后 Iterator 如何保持依旧可用而不被释放?

 

重点类结构及其关系:ColumnFamilyHandle

ColumnFamilyHandle <--- ColumnFamilyHandleImpl ---+ ColumnFamilyData  ---+ SuperVersion   -----------------------+ Version current ------------------+ uint64_t version_number
                                                  + MemTable mem         + MemTableListVersion imm               + ColumnFamilyData cfd
                                                  + MemTableList imm     + MemTable mem                          + VersionStorageInfo storage_info (SSTs meta)
                                                  + Ref refs             + Ref refs
                                                  + ColumnFamilyOptions

 

ColumnFamilyHandle是CF(类似表Table)的描述符,从创建CF或打开数据库时,就可以拿到各CF的Handle,对表的任何操作都需要ColumnFamilyHandle描述符来进行,比如put、get、scan,如示例:rocksdb.put(cfHandle, key, value)。

ColumnFamilyHandle可通过如下示例代码获取:

cfHandle=RocksDB.createCF()

cfHandles=RocksDB.open(cfNames) 

ColumnFamilyHandle下层的ColumnFamilyData则管理着CF的各种状态、资源,包括memtable、immutables,以及通过SuperVersion管理CF的元数据,如当前版本号、SSTs文件信息等,而所有的ColumnFamilyData都放在db实例的ColumnFamilySet中。

 

重点类结构及其关系:Iterator

Iterator <--- ArenaWrappedDBIter ---+ DBIter db_iter ----------+ InternalIterator iter <------- MergingIterator ---+ vector<InternalIterator> children  ---+ MemTableIterator memtable
                                    + Arena arena              + bool valid                                        + MergerMinIterHeap minHeap             + MemTableIterator immutables
                                    + uint64_t sv_number       + IterKey saved_key                                 + InternalIterator current              + BlockBasedTableIterator level 0
                                                               + string saved_value                                                                        + LevelIterator level 1~n
                                                               + SequenceNumber sequence
                                                               + iterate_lower_bound、iterate_upper_bound、prefix_start_key
                                                               + user_comparator、merge_operator、prefix_extractor
                                                               + LocalStatistics local_stats

查询时,最外层使用RocksDB.newIterator(cfHandle)来得到Iterator,进一步通过Iterator来查询指定CF的数据,除了点查get操作根据key获得value外,其它所有查询都是基于Iterator之上的,包括全表扫描、范围查找(大于、小于、区间)、前缀查找等。Iterator涵盖内容和生命周期都比较复杂,读取路径基本蕴含RocksDB的大部分关键概念。

 

构建最外层迭代器:RocksDB.newIterator(cfHandle) 调用栈:

ArenaWrappedDBIter::Init 0x7feefb8f5c00, allow_refresh_=1
ArenaWrappedDBIter::Init()
 0   librocksdbjni3300438414871377681.jnilib 0x0000000121dc8236 _ZN7rocksdb18ArenaWrappedDBIter4InitEPNS_3EnvERKNS_11ReadOptionsERKNS_18ImmutableCFOptionsERKyyyPNS_12ReadCallbackEbb + 214
 1   librocksdbjni3300438414871377681.jnilib 0x0000000121dc85ba _ZN7rocksdb25NewArenaWrappedDbIteratorEPNS_3EnvERKNS_11ReadOptionsERKNS_18ImmutableCFOptionsERKyyyPNS_12ReadCallbackEPNS_6DBImplEPNS_16ColumnFamilyDataEbb + 266
 2   librocksdbjni3300438414871377681.jnilib 0x0000000121d640f9 _ZN7rocksdb6DBImpl11NewIteratorERKNS_11ReadOptionsEPNS_18ColumnFamilyHandleE + 617
 3   librocksdbjni3300438414871377681.jnilib 0x0000000121c8757e Java_org_rocksdb_RocksDB_iteratorCF__JJ + 78

RocksDB.newIterator()返回的是一个ArenaWrappedDBIter对象,ArenaWrappedDBIter相当于一个外壳,其持有的DBIter包括了大量的状态变量(上图类结构Iterator最高部分,如当前读取key&value),还持有一个内部迭代器InternalIterator,DBIter的作用是将查询转发给底层InternalIterator,InternalIterator返回的KV是原始的二进制数据,DBIter获取到数据之后解析为有含义的内容,包括版本号sequence(末尾8-1字节)、操作类型type(末尾1字节,包括普通的Value Key、删除操作Delete Key、合并操作Merge Key等)、实际用户Key内容,比如Delete Key则需要跳过去读取下一个Key,Merge Key则需要合并新老值,处理完成之后才返回结果。

其中Arena是用来存放DBIter以及其内部的InternalIterator的,目的是用于防止过多小内存碎片,DBIter中包括大量成员,Arena申请了一大片空间用于存放所有这些成员,而非每个成员申请一小点内存。

此外,ArenaWrappedDBIter还包括部分额外用于迭代器 Refresh 的信息ColumnFamilyData cfd_ 、DBImpl db_impl_ 、ReadOptions read_options_,Refresh是指当SuperVersionNumber比创建迭代器时的版本更新时,需要重新创建内部DBIter和InternalIterator,详见方法ArenaWrappedDBIter::Refresh()

详细的KV格式见 db/memtable.cc / MemTable::Add():internal_key_size(varint) + internal_key(user_key+sequence+type) + value_size(varint) + value。对于上层来说其中的user_key可能还在真正的用户数据末尾包含了timestamp。

WriteBatch层格式见 db/write_batch.cc / WriteBatchInternal::Put():tag(type) + cf_id(varint) + key_and_timestamp_size(varint) + key_data + timestamp + value_size(varint) + value_data。

注意当启用TTL时,DBWithTTLImpl::Write()中显示,timestamp是加到value后面的4字节,TTL的过滤见TtlCompactionFilter。

更多Put()内容见 DBImpl::WriteImpl() -> WriteBatchInternal::InsertInto() -> WriteBatch::Iterate() -> WriteBatchInternal::Iterate() -> MemTableInserter::PutCFImpl() -> MemTable::Add()。

MergingIterator是一个包罗万象的迭代器,是InternalIterator的一种,下层的各种类型的子迭代器都被放在MergingIterator中,包括memtable、immutables、SSTs的InternalIterator,由一个vector集合持有,并通过最小堆minHeap来优化pick哪个字迭代器的KV。

 

重点代码概览:

  • 构建InternalIterator:DBImpl::NewInternalIterator(),代码详见末尾。

  • MergingIterator从子迭代器中选择读取下一个键值:MergingIterator::SeekToFirst() & Next(),代码详见末尾。

  • 迭代器解析数据方法:DBIter::FindNextUserEntryInternal(),代码详见末尾。

 

解答一下开头的几个问题:

问题1,Iterator、ColumnFamilyHandle 背后的是怎么把 MemTable、ImmMemTable、Manifest、SST 等组织起来的?

经过上面的类结构图分析,应该基本清楚了。

 

问题2,要查找某个 CF 中指定key范围的值,如何定位到某个文件的某个位置?

从 ArenaWrappedDBIter::Seek(const Slice& target) 方法一直往下追即可,到 MergingIterator::Seek(const Slice& target) 时,对所有的子迭代器进行一次Seek,然后按key排序将子迭代器放入最小堆中,返回最小key的子迭代器,通过 ArenaWrappedDBIter::Next() 获取下一个key时,将上次最小迭代器的值取走,接着依然返回最小key的子迭代器,如此循环往复直到上界。

那么子迭代器的Seek是如何完成的?

  • 内存中的MemTableIterator的Seek,以SkipList表为例,会通过SkipListRep::Iterator::Seek()找到SkipList对应的节点;

  • level 0 SST文件(可能有多个)的Seek,会通过BlockBasedTableIterator::Seek()/PlainTableIterator::Seek()找到,BlockBasedTable是SST的默认格式,BlockBasedTableIterator内部又通过SST的Block索引IndexIterator::Seek()来快速定位文件内部大致位置(哪个Block,一般一个Block为4K大小),最终在Block内通过BlockIter::Seek()以二分查找找到key对应的具体Entry;

  • level 1~n SST文件的Seek,则是每层有一个LevelIterator,对于一层的多个SST文件,其内容都是排好序的,LevelIterator::Seek()先找到key对应的该层文件,并返回某个SST文件的BlockBasedTableIterator,再调用BlockBasedTableIterator::Seek(),接下来流程与上述level 0中分析类似;

 

问题3,Iterator 的生命周期如何管理?在 CF close 之后 Iterator 如何保持依旧可用而不被释放?

在ColumnFamilyData结构中有一个refs引用计数,当调用ColumnFamilyHandle.close()释放CF描述符时,只会对下层的ColumnFamilyData引用减1,只有引用refs=0时才真正释放(代码参考析构函数~ColumnFamilyHandleImpl())。