本文基于leveldb 1.22 版本展開搂妻，主要討論 LevelDB 的緩存 cache 實現(xiàn)蒙保。cache 可以根據(jù)數(shù)據(jù)內(nèi)容是否進(jìn)行了解壓縮分為 compressed cache 和 uncompressed cache。前者通常直接緩存磁盤數(shù)據(jù)塊的鏡像欲主，后者則緩存解壓后的數(shù)據(jù)塊邓厕。對于 LevelDB 而言逝嚎，在用戶態(tài)僅僅實現(xiàn)了對 uncompressed cache 的支持，由操作系統(tǒng)的 page cache 發(fā)揮 compressed cache 的作用详恼。而 RocksDB 則在這基礎(chǔ)上更進(jìn)一步补君，在用戶態(tài)實現(xiàn)了 compressed cache 的支持。
SSTable 文件布局
LevelDB 的數(shù)據(jù)存儲在 SSTable 文件中昧互，每個文件對應(yīng)一個 sorted table挽铁，即一系列按照 key 進(jìn)行排序的 entry。entry 可能有兩種類型：一種保存對應(yīng) key 的 value敞掘；另一種則保存了對應(yīng) key 的刪除標(biāo)記叽掘。LSM 的刪除操作是惰性的，在執(zhí)行 compaction 時數(shù)據(jù)的實際刪除才可能發(fā)生玖雁。
<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 文件的數(shù)據(jù)布局如上所示：
- data block 保存數(shù)據(jù)的 key/value 對更扁；
- meta block 目前有 filter meta block 和 stats meta block 兩種類型；
- metaindex block 包含對應(yīng)每個 meta block 的多個 entry赫冬，key 是 meta block 的名字浓镜，value 則是 meta block 的 offset 和 size；
- index block 包括對應(yīng)每個 data block 的多個 entry劲厌，key 是介于當(dāng)前 data block 的最后一個 key 和下一個 data block 的第一個 key 之間的值膛薛，value 則是 data block 的 offset 和 size；
- footer 存儲在 SSTable 文件的末尾补鼻，保存 metaindex block 和 index block 的 offset 和 size相叁，還包括一些補(bǔ)零和一個魔數(shù) 0xdb4775248b80fb57。
LevelDB 的 cache 根據(jù)緩存的數(shù)據(jù)類型分為兩種辽幌，緩存 meta block 數(shù)據(jù)的 table cache 和 緩存 data block 數(shù)據(jù)的 block cache增淹。
數(shù)據(jù)結(jié)構(gòu)
LevelDB 的兩種 cache 都基于共同的數(shù)據(jù)結(jié)構(gòu) ShardedLRUCache。數(shù)據(jù)的淘汰按照 LRU（the least recent used）規(guī)則乌企；根據(jù) key 的前4個 byte 計算 hash 值虑润，將其分布在16個 shard 上，每個 shard 的數(shù)據(jù)結(jié)構(gòu)為 LRUCache加酵。如此拳喻，可以將鎖的粒度降低為 shard 級別，提升 cache 的并發(fā)讀寫能力猪腕。
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 的實現(xiàn)與通常一樣冗澈，基于鏈表和 hash table 實現(xiàn)。其中鏈表存儲實際的數(shù)據(jù)陋葡，支持?jǐn)?shù)據(jù)的快速尾部插入和數(shù)據(jù)的移動亚亲；而 hash table 則存儲指向鏈表元素的指針，支持?jǐn)?shù)據(jù)的快速查詢。
LRUCache 維護(hù)了 in_use_ 和 lru_ 兩個 entry 鏈表捌归，其中 in_use_ 鏈表包括了當(dāng)前正在被客戶端引用的 entry肛响；lru_ 包括當(dāng)前沒有被客戶端引用的 entry，并按照 LRU 規(guī)則進(jìn)行了排序惜索。在進(jìn)行數(shù)據(jù)查詢時特笋，正在被客戶端訪問的 entry 引用計數(shù)自增1，entry 指針移動到 in_use_ 頭部巾兆；當(dāng)沒有客戶端引用時猎物，entry 引用計數(shù)此時為1，entry 指針移動到 lru_ 頭部角塑；當(dāng)有新的 entry 插入時蔫磨，entry 引用計數(shù)自增1。對于覆蓋更新的場景吉拳，淘汰與新插入 key 相同的已有 entry，并將 entry 加入到 in_use_ 頭部适揉。對于全新插入的場景留攒，將 entry 直接加入到 in_use_ 頭部，并淘汰 lru_ 中最舊的 entry嫉嘀。如此炼邀，entry 的所有權(quán)不歸屬于 cache 來管理，可以減少一次數(shù)據(jù)拷貝剪侮，提升性能拭宁。
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 的實現(xiàn)，提供的主要接口如下：
- Insert 實現(xiàn)數(shù)據(jù)的插入瓣俯。由于傳入的 key 和 value 所有權(quán)并不一定屬于 cache杰标，所以需要提供對應(yīng)數(shù)據(jù)的刪除函數(shù) deleter；
- Lookup 查找特定 key 對應(yīng)的 entry彩匕；
- Release 對應(yīng) entry 引用計數(shù)減1腔剂，若引用計數(shù)為0，則調(diào)用 deleter 刪除該 entry驼仪。通常用于釋放 Lookup 返回的 entry掸犬；
- Erase 從 hash table 中刪除該 key 對應(yīng)的entry，并且從 in_use_/lru_ 中刪除該 entry绪爸，若引用計數(shù)為0湾碎，調(diào)用 deleter 刪除該 entry；
- Value 讀取對應(yīng) entry 的值奠货，通常用于從 Lookup 讀取的 entry 讀取值介褥；
- NewId 每打開一個 table cache，就會生成一個新的 cache id；
- Prune 移除所有未使用（在 lru_ 中）的 entry呻顽；
- TotalCharge 返回內(nèi)存消耗數(shù)值雹顺。
cache 中的數(shù)據(jù)是文件的副本，讀取流程如下：
- 在 cache 中查找特定 key廊遍，若找到則直接返回相應(yīng)的 entry嬉愧；若未找到則繼續(xù)執(zhí)行；
- 從文件中讀取 key 對應(yīng) entry 到 cache 中喉前，再返回相應(yīng)的 entry
由于 LSM Tree 的 SSTable 文件的不變性没酣，SSTable 文件只會被刪除而不會被更改，因此無需考慮數(shù)據(jù)更新帶來的 cache 和文件數(shù)據(jù)不一致的問題卵迂， cache 也無需支持?jǐn)?shù)據(jù)的更新 裕便，這也是 LSM Tree 的 cache 實現(xiàn)一大特點。
由于 table cache 緩存的是 block cache 中 block 的元信息见咒，所以兩者需要結(jié)合起來發(fā)揮作用偿衰。一個完整的數(shù)據(jù)查詢流程是，先從 table cache 中獲取到元信息改览，再根據(jù)元信息去 block cache 或 SSTable 文件中查找相應(yīng)的 block 數(shù)據(jù)下翎。
table cache
table cache 中緩存的是 meta block 的數(shù)據(jù)，key 為 SSTable 文件對應(yīng)的 file_number宝当，這是一個在進(jìn)行 L0 compaction 時就確定的序號视事，在數(shù)據(jù)庫級別單調(diào)遞增且保證唯一。這個 file_number 同時也是 SSTable 文件的文件名庆揩。
在讀取過程中俐东，當(dāng) table cache 中找不到 key 對應(yīng)的 entry 時，需要從文件中加載數(shù)據(jù)構(gòu)建订晌。讀取通過 mmap 將整個文件映射到內(nèi)存中實現(xiàn)虏辫。先從文件中讀取固定長度（48 字節(jié)）的 footer，從 footer 中解析出 index block/metaindex block 的 offset 和 size 信息锈拨，最后讀取 index block 和 metaindex block 的信息乒裆。
在得到 index block 數(shù)據(jù)后，通常需要根據(jù) index 查找 data block推励。index 可以認(rèn)為是一個有序數(shù)組鹤耍，查找需要利用到二分查找。不同的是验辞，為了減少 key 所占用的存儲空間稿黄，LevelDB 采取了 key 壓縮技術(shù)，簡單來說就是每個若干個 key 保存一個完整的 key 的 entry 作為重啟點跌造，重啟點之間的 key 則只需要在重啟點的公共前綴基礎(chǔ)上存儲后綴即可杆怕。因此族购，在進(jìn)行二分查找時需要首先找到重啟點，根據(jù)最近的重啟點信息構(gòu)結(jié)合 entry 的非公共后綴找到最終需要查找的 entry陵珍。LevelDB 的 key 壓縮又是一個很有意思的話題寝杖，我們后續(xù)的 compaction 篇章再見。
block cache
block cache 中緩存的是 data block 的數(shù)據(jù)互纯，key 為 table cache 的 cache_id 和從 index 中獲取的 data block offset瑟幕。當(dāng) block cache 中找不到 key 對應(yīng)的 entry 時，將從 table cache 之前使用過的 mmap 內(nèi)存中加載數(shù)據(jù)構(gòu)建 block cache留潦，不會出現(xiàn)再次 mmap只盹。
總而言之，cache 是一種常用的用于加速磁盤文件訪問的手段兔院，在系統(tǒng)具備查詢熱點時可以顯著提升查詢性能殖卑。需要指出的是，在范圍查詢的場景下坊萝，cache 往往會因為大范圍的數(shù)據(jù)掃描導(dǎo)致熱數(shù)據(jù)被淘汰孵稽，而冷數(shù)據(jù)被加載至內(nèi)存中。系統(tǒng)的緩存命中率會急劇下降十偶，造成系統(tǒng)性能降低菩鲜。針對這個問題，InnoDB 存儲引擎將 buffer pool 調(diào)整分為 old扯键、young 兩個區(qū)域睦袖。因為范圍查詢引入的數(shù)據(jù)通常只會被訪問一次珊肃，這樣的數(shù)據(jù)將被放在 old 區(qū)域荣刑，而 young 區(qū)域則會保存多次訪問的熱點數(shù)據(jù)。
