本文基于leveldb 1.22 版本展开，主要讨论 LevelDB 的缓存 cache 实现。cache 可以根据数据内容是否进行了解压缩分为 compressed cache 和 uncompressed cache。前者通常直接缓存磁盘数据块的镜像，后者则缓存解压后的数据块。对于 LevelDB 而言，在用户态仅仅实现了对 uncompressed cache 的支持，由操作系统的 page cache 发挥 compressed cache 的作用。而 RocksDB 则在这基础上更进一步，在用户态实现了 compressed cache 的支持。

SSTable 文件布局

LevelDB 的数据存储在 SSTable 文件中，每个文件对应一个 sorted table，即一系列按照 key 进行排序的 entry。entry 可能有两种类型：一种保存对应 key 的 value；另一种则保存了对应 key 的删除标记。LSM 的删除操作是惰性的，在执行 compaction 时数据的实际删除才可能发生。

    <beginning_of_file>
    [data block 1]
    [data block 2]
    ...
    [data block N]
    [meta block 1]
    ...
    [meta block K]
    [metaindex block]
    [index block]
    [Footer]        (fixed size; starts at file_size - sizeof(Footer))
    <end_of_file>

SSTable 文件的数据布局如上所示：

• data block 保存数据的 key/value 对；
• meta block 目前有 filter meta block 和 stats meta block 两种类型；
• metaindex block 包含对应每个 meta block 的多个 entry，key 是 meta block 的名字，value 则是 meta block 的 offset 和 size；
• index block 包括对应每个 data block 的多个 entry，key 是介于当前 data block 的最后一个 key 和下一个 data block 的第一个 key 之间的值，value 则是 data block 的 offset 和 size；
• footer 存储在 SSTable 文件的末尾，保存 metaindex block 和 index block 的 offset 和 size，还包括一些补零和一个魔数 0xdb4775248b80fb57。

LevelDB 的 cache 根据缓存的数据类型分为两种，缓存 meta block 数据的 table cache 和 缓存 data block 数据的 block cache。

数据结构

ShardedLRUCache

LevelDB 的两种 cache 都基于共同的数据结构 ShardedLRUCache。数据的淘汰按照 LRU（the least recent used）规则；根据 key 的前4个 byte 计算 hash 值，将其分布在16个 shard 上，每个 shard 的数据结构为 LRUCache。如此，可以将锁的粒度降低为 shard 级别，提升 cache 的并发读写能力。

class LRUCache {
 public:
  LRUCache();
  ~LRUCache();

  // Like Cache methods, but with an extra "hash" parameter.
  Cache::Handle* Insert(const Slice& key, uint32_t hash, void* value,
                        size_t charge,
                        void (*deleter)(const Slice& key, void* value));
  Cache::Handle* Lookup(const Slice& key, uint32_t hash);
  void Release(Cache::Handle* handle);
  void Erase(const Slice& key, uint32_t hash);
  void Prune();

 private:
  // mutex_ protects the following state.
  mutable port::Mutex mutex_;
  LRUHandle lru_ GUARDED_BY(mutex_);

  // Dummy head of in-use list.
  // Entries are in use by clients, and have refs >= 2 and in_cache==true.
  LRUHandle in_use_ GUARDED_BY(mutex_);

  HandleTable table_ GUARDED_BY(mutex_);
};

LRUCache 的实现与通常一样，基于链表和 hash table 实现。其中链表存储实际的数据，支持数据的快速尾部插入和数据的移动；而 hash table 则存储指向链表元素的指针，支持数据的快速查询。
LRUCache 维护了 in_use_ 和 lru_ 两个 entry 链表，其中 in_use_ 链表包括了当前正在被客户端引用的 entry；lru_ 包括当前没有被客户端引用的 entry，并按照 LRU 规则进行了排序。在进行数据查询时，正在被客户端访问的 entry 引用计数自增1，entry 指针移动到 in_use_ 头部；当没有客户端引用时，entry 引用计数此时为1，entry 指针移动到 lru_ 头部；当有新的 entry 插入时，entry 引用计数自增1。对于覆盖更新的场景，淘汰与新插入 key 相同的已有 entry，并将 entry 加入到 in_use_ 头部。对于全新插入的场景，将 entry 直接加入到 in_use_ 头部，并淘汰 lru_ 中最旧的 entry。如此，entry 的所有权不归属于 cache 来管理，可以减少一次数据拷贝，提升性能。

cache

class ShardedLRUCache : public Cache {
 public:
  explicit ShardedLRUCache(size_t capacity);
  ~ShardedLRUCache() override;
  Handle* Insert(const Slice& key, void* value, size_t charge,
                 void (*deleter)(const Slice& key, void* value)) override;
  Handle* Lookup(const Slice& key) override;
  void Release(Handle* handle) override;
  void Erase(const Slice& key) override;
  void* Value(Handle* handle) override;
  uint64_t NewId() override;
  void Prune() override;
  size_t TotalCharge() const override;
};

ShardedLRUCache 是 cache 的实现，提供的主要接口如下：

1. Insert 实现数据的插入。由于传入的 key 和 value 所有权并不一定属于 cache，所以需要提供对应数据的删除函数 deleter；
2. Lookup 查找特定 key 对应的 entry；
3. Release 对应 entry 引用计数减1，若引用计数为0，则调用 deleter 删除该 entry。通常用于释放 Lookup 返回的 entry；
4. Erase 从 hash table 中删除该 key 对应的entry，并且从 in_use_/lru_ 中删除该 entry，若引用计数为0，调用 deleter 删除该 entry；
5. Value 读取对应 entry 的值，通常用于从 Lookup 读取的 entry 读取值；
6. NewId 每打开一个 table cache，就会生成一个新的 cache id；
7. Prune 移除所有未使用（在 lru_ 中）的 entry；
8. TotalCharge 返回内存消耗数值。

cache 中的数据是文件的副本，读取流程如下：

1. 在 cache 中查找特定 key，若找到则直接返回相应的 entry；若未找到则继续执行；
2. 从文件中读取 key 对应 entry 到 cache 中，再返回相应的 entry

由于 LSM Tree 的 SSTable 文件的不变性，SSTable 文件只会被删除而不会被更改，因此无需考虑数据更新带来的 cache 和文件数据不一致的问题， cache 也无需支持数据的更新 ，这也是 LSM Tree 的 cache 实现一大特点。
由于 table cache 缓存的是 block cache 中 block 的元信息，所以两者需要结合起来发挥作用。一个完整的数据查询流程是，先从 table cache 中获取到元信息，再根据元信息去 block cache 或 SSTable 文件中查找相应的 block 数据。

table cache

table cache 中缓存的是 meta block 的数据，key 为 SSTable 文件对应的 file_number，这是一个在进行 L0 compaction 时就确定的序号，在数据库级别单调递增且保证唯一。这个 file_number 同时也是 SSTable 文件的文件名。
在读取过程中，当 table cache 中找不到 key 对应的 entry 时，需要从文件中加载数据构建。读取通过 mmap 将整个文件映射到内存中实现。先从文件中读取固定长度（48 字节）的 footer，从 footer 中解析出 index block/metaindex block 的 offset 和 size 信息，最后读取 index block 和 metaindex block 的信息。
在得到 index block 数据后，通常需要根据 index 查找 data block。index 可以认为是一个有序数组，查找需要利用到二分查找。不同的是，为了减少 key 所占用的存储空间，LevelDB 采取了 key 压缩技术，简单来说就是每个若干个 key 保存一个完整的 key 的 entry 作为重启点，重启点之间的 key 则只需要在重启点的公共前缀基础上存储后缀即可。因此，在进行二分查找时需要首先找到重启点，根据最近的重启点信息构结合 entry 的非公共后缀找到最终需要查找的 entry。LevelDB 的 key 压缩又是一个很有意思的话题，我们后续的 compaction 篇章再见。

block cache

block cache 中缓存的是 data block 的数据，key 为 table cache 的 cache_id 和从 index 中获取的 data block offset。当 block cache 中找不到 key 对应的 entry 时，将从 table cache 之前使用过的 mmap 内存中加载数据构建 block cache，不会出现再次 mmap。

总而言之，cache 是一种常用的用于加速磁盘文件访问的手段，在系统具备查询热点时可以显著提升查询性能。需要指出的是，在范围查询的场景下，cache 往往会因为大范围的数据扫描导致热数据被淘汰，而冷数据被加载至内存中。系统的缓存命中率会急剧下降，造成系统性能降低。针对这个问题，InnoDB 存储引擎将 buffer pool 调整分为 old、young 两个区域。因为范围查询引入的数据通常只会被访问一次，这样的数据将被放在 old 区域，而 young 区域则会保存多次访问的热点数据。

参考文献

LevelDB Table Format
RocksDB Block Cache
MySQL Buffer Pool