LevelDB剖析(2):sstable 和 recordio

本节看下持久层的数据存储结构:LevelDB中用户的key-value数据以sstable的格式持久化存储,memtable中尚未落地的数据以recordio的格式保存在日志文件中;而DB元数据及相关变更记录也是以recordio的格式单独存储的. 理解数据在内存和磁盘上的组织方式有助于深入理解LevelDB各个内部流程.

一、sstable
leveldb中持久化数据存储的基本单元是sstable文件. sstable本质上是一个排序的map(kv pair),由默认4K大小的数据block以及文件尾部的索引和过滤器等元数据block外加一个Footer组成:

sstable

用户kv数据都在data block里,切分block主要是为了按块存取和缓存,提高IO吞吐. index block是块索引,格式与data block相同,index block的key对应data block里的最大的key(即最后一个),value是该data block在文件中的(offset, length). metaindex block类似,记录是meta block在块中的位置. 当前meta block只有一种即filter block,用于block-wise的查询过滤,如默认的BloomFilter会将每个block的key集合的bloom hash bits信息写入其中. Footer在文件结尾的一块固定位置,里面记录了index block等元数据的位置,是加载文件的入口.

data block、index block和metaindex block的格式如下:

block_format

block内各kv entry按key的顺序依次排列,每个entry实际上记录的就是 key-len|value-len|key-data|value-data,只是这里利用了有序的特性做了个存储空间优化,即相邻的key很可能有相同的前缀,那么每个key只需要存与前一个key不相同的部分即可,因此上图entry里单独记录了shared_key_len,用于计算完整key,而key-data只需要存nonshared的部分. 每个block末尾还存储了一个迷你索引即restart point数组,用于block在内存中的二分查找:每个restart point指向一个entry的起始位置,默认每16个entry设一个restart point,也能用于加速iterator的prev等操作. 结合单key查找的场景不难得出,被restart point指向的key是应当是完整存储的,即shared_key_len为0.

filter block的格式如下:

----------------------------------------
[filter data 0]
[filter data 1]
[filter data 2]
...
[filter data N-1]

[offset of filter data 0] : 4 bytes
[offset of filter data 1] : 4 bytes
[offset of filter data 2] : 4 bytes
...
[offset of filter data N-1] : 4 bytes

[offset of beginning of offset array] : 4 bytes
lg(base) : 1 byte
----------------------------------------

一个sstable只有一个filter block,其内存储了所有block的filter数据. 具体来说,filter_data_k 包含了所有起始位置处于 [base*k, base*(k+1)]范围内的block的key的集合的filter数据,按数据大小而非block切分主要是为了尽量均匀,以应对存在一些block的key很多,另一些block的key很少的情况. offset数组是一个内部索引,假如通过索引知道了data block的起始位置p,可以快速计算出offset = p / base (或者p >> lg(base)),进而取到该data block所属的filter data.

现在可以来看下单个sstable上的key的查找过程:

Status Table::InternalGet(const ReadOptions& options, const Slice& k,
                          void* arg,
                          void (*saver)(void*, const Slice&, const Slice&)) {
  Status s;
  Iterator* iiter = rep_->index_block->NewIterator(rep_->options.comparator);
  iiter->Seek(k);
  if (iiter->Valid()) {
    Slice handle_value = iiter->value();
    FilterBlockReader* filter = rep_->filter;
    BlockHandle handle;
    if (filter != NULL &&
        handle.DecodeFrom(&handle_value).ok() &&
        !filter->KeyMayMatch(handle.offset(), k)) {
      // Not found
    } else {
      Iterator* block_iter = BlockReader(this, options, iiter->value());
      block_iter->Seek(k);
      if (block_iter->Valid()) {
        (*saver)(arg, block_iter->key(), block_iter->value());
      }
      s = block_iter->status();
      delete block_iter;
    }
  }
  if (s.ok()) {
    s = iiter->status();
  }
  delete iiter;
  return s;
}

LevelDB中的查找操作都是通过Iterator的接口调用的。InternalGet实现单个sstable中对key的查找,并通过saver回调处理找到的kv记录,例如将value存到某个用户buffer. 调用此函数时table的相关元数据如index block、filter block等内容已经加载到内存,首先第6行iiter->Seek(k)根据索引找到目标data block的位置(offset+length),然后第13行filter->KeyMayMatch(offset, k)进行key过滤,如果判断出key实际不存在于block中则返回,否则通过BlockReader去真正发起IO将block读到内存,最后block_iter->Seek(k)在block内查找该记录,并将结果提交给saver. BlockReader内部会处理解压缩和缓存. 另外考虑到BloomFilter存在一定的误判率(False Positive),因此需要通过检查block_iter->Valid()以及在saver内部进一步判断.

二、recordio
recordio适用于操作流水日志的存储. LevelDB中以32K为一个recordio block,如果一条逻辑记录的大小超过了32K,则必须切分为几条物理子记录跨block存储,并打上相应的类型标记,比如:

recordio_2

上图中record_A较小,被完全容纳在block中,类型为'full'. 而record_B较大被分成了3条物理记录,分别标记为head, patial, last类型. 这种格式相比简单的 (length,data)* 格式的优势是:如果某个记录损坏了(如crc校验失败),则只需要跳到下一个block去找到head或full的record即可开始下一个record的读取,跳过坏记录很简单。而对于不分block的(length,data)*简单格式,如果中间某个length错了,则其后整个文件的内容都不可信了.

因此LevelDB用recordio格式来做memtable的backing log,可以尽量减少log损坏带来的记录丢失.

另外LevelDB用来存元数据的文件也是一个单独的recordio log文件,叫做manifest.log,其内容如下:

manifest_log

LevelDB的元数据主要指每个level到其文件列表的映射,还包括一些当前log文件编号、最大table文件编号、版本序列等信息,manfifest文件新建时会将当前DB元数据快照作为基础元数据信息写入,其后每当元数据变更,比如一轮Compaction过后某些level的文件列表会有增删等变更,此时仅需将增量部分如相关level的added_files,deleted_files作为edit log records追加到文件末尾即可. 下次重新打开DB时需要根据这些edit log在内存中恢复出最新版本元数据. 增量log的好处是节省IO开销,特别是数据较大时,另外安全性和可靠性也更加有保障.

写recordio的代码比简单,仅需注意block边界处理即可. 读recordio时由于要校验正确性做跳过bad record处理,并且还支持从任意用户指定的位置(可能指向某个record中间)开始读读,相关代码相对比较tricky.

三、压缩和校验
recordio(log)数据目前没有引入压缩.
sstable数据可以选择按block进行Snappy压缩,并计算crc校验. 所以每个block位置实际存储的是 压缩后内容+压缩类型(Snappy or No Compression)+crc. 读取block时在解压缩之前会先进行crc校验. Snappy压缩的好处是速度快,相对智能:对压缩率低的数据会自动放弃压缩.

发表评论

电子邮件地址不会被公开。