LevelDB 源碼解析之 Cache 緩存

GitHub: https://github.com/storagezhang

Emai: debugzhang@163.com

LevelDB: https://github.com/google/leveldb

影響數據庫讀性能的一個重要組件是緩存。如果 LevelDB 的每一次讀取都會帶來一次磁盤 IO，這些磁盤 IO 就會讓系統的整體效率非常低下。

所以，LevelDB 使用了一種基于 LRUCache 的緩存機制，用于緩存：

已打開的 sstable 文件對象和相關元數據；

sstable 中的 dataBlock 的內容。

這種緩存機制使得對熱數據的讀取盡量在 cache 中命中，避免 IO 調用。

cache 類

Cache 是一個抽象類，聲明了一個全局函數：

Cache* NewLRUCache(size_t capacity) { return new ShardedLRUCache(capacity); }

該函數用來創建具有固定容量的緩存，此緩存實現使用最近最少使用的淘汰策略（LRU, least-recently-used），當數據所占內存達到一定閾值時，刪掉最近最少使用的數據。

Cache 中的數據是文件的副本，其讀取流程為：

在 cache 中查找特定的 key，若找到該 key，直接返回對應的 handle，若未找到，執行第 2 步；

從文件中讀取 key 對應的 entry 到 cache 中，再返回相應的 handle。

接口

Cache 聲明了一系列接口：

virtual ~Cache();

通過調用 deleter 刪除所有的 entry。

struct Handle {};

緩存中所存儲的項 entry 對應的句柄 handle；

除了保存 key-value 數據外還保存了一些維護信息；

Handle 是通用接口，此處僅定義空結構體。

virtual Handle* Insert(const Slice& key, void* value, size_t charge, void (*deleter)(const Slice& key, void* value)) = 0;

將一個對應 key-value 的 entry 插入緩存；

返回 entry 對應的 handle，當不再需要返回的 handle，調用者必須調用 this->Release(handle)；

entry 被刪除時，key 和 value 將會傳遞給 deleter。

virtual Handle* Lookup(const Slice& key) = 0;

如果當前緩存中沒有對應 key 的 entry，返回 nullptr；

否則返回 entry 對應的 handle，當不再需要返回的 handle 時，調用者必須調用 this->Release(handle)。

virtual void Release(Handle* handle) = 0;

釋放調用 this->Lookup 查找到的 handle：

對應 entry 的引用計數減 1；

若引用計數為 0，調用 deleter?刪除該 entry。

注意：handle 必須尚未釋放。

virtual void* Value(Handle* handle) = 0;

返回調用 this->Lookup(key) 查找到的 handle 中封裝的值。

注意：handle 必須尚未釋放。

virtual void Erase(const Slice& key) = 0;

從緩存刪除 key 對應的 entry。

注意：entry 將一直保留，直到 entry 對應的所有 handle 都被 this->Release(handle) 釋放。

virtual uint64_t NewId() = 0;

返回一個新的數字 id。

共享同一緩存的多個客戶端可以使用該標識對保存 key 的空間進行分區。

通常客戶端將在啟動時分配一個新的 id，并預先將該 id 添加到它保存 key 的緩存中。

virtual void Prune() {}

刪除所有不活躍的 entry。

內存受限的應用程序可能希望調用此方法以減少內存使用。

virtual size_t TotalCharge() const = 0;

返回緩存內存消耗的估計值。

LRUHandle 結構體

LRUHandle 是一個雙向循環鏈表，存儲緩存中的 entry，它的功能有：

存儲 key-value 數據；

作為 LRU 鏈表，是一個可變長度的堆分配結構；

記錄引用計數并負責清理。

struct LRUHandle { // 存儲的 value 對象的指針，可以存儲任意類型的值 void* value; // 當引用計數 `refs` 降為 0 時的清理函數 void (*deleter)(const Slice&, void* value); // 哈希表通過鏈地址法解決哈希沖突，發生哈希沖突時指向下一個 entry LRUHandle* next_hash; // LRU 鏈表雙向指針 LRUHandle* next; LRUHandle* prev; // 分配的可以消耗的內存量 size_t charge; // key 的字節數 size_t key_length; // entry 是否存在緩存中 bool in_cache; // 引用計數，記錄 entry 被不同緩存的引用，用于 entry 刪除 uint32_t refs; // `key()` 對應的哈希，用于快速分區和比較 uint32_t hash; // 存儲 key 的開始地址，結合 `key_length` 獲取真正的 key // GCC 支持 C99 標準，允許定義 char key_data[] 這樣的柔性數組（Flexible Array)。 // C++ 標準并不支持柔性數組的實現，這里定義為 key_data[1]，這也是 c++ 中的標準做法。 char key_data[1]; Slice key() const { // 只有當當前節點是空鏈表頭時，`next` 才會等于 `this` // 鏈表是循環雙向鏈表，空鏈表的頭節點 next 和 prev 都指向自己構成環 // 鏈表頭是冗余的 handle，不存儲數據，只利用它的 next 和 prev assert(next != this); return Slice(key_data, key_length); } };

HandleTable 類

LevelDB 實現了一個內部哈希表 HandleTable，它消除了大量的移植漏洞，比一些編譯器/運行時組合中的內置哈希表實現更快。例如，隨機讀的速度比 g++4.4.3 的內置哈希表提高了約 5%。

成員變量

每一個 LRUHandle 即是 HashTable 中的一個哈希桶，相同哈希值的 entry 通過 next_hash 連成鏈表，同時這些 entry 也通過 next 和 prev 連成為雙向鏈表，最新插入的數據排在鏈表尾部。

class HandleTable { public: HandleTable() : length_(0), elems_(0), list_(nullptr) { Resize(); } ~HandleTable() { delete[] list_; } private: // list 數組的長度，即哈希桶的個數 uint32_t length_; // 存儲的元素總個數，當 elems > length 時，擴展 list 數組并重新 hash uint32_t elems_; // 存儲 entry 的數組，即哈希桶，初始大小為 4，動態擴展，成倍增長 LRUHandle** list_; } };

Resize

Resize 函數用于元素增加時動態擴展數組：

void Resize() { // 初始化時，哈希桶的個數為 4 uint32_t new_length = 4; // 隨著不同哈希值的增加動態擴展，每次擴展為原容量的兩倍 while (new_length < elems_) { new_length *= 2; } // 按照新容量申請內存，分配給新鏈表，并將原數據復制過去 LRUHandle** new_list = new LRUHandle*[new_length]; memset(new_list, 0, sizeof(new_list[0]) * new_length); uint32_t count = 0; for (uint32_t i = 0; i < length_; i++) { LRUHandle* h = list_[i]; while (h != nullptr) { LRUHandle* next = h->next_hash; uint32_t hash = h->hash; LRUHandle** ptr = &new_list[hash & (new_length - 1)]; h->next_hash = *ptr; *ptr = h; h = next; count++; } } assert(elems_ == count); // 釋放原數組 delete[] list_; // 更新哈希表數據 list_ = new_list; length_ = new_length; }

LevelDB 只在 entry 增長的時候擴大 list_，沒有縮小，這符合 LevelDB 的使用場景。

FindPointer

FindPointer 函數返回適合所傳入的 key 和 hash 的插入位置：

LRUHandle** FindPointer(const Slice& key, uint32_t hash) { // list_[hash & (length_ - 1)] 中存儲著 next_hash 的地址 // ptr 等于 next_hash 的地址 // *ptr 等于其指向的 next_hash，即指向 next_hash 所連成的鏈表 // **ptr 等于 next_hash 所指向的 LRUHandle，即指向具體的 entry LRUHandle** ptr = &list_[hash & (length_ - 1)]; // 利用 *ptr 遍歷這個鏈表，直到找到 key 對應的 entry // 如果沒有找到，ptr 就指向鏈表的尾部，這最后一個 next_hash 的值是 nullptr while (*ptr != nullptr && ((*ptr)->hash != hash || key != (*ptr)->key())) { ptr = &(*ptr)->next_hash; } // 返回符合條件的 next_hash 的地址 return ptr; }

Lookup，Insert 和 Remove

有了 FindPointer?返回的指針，查找函數 Lookup?直接讀取指針指向的值:

LRUHandle* Lookup(const Slice& key, uint32_t hash) { return *FindPointer(key, hash); }

插入函數 Insert 直接在指針所指向的位置上插入：

LRUHandle* Insert(LRUHandle* h) { LRUHandle** ptr = FindPointer(h->key(), h->hash); LRUHandle* old = *ptr; h->next_hash = (old == nullptr ? nullptr : old->next_hash); *ptr = h; if (old == nullptr) { ++elems_; // 當存儲元素個數大于哈希桶個數時，擴展哈希桶數組 // 因為每個緩存項都相當大，所以我們的目標是使鏈表的平均長度較小（<=1）。 if (elems_ > length_) { Resize(); } } return old; }

刪除函數 Remove?直接刪除指針所指向的 next_hash?所指向的 entry：

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

LRUCache 類

LRUCache 是 LRUCache 的內部實現，不對外暴露接口，作為 ShardedLRUCache 的分片存在。

成員變量

class LRUCache { private: // 緩存的容量，在初始化時指定 size_t capacity_; // 互斥鎖，保護下列數據 mutable port::Mutex mutex_; // 緩存中所有 entry 的 charge 總和 // usage 必須小于 capacity size_t usage_ GUARDED_BY(mutex_); // 存儲 entry 的循環雙向鏈表，鏈表頭冗余，同時維護使用熱度 // lru.next 指向最舊的 entry，lru.prev 指向最新的 entry // 當緩存滿了時，先從 lru.next 開始淘汰 entry // lru 保存 refs==1，并且 in_cache==true 的 entry LRUHandle lru_ GUARDED_BY(mutex_); // 存儲正在使用的 entry 的循環雙向鏈表，鏈表頭冗余 // 這些 entry 不能被淘汰。 LRUHandle in_use_ GUARDED_BY(mutex_); // 保存所有 entry 的哈希表，用于快速查找數據 HandleTable table_ GUARDED_BY(mutex_); };

構造函數和析構函數

LRUCache::LRUCache() : capacity_(0), usage_(0) { // lru 和 in_use 都是循環雙向鏈表 // 空鏈表的頭節點 next 和 prev 都指向自己構成環，鏈表頭冗余 lru_.next = &lru_; lru_.prev = &lru_; in_use_.next = &in_use_; in_use_.prev = &in_use_; }

LRUCache::~LRUCache() { // in_use 鏈表不能為空 assert(in_use_.next == &in_use_); for (LRUHandle* e = lru_.next; e != &lru_;) { LRUHandle* next = e->next; // entry 必須在緩存中 assert(e->in_cache); // 將 entry 移除緩存 e->in_cache = false; // entry 的引用計數必須為 1 assert(e->refs == 1); // 刪除 entry Unref(e); e = next; } }

Cache 相關接口實現

Lookup

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) { MutexLock l(&mutex_); // 借助哈希表快速定位 entry LRUHandle* e = table_.Lookup(key, hash); if (e != nullptr) { // 如果找到，增加 entry 的引用計數 Ref(e); } return reinterpret_cast(e); } void LRUCache::Ref(LRUHandle* e) { if (e->refs == 1 && e->in_cache) { // 如果當前 entry 在 lru 鏈表中，需要將其移動到 in_use 鏈表，不需要等待淘汰 LRU_Remove(e); // 添加到鏈表頭部 LRU_Append(&in_use_, e); } e->refs++; }

Release

void LRUCache::Release(Cache::Handle* handle) { MutexLock l(&mutex_); // 對 entry 解引用 Unref(reinterpret_cast(handle)); } void LRUCache::Unref(LRUHandle* e) { assert(e->refs > 0); // 引用計數減少 e->refs--; if (e->refs == 0) { // 當引用計數為 0 時進行清理 assert(!e->in_cache); (*e->deleter)(e->key(), e->value); free(e); } else if (e->in_cache && e->refs == 1) { // 當引用計數為 1 時移動到 lru 鏈表等待淘汰 LRU_Remove(e); // 添加到鏈表頭部 LRU_Append(&lru_, e); } }

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_); LRUHandle* e = reinterpret_cast(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; // 返回 handle，引用計數加一 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)); } else { // 不緩存（支持 capacity==0，這表示關閉緩存 // next 會影響 `key()` 中的斷言，因此必須對其進行初始化 e->next = nullptr; } while (usage_ > capacity_ && lru_.next != &lru_) { // entry 的總消耗大于緩存的容量 LRUHandle* old = lru_.next; assert(old->refs == 1); bool erased = FinishErase(table_.Remove(old->key(), old->hash)); if (!erased) { // 在編譯 NDEBUG 時避免使用未使用的變量 assert(erased); } } return reinterpret_cast(e); }

Erase

bool LRUCache::FinishErase(LRUHandle* e) { if (e != nullptr) { assert(e->in_cache); // 從 in_use 鏈表中刪除 LRU_Remove(e); e->in_cache = false; usage_ -= e->charge; // 解引用 Unref(e); } return e != nullptr; } void LRUCache::Erase(const Slice& key, uint32_t hash) { MutexLock l(&mutex_); FinishErase(table_.Remove(key, hash)); }

Prune

void LRUCache::Prune() { MutexLock l(&mutex_); // 清空 lru 鏈表 while (lru_.next != &lru_) { LRUHandle* e = lru_.next; assert(e->refs == 1); bool erased = FinishErase(table_.Remove(e->key(), e->hash)); if (!erased) { // 在編譯 NDEBUG 時避免使用未使用的變量 assert(erased); } } }

entry 的引用計數

LRUCache 中的 entry 可以分為四個狀態：

圖片來源：http://kaiyuan.me/2017/06/12/leveldb-05/

in use (ref=2)：

該 entry 在 table 中，并且在 in_use 鏈表中；由于該 entry 既被外部 handle 引用，也被 in_use 鏈表使用，因此有 ref=2；

Insert 函數創建一個新的 entry 保存相應的 key-value 數據，并加入 in_use 鏈表的表頭，然后返回對應的 handle 到外部，并將 ref 設置為 2；

in lru (ref=1)：

該 entry 在 table 中，并且在 lru 鏈表中；由于該 entry 只被 lru 鏈表使用，因此有 ref=1；

Lookup?函數和 Release?函數成對出現。Lookup?查找 key 對應的 entry，并返回 entry 對應的 handle 給外部，增加一個引用， ref 加 1；Release?函數則相反，釋放 handle，減少一個引用，ref 減 1；

not in lru, not in table (ref=1)：

該 entry 不在鏈表中也不在 table 中，但是仍然被外部 handle 引用且 handle 未釋放，因此 ref=1；

Erase?函數將 entry 從 table?和 in_use?中刪除，減少一個引用，ref 減 1，但是若此 entry 還被外部 handle 引用，不能直接釋放 entry 占用的內存，必須等外部使用者調用 Release?函數之后才能釋放內存；

not in lru, not in table (ref=0)：該 entry 不在鏈表中也不在 table 中，也不被外部使用，因此 ref=0；

ShardedLRUCache 類

ShardedLRUCache 是 LevelDB 對外暴露的 LRUCache。

static const int kNumShardBits = 4; static const int kNumShards = 1 << kNumShardBits; class ShardedLRUCache : public Cache { private: LRUCache shard_[kNumShards]; port::Mutex id_mutex_; uint64_t last_id_; public: explicit ShardedLRUCache(size_t capacity) : last_id_(0) { const size_t per_shard = (capacity + (kNumShards - 1)) / kNumShards; for (int s = 0; s < kNumShards; s++) { shard_[s].SetCapacity(per_shard); } } }

ShardedLRUCache 中定義了 16 個 LRUCache，每次進行插入或者查找時，使用哈希值的最高四位判斷當前應該在哪個 LRUCache 中查找，然后在找到的 LRUCache 中進行相應的操作。

static inline uint32_t HashSlice(const Slice& s) { return Hash(s.data(), s.size(), 0); } static uint32_t Shard(uint32_t hash) { return hash >> (32 - kNumShardBits); }

因為 LRUCache 的查找、插入和釋放均需要加鎖，而這種分片的方式能夠提高 LevelDB 對于緩存的并發訪問，也就是從側面降低了鎖的粒度，提高訪問效率。

Cache 相關接口實現

ShardedLRUCache?的接口實現非常簡單，它自己只進行哈希值的計算，然后選擇相應的 LRUCache，調用相應 LRUCache?的相關接口實現。

Handle* Insert(const Slice& key, void* value, size_t charge, void (*deleter)(const Slice& key, void* value)) override { const uint32_t hash = HashSlice(key); return shard_[Shard(hash)].Insert(key, hash, value, charge, deleter); } Handle* Lookup(const Slice& key) override { const uint32_t hash = HashSlice(key); return shard_[Shard(hash)].Lookup(key, hash); } void Release(Handle* handle) override { LRUHandle* h = reinterpret_cast(handle); shard_[Shard(h->hash)].Release(handle); } void Erase(const Slice& key) override { const uint32_t hash = HashSlice(key); shard_[Shard(hash)].Erase(key, hash); } void* Value(Handle* handle) override { return reinterpret_cast(handle)->value; } uint64_t NewId() override { MutexLock l(&id_mutex_); return ++(last_id_); } void Prune() override { for (int s = 0; s < kNumShards; s++) { shard_[s].Prune(); } } size_t TotalCharge() const override { size_t total = 0; for (int s = 0; s < kNumShards; s++) { total += shard_[s].TotalCharge(); } return total; }

存儲 數據庫 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。