加速leveldb查询性能之Cache技术

1.两种Cache
2.Table Cache
3.Block Cache

注：本节所有内容更新至星球。

学习本节之前最好提前需要学习前面两篇文章，这样便好理解本节内容。

多图文讲解leveldb之SST/LDB文件格式

【深入浅出leveldb】LRU与哈希表

1.两种Cache

在leveldb中有两种cache，分别table cache与block cache，这两个都是cache但不一样。

table cache是用来缓存sstable的文件描述符、index block、meta block等信息。

block cache是缓存解压后的data block。

两者相同点都是基于前面一节讲的ShardedLRUCache实现。

维度	Block Cache	Table Cache
缓存内容	数据块（存储实际键值对）	SSTable元数据（索引、文件句柄等）
优化目标	减少磁盘I/O和重复解压	减少文件打开和元数据解析开销
生命周期	随数据块访问频率动态更新	随SSTable文件的访问频率更新
配置参数	`Options.block_cache`	`Options.max_open_files`

通常来说一个block的大小在4K ~ 4MB之间，block cache默认是一个8MB的LRU cache。

table cache默认的文件数是990(可以理解为990个sstable文件或索引(data block index))，还保留十个左右的文件用于其他用途，并将其余990个文件交给 TableCache。

假设查询键K：

Table Cache帮助快速定位K在SSTable-X的Block 5。
Block Cache若已缓存Block 5，则直接读取；否则从磁盘加载Block 5并缓存。
整个过程避免了重复打开SSTable-X文件和解压Block 5的开销。

通过这种分层缓存设计，LevelDB在有限内存下显著提升了读取效率。

下面来讲一下这两块的实现。

2.Table Cache

开始是在DBImpl构造函数时创建table cache：

new TableCache(dbname_, options_, TableCacheSize(options_)

此时会通过NewLRUCache缓存990个文件。

lru cache中的kv分别是：

k = file name(压缩之后)
v = TableAndFile

struct TableAndFile {RandomAccessFile* file;  // 已打开的文件句柄Table* table;            // 对应的 SSTable 解析结构
};char buf[sizeof(file_number)];
EncodeFixed64(buf, file_number);
Slice key(buf, sizeof(buf));
TableAndFile* tf = new TableAndFile;
tf->file = file;
tf->table = table;
*handle = cache_->Insert(key, tf, 1, &DeleteEntry);

核心接口有4个，分别是：

1.Evict

删除这个文件的缓存

2.FindTable

比如现在要打开某一个sstable，通过table cache可以快速拿到sstable的索引/filter，随后快速查询data block数据。

这里其实就是对lru的操作：

k = 压缩的file_name不存在，打开sstable文件，并缓存下来，此时会在table cache的lru中写入<k = 压缩的 filename, v = TableAndFile>
如果k是直接在缓存中，直接从lru中拿到handle，随后从handle拿到 value就是TableAndFile。

Status TableCache::FindTable(uint64_t file_number, uint64_t file_size,Cache::Handle** handle) {}

3.Get

Get接口用来查询某个key在不在sstable中，如果在回调处理函数；不在返回即可。

所以 Get函数第一步调用FindTable拿到缓存的handle，然后从TableAndFile中拿到table，调用其接口InternalGet，随后释放这个handle。

InternalGet的实现步骤如下：

先通过data block index 看看这个key在不在
在的话在打开拿到了对应data block的handle
- 然后通过filter来查，不在的话直接返回不存在
- 存在的话再通过BlockReader拿到这个block并构造出iter
- 然后iter定位到key，找到调用回调处理即可。

4.NewIterator

根据key=file_name查找cache，并返回这个cache与基于这个cache创建的iterator。

2.Block Cache

block cache是在读取真正的data block的时候使用，函数是BlockReader。

根据输入的索引数据(二进制)，解析为对应data block的block handle，此时去看options有没有设置block_cache，如果没有直接ReadBlock，否则从block_cache中查询key是一个16字节，具体来说：

key = 8字节id + block的offset

value = Block

所以这里查询的时候，能查找到就拿到Block，否则ReadBlock之后写入cache。

if (cache_handle != nullptr) {block = reinterpret_cast<Block*>(block_cache->Value(cache_handle));
} else {s = ReadBlock(table->rep_->file, options, handle, &contents);if (s.ok()) {block = new Block(contents);if (contents.cachable && options.fill_cache) {cache_handle = block_cache->Insert(key, block, block->size(),&DeleteCachedBlock);}}
}