从 Row Cache 的 Get 来看 Rocksdb LRUCache

本文简单介绍 RocksDB 6.7.3 版本的 LRUCache。

Row Cache

Row Cache 对查找的 key 在 SST 中对应的 value 进行 cache。如果 row_cache 打开，在 TableCache::Get 函数中，会调用 CreateRowCacheKeyPrefix 和 GetFromRowCache 获取 row cache 的 key（fd_number + seq_no + user_key），在 GetFromRowCache 中，会调用 row_cache->Lookup，得到 row cache 缓存的 row_handle，构造 found_row_cache_entry 指针指向 value，利用 Cleannable 类的特性，可以通过减少一次对 value 内存拷贝的方式来获取最终的结果。

Status TableCache::Get(const ReadOptions& options,
                       const InternalKeyComparator& internal_comparator,
                       const FileMetaData& file_meta, const Slice& k,
                       GetContext* get_context,
                       const SliceTransform* prefix_extractor,
                       HistogramImpl* file_read_hist, bool skip_filters,
                       int level) {
  ...
  if (ioptions_.row_cache && !get_context->NeedToReadSequence()) {
    auto user_key = ExtractUserKey(k);
    CreateRowCacheKeyPrefix(options, fd, k, get_context, row_cache_key);
    done = GetFromRowCache(user_key, row_cache_key, row_cache_key.Size(),
                           get_context);
    if (!done) {
      row_cache_entry = &row_cache_entry_buffer;
    }
  }
  ...
}

void TableCache::CreateRowCacheKeyPrefix(const ReadOptions& options,
                                         const FileDescriptor& fd,
                                         const Slice& internal_key,
                                         GetContext* get_context,
                                         IterKey& row_cache_key) {
  uint64_t fd_number = fd.GetNumber();
  uint64_t seq_no = 0;
  ...
  AppendVarint64(&row_cache_key, fd_number);
  AppendVarint64(&row_cache_key, seq_no);
}

bool TableCache::GetFromRowCache(const Slice& user_key, IterKey& row_cache_key,
                                 size_t prefix_size, GetContext* get_context) {
  bool found = false;

  row_cache_key.TrimAppend(prefix_size, user_key.data(), user_key.size());
  if (auto row_handle =
          ioptions_.row_cache->Lookup(row_cache_key.GetUserKey())) {
    // Cleanable routine to release the cache entry
    Cleanable value_pinner;
    auto release_cache_entry_func = [](void* cache_to_clean,
                                       void* cache_handle) {
      ((Cache*)cache_to_clean)->Release((Cache::Handle*)cache_handle);
    };
    auto found_row_cache_entry =
        static_cast<const std::string*>(ioptions_.row_cache->Value(row_handle));
    // If it comes here value is located on the cache.
    // found_row_cache_entry points to the value on cache,
    // and value_pinner has cleanup procedure for the cached entry.
    // After replayGetContextLog() returns, get_context.pinnable_slice_
    // will point to cache entry buffer (or a copy based on that) and
    // cleanup routine under value_pinner will be delegated to
    // get_context.pinnable_slice_. Cache entry is released when
    // get_context.pinnable_slice_ is reset.
    value_pinner.RegisterCleanup(release_cache_entry_func,
                                 ioptions_.row_cache.get(), row_handle);
    replayGetContextLog(*found_row_cache_entry, user_key, get_context,
                        &value_pinner);
    RecordTick(ioptions_.statistics, ROW_CACHE_HIT);
    found = true;
  } else {
    RecordTick(ioptions_.statistics, ROW_CACHE_MISS);
  }
  return found;
}

LRUCache 类

• Cache
  定义了 Cache 的接口，包括 Insert, Lookup, Release 等操作。

• ShardedCache
  支持对 Cache 进行分桶，分桶数量为 2^num_shard_bits，每个桶的容量相等。分桶的依据是取 key 的 hash 值的高 num_shard_bits 位。

• LRUCache
  实现了 ShardedCache，维护了一个 LRUCacheShard 数组，一个 shard 就是一个桶。

• CacheShard
  定义了一个桶的接口，包括 Insert, Lookup, Release 等操作，Cache 的相关调用经过分桶处理后，都会调用指定桶的对应操作。

• LRUCacheShard
  实现了 CacheShard，维护了一个 LRU list 和 hash table，用来实现 LRU 策略，他们的成员类型都是 LRUHandle。

• LRUHandle
  保存 key 和 value 的单元，并且包含前向和后续指针，可以组成双向循环链表作为 LRU list。

• LRUHandleTable
  hash table 的实现，根据 key 再次做了分组处理，并且尽量保证每个桶中只有一个元素，元素类型为 LRUHandle。提供了Lookup, Insert, Remove操作。

Lookup

在 GetFromRowCache 中，会调用 row_cache->Lookup，这里实际调用的是 ShardedCache::Lookup

Cache::Handle* ShardedCache::Lookup(const Slice& key, Statistics* /*stats*/) {
  uint32_t hash = HashSlice(key);
  return GetShard(Shard(hash))->Lookup(key, hash);
}

获取哈希值，根据 hash 值的高 num_shard_bits 位获取 shard，再调用 LRUCacheShard::Lookup

Cache::Handle* LRUCacheShard::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);
  if (e != nullptr) {
    assert(e->InCache());
    if (!e->HasRefs()) {
      // The entry is in LRU since it's in hash and has no external references
      LRU_Remove(e);
    }
    e->Ref();
    e->SetHit();
  }
  return reinterpret_cast<Cache::Handle*>(e);
}

LRUCacheShard::Lookup 中又会调用 LRUHandleTable::Lookup，在 FindPointer 中，hash 到特定位置后，如果当前位置的 hash 和当前 hash 不一样，或者 key 不一样，并且指针也不为空，则继续向下找，直到找到

LRUHandle* LRUHandleTable::Lookup(const Slice& key, uint32_t hash) {
  return *FindPointer(key, hash);
}

LRUHandle** LRUHandleTable::FindPointer(const Slice& key, uint32_t hash) {
  LRUHandle** ptr = &list_[hash & (length_ - 1)];
  while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
    ptr = &(*ptr)->next_hash;
  }
  return ptr;
}

总结

LRUCache 就是把多个 LRUCacheShard 组合起来，每个 LRUCacheShard 维护了一个 LRUHandle list 和 hash table，LRUHandleTable 用拉链法实现哈希表。通过对缓存的 Lookup 调用链分析可以看到具体的实现非常简练。

参考

1. Rocksdb Source Code 6.7.3
2. RocksDB. LRUCache源码分析
3. RocksDB中的LRUCache