以RocksDB为存储引擎的MyRocks是近几年流行起来的MySQL分支，在Facebook等公司广泛使用，网易杭研的数据库内核团队从2018年初开始系统研究MyRocks，目前已在内部进行小范围推广使用，效果比较理想。

在调研、测试和试用期间，积累了一些经验，包括技术实现等。本系列想跟大家分享我们组内小伙伴做的LevelDB调研输出，这是第三篇，介绍LevelDB的缓存机制。

第二篇链接：

温正湖：LevelDB设计与实现 - 读写流程zhuanlan.zhihu.com

Cache

在图8中有两个cache是为了优化读性能的：TableCache和BlockCache。这两种Cache都采用了LRUCache机制，只是内部存储的数据类型不同。

TableCache:

key: file number

  char buf[sizeof(file_number)];
  EncodeFixed64(buf, file_number);
  Slice key(buf, sizeof(buf));

value: TableAndFile,主要是sstable file的index block的数据。

//table_cache.cc
struct TableAndFile {
  RandomAccessFile* file;
  Table* table;
};
//table.cc
//Table里的主要数据即Rep
struct Table::Rep {
  ~Rep() {
    delete filter;
    delete [] filter_data;
    delete index_block;
  }
  Options options;
  Status status;
  RandomAccessFile* file;
  uint64_t cache_id;
  FilterBlockReader* filter;
  const char* filter_data;
  BlockHandle metaindex_handle;  
  Block* index_block;
};

BlockCache:

key: cache_id 和 block 在sstable中的offset的组合

      //table.cc
      char cache_key_buffer[16];
      //构造blockcache的key
      EncodeFixed64(cache_key_buffer, table->rep_->cache_id);
      EncodeFixed64(cache_key_buffer+8, handle.offset());
      Slice key(cache_key_buffer, sizeof(cache_key_buffer));

value: data block的内容

//block.h
class Block {
 public:
  // Initialize the block with the specified contents.
  explicit Block(const BlockContents& contents);
  ~Block();
  size_t size() const { return size_; }
  Iterator* NewIterator(const Comparator* comparator);
 private:
  uint32_t NumRestarts() const;
  const char* data_;
  size_t size_;
  uint32_t restart_offset_;     // Offset in data_ of restart array
  bool owned_;                  // Block owns data_[]
  // No copying allowed
  Block(const Block&);
  void operator=(const Block&);
  class Iter;
};

LevelDB的LRUCache设计有4个数据结构，是依次递进的关系，分别是：

LRUHandle，其实就是LRU结点。
HandleTable，其实就是哈希表。
LRUCache，做了一层封装，内部有两个链表和一个哈希表。
ShardedLRUCache，为了减少锁竞争，LevelDB分成了16个LRUCache。

LevelDB整个LRUCache的结构如下图：

LRUCache是分成了16个组，组内上锁不影响其他的组，每个组内又是利用哈希表加快查找速度。默认的哈希表是4个桶，LRUCache有两条链表，一条是in_use表示正在使用的Cache，另一条是lru_表示不经常使用的，在这条里面的Cache是会被淘汰的。

未完待续。。。

ITPub博客

LevelDB设计与实现 - 缓存机制

最新文章