概述

Rocksdb的是基于磁盘的存储引擎,前面介绍的Immutable Memtable的Compact操作会将内存中的数据落盘,落盘的数据以Static Sorted Table的形式存放,即SST。SST本质上应该属于一个抽象的数据格式Table。

Rocksdb支持两种类型的Table: plain tableblock based table,这里我们以默认的Block-based table类型来详细介绍:

SST格式

Rocksdb继承Leveldb的格式,将一个SST划分为多个Block,其中包括存储数据的Block,存储元信息的Block,存储索引信息的Block,另外Rocksdb增加一个范围删除的Blockrange_del_block

sst_format

  • Data Block 存放Key-Value数据的Block
  • Meta Block 各个元信息的Block,包括Filter、Properties(整个table的属性信息)、Compression dictionary、Range deletion tombstone
  • MetaIndex Block 指向各个元信息Meta Block的索引指针
  • Index Block 每个Data Block
  • Footer 包括指向MetaIndex 和 Index Block的索引指针

创建SST

我们是基于默认的Block Based Table来介绍,所以主要的接口在table/block_based_table_builder.h及对应的.cc实现文件,构建Table的接口是Add():

  • 判断Key的类型,如果是范围删除类型,即kTypeRangeDeletion,写入range_del_block
  • 如果是值类型,即需要被写入Data Block的Key,需要判断被写入的Block是否已经达到了限定的大小,如果超过了限定的数值,需要被Flush
  • 将Key-Value写入Data Block:r->data_block.Add(key, value)
  • 每次写入需要更新SST的Version元信息,即SST的边界的最大、最小Key:smallest_keylargest_key
  • 完成Meta Block 和MetaIndex Block的写入,保存的是一个handle,即一个block的指针,包括偏移量offset_size_
  • 更新Version的元信息

读取SST

前面我们介绍过Rocksdb的Get()接口,首先在Memtable中查找,之后是Immutable Memtable,最后再去SST文件中查找:

  • 通过Version中记录的信息遍历Level中的所有SST文件,利用SST文件记录的边界最大,最小key- smallest_keylargest_key来判断查找的key是否有可能存在
  • 如果在该Level中可能存在,调用TableReader的接口来查找SST文件
    • 首先通过SST文件中的Filter来初判key是否存在
    • 如果存在key存在,进入Data Block中查找
    • 在Data Block利用Block的迭代器BlockIter利用二分查找BinarySeek或者前缀查找PrefixSeek
  • 如果查找成功则返回,如果该Level不存在查找的Key,继续利用Version中的信息进行下一个Level的查找,直到最大的一个Level