[[398307]]

本文轉(zhuǎn)載自微信公眾號(hào)「木鳥雜記」，作者穆尼奧  。轉(zhuǎn)載本文請聯(lián)系木鳥雜記公眾號(hào)。

早對 LevelDB 有所耳聞，這次心血來潮結(jié)合一些資料粗略過了遍代碼，果然名不虛傳。如果你對存儲(chǔ)感興趣、如果你想優(yōu)雅使用 C++、如果你想學(xué)習(xí)如何架構(gòu)項(xiàng)目，都推薦來觀摩一下。更何況作者是 Sanjay Ghemawat 和 Jeff Dean 呢。

看過一遍如果不輸出點(diǎn)什么，以我的記性，定會(huì)很快拋諸腦后。便想寫點(diǎn)東西說說 LevelDB 之妙，但又不想走尋常路：從架構(gòu)概覽說起，以模塊分析做合。讀代碼的這些天，一直在盤算從哪下筆比較好。在將將讀完之時(shí)，印象最深的反而是 LevelDB 的各種精妙的數(shù)據(jù)結(jié)構(gòu)：貼合場景、從頭構(gòu)建、剪裁得當(dāng)、代碼精到。不妨， LevelDB 系列就從這些邊邊角角的小構(gòu)件開始吧。

本系列主要想分享 LevelDB 中用到的三個(gè)工程中常用的經(jīng)典數(shù)據(jù)結(jié)構(gòu)，分別是用以快速讀寫 memtable 的 Skip List、用以快速篩選 sstable 的 Bloom Filter 和用以部分緩存 sstable 的 LRUCache 。這是第三篇，LRUCache。

引子

LRU 是工程中多見的一個(gè)數(shù)據(jù)結(jié)構(gòu)，常用于緩存場景。近年來，LRU 也是面試中一道炙手可熱的考題，一來工程用的多，二來代碼量較少，三來涉及的數(shù)據(jù)結(jié)構(gòu)也很典型。LeetCode 中有一道相應(yīng)的題目：lru-cache。相對實(shí)際場景，題目進(jìn)行了簡化：本質(zhì)上要求維護(hù)一個(gè)按訪問時(shí)間有序的 kv 集合，且 kv 皆是整數(shù)。經(jīng)典解法是使用一個(gè)哈希表(unordered_map)和一個(gè)雙向鏈表，哈希表解決索引問題，雙向鏈表維護(hù)訪問順序。這是我當(dāng)時(shí)的一個(gè)解法，特點(diǎn)是用了兩個(gè)輔助函數(shù)，并且可以返回節(jié)點(diǎn)自身，以支持鏈?zhǔn)秸{(diào)用，從而簡化了代碼。

說回 LevelDB 源碼，作為一個(gè)工業(yè)品，它使用 的 LRUCache 又做了哪些優(yōu)化和變動(dòng)呢?下面讓我們一塊來拆解下 LevelDB 中使用的 LRUCache，看看有什么不同。

本文首先明確 LRUCache 的使用方法，然后總覽分析 LRUCache 的實(shí)現(xiàn)思路，最后詳述相關(guān)數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)細(xì)節(jié)。

緩存使用

在分析 LRUCache 的實(shí)現(xiàn)之前，首先了解下 LRUCache 的使用方法，以明確 LRUCache 要解決的問題。以此為基礎(chǔ)，我們才能了解為什么要這么實(shí)現(xiàn)，甚至更進(jìn)一步，探討有沒有更好的實(shí)現(xiàn)。

首先來看下 LevelDB 的導(dǎo)出接口 Cache：

// 插入一個(gè)鍵值對（key，value）到緩存（cache）中， 
// 并從緩存總?cè)萘恐袦p去該鍵值對所占額度（charge）  
//  
// 返回指向該鍵值對的句柄（handle），調(diào)用者在用完句柄后， 
// 需要調(diào)用 this->Release(handle) 進(jìn)行釋放 
// 
// 在鍵值對不再被使用時(shí)，鍵值對會(huì)被傳入的 deleter 參數(shù) 
// 釋放 
virtual Handle* Insert(const Slice& key, void* value, size_t charge, 
                       void (*deleter)(const Slice& key, void* value)) = 0; 
 
// 如果緩存中沒有相應(yīng)鍵（key），則返回 nullptr 
// 
// 否則返回指向?qū)?yīng)鍵值對的句柄（Handle）。調(diào)用者用完句柄后， 
// 要記得調(diào)用 this->Release(handle) 進(jìn)行釋放 
virtual Handle* Lookup(const Slice& key) = 0; 
 
// 釋放 Insert/Lookup 函數(shù)返回的句柄 
// 要求：該句柄沒有被釋放過，即不能多次釋放 
// 要求：該句柄必須是同一個(gè)實(shí)例返回的 
virtual void Release(Handle* handle) = 0; 
 
// 獲取句柄中的值，類型為 void*（表示任意用戶自定義類型） 
// 要求：該句柄沒有被釋放 
// 要求：該句柄必須由同一實(shí)例所返回 
virtual void* Value(Handle* handle) = 0; 
 
// 如果緩存中包含給定鍵所指向的條目，則刪除之。 
// 需要注意的是，只有在所有持有該條目句柄都釋放時(shí)，該條目所占空間才會(huì)真正被釋放 
virtual void Erase(const Slice& key) = 0; 
 
// 返回一個(gè)自增的數(shù)值 id。當(dāng)一個(gè)緩存實(shí)例由多個(gè)客戶端共享時(shí)， 
// 為了避免多個(gè)客戶端的鍵沖突，每個(gè)客戶端可能想獲取一個(gè)獨(dú)有 
// 的 id，并將其作為鍵的前綴。類似于給每個(gè)客戶端一個(gè)單獨(dú)的命名空間。 
virtual uint64_t NewId() = 0; 
 
// 驅(qū)逐全部沒有被使用的數(shù)據(jù)條目 
// 內(nèi)存吃緊型的應(yīng)用可能想利用此接口定期釋放內(nèi)存。 
// 基類中的 Prune 默認(rèn)實(shí)現(xiàn)為空，但強(qiáng)烈建議所有子類自行實(shí)現(xiàn)。 
// 將來的版本可能會(huì)增加一個(gè)默認(rèn)實(shí)現(xiàn)。 
virtual void Prune() {} 
 
// 返回當(dāng)前緩存中所有數(shù)據(jù)條目所占容量總和的一個(gè)預(yù)估 
virtual size_t TotalCharge() const = 0; 

依據(jù)上述接口，可捋出 LevelDB 緩存相關(guān)需求：

1. 多線程支持
2. 性能需求
3. 數(shù)據(jù)條目的生命周期管理

用狀態(tài)機(jī)來表示 Cache 中的 Entry 的生命周期如下：

leveldb entry lifecycle

可以看出該狀態(tài)機(jī)要比 LeetCode 中復(fù)雜一些，首先增加了多線程的引用，其次需要區(qū)分被引用(inuse) 和空閑(idle) 狀態(tài)。

多個(gè)線程可以通過 Insert、Lookup 對同一個(gè)條目進(jìn)行插入和引用，因此緩存需要維護(hù)每個(gè)條目(entry)的引用數(shù)量。只有引用數(shù)量為 0 的條目才會(huì)進(jìn)入一個(gè)待驅(qū)逐(idle)的狀態(tài)，將所有待驅(qū)逐的條目按 LRU 順序排序，在用量超過容量時(shí)，將依據(jù)上述順序?qū)ψ罹脹]使用過的條目進(jìn)行驅(qū)逐。

此外，需要進(jìn)行線程間同步和互斥，以保證 Cache 是線程安全的，最簡單的方法是整個(gè) Cache 使用一把鎖，但這樣多線程間爭搶比較嚴(yán)重，會(huì)有性能問題。

接下來看看 LevelDB 的 LRUCache 是如何解決這些問題的。

思路總覽

總體上來說，LevelDB 的 LRUCache 也使用了哈希表和雙向鏈表的實(shí)現(xiàn)思路，但又有些不同：

使用數(shù)組+鏈表處理沖突定制了一個(gè)極簡哈希表，便于控制分配以及伸縮。

多線程支持。了提高并發(fā)，引入了分片;為了區(qū)分是否被客戶端引用，引入兩個(gè)雙向鏈表。

整個(gè)代碼相當(dāng)簡潔，思想也比較直觀。

定制哈希表

LevelDB 中哈希表保持桶的個(gè)數(shù)為 2 的次冪，從而使用位運(yùn)算來通過鍵的哈希值快速計(jì)算出桶位置。通過 key 的哈希值來獲取桶的句柄方法如下：

LRUHandle** ptr = &list_[hash & (length_ - 1)];

每次調(diào)整時(shí)，在擴(kuò)張時(shí)將桶數(shù)量增加一倍，在縮減時(shí)將桶數(shù)量減少一倍，并需要對所有數(shù)據(jù)條目進(jìn)行重新分桶。

兩個(gè)鏈表

LevelDB 使用兩個(gè)雙向鏈表保存數(shù)據(jù)，緩存中的所有數(shù)據(jù)要么在一個(gè)鏈表中，要么在另一個(gè)鏈表中，但不可能同時(shí)存在于兩個(gè)鏈表中。這兩個(gè)鏈表分別是：

1. in-use 鏈表。所有正在被客戶端使用的數(shù)據(jù)條目(an kv item)都存在該鏈表中，該鏈表是無序的，因?yàn)樵谌萘坎粔驎r(shí)，此鏈表中的條目是一定不能夠被驅(qū)逐的，因此也并不需要維持一個(gè)驅(qū)逐順序。
2. lru 鏈表。所有已經(jīng)不再為客戶端使用的條目都放在 lru 鏈表中，該鏈表按最近使用時(shí)間有序，當(dāng)容量不夠用時(shí)，會(huì)驅(qū)逐此鏈表中最久沒有被使用的條目。

另外值得一提的是，哈希表中用來處理沖突的鏈表節(jié)點(diǎn)與雙向鏈表中的節(jié)點(diǎn)使用的是同一個(gè)數(shù)據(jù)結(jié)構(gòu)(LRUHandle)，但在串起來時(shí)，用的是 LRUHandle 中不同指針字段。

數(shù)據(jù)結(jié)構(gòu)

LRUCache 實(shí)現(xiàn)主要涉及到了四個(gè)數(shù)據(jù)結(jié)構(gòu)：LRUHandle、HandleTable、LRUCache 和 ShardedLRUCache。前三者組織形式如下：

lru cache architecture

ShardedLRUCache 由一組 LRUCache 組成，每個(gè) LRUCache 作為一個(gè)分片，同時(shí)是一個(gè)加鎖的粒度，他們都實(shí)現(xiàn)了 Cache 接口。下圖畫了 4 個(gè)分片，代碼中是 16 個(gè)。

shared lru cache

LRUHandle——基本數(shù)據(jù)單元

LRUHandle 是雙向鏈表和哈希表的基本構(gòu)成單位。其結(jié)構(gòu)如下：

struct LRUHandle { 
  void* value; 
  void (*deleter)(const Slice&, void* value); // 釋放 key,value 空間的用戶回調(diào) 
  LRUHandle* next_hash;  // 用于 hashtable 中鏈表處理沖突 
  LRUHandle* next;       // 用于雙向鏈表中維護(hù) 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)機(jī)中 ref 含義并不一樣。LevelDB 實(shí)現(xiàn)時(shí)，把 Cache 的引用也算一個(gè)引用。因此在 Insert 時(shí)，會(huì)令 refs = 2，一個(gè)為客戶端的引用，一個(gè)為 LRUCache 的引用。refs==1 && in_cache即說明該數(shù)據(jù)條目只被 LRUCache 引用了。

這個(gè)設(shè)計(jì)開始看著有點(diǎn)別扭，但是想了想反而覺得很貼切自然。

HandleTable——哈希表索引

使用位操作來對 key 進(jìn)行路由，使用鏈表來處理沖突，實(shí)現(xiàn)比較直接。鏈表中節(jié)點(diǎn)是無序的，因此每次查找都需要全鏈表遍歷。

其中值得一說的是 FindPointer 這個(gè)查找輔助函數(shù)，該函數(shù)用了雙重指針，在增刪節(jié)點(diǎn)時(shí)比較簡潔，開始時(shí)可能不太好理解。在通常實(shí)現(xiàn)中，增刪節(jié)點(diǎn)時(shí)，我們會(huì)找其前驅(qū)節(jié)點(diǎn)。但其實(shí)增刪只用到了前驅(qū)節(jié)點(diǎn)中的 next_hash 指針：

1. 刪除：會(huì)修改 next_hash 的指向。
2. 新增：首先讀取 next_hash，找到下一個(gè)鏈節(jié)，將其鏈到待插入節(jié)點(diǎn)后邊，然后修改前驅(qū)節(jié)點(diǎn) next_hash 指向。

由于本質(zhì)上只涉及到前驅(qū)節(jié)點(diǎn) next_hash 指針的讀寫，因此返回前驅(qū)節(jié)點(diǎn) next_hash 指針的指針是一個(gè)更簡潔的做法：

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 值通過位運(yùn)算，定位到某個(gè)桶。然后在該桶中逐個(gè)遍歷節(jié)點(diǎn)：

1. 如果節(jié)點(diǎn)的 hash 或者 key 匹配上，則返回該節(jié)點(diǎn)的雙重指針(前驅(qū)節(jié)點(diǎn)的 next_hash 指針的指針)。
2. 否則，返回該鏈表的最后一個(gè)節(jié)點(diǎn)的雙重指針(邊界情況，如果是空鏈表，最后一個(gè)節(jié)點(diǎn)便是桶頭)。

由于返回的是其前驅(qū)節(jié)點(diǎn) next_hash 的地址，因此在刪除時(shí)，只需將該 next_hash 改為待刪除節(jié)點(diǎn)后繼節(jié)點(diǎn)地址，然后返回待刪除節(jié)點(diǎn)即可。

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; 
} 

在插入時(shí)，也是利用 FindPointer 函數(shù)找到待插入桶的鏈表尾部節(jié)點(diǎn) next_hash 指針的指針，對于邊界條件空桶來說，會(huì)找到桶的空頭結(jié)點(diǎn)。之后需要判斷是新插入還是替換，如果替換，則把被替換的舊節(jié)點(diǎn)返回，下面是插入新節(jié)點(diǎn)示意圖：

leveldb lru table insert

如果是新插入節(jié)點(diǎn)，節(jié)點(diǎn)總數(shù)會(huì)變多，如果節(jié)點(diǎn)總數(shù)多到大于某個(gè)閾值后，為了保持哈希表的性能，就需要進(jìn)行 resize，以增加桶的個(gè)數(shù)，同時(shí)將所有節(jié)點(diǎn)進(jìn)行重新分桶。LevelDB 選定的閾值是 length_ —— 桶的個(gè)數(shù)。

resize 的操作比較重，因?yàn)樾枰獙λ泄?jié)點(diǎn)進(jìn)行重新分桶，而為了保證線程安全，需要加鎖，但這會(huì)使得哈希表一段時(shí)間不能提供服務(wù)。當(dāng)然通過分片已經(jīng)減小了單個(gè)分片中節(jié)點(diǎn)的數(shù)量，但如果分片不均勻，仍然會(huì)比較重。這里有提到一種漸進(jìn)式的遷移方法：Dynamic-sized NonBlocking Hash table，可以將遷移時(shí)間進(jìn)行均攤，有點(diǎn)類似于 Go GC 的演化。

LRUCache—— 哈希表索引+雙向環(huán)形鏈表

將之前分析過的導(dǎo)出接口 Cache 所包含的函數(shù)去掉后，LRUCache 類簡化如下：

class LRUCache { 
 public: 
  LRUCache(); 
  ~LRUCache(); 
 
  // 從構(gòu)造函數(shù)分離出此參數(shù)的設(shè)置方法，可以讓調(diào)用者在使用時(shí)進(jìn)行靈活的調(diào)整 
  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ù)：從緩存中刪除單個(gè)鏈節(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 雙向鏈表的空表頭 
  // 保存所有仍然被客戶端引用的條目 
  // 由于在被客戶端引用的同時(shí)還被緩存引用， 
  // 肯定有 refs >= 2 和 in_cache==true. 
  LRUHandle in_use_ GUARDED_BY(mutex_); 
 
  // 所有條目的哈希表索引 
  HandleTable table_ GUARDED_BY(mutex_); 
}; 

可以看出該實(shí)現(xiàn)有以下特點(diǎn)：

1. 使用兩個(gè)雙向鏈表將整個(gè)緩存分成兩個(gè)不相交的集合：被客戶端引用的 in-use 鏈表，和不被任何客戶端引用的 lru_ 鏈表。
2. 每個(gè)雙向鏈表使用了一個(gè)空的頭指針，以便于處理邊界情況。并且表頭的 prev 指針指向最新的條目，next 指針指向最老的條目，從而形成了一個(gè)雙向環(huán)形鏈表。
3. 使用 usage_ 表示緩存當(dāng)前已用量，用 capacity_ 表示該緩存總量。
4. 抽象出了幾個(gè)基本操作：LRU_Remove、LRU_Append、Ref、Unref 作為輔助函數(shù)進(jìn)行復(fù)用。
5. 每個(gè) LRUCache 由一把鎖 mutex_ 守護(hù)。

了解了所有字段，以及之前的狀態(tài)機(jī)，每個(gè)函數(shù)的實(shí)現(xiàn)應(yīng)該比較容易理解。下面不再一一羅列所有函數(shù)的實(shí)現(xiàn)，僅挑比較復(fù)雜的 Insert 進(jìn)行注釋說明：

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_); 
 
  // 構(gòu)建數(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)); // 如果是替換，要?jiǎng)h除原來數(shù)據(jù) 
  } else {  // capacity_==0 時(shí)表示關(guān)閉緩存，不進(jìn)行任何緩存 
    // next 會(huì)在 key() 函數(shù)中被 assert 測試，因此要初始化一下 
    e->next = nullptr; 
  } 
 
  // 當(dāng)超數(shù)據(jù)條目超出容量時(shí)，根據(jù) LRU 策略將不被客戶端引用的數(shù)據(jù)條目驅(qū)逐出內(nèi)存 
  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 個(gè) bit 作為分片路由，可以支持 kNumShards = 1 << kNumShardBits 16 個(gè)分片。通過 key 的哈希值計(jì)算分片索引的函數(shù)如下：

static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); } 

由于 LRUCache 和 ShardedLRUCache 都實(shí)現(xiàn)了 Cache 接口，因此 ShardedLRUCache 只需將所有 Cache 接口操作路由到對應(yīng) Shard 即可，總體來說 ShardedLRUCache 沒有太多邏輯，更像一個(gè) 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