LevelDB設計與實現 - 緩存機制
以RocksDB為存儲引擎的MyRocks是近幾年流行起來的MySQL分支，在Facebook等公司廣泛使用，網易杭研的資料庫內核團隊從2018年初開始系統研究MyRocks，目前已在內部進行小範圍推廣使用，效果比較理想。
在調研、測試和試用期間，積累了一些經驗，包括技術實現等。本系列想跟大家分享我們組內小夥伴做的LevelDB調研輸出，這是第三篇，介紹LevelDB的緩存機制。
第二篇鏈接：
溫正湖：LevelDB設計與實現 - 讀寫流程
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是會被淘汰的。
未完待續。。。
推薦閱讀：