LevelDB 学习笔记-Cache

Cache

Cache 是一个抽象类，里面定义了一系列操纵 Cache 的方法，而 ShardedLRUCache 是 Cache 的实现类，可以使用 NewLRUCache(size_t capacity) 创建一个新 ShardedLRUCache 实例。

Handle 是在 Cache 中定义的一个空结构体，但是对用户来说，它代表了一个 Cache 缓存项的凭依。啥意思呢？就是说用户可以调用 Insert 或 Lookup 方法获取一个 Handle，也可以调用 Release 方法释放该缓存项，但是用户是不能够直接操作 Handle 的，因为它没有定义任何属性和方法。

需要注意的是，在 Insert 方法中需要传入缓存项的大小 charge，当超出缓存容量时会将部分缓存淘汰。Insert 中还需要提供一个 deleter 函数，该函数以 key 和 value 作为参数，当缓存项的引用计数变为 0 时会调用该方法

LRUCache

LRUCache 是一个 LRU Cache 的实现，里面包含了两个双向链表 lru_ 和 in_use_。其中 lru_ 链表按照最近使用的顺序存放着存在于缓存中，但是没有使用的缓存项；in_use_ 存放着正在使用的缓存项。

LRUCache 中的缓存项可以通过 LRUHandle 进行管理，其内部有一个 ref_ 引用计数，当缓存项被使用时，需要调用 Ref 将引用计数加一，这时会将缓存项移除并加入到 in_use_ 链表中。当引用计数变为 1 时，会从 in_use_ 中移除并加入到 lur_ 链表中。当引用计数变为 0 时，会释放该缓存项。可以理解为当缓存项正在使用时，就将其 pin 注，这样就不能将其淘汰了

HandleTable 是一个 Hash Table，其内部实现采用的是链地址法。HandleTable 的使用目的是加速访问缓存项，其内部包含 lru_ 和 in_use_ 中的所有元素。刚创建时其数组容量为 0，当第一次插入时，会扩容为 4。当容量超过 4 时会扩容为 8，当容量减少到小于 4 时，会缩容为 4

ShardedLRUCache

ShardedLRUCache 是 Cache 的实现类，从名字也可以看出来，ShardedLRUCache 是一个分片的缓存，每一部分是一个 LRUCache。ShardedLRUCache 通过 Shard(uint32_t hash) 来决定某个 key 应该放入哪个分片，其实现只是简单的讲 key 的 hash 值右移 28 位(即取 uint32_t 值的高 4 位)。ShardedLRUCache 的内部实现也很简单，基本上只是调用了 LRUCache 的方法而已

为什么要进行分片？

每个 LRUCache 都有自己独立的锁，将 cache 进行分片能够减少锁的争用，增加并行性 {% endnote %}

Cache 以及其相关实现都是线程安全的，因此上层用户可以放心地使用

TableCache

TableCache 是对 Cache 的包装，并作为 VersionSet 的成员变量对 Table 进行缓存。

class TableCache {
 public:
  TableCache(const std::string& dbname, const Options& options, int entries);

  TableCache(const TableCache&) = delete;
  TableCache& operator=(const TableCache&) = delete;

  ~TableCache();

  // Return an iterator for the specified file number (the corresponding
  // file length must be exactly "file_size" bytes).  If "tableptr" is
  // non-null, also sets "*tableptr" to point to the Table object
  // underlying the returned iterator, or to nullptr if no Table object
  // underlies the returned iterator.  The returned "*tableptr" object is owned
  // by the cache and should not be deleted, and is valid for as long as the
  // returned iterator is live.
  Iterator* NewIterator(const ReadOptions& options, uint64_t file_number,
                        uint64_t file_size, Table** tableptr = nullptr);

  // If a seek to internal key "k" in specified file finds an entry,
  // call (*handle_result)(arg, found_key, found_value).
  Status Get(const ReadOptions& options, uint64_t file_number,
             uint64_t file_size, const Slice& k, void* arg,
             void (*handle_result)(void*, const Slice&, const Slice&));

  // Evict any entry for the specified file number
  void Evict(uint64_t file_number);

 private:
  Status FindTable(uint64_t file_number, uint64_t file_size, Cache::Handle**);

  Env* const env_;
  const std::string dbname_;
  const Options& options_;
  Cache* cache_;
};

当 VersionSet 需要使用 Table 时，会通过 Get 方法先从 TableCache 中获取，查找的具体逻辑实在 FindTable() 中实现的。如果 cache 中没有该 table，FindTable 打开该 table，并将其插入到 cache 中的 in_use_ 链表中。当使用完毕后，会调用 Cache::Release 方法将其移动到 lru_ 链表中

Status TableCache::Get(const ReadOptions& options, uint64_t file_number,
                       uint64_t file_size, const Slice& k, void* arg,
                       void (*handle_result)(void*, const Slice&,
                                             const Slice&)) {
  Cache::Handle* handle = nullptr;
  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, handle_result);
    cache_->Release(handle); // 从 in_use_ 链表移动到 lru_ 链表
  }
  return s;
}

void (*handle_result)(void*, const Slice&, const Slice&) 的作用是传递给 Table#InternalGet，在这个方法中会调用传递的 handle_result 方法

这里我们只关注于缓存相关的实现，所以我们现在只关注 FindTable 方法

Status TableCache::FindTable(uint64_t file_number, uint64_t file_size,
                             Cache::Handle** handle) {
  Status s;
  char buf[sizeof(file_number)];
  EncodeFixed64(buf, file_number);
  Slice key(buf, sizeof(buf));
  *handle = cache_->Lookup(key); // 从缓存中查找
  if (*handle == nullptr) { // 如果没找到，就打开文件，并插入 cache
    
    std::string fname = TableFileName(dbname_, file_number);
    RandomAccessFile* file = nullptr;
    Table* table = nullptr;
    s = env_->NewRandomAccessFile(fname, &file);
    s = Table::Open(options_, file, file_size, &table);

    // 插入 cache
    TableAndFile* tf = new TableAndFile;
    tf->file = file;
    tf->table = table;
    *handle = cache_->Insert(key, tf, 1, &DeleteEntry);
  }
  return s;
}

Table

Table 是 SSTable 的内存形式，在之前已经介绍过 SSTable 的格式了，这里只着重看 Table 的内存形式。

Table 只包含了一个成员变量 Rep，其中包含了 index_block 和 metaindex_handle 以及 filter 和 filter_data，在打开一个 Table 时都会为这些变量赋值。只有两个地方调用了 Open 方法，一个是 FindTable，另一个是 DumpTable，下面我们来看一下 Open 方法

Status Table::Open(const Options& options, RandomAccessFile* file,
                   uint64_t size, Table** table) {
  *table = nullptr;

  char footer_space[Footer::kEncodedLength];
  Slice footer_input;
  Status s = file->Read(size - Footer::kEncodedLength, Footer::kEncodedLength,
                        &footer_input, footer_space); // 读取 Footer

  Footer footer;
  s = footer.DecodeFrom(&footer_input);

  // Read the index block
  BlockContents index_block_contents;
  ReadOptions opt;
  if (options.paranoid_checks) {
    opt.verify_checksums = true;
  }
  // 读取 index block
  s = ReadBlock(file, opt, footer.index_handle(), &index_block_contents);

  if (s.ok()) {
    // We've successfully read the footer and the index block: we're
    // ready to serve requests.
    Block* index_block = new Block(index_block_contents);
    Rep* rep = new Table::Rep;
    rep->options = options;
    rep->file = file;
    rep->metaindex_handle = footer.metaindex_handle();
    rep->index_block = index_block;
    rep->cache_id = (options.block_cache ? options.block_cache->NewId() : 0);
    rep->filter_data = nullptr;
    rep->filter = nullptr;
    *table = new Table(rep);
    (*table)->ReadMeta(footer);
  }

  return s;
}

Footer 中包含了 metaindex_handle 以及 index_handle，可以参考 SSTable 那篇文章

在 FindTable 中打开 Table 后会放入缓存中，也就是说 TableCache 的缓存项中包含了 Table 这个结构，其中比较重要的是 index_block 这个结构。index_block 中存放的是每个 Data Block 中的 last key，通过查找 index block 可以知道某个 key 是否在该 table 的 key 的范围中，以及该 key 在该文件的哪个 data block 中。如果制定了 filter 还会通过 filter 进一步判断 table 是否有某个 key。

从 Open() 方法中我们可以看到 Options 结构还有一个 block_cache 字段。这个字段是一个 Cache 结构，默认为 ShardedLRUCache，默认大小为 8 M，在 DBImpl 的构造函数中创建，用户也可以自定义 Cache。

cache_block 主要作用是将当前迭代的 block 放入缓存中，具体存放时机在 Table::BlockReader 方法中。这一点在迭代的时候很有用，否则就需要从文件中读取了。

综上，缓存的作用主要体现在以下几点：

• 缓存 Table，通过 Table 中的 index block 和 filter 判断 Key 是否在 table 中，从而减少 I/O 的次数
• 缓存 Block，迭代 block 时将 block 缓存，从而减少 I/O