在LevelDB详解:读过程一中主要描述了LevelDB读一个key的整体流程。从memtable读直到读取sstable。本文中主要描述如何从sstable中读取内容的细节,可以加深对sstable数据布局的理解。

从sstable读取(key,value)的入口为 TableCache::Get()

Status TableCache::Get(const ReadOptions& options,
                uint64_t file_number,
                uint64_t file_size,
                const Slice& k,
                void* arg,
                void (*saver)(void*, const Slice&, const Slice&)) {
  Cache::Handle* handle = NULL;
  Status s = FindTable(file_number, file_size, &handle);
  if (s.ok()) {
    Table* t = reinterpret_cast<TableAndFile*>(cache_->Value(handle))->table;
    s = t->InternalGet(options, k, arg, saver);
    cache_->Release(handle);
  }
  return s;
}

TableCache顾名思义,缓存了描述sstable的描述对象Table。要想读取sstable的<key, value>,必须通过Table。

首先通过 FindTable 在缓存中查找文件名对应的Table,如果本地缓存未命中,需要创建这样一个对象并插入table cache。创建Table对象的过程比较复杂,值得仔细分析。

Status TableCache::FindTable(uint64_t file_number, uint64_t file_size, Cache::Handle** handle) {
  *handle = cache_->Lookup(key);
  if (*handle == NULL) {
    // table cache未命中,table尚未被加载至内存
    // open, 然后插入cache
    ......
    }
    if (s.ok()) {
      // Open过程干了很多事,值得仔细分析
      s = Table::Open(*options_, file, file_size, &table);
    }
    // 打开失败处理
    if (!s.ok()) {
     ...
    } else {
      TableAndFile* tf = new TableAndFile;
      tf->file = file;
      tf->table = table;
      // 插入table cache
      *handle = cache_->Insert(key, tf, 1, &DeleteEntry);
    }
  }
  return s;
}

我想,这里最重要的逻辑是创建一个新的Table对象并调用Table::Open()方法。

Status Table::Open(const Options& options,
                   RandomAccessFile* file,
                   uint64_t size,
                   Table** table) {
  *table = NULL;
  ......
  char footer_space[Footer::kEncodedLength];
  Slice footer_input;
  // 首先读取footer,sstable的其他元数据信息可通过footer索引
  // footer大小固定Footer::kEncodedLength
  Status s = file->Read(size - Footer::kEncodedLength, Footer::kEncodedLength, &footer_input, footer_space);
  if (!s.ok()) return s;

  // 读出index block是关键
  BlockContents contents;
  Block* index_block = NULL;
  if (s.ok()) {
    s = ReadBlock(file, opt, footer.index_handle(), &contents);
    if (s.ok()) {
      index_block = new Block(contents);
    }
  }
  if (s.ok()) {
    ......
    *table = new Table(rep);
    // ReadMeta主要是filter信息
    (*table)->ReadMeta(footer);
  } else {
    if (index_block) delete index_block;
  }
  return s;

Table::Open()首先从sstable中读出footer,还记得footer的作用么?主要是为了索引到索引块和metaindex的起始位置,如下图:

接下来便是从sstable中读出index block和metaindex block(ReadMeta())。这里ReadMeta()的主要作用是Bloom filter所需信息,关于LevelDB中的bloom filter,我们会在后面专门描述其实现。

上面的步骤打开了Table,根据逻辑,接下来就是从Table中获取<key, value>了。这调用了Table::InternalGet(),如下:

Status Table::InternalGet(const ReadOptions& options, const Slice& k, void* arg, void (*saver)(void*, const Slice&, const Slice&)) {
  Status s;
  // 首先从index_block中seek至感兴趣的key
  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;
    // 利用bloom filter机制先判断可以是否存在
    if (filter != NULL &&
        handle.DecodeFrom(&handle_value).ok() &&
        !filter->KeyMayMatch(handle.offset(), k)) {
      // Not found
    } else {
      // 根据index block中的记录构造BlockReader去读取Block中的key内容
      Iterator* block_iter = BlockReader(this, options, iiter->value());
      // seek至感兴趣的key
      block_iter->Seek(k);
      if (block_iter->Valid()) {
        // 将key对应的value读取出来
        (*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;
}

这个过程并不复杂:

  1. 从index_block中seek至感兴趣的key,找到存储key的block位置(offset, size);
  2. 以该Block信息构造BlockReader,从block中读取感兴趣的key,这同样也是一个seek过程。

如何从block中seek至感兴趣的key,我们会在接下来的文章中详细描述。另外,为了提高查找速度,LevelDB还实现了data block的cache。以table 的cache id(创建table时生成)以及data block在sstable文件的偏移量组织成key索引缓存项。这同样在我们以后的文章中详细描述。关于这两个问题就不再作过多阐述。

levelDB读流程(2)

TableCache::Get()流程图