LevelDB 完全解析（5）：Cache
LevelDB 完全解析（5）：Cache
前文回顾
- LevelDB 完全解析（0）：基本原理和整体架构
- LevelDB 完全解析（1）：MemTable
- LevelDB 完全解析（2）：Log
- LevelDB 完全解析（3）：SSTable
- LevelDB 完全解析（4）：Manifest
根据功能的不同，LevelDB 中有两种 cache：
- Block cache：缓存解压后的 data block，可以加快热数据的查询。
- Table cache：缓存打开的 SSTable 文件描述符和对应的 index block、meta block 等信息。
在 LevelDB 中，block cache 和 table cache 都是基于 ShardedLRUCache 实现的。
ShardedLRUCache
ShardedLRUCache 是在 LRUCache 上包装了一层分片——根据 key 的哈希值的前 4 位（kNumShardBits）分 16 个（kNumShards） LRUCache。
分片的作用是减少多线程对同一个 LRUCache 对象的争用。
LRUCache
LRU，全称是 Least Recently Used（最近最少使用），是一种利用局部性原理（如果数据最近被访问过，那么将来被访问的几率也更高）的缓存淘汰策略。LRUCache 即是一个基于 LRU 淘汰策略的缓存。当热点数据比较集中时，LRUCache 的效率比较高。
LevelDB 的 LRUCache 的实现由一个哈希表和两个链表组成：
- 链表 lru_：维护 cache 中的缓存对象的使用热度。数据每次被访问的时候，都会被插入到这个链表最新的地方。 lru_->next 指向最旧的数据， lru_->prev 指向最新的数据。当 cache 占用的内存超过限制时，则从 lru_->next 开始清理数据。
- 链表 in_use_：维护 cache 中有哪些缓存对象被返回给调用端使用。这些数据不能被淘汰。
- 哈希表 table_：保存所有 key -> 缓存对象，用于快速查找数据。
LRUCache 的 Insert 和 Lookup 的时间复杂度都是 O(1)。
LRUHandle
LRUHandle 是 LRUCache 中的一个对象。
struct LRUHandle {
void* value;
void (*deleter)(const Slice&, void* value);
LRUHandle* next_hash;
LRUHandle* next;
LRUHandle* prev;
size_t charge; // TODO(opt): Only allow uint32_t?
size_t key_length;
bool in_cache; // Whether entry is in the cache.
uint32_t refs; // References, including cache reference, if present.
uint32_t hash; // Hash of key(); used for fast sharding and comparisons
char key_data[1]; // Beginning of key
Slice key() const {
// next_ is only equal to this if the LRU handle is the list head of an
// empty list. List heads never have meaningful keys.
assert(next != this);
return Slice(key_data, key_length);
}
};重点关注三个 LRUHandle 的指针：
-
next_hash: 哈希表的实现采用的是拉链法来处理哈希冲突，用next_hash维护落到同一个 bucket 的对象。 -
next/prev: LRUCache 通过链表来维护缓存对象的使用“热度”和是否正在被调用端使用，这两个指针就是用来实现链表的。
HandleTable
HandleTable 是 LevelDB 采用拉链法实现的一个哈希表，主要提供了 Lookup、Insert、Remove 三个接口。没有做什么特殊优化，逻辑很清楚。
当哈希表的元素数量超过 list_ 的长度 length_ ，会调用 Resize 进行重新哈希（rehash）。直接扫描整个哈希表进行全量 rehash，如果哈希表很大，遇到 rehash 可能会导致系统抖动。
缓存淘汰策略
LRU
LRU 是一种常用的缓存淘汰策略，因为大部分情况下，数据的访问都是具有局部性的——最近访问过的数据，短时间内还被访问的概率比较大；而比较久没被访问的数据，短时间内会被访问的概率比较小。
当热点数据比较集中时，LRU 的缓存命中率比较高。但是在某些场景下，LRU 的缓存命中率会急剧下降，比如批量遍历。
LevelDB 在读参数 ReadOptions 提供了一个参数 fill_cache ，让上层控制是否要将 data block 放入到 block cache。
MySQL 的 InnoDB 的 LRU 缓存实现为了避免扫描操作污染 cache，采用了两级的 LRU cache。数据会先进入第一级 cache，一段时间之后还有访问再放到第二级 cache。
FIFO
FIFO，全称 First In First Out，其实就是一个队列，按先进先出的方法淘汰数据。新的数据插入队列尾部（入队），队列满了之后从队列的头部开始删除（出队）。
LFU
LFU，全称 Least Frequently Used，根据数据的访问频率来淘汰数据，适用于“如果数据过去被访问多次，那么将来被访问的频率也更高”的场景。
Random
随机淘汰缓存对象。好处是不用根据 LRU、FIFO、LFU 的要求维护缓存对象的顺序。
Block Cache
一个 SSTable 在被打开的时候，会通过 options.block_cache 的 NewId 为其分配一个唯一的 cache_id。
每个 data block 保存到 block cache 的 key 为 cache_id + offset。
由于 SSTable 是只读的，block 的读取和 block cache 的维护非常简单，具体参考 Table::BlockReader。
Table Cache
Table cache 的具体实现在 table_cache.h 和 table_cache.cc。
Table cache 的 key 是 SSTable 的 file_number，value 是一个 TableAndFile 对象。
TableAndFile 有两个成员变量 file 和 table，重点是 table 。
struct TableAndFile {
RandomAccessFile* file;
Table* table;
};Table 内部封装了 index 和 filter，以及其他一些 SSTable 的元数据（参考代码）。
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; // Handle to metaindex_block: saved from footer
Block* index_block;
};