概述

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

RocksDB支持两种类型的Table: plain table和block 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_key、largest_key

  • 完成Meta Block 和MetaIndex Block的写入，保存的是一个handle，即一个block的指针，包括偏移量offset_和size_

  • 更新Version的元信息

读取SST

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

  • 通过Version中记录的信息遍历Level中的所有SST文件，利用SST文件记录的边界最大，最小key- smallest_key和largest_key来判断查找的key是否有可能存在

  • 如果在该Level中可能存在，调用TableReader的接口来查找SST文件

    • 首先通过SST文件中的Filter来初判key是否存在

    • 如果存在key存在，进入Data Block中查找

    • 在Data Block利用Block的迭代器BlockIter利用二分查找BinarySeek或者前缀查找PrefixSeek

  • 如果查找成功则返回，如果该Level不存在查找的Key，继续利用Version中的信息进行下一个Level的查找，直到最大的一个Level