漫談 LevelDB 數(shù)據(jù)結構之 LRU 緩存（ LRUCache）
本文轉載自微信公眾號「木鳥雜記」，作者穆尼奧 。轉載本文請聯(lián)系木鳥雜記公眾號。
早對 LevelDB 有所耳聞，這次心血來潮結合一些資料粗略過了遍代碼，果然名不虛傳。如果你對存儲感興趣、如果你想優(yōu)雅使用 C++、如果你想學習如何架構項目，都推薦來觀摩一下。更何況作者是 Sanjay Ghemawat 和 Jeff Dean 呢。
看過一遍如果不輸出點什么，以我的記性，定會很快拋諸腦后。便想寫點東西說說 LevelDB 之妙，但又不想走尋常路：從架構概覽說起，以模塊分析做合。讀代碼的這些天，一直在盤算從哪下筆比較好。在將將讀完之時，印象最深的反而是 LevelDB 的各種精妙的數(shù)據(jù)結構：貼合場景、從頭構建、剪裁得當、代碼精到。不妨， LevelDB 系列就從這些邊邊角角的小構件開始吧。
本系列主要想分享 LevelDB 中用到的三個工程中常用的經(jīng)典數(shù)據(jù)結構，分別是用以快速讀寫 memtable 的 Skip List、用以快速篩選 sstable 的 Bloom Filter 和用以部分緩存 sstable 的 LRUCache 。這是第三篇，LRUCache。
引子
LRU 是工程中多見的一個數(shù)據(jù)結構，常用于緩存場景。近年來，LRU 也是面試中一道炙手可熱的考題，一來工程用的多，二來代碼量較少，三來涉及的數(shù)據(jù)結構也很典型。LeetCode 中有一道相應的題目：lru-cache。相對實際場景，題目進行了簡化：本質上要求維護一個按訪問時間有序的 kv 集合，且 kv 皆是整數(shù)。經(jīng)典解法是使用一個哈希表(unordered_map)和一個雙向鏈表，哈希表解決索引問題，雙向鏈表維護訪問順序。這是我當時的一個解法，特點是用了兩個輔助函數(shù)，并且可以返回節(jié)點自身，以支持鏈式調用，從而簡化了代碼。
說回 LevelDB 源碼，作為一個工業(yè)品，它使用 的 LRUCache 又做了哪些優(yōu)化和變動呢?下面讓我們一塊來拆解下 LevelDB 中使用的 LRUCache，看看有什么不同。
本文首先明確 LRUCache 的使用方法，然后總覽分析 LRUCache 的實現(xiàn)思路，最后詳述相關數(shù)據(jù)結構的實現(xiàn)細節(jié)。
緩存使用
在分析 LRUCache 的實現(xiàn)之前，首先了解下 LRUCache 的使用方法，以明確 LRUCache 要解決的問題。以此為基礎，我們才能了解為什么要這么實現(xiàn)，甚至更進一步，探討有沒有更好的實現(xiàn)。
首先來看下 LevelDB 的導出接口 Cache：
- // 插入一個鍵值對（key，value）到緩存（cache）中，
- // 并從緩存總容量中減去該鍵值對所占額度（charge）
- //
- // 返回指向該鍵值對的句柄（handle），調用者在用完句柄后，
- // 需要調用 this->Release(handle) 進行釋放
- //
- // 在鍵值對不再被使用時，鍵值對會被傳入的 deleter 參數(shù)
- // 釋放
- virtual Handle* Insert(const Slice& key, void* value, size_t charge,
- void (*deleter)(const Slice& key, void* value)) = 0;
- // 如果緩存中沒有相應鍵（key），則返回 nullptr
- //
- // 否則返回指向對應鍵值對的句柄（Handle）。調用者用完句柄后，
- // 要記得調用 this->Release(handle) 進行釋放
- virtual Handle* Lookup(const Slice& key) = 0;
- // 釋放 Insert/Lookup 函數(shù)返回的句柄
- // 要求：該句柄沒有被釋放過，即不能多次釋放
- // 要求：該句柄必須是同一個實例返回的
- virtual void Release(Handle* handle) = 0;
- // 獲取句柄中的值，類型為 void*（表示任意用戶自定義類型）
- // 要求：該句柄沒有被釋放
- // 要求：該句柄必須由同一實例所返回
- virtual void* Value(Handle* handle) = 0;
- // 如果緩存中包含給定鍵所指向的條目，則刪除之。
- // 需要注意的是，只有在所有持有該條目句柄都釋放時，該條目所占空間才會真正被釋放
- virtual void Erase(const Slice& key) = 0;
- // 返回一個自增的數(shù)值 id。當一個緩存實例由多個客戶端共享時，
- // 為了避免多個客戶端的鍵沖突，每個客戶端可能想獲取一個獨有
- // 的 id，并將其作為鍵的前綴。類似于給每個客戶端一個單獨的命名空間。
- virtual uint64_t NewId() = 0;
- // 驅逐全部沒有被使用的數(shù)據(jù)條目
- // 內存吃緊型的應用可能想利用此接口定期釋放內存。
- // 基類中的 Prune 默認實現(xiàn)為空，但強烈建議所有子類自行實現(xiàn)。
- // 將來的版本可能會增加一個默認實現(xiàn)。
- virtual void Prune() {}
- // 返回當前緩存中所有數(shù)據(jù)條目所占容量總和的一個預估
- virtual size_t TotalCharge() const = 0;
依據(jù)上述接口，可捋出 LevelDB 緩存相關需求：
- 多線程支持
- 性能需求
- 數(shù)據(jù)條目的生命周期管理
用狀態(tài)機來表示 Cache 中的 Entry 的生命周期如下：
leveldb entry lifecycle
可以看出該狀態(tài)機要比 LeetCode 中復雜一些，首先增加了多線程的引用，其次需要區(qū)分被引用(inuse) 和空閑(idle) 狀態(tài)。
多個線程可以通過 Insert、Lookup 對同一個條目進行插入和引用，因此緩存需要維護每個條目(entry)的引用數(shù)量。只有引用數(shù)量為 0 的條目才會進入一個待驅逐(idle)的狀態(tài)，將所有待驅逐的條目按 LRU 順序排序，在用量超過容量時，將依據(jù)上述順序對最久沒使用過的條目進行驅逐。
此外，需要進行線程間同步和互斥，以保證 Cache 是線程安全的，最簡單的方法是整個 Cache 使用一把鎖，但這樣多線程間爭搶比較嚴重，會有性能問題。
接下來看看 LevelDB 的 LRUCache 是如何解決這些問題的。
思路總覽
總體上來說，LevelDB 的 LRUCache 也使用了哈希表和雙向鏈表的實現(xiàn)思路，但又有些不同：
使用數(shù)組+鏈表處理沖突定制了一個極簡哈希表，便于控制分配以及伸縮。
多線程支持。了提高并發(fā)，引入了分片;為了區(qū)分是否被客戶端引用，引入兩個雙向鏈表。
整個代碼相當簡潔，思想也比較直觀。
定制哈希表
LevelDB 中哈希表保持桶的個數(shù)為 2 的次冪，從而使用位運算來通過鍵的哈希值快速計算出桶位置。通過 key 的哈希值來獲取桶的句柄方法如下：
LRUHandle** ptr = &list_[hash & (length_ - 1)];
每次調整時，在擴張時將桶數(shù)量增加一倍，在縮減時將桶數(shù)量減少一倍，并需要對所有數(shù)據(jù)條目進行重新分桶。
兩個鏈表
LevelDB 使用兩個雙向鏈表保存數(shù)據(jù)，緩存中的所有數(shù)據(jù)要么在一個鏈表中，要么在另一個鏈表中，但不可能同時存在于兩個鏈表中。這兩個鏈表分別是：
- in-use 鏈表。所有正在被客戶端使用的數(shù)據(jù)條目(an kv item)都存在該鏈表中，該鏈表是無序的，因為在容量不夠時，此鏈表中的條目是一定不能夠被驅逐的，因此也并不需要維持一個驅逐順序。
- lru 鏈表。所有已經(jīng)不再為客戶端使用的條目都放在 lru 鏈表中，該鏈表按最近使用時間有序，當容量不夠用時，會驅逐此鏈表中最久沒有被使用的條目。
另外值得一提的是，哈希表中用來處理沖突的鏈表節(jié)點與雙向鏈表中的節(jié)點使用的是同一個數(shù)據(jù)結構(LRUHandle)，但在串起來時，用的是 LRUHandle 中不同指針字段。
數(shù)據(jù)結構
LRUCache 實現(xiàn)主要涉及到了四個數(shù)據(jù)結構：LRUHandle、HandleTable、LRUCache 和 ShardedLRUCache。前三者組織形式如下：
lru cache architecture
ShardedLRUCache 由一組 LRUCache 組成，每個 LRUCache 作為一個分片，同時是一個加鎖的粒度，他們都實現(xiàn)了 Cache 接口。下圖畫了 4 個分片，代碼中是 16 個。
shared lru cache
LRUHandle——基本數(shù)據(jù)單元
LRUHandle 是雙向鏈表和哈希表的基本構成單位。其結構如下：
- struct LRUHandle {
- void* value;
- void (*deleter)(const Slice&, void* value); // 釋放 key,value 空間的用戶回調
- LRUHandle* next_hash; // 用于 hashtable 中鏈表處理沖突
- LRUHandle* next; // 用于雙向鏈表中維護 LRU 順序
- LRUHandle* prev;
- size_t charge; // TODO(opt): Only allow uint32_t?
- size_t key_length;
- bool in_cache; // 該 handle 是否在 cache table 中
- uint32_t refs; // 該 handle 被引用的次數(shù)
- uint32_t hash; // key 的 hash 值，用于確定分片和快速比較
- char key_data[1]; // 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 中的 refs 和我們前一小節(jié)中所畫圖中的狀態(tài)機中 ref 含義并不一樣。LevelDB 實現(xiàn)時，把 Cache 的引用也算一個引用。因此在 Insert 時，會令 refs = 2，一個為客戶端的引用，一個為 LRUCache 的引用。refs==1 && in_cache即說明該數(shù)據(jù)條目只被 LRUCache 引用了。
這個設計開始看著有點別扭，但是想了想反而覺得很貼切自然。
HandleTable——哈希表索引
使用位操作來對 key 進行路由，使用鏈表來處理沖突，實現(xiàn)比較直接。鏈表中節(jié)點是無序的，因此每次查找都需要全鏈表遍歷。
其中值得一說的是 FindPointer 這個查找輔助函數(shù)，該函數(shù)用了雙重指針，在增刪節(jié)點時比較簡潔，開始時可能不太好理解。在通常實現(xiàn)中，增刪節(jié)點時，我們會找其前驅節(jié)點。但其實增刪只用到了前驅節(jié)點中的 next_hash 指針：
- 刪除：會修改 next_hash 的指向。
- 新增：首先讀取 next_hash，找到下一個鏈節(jié)，將其鏈到待插入節(jié)點后邊，然后修改前驅節(jié)點 next_hash 指向。
由于本質上只涉及到前驅節(jié)點 next_hash 指針的讀寫，因此返回前驅節(jié)點 next_hash 指針的指針是一個更簡潔的做法：
- LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
- LRUHandle** ptr = &list_[hash & (length_ - 1)];
- while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) {
- ptr = &(*ptr)->next_hash;
- }
- return ptr;
- }
該函數(shù)首先使用 hash 值通過位運算，定位到某個桶。然后在該桶中逐個遍歷節(jié)點：
- 如果節(jié)點的 hash 或者 key 匹配上，則返回該節(jié)點的雙重指針(前驅節(jié)點的 next_hash 指針的指針)。
- 否則，返回該鏈表的最后一個節(jié)點的雙重指針(邊界情況，如果是空鏈表，最后一個節(jié)點便是桶頭)。
由于返回的是其前驅節(jié)點 next_hash 的地址，因此在刪除時，只需將該 next_hash 改為待刪除節(jié)點后繼節(jié)點地址，然后返回待刪除節(jié)點即可。
- LRUHandle* Remove(const Slice& key, uint32_t hash) {
- LRUHandle** ptr = FindPointer(key, hash);
- LRUHandle* result = *ptr;
- if (result != nullptr) {
- *ptr = result->next_hash;
- --elems_;
- }
- return result;
- }
在插入時，也是利用 FindPointer 函數(shù)找到待插入桶的鏈表尾部節(jié)點 next_hash 指針的指針，對于邊界條件空桶來說，會找到桶的空頭結點。之后需要判斷是新插入還是替換，如果替換，則把被替換的舊節(jié)點返回，下面是插入新節(jié)點示意圖：
leveldb lru table insert
如果是新插入節(jié)點，節(jié)點總數(shù)會變多，如果節(jié)點總數(shù)多到大于某個閾值后，為了保持哈希表的性能，就需要進行 resize，以增加桶的個數(shù)，同時將所有節(jié)點進行重新分桶。LevelDB 選定的閾值是 length_ —— 桶的個數(shù)。
resize 的操作比較重，因為需要對所有節(jié)點進行重新分桶，而為了保證線程安全，需要加鎖，但這會使得哈希表一段時間不能提供服務。當然通過分片已經(jīng)減小了單個分片中節(jié)點的數(shù)量，但如果分片不均勻，仍然會比較重。這里有提到一種漸進式的遷移方法：Dynamic-sized NonBlocking Hash table，可以將遷移時間進行均攤，有點類似于 Go GC 的演化。
LRUCache—— 哈希表索引+雙向環(huán)形鏈表
將之前分析過的導出接口 Cache 所包含的函數(shù)去掉后，LRUCache 類簡化如下：
- class LRUCache {
- public:
- LRUCache();
- ~LRUCache();
- // 從構造函數(shù)分離出此參數(shù)的設置方法，可以讓調用者在使用時進行靈活的調整
- void SetCapacity(size_t capacity) { capacity_ = capacity; }
- private:
- // 輔助函數(shù)：將鏈節(jié) e 從雙向鏈表中摘除
- void LRU_Remove(LRUHandle* e);
- // 輔助函數(shù)：將鏈節(jié) e 追加到鏈表頭
- void LRU_Append(LRUHandle* list, LRUHandle* e);
- // 輔助函數(shù)：增加鏈節(jié) e 的引用
- void Ref(LRUHandle* e);
- // 輔助函數(shù)：減少鏈節(jié) e 的引用
- void Unref(LRUHandle* e);
- // 輔助函數(shù)：從緩存中刪除單個鏈節(jié) e
- bool FinishErase(LRUHandle* e) EXCLUSIVE_LOCKS_REQUIRED(mutex_);
- // 在使用 LRUCache 前必須先初始化此值
- size_t capacity_;
- // mutex_ 用以保證此后的字段的線程安全
- mutable port::Mutex mutex_;
- size_t usage_ GUARDED_BY(mutex_);
- // lru 雙向鏈表的空表頭
- // lru.prev 指向最新的條目，lru.next 指向最老的條目
- // 此鏈表中所有條目都滿足 refs==1 和 in_cache==true
- // 表示所有條目只被緩存引用，而沒有客戶端在使用
- LRUHandle lru_ GUARDED_BY(mutex_);
- // in-use 雙向鏈表的空表頭
- // 保存所有仍然被客戶端引用的條目
- // 由于在被客戶端引用的同時還被緩存引用，
- // 肯定有 refs >= 2 和 in_cache==true.
- LRUHandle in_use_ GUARDED_BY(mutex_);
- // 所有條目的哈希表索引
- HandleTable table_ GUARDED_BY(mutex_);
- };
可以看出該實現(xiàn)有以下特點：
- 使用兩個雙向鏈表將整個緩存分成兩個不相交的集合：被客戶端引用的 in-use 鏈表，和不被任何客戶端引用的 lru_ 鏈表。
- 每個雙向鏈表使用了一個空的頭指針，以便于處理邊界情況。并且表頭的 prev 指針指向最新的條目，next 指針指向最老的條目，從而形成了一個雙向環(huán)形鏈表。
- 使用 usage_ 表示緩存當前已用量，用 capacity_ 表示該緩存總量。
- 抽象出了幾個基本操作：LRU_Remove、LRU_Append、Ref、Unref 作為輔助函數(shù)進行復用。
- 每個 LRUCache 由一把鎖 mutex_ 守護。
了解了所有字段，以及之前的狀態(tài)機，每個函數(shù)的實現(xiàn)應該比較容易理解。下面不再一一羅列所有函數(shù)的實現(xiàn)，僅挑比較復雜的 Insert 進行注釋說明：
- Cache::Handle* LRUCache::Insert(const Slice& key, uint32_t hash, void* value,
- size_t charge,
- void (*deleter)(const Slice& key,
- void* value)) {
- MutexLock l(&mutex_);
- // 構建數(shù)據(jù)條目句柄
- LRUHandle* e =
- reinterpret_cast<LRUHandle*>(malloc(sizeof(LRUHandle) - 1 + key.size()));
- e->value = value;
- e->deleter = deleter;
- e->charge = charge;
- e->key_length = key.size();
- e->hash = hash;
- e->in_cache = false;
- e->refs = 1; // 客戶端引用
- std::memcpy(e->key_data, key.data(), key.size());
- if (capacity_ > 0) {
- e->refs++; // 緩存本身引用
- e->in_cache = true;
- LRU_Append(&in_use_, e);
- usage_ += charge;
- FinishErase(table_.Insert(e)); // 如果是替換，要刪除原來數(shù)據(jù)
- } else { // capacity_==0 時表示關閉緩存，不進行任何緩存
- // next 會在 key() 函數(shù)中被 assert 測試，因此要初始化一下
- e->next = nullptr;
- }
- // 當超數(shù)據(jù)條目超出容量時，根據(jù) LRU 策略將不被客戶端引用的數(shù)據(jù)條目驅逐出內存
- while (usage_ > capacity_ && lru_.next != &lru_) {
- LRUHandle* old = lru_.next;
- assert(old->refs == 1);
- bool erased = FinishErase(table_.Remove(old->key(), old->hash));
- if (!erased) { // to avoid unused variable when compiled NDEBUG
- assert(erased);
- }
- }
- return reinterpret_cast<Cache::Handle*>(e);
- }
ShardedLRUCache——分片 LRUCache
引入 SharedLRUCache 的目的在于減小加鎖的粒度，提高讀寫并行度。策略比較簡潔—— 利用 key 哈希值的前 kNumShardBits = 4 個 bit 作為分片路由，可以支持 kNumShards = 1 << kNumShardBits 16 個分片。通過 key 的哈希值計算分片索引的函數(shù)如下：
- static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }
由于 LRUCache 和 ShardedLRUCache 都實現(xiàn)了 Cache 接口，因此 ShardedLRUCache 只需將所有 Cache 接口操作路由到對應 Shard 即可，總體來說 ShardedLRUCache 沒有太多邏輯，更像一個 Wrapper，這里不再贅述。
參考
LevelDB 緩存代碼：https://github.com/google/leveldb/blob/master/util/cache.cc
LevelDB handbook 緩存系統(tǒng)：https://leveldb-handbook.readthedocs.io/zh/latest/cache.html#dynamic-sized-nonblocking-hash-table【編輯推薦】
原文鏈接：https://mp.weixin.qq.com/s/zcvgWO4cIxfphfE7I41GYA
