早對 LevelDB 有所耳聞，這次心血來潮結合一些資料粗略過了遍代碼，果然名不虛傳——絕對是不世出的工藝品！如果你對存儲感興趣、如果你想優(yōu)雅使用C++、如果你想學習如何架構項目，都推薦來觀摩一下。谷歌出品，必是精品，更何況作者是 Sanjay Ghemawat 和 Jeff Dean 呢。
看過一遍如果不輸出點什么，以我的記性，定會很快拋諸腦后。便想寫點東西說說 LevelDB 之妙，但又不想走尋常路，從架構概覽說起，以模塊分析做合。讀代碼的這些天，一直在盤算從哪下筆比較好。在將將讀完之時，印象最深的反而是 LevelDB 的各種精妙的數(shù)據(jù)結構：貼合場景、從頭構建、剪裁得當、代碼精到。不妨， LevelDB 系列就從這些邊邊角角的小構件開始吧。
本系列主要想分享 LevelDB 中用到的三個工程中常用的經典數(shù)據(jù)結構，分別是用以快速讀寫 memtable 的 Skip List、用以快速篩選 sstable 的 Bloom Filter 和用以部分緩存 sstable 的 LRUCache 。這是第一篇，Skip List。

需求

LevelDB 是一個單機的 KV 存儲引擎。KV 引擎在本質上可認為只提供對數(shù)據(jù)條目（key，val） Put(key, val), Get(key) val, Delete(key) 操作的三個接口。而在實現(xiàn)上，LevelDB 在收到刪除請求時不會真正刪除數(shù)據(jù)，而是為該 Key 寫一個特殊標記，以備讀取時發(fā)現(xiàn)該 Key 不存在，從而將 Delete 轉為 Put ，進而將三個接口簡化為兩個。砍完這一刀后，剩下的就是在 Put 和 Get 間進行性能取舍，LevelDB 的選擇是：犧牲部分 Get 性能，換取強悍 Put 性能，再極力優(yōu)化 Get。

我們知道，在存儲層次體系（Memory hierarchy）中，內存訪問遠快于磁盤，因此 LevelDB 為了達到目標做了以下設計：

寫入（Put）：讓所有寫入都發(fā)生在內存中，然后達到一定尺寸后將其批量刷磁盤。

讀取（Get）：隨著時間推移，數(shù)據(jù)不斷寫入，內存中會有一小部分數(shù)據(jù)，磁盤中有剩余大部分數(shù)據(jù)。讀取時，如果在內存中沒命中，就需要去磁盤查找。

為了保證寫入性能，同時優(yōu)化讀取性能，需要內存中的存儲結構能夠同時支持高效的插入和查找。

之前聽說 LevelDB 時，最自然的想法，以為該內存結構（memtable）為是平衡樹，比如紅黑樹、AVL 樹等，可以保證插入和查找的時間復雜度都是 lg(n)，看源碼才知道用了跳表。相比平衡樹，跳表優(yōu)勢在于，在保證讀寫性能的同時，大大簡化了實現(xiàn)。

此外，為了將數(shù)據(jù)定期 dump 到磁盤，還需要該數(shù)據(jù)結構支持高效的順序遍歷。總結一下 LevelDB 內存數(shù)據(jù)結構（memtable）需求點：

高效查找

高效插入

高效順序遍歷

作者：青藤木鳥 https://www.qtmuniao.com/2020/07/03/leveldb-data-structures-skip-list ,轉載請注明出處

原理

跳表由 William Pugh 在 1990 年提出，相關論文為：Skip Lists: A Probabilistic Alternative to Balanced Trees。從題目可以看出，作者旨在設計一種能夠替換平衡樹的數(shù)據(jù)結構，正如他在開篇提到：

Skip lists are a data structure that can be used in place of balanced trees.
Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
跳表是一種可以取代平衡樹的數(shù)據(jù)結構。
跳表使用概率均衡而非嚴格均衡策略，從而相對于平衡樹，大大簡化和加速了元素的插入和刪除。

這段話中有個關鍵詞：概率均衡（probabilistic balancing），先賣個關子，按下不表。

接下來我們從兩個角度來解讀跳表：鏈表和跳表，跳表和平衡樹。

鏈表到跳表

簡言之，跳表就是帶有額外指針的鏈表。為了理解這個關系，我們來思考一下優(yōu)化有序鏈表查找性能的過程。

假設我們有個有序鏈表，可知其查詢和插入復雜度都為 O(n)。相比數(shù)組，鏈表不能進行二分查找的原因在于，不能用下標索引進行常數(shù)復雜度數(shù)據(jù)訪問，從而不能每次每次快速的篩掉現(xiàn)有規(guī)模的一半。那么如何改造一下鏈表使之可以進行二分？

利用 map 構造一個下標到節(jié)點的映射？這樣雖然可以進行二分查詢了，但是每次插入都會引起后面所有元素的下標變動，從而需要在 map 中進行 O(n) 的更新。

增加指針使得從任何一個節(jié)點都能直接跳到其他節(jié)點？那得構造一個全連接圖，指針耗費太多空間不說，每次插入指針的更新仍是 O(n) 的。

跳表給出了一種思路，跳步采樣，構建索引，逐層遞減。下面利用論文中的一張圖來詳細解釋下。

帶有額外指針的鏈表

如上圖，初始我們有個帶頭結點的有序鏈表 a，其查找復雜度為 O(n)。然后，我們進行跳步采樣，將采樣出的節(jié)點按用指針依次串聯(lián)上，得到表 b，此時的查找復雜度為 O(llogn/2 + 1) [注1]。其后，我們在上次采樣出的節(jié)點，再次進行跳步采樣，并利用指針依次串聯(lián)上，得到表 c，此時的查找復雜為 O(log2n/4 + 2)。此后，我們重復這個跳步采樣、依次串聯(lián)的過程，直到采樣出的節(jié)點只剩一個，如圖 e，此時的查找復雜度，可以看出為 O(log2n) [注2]。

代價是我們增加了一堆指針，增加了多少呢？我們來逐次考慮這個問題。從圖中可以看出，每次采樣出多少節(jié)點，便會增加多少個指針；我們的采樣策略是，每次在上一次的節(jié)點集中間隔采樣，初始節(jié)點數(shù)為 n，最后采到只剩一個節(jié)點為止。將其加和則為：(n/2 + n/4 + ... + 1) = n。這和一個節(jié)點為 n 的二叉樹的指針數(shù)是相同的。

這里我們回避了一個問題：該結構的插入時間復雜度是多少？這其實進一步了引出本質問題，我們該如何進行插入。

跳表和平衡樹

在實踐中，我們常用搜索二叉樹作為字典表或者順序表。在插入過程中，如果數(shù)據(jù)在 key 空間具有很好地隨機性，那么二叉搜索樹每次順序插入就可以維持很好的查詢性能。但如果我們順序的插入數(shù)據(jù)，則會使得二叉搜索樹嚴重失衡，從而使讀寫性能都大幅度退化。

為了保證性能，需要在發(fā)現(xiàn)不平衡時進行調整，于是有了 AVL 樹和紅黑樹。眾所周知，AVL 的旋轉策略和紅黑樹的標色策略都稍顯復雜，反正我粗看了兩次都沒記住，面試手擼更是不可能。

而跳表在保證同樣查詢效率的情況下，使用了一種很巧妙的轉化，大大簡化了插入的實現(xiàn)。我們不能保證所有的插入請求在 key 空間具有很好地隨機性，或者說均衡性；但我們可以控制每個節(jié)點其他維度的均衡性。比如，跳表中每個節(jié)點的指針數(shù)分布的概率均衡。

概率均衡

為了更好地講清楚這個問題，我們梳理一下跳表的結構和所涉及到概念。跳表每個節(jié)點都會有1 ~ MaxLevel 個指針，有 k 個指針的節(jié)點稱為 k 層節(jié)點（level k node）；所有節(jié)點的層次數(shù)的最大值為跳表的最大層數(shù)（MaxLevel）。跳表帶有一個空的頭結點，頭結點有 MaxLevel 個指針。

按前面從有序鏈表構建跳表的思路，每次插入新節(jié)點就變成了難題，比如插入的節(jié)點需要有多少個指針？插入后如何才能保證查找性能不下降（即維持采樣的均衡）？

為了解決這個問題， Pugh 進行了一個巧妙的轉化：將全局、靜態(tài)的構建索引拆解為獨立、動態(tài)的構建索引。其中的關鍵在于通過對跳表全局節(jié)點指針數(shù)概率分布的維持，達到對查詢效率的保持。分析上面見索引逐層采樣的過程我們可以發(fā)現(xiàn)，建成的跳表中有 50% 的節(jié)點為 1 層節(jié)點，25% 的節(jié)點為 2 層節(jié)點，12.5% 的節(jié)點為三層節(jié)點，依次類推。若能維持我們構造的跳表中的節(jié)點具有同樣的概率分布，就能保證差不多查詢性能。這在直覺上似乎沒問題，這里不去深入探討背后的數(shù)學原理，感興趣的同學可以去讀一讀論文。

經過這樣的轉化，就解決了上面提出的兩個問題：

插入新節(jié)點的指針數(shù)通過獨立的計算一個概率值決定，使全局節(jié)點的指針數(shù)滿足幾何分布即可。

插入時不需要做額外的節(jié)點調整，只需要先找到其需要放的位置，然后修改他和前驅的指向即可。

這樣插入節(jié)點的時間復雜度為查找的時間復雜度 O(log2n)，與修改指針的復雜度 O(1) [注3]之和，即也為 O(log2n)，刪除過程和插入類似，也可以轉化為查找和修改指針值，因此復雜度也為 O(log2n)。

源碼分析

千呼萬喚始出來，讓我們進入正題。LevelDB 中對 SkipList 的實現(xiàn)增加了多線程并發(fā)訪問方面的優(yōu)化的代碼，提供以下保證：

Write：在修改跳表時，需要在用戶代碼側加鎖。

Read：在訪問跳表（查找、遍歷）時，只需保證跳表不被其他線程銷毀即可，不必額外加鎖。

也就是說，用戶側只需要處理寫寫沖突，LevelDB 跳表保證沒有讀寫沖突。

這是因為在實現(xiàn)時，LevelDB 做了以下假設（Invariants）：

除非跳表被銷毀，跳表節(jié)點只會增加而不會被刪除，因為跳表對外根本不提供刪除接口。

被插入到跳表中的節(jié)點，除了 next 指針其他域都是不可變的，并且只有插入操作會改變跳表。

接口

LevelDB 的 Skip List 對外提供的接口主要有三個，分別是插入、查詢和遍歷。

// 插入 key 到跳表中. // 要求: 不能夠插入和跳表中的節(jié)點判等的 key. template <typename Key, class Comparator> void SkipList<Key, Comparator>::Insert(const Key& key)// 當且僅當跳表中有和給定 key 判等的節(jié)點才返回真. template <typename Key, class Comparator> bool SkipList<Key, Comparator>::Contains(const Key& key) const// 返回給定跳表的迭代器 template <typename Key, class Comparator> inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list)

為了靈活適配，LevelDB 的 SkipList 使用了類模板（template class），使得調用方可以自定義 Key 的類型，并且基于該 Key 定制比較類 Comparator。

在詳細分析這幾個接口之前，首先看下跳表的基本構成元素 SkipList::Node 的數(shù)據(jù)結構，代碼里有一些多線程讀寫共享變量時進行同步的代碼。這里主要涉及到指令重排的一些內容，下面稍微展開說一下。

我們知道，編譯器/CPU 在保在達到相同效果的情況下會按需（加快速度、內存優(yōu)化等）對指令進行重排，這對單線程來說的確沒什么。但是對于多線程，指令重排會使得多線程間代碼執(zhí)行順序變的各種反直覺。用 go 代碼舉個例子：

var a, b intfunc f() {a = 1b = 2 }func g() {print(b)print(a) }func main() {go f()g() }

該代碼片段可能會打印出 2 0！

原因在于編譯器/CPU 將 f() 賦值順序重排了或者將 g() 中打印順序重排了。這就意味著你跟隨直覺寫出的多線程代碼，可能會出問題。因為你無形中默認了單個線程中執(zhí)行順序是代碼序，多線程中雖然代碼執(zhí)行會產生交錯，但仍然保持各自線程內的代碼序。實則不然，由于編譯器/CPU 的指令重排，如果不做顯式同步，你不能對多線程間代碼執(zhí)行順序有任何假設。

回到 LevelDB 跳表代碼上，主要涉及 C++11 中 atomic 標準庫中新支持的幾種 memory order，規(guī)定了一些指令重排方面的限制，僅說明下用到的三種：

std::memory_order_release：不對重排做限制，只保證相關共享內存訪問的原子性。

std::memory_order_acquire: 用在 load 時，保證同線程中該 load 之后的對相關內存讀寫語句不會被重排到 load 之前，并且其他線程中對同樣內存用了 store release 都對其可見。

std::memory_order_release：用在 store 時，保證同線程中該 store 之后的對相關內存的讀寫語句不會被重排到 store 之前，并且該線程的所有修改對用了 load acquire 的其他線程都可見。

template <typename Key, class Comparator> struct SkipList<Key, Comparator>::Node {explicit Node(const Key& k) : key(k) {}Key const key;Node* Next(int n) {assert(n >= 0);return next_[n].load(std::memory_order_acquire);}void SetNext(int n, Node* x) {assert(n >= 0);next_[n].store(x, std::memory_order_release);}// 不帶內存屏障版本的訪問器。內存屏障（Barrier）是個形象的說法，也即加一塊擋板，阻止重排/進行同步Node* NoBarrier_Next(int n) {assert(n >= 0);return next_[n].load(std::memory_order_relaxed);}void NoBarrier_SetNext(int n, Node* x) {assert(n >= 0);next_[n].store(x, std::memory_order_relaxed);}private:// 指針數(shù)組的長度即為該節(jié)點的 level，next_[0] 是最低層指針.std::atomic<Node*> next_[1]; // 指向指針數(shù)組的指針 };

查找

查找是插入的基礎，每個節(jié)點要先找到合適位置，才能進行插入。因此 LevelDB 抽象出了一個公用函數(shù)： FindGreaterOrEqual ：

template <typename Key, class Comparator> bool SkipList<Key, Comparator>::Contains(const Key& key) const {Node* x = FindGreaterOrEqual(key, nullptr);if (x != nullptr && Equal(key, x->key)) {return true;} else {return false;} }

該函數(shù)的含義為：在跳表中查找不小于給 Key 的第一個值，如果沒有找到，則返回 nullptr。如果參數(shù) prev 不為空，在查找過程中，記下待查找節(jié)點在各層中的前驅節(jié)點。顯然，如果查找操作，則指定 prev = nullptr 即可；若要插入數(shù)據(jù)，則需傳入一個合適尺寸的 prev 參數(shù)。

template <typename Key, class Comparator> typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key, Node** prev) const {Node* x = head_; // 從頭結點開始查找int level = GetMaxHeight() - 1; // 從最高層開始查找while (true) {Node* next = x->Next(level); // 該層中下一個節(jié)點if (KeyIsAfterNode(key, next)) {x = next; // 待查找 key 比 next 大，則在該層繼續(xù)查找} else {if (prev != nullptr) prev[level] = x;if (level == 0) { // 待查找 key 不大于 next，則到底返回return next;} else { // 待查找 key 不大于 next，且沒到底，則往下查找level--;}}} }

該過程借用論文中圖示如下：

跳表查找和插入過程

插入

在 FindGreaterOrEqual 基礎上，記下待插入節(jié)點的各層次前驅節(jié)點，比如上圖中，調用 FindGreaterOrEqual(17, prev) 后 prev = [12, 9, 6, 6]。插入代碼如下：

template <typename Key, class Comparator> void SkipList<Key, Comparator>::Insert(const Key& key) {// 待做(opt): 由于插入要求外部加鎖，因此可以使用 NoBarrier_Next 的 FindGreaterOrEqual 以提高性能Node* prev[kMaxHeight]; // 長度設定簡單粗暴，直接取最大值（kMaxHeight = 12）肯定沒錯。Node* x = FindGreaterOrEqual(key, prev);// LevelDB 跳表要求不能插入重復數(shù)據(jù)assert(x == nullptr || !Equal(key, x->key));int height = RandomHeight(); // 隨機獲取一個 level 值if (height > GetMaxHeight()) { // GetMaxHeight() 為獲取跳表當前for (int i = GetMaxHeight(); i < height; i++) {prev[i] = head_;}// 此處不用為并發(fā)讀加鎖。因為并發(fā)讀在（在另外線程中通過 FindGreaterOrEqual 中的 GetMaxHeight）// 讀取到更新后跳表層數(shù)，但該節(jié)點尚未插入時也無妨。因為這意味著它會讀到 nullptr，而在 LevelDB// 的 Comparator 設定中，nullptr 比所有 key 都大。因此，FindGreaterOrEqual 會繼續(xù)往下找，// 符合預期。max_height_.store(height, std::memory_order_relaxed);}x = NewNode(key, height);for (int i = 0; i < height; i++) {// 此句 NoBarrier_SetNext() 版本就夠用了，因為后續(xù) prev[i]->SetNext(i, x) 語句會進行強制同步。// 并且為了保證并發(fā)讀的正確性，一定要先設置本節(jié)點指針，再設置原條表中節(jié)點（prev）指針x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));prev[i]->SetNext(i, x);} }

LevelDB 跳表實現(xiàn)的復雜點在于提供不加鎖的并發(fā)讀的正確性保證。但算法的關鍵點在于每個節(jié)點插入時，如何確定新插入節(jié)點的層數(shù)，以使跳表滿足概率均衡，進而提供高效的查詢性能。即 RandomHeight 的實現(xiàn)：

template <typename Key, class Comparator> int SkipList<Key, Comparator>::RandomHeight() {// 每次以 1/4 的概率增加層數(shù)static const unsigned int kBranching = 4;int height = 1;while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {height++;}assert(height > 0);assert(height <= kMaxHeight);return height; }

LevelDB 的采樣較為稀疏，每四個采一個，且層數(shù)上限為 kMaxHeight = 12。具體實現(xiàn)過程即為構造 P = 3/4 的幾何分布的過程。結果為所有節(jié)點中：3/4 的節(jié)點為 1 層節(jié)點，3/16 的節(jié)點為 2 層節(jié)點，3/64 的節(jié)點為 3 層節(jié)點，依次類推。這樣平均每個節(jié)點含指針數(shù) 1/P = 4/3 = 1.33 個。當然，在論文中的 p 的含義為相鄰兩層間采樣的比例，和我提到的 P 的關系為：p = 1-P。

選 p = 1/4 相比 p = 1/2 是用時間換空間，即只犧牲了一些常數(shù)的查詢效率，換取平均指針數(shù)的減少，從而減小內存使用。論文中也推薦 p = 1/4 ，除非讀速度要求特別嚴格。在此情況下，可以最多支持 n = (1/p)^kMaxHeight 個節(jié)點的情況，查詢時間復雜度不退化。如果選 kMaxHeight = 12，則跳表最多可以支持 n = 4 ^ 12 = 16M 個值。

遍歷

LevelDB 為跳表構造了一個內部類 Iterator，以 SkipList 作為構造函數(shù)參數(shù)，實現(xiàn)了 LevelDB 導出的 Iterator 接口的大部分函數(shù)，如 Next，Prev，Seek，SeekToFirst，SeekToLast 等等。

template <typename Key, class Comparator> inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list) {list_ = list;node_ = nullptr; }template <typename Key, class Comparator> inline bool SkipList<Key, Comparator>::Iterator::Valid() const {return node_ != nullptr; }template <typename Key, class Comparator> inline const Key& SkipList<Key, Comparator>::Iterator::key() const {assert(Valid());return node_->key; }template <typename Key, class Comparator> inline void SkipList<Key, Comparator>::Iterator::Next() {assert(Valid());node_ = node_->Next(0); }template <typename Key, class Comparator> inline void SkipList<Key, Comparator>::Iterator::Prev() {// 相比在節(jié)點中額外增加一個 prev 指針，我們使用從頭開始的查找定位其 prev 節(jié)點assert(Valid());node_ = list_->FindLessThan(node_->key);if (node_ == list_->head_) {node_ = nullptr;} }template <typename Key, class Comparator> inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {node_ = list_->FindGreaterOrEqual(target, nullptr); }template <typename Key, class Comparator> inline void SkipList<Key, Comparator>::Iterator::SeekToFirst() {node_ = list_->head_->Next(0); }template <typename Key, class Comparator> inline void SkipList<Key, Comparator>::Iterator::SeekToLast() {node_ = list_->FindLast();if (node_ == list_->head_) {node_ = nullptr;} }

可以看出該迭代器沒有為每個節(jié)點增加一個額外的 prev 指針以進行反向迭代，而是用了選擇從 head 開始查找。這也是一種用時間換空間的取舍。當然，其假設是前向遍歷情況相對較少。

其中 FindLessThan 和 FindLast 的實現(xiàn)與 FindGreaterOrEqual 思路較為相似，不再贅述。

// Return the latest node with a key < key. // Return head_ if there is no such node. Node* FindLessThan(const Key& key) const;// Return the last node in the list. // Return head_ if list is empty. Node* FindLast() const;

小結

跳表本質上是對鏈表的一種優(yōu)化，通過逐層跳步采樣的方式構建索引，以加快查找速度。使用概率均衡的思路，確定新插入節(jié)點的層數(shù)，使其滿足集合分布，在保證相似的查找效率簡化了插入實現(xiàn)。

LevelDB 的跳表實現(xiàn)還專門對多線程讀做了優(yōu)化，但寫仍需外部加鎖。在實現(xiàn)思路上，整體采用時間換空間的策略，優(yōu)化內存使用。

下一篇中，將繼續(xù)剖析 LevelDB 中用到的另一個經典的數(shù)據(jù)結構：布隆過濾器（Bloom Filter）。

注解

[1] 先在上層查找，然后縮小到某個范圍后去下層查找。

[2] 可以證明，也可以簡單的找規(guī)律： O(log2(n/2) + 1) -> O(log2(n/4) + 2) -> ... -> O(1 + log2n)，即 O(log2n) 。

[3] 通過采樣過程可知所有節(jié)點的概率滿足 p = 0.5 的幾何分布，則每個節(jié)點的期望指針個數(shù)為 1/p = 2，則每次插入平均需要修改 2 * 2 個指針，即為常數(shù)級別。

參考

LevelDB handbook：https://leveldb-handbook.readthedocs.io/zh/latest/index.html

庖丁解 LevelDB 之數(shù)據(jù)存儲：https://catkang.github.io/2017/01/17/leveldb-data.html

C++ atomic memory order：https://en.cppreference.com/w/cpp/atomic/memory_order

The last thing

Leetcode 上有跳表簡化版的題目，看完了本文可以趁熱打鐵去實現(xiàn)一下：https://leetcode.com/problems/design-skiplist/

這是我的實現(xiàn)版本：https://leetcode.com/problems/design-skiplist/discuss/740881/C%2B%2B-clean-and-simple-solution-from-leveldb

---

總結

以上是生活随笔為你收集整理的二叉树 跳表_漫谈 LevelDB 数据结构（一）：跳表（Skip List）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。