何為跳表

跳躍表（skiplist），簡(jiǎn)稱「跳表」备典。是一種在鏈表基礎(chǔ)上進(jìn)行優(yōu)化的數(shù)據(jù)結(jié)構(gòu)，最早由 William Pugh 在論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中提出。

William Pugh 于 1989 在論文中將「跳表」定位為：一種能夠替代平衡樹的數(shù)據(jù)結(jié)構(gòu)膏秫，比起使用強(qiáng)制平衡算法的各種平衡樹，跳表采用一種隨機(jī)平衡的策略做盅。因此跳表擁有更為簡(jiǎn)單的算法實(shí)現(xiàn)缤削，同時(shí)擁有與平衡樹相媲美的時(shí)間復(fù)雜度(logn 級(jí)別)和操作效率。

設(shè)計(jì)思想

普通鏈表是一種順序查找的數(shù)據(jù)結(jié)構(gòu)吹榴。即在查找某個(gè)元素時(shí)需要依次遍歷所有元素進(jìn)行比較亭敢。且在元素有序的情況下也無法像數(shù)組那樣利用二分查找，固元素查詢時(shí)間復(fù)雜度為 O(n)图筹，若需維護(hù)鏈表有序吨拗，元素插入的時(shí)間復(fù)雜度也同樣需要 O(n)。

在一些數(shù)據(jù)量極大的場(chǎng)景下婿斥，O(n) 的時(shí)間復(fù)雜度仍然存在優(yōu)化的空間劝篷。

平衡二叉查找樹 AVL 或者紅黑樹是經(jīng)常被用來實(shí)現(xiàn)上述優(yōu)化的數(shù)據(jù)結(jié)構(gòu)。但這些平衡樹需要在整個(gè)過程中保持樹的平衡民宿，這帶來了一定的復(fù)雜度娇妓。

而跳表的核心思想類似于對(duì)有序鏈表中元素建立索引。整個(gè)跳表按照層次進(jìn)行構(gòu)建活鹰，底層為原始的有序鏈表哈恰，然后抽取鏈表中的關(guān)鍵元素到上一層作為索引，從剛構(gòu)建的索引中可以繼續(xù)抽取關(guān)鍵元素到新的一層志群，以此類推着绷。

跳表原理結(jié)構(gòu)如下圖所示：

normal_skip_list.png

以查找元素 2 為例，查找將從第 2 層索引確定 1 ～ 5 范圍锌云，再到第 1 層索引進(jìn)一步確定 1 ～ 3 范圍荠医，最后回到底層原始鏈表查找到元素 2。

性能分析

上文提到了「抽取每一層的關(guān)鍵元素到上一層作為索引」，但是隨著數(shù)據(jù)量的增加每一層的結(jié)點(diǎn)也會(huì)越來越多彬向，該如何選取結(jié)點(diǎn)讓跳表的結(jié)點(diǎn)呈現(xiàn)我們所需的分布兼贡？

跳表采用「投硬幣」的方式?jīng)Q定結(jié)點(diǎn)是否向上提升。

假設(shè)現(xiàn)在底層有序鏈表有 n 個(gè)結(jié)點(diǎn)且投硬幣概率為 50%娃胆，則第一層應(yīng)該^[1]有 n/2 個(gè)索引結(jié)點(diǎn)遍希，第二層有 n/4 個(gè)索引結(jié)點(diǎn)，第 i 層索引有 n/2ⁱ 個(gè)結(jié)點(diǎn)里烦，當(dāng) n/2ⁱ 等于 2 時(shí)凿蒜，意味著已經(jīng)到了最高層。此時(shí)由 n/2ⁱ = 2胁黑，可推導(dǎo)出 i = log₂n废封。

即投硬幣概率為 50% 時(shí)，跳表層高為 log₂n别厘，且由于每?jī)蓚€(gè)結(jié)點(diǎn)就有一個(gè)結(jié)點(diǎn)上升為一個(gè)索引結(jié)點(diǎn)虱饿。所以當(dāng)從最上層向下搜索的過程中，每一個(gè)最多只會(huì)比較 3 個(gè)結(jié)點(diǎn)（常數(shù)級(jí)）触趴，所以整個(gè)搜索過程時(shí)間復(fù)雜度最終為 log₂n氮发。

^[1] 概率事件，并非一定具有準(zhǔn)確的 n/2 結(jié)點(diǎn)冗懦。

將上述過程進(jìn)一步擴(kuò)展概率為 p爽冕，則時(shí)間復(fù)雜度為 log_1/pn。其中每一層比較的次數(shù)不超過 1/p披蕉。

上述是為了方便理解而簡(jiǎn)化的概率推導(dǎo)過程颈畸，結(jié)論也建立在 n 足夠大的前提下。實(shí)際推導(dǎo)過程要復(fù)雜很多没讲，有興趣的讀者可以閱讀論文原文：《Skip Lists: A Probabilistic Alternative to Balanced Trees》

實(shí)現(xiàn)

上文介紹了跳表的基本思想眯娱，其中為了方便理解和講述，我們將索引結(jié)點(diǎn)單獨(dú)繪制成一個(gè)結(jié)點(diǎn)爬凑。如果完全按照上文圖示實(shí)現(xiàn)跳表徙缴，則跳表需要額外 n 個(gè)結(jié)點(diǎn)空間。但在實(shí)際實(shí)現(xiàn)時(shí)嘁信，無需額外結(jié)點(diǎn)只需使用指針指向相應(yīng)結(jié)點(diǎn)即可于样，因此只是多出了 n 個(gè)指針而已。

即跳表實(shí)際實(shí)現(xiàn)的結(jié)構(gòu)如下圖所示：

skip_list_wiki.png

其中黃色格子為數(shù)據(jù)結(jié)點(diǎn)潘靖，白色格子為數(shù)據(jù)結(jié)點(diǎn)內(nèi)的指針穿剖。

LevelDB 中的跳表源碼解析

我們以 LevelDB 中的跳表實(shí)現(xiàn) skiplist.h 為例，分析跳表的具體實(shí)現(xiàn)

設(shè)計(jì)結(jié)點(diǎn)結(jié)構(gòu)如下：

template <typename Key, class Comparator>
struct SkipList<Key, Comparator>::Node {
  explicit Node(const Key& k) : key(k) {}
  // 存儲(chǔ) key
  Key const key;

  // ...... 

  private:
    // 下標(biāo)表示結(jié)點(diǎn)的層次 level
    // 整個(gè)數(shù)組表示該結(jié)點(diǎn)在各層次的存儲(chǔ)情況
    std::atomic<Node*> next_[1];
}

如下圖所示：

data_structure_0.png

進(jìn)一步理解如下圖所示：

data_structure_1.png

其中上圖 head_ 內(nèi)的 next_ 數(shù)組存儲(chǔ)著指向各個(gè)索引層次第一個(gè)元素的指針卦溢。

其它每個(gè)結(jié)點(diǎn)（如圖中的結(jié)點(diǎn) 1）中的 next_ 數(shù)組包含了如下信息：

結(jié)點(diǎn)在各個(gè)索引層中的下一個(gè)結(jié)點(diǎn)的指針

查詢?cè)?/h4>

元素查詢主要邏輯集中在 FindGreaterOrEqual 這個(gè)函數(shù)糊余，就以這個(gè)函數(shù)為例秀又，體現(xiàn)元素查詢過程：

// 搜索大于等于 key 的所有結(jié)點(diǎn)
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
                                              Node** prev) const {
  Node* x = head_;
  // 獲取當(dāng)前結(jié)點(diǎn)的層高
  // 從最上層的索引層開始遍歷
  int level = GetMaxHeight() - 1;
  while (true) {
    // 假設(shè) next_ = [*3, *5, *6]
    // 表示該結(jié)點(diǎn)：
    // 在第 2 層的下一個(gè)索引結(jié)點(diǎn)為 6
    // 在第 1 層的下一個(gè)索引結(jié)點(diǎn)為 5
    // 在第 0 層的下一個(gè)結(jié)點(diǎn)為 3
    // 那么就可以直接通過 next_[level] 找到下一個(gè)索引結(jié)點(diǎn)
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {  // key 是否在當(dāng)前結(jié)點(diǎn)之后（大小關(guān)系由比較器最終確認(rèn)）
      // Keep searching in this list
      // 繼續(xù)遍歷搜索該層的剩余結(jié)點(diǎn)
      x = next;
    } else {  // key 是否在當(dāng)前結(jié)點(diǎn)之后（大小關(guān)系由比較器最終確認(rèn)）
      // 記錄結(jié)點(diǎn)到 prev 數(shù)組
      // prev 數(shù)組記錄每個(gè)索引層次要插入 key 的位置
      if (prev != nullptr) prev[level] = x; prev
      if (level == 0) { // 遍歷到 0 層，遍歷結(jié)束
        return next;
      } else {
        // Switch to next list
        // 進(jìn)入下一層遍歷
        level--;
      }
    }
  }
}

刪除元素

LevelDB 業(yè)務(wù)層面無刪除結(jié)點(diǎn)的需求啄刹，見源碼注解如下：

// (1) Allocated nodes are never deleted until the SkipList is
// destroyed.  This is trivially guaranteed by the code since we
// never delete any skip list nodes.

插入元素

template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key) {
  // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
  // here since Insert() is externally synchronized.
  Node* prev[kMaxHeight];
  // 獲取所有大于等于（比較器定義） key 的結(jié)點(diǎn)
  // prev 保存各個(gè)索引層要插入的前一個(gè)結(jié)點(diǎn)
  Node* x = FindGreaterOrEqual(key, prev);

  // Our data structure does not allow duplicate insertion
  // 不允許插入重復(fù)的元素
  // 那么為空涮坐，表示沒有 >= key 的結(jié)點(diǎn)凄贩。要么不等于列表中的所有 key誓军，表示沒有重復(fù)元素
  assert(x == nullptr || !Equal(key, x->key));

  // 生成一個(gè)隨機(jī)高度
  int height = RandomHeight();
  // 如果隨機(jī)高度比當(dāng)前最大高度大
  if (height > GetMaxHeight()) {
    // prev 下標(biāo)從原先的最大 height 到最新的最大 height 之間初始化為 head_
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    // It is ok to mutate max_height_ without any synchronization
    // with concurrent readers.  A concurrent reader that observes
    // the new value of max_height_ will see either the old value of
    // new level pointers from head_ (nullptr), or a new value set in
    // the loop below.  In the former case the reader will
    // immediately drop to the next level since nullptr sorts after all
    // keys.  In the latter case the reader will use the new node.
    // 原子操作：保存最新的最大高度
    max_height_.store(height, std::memory_order_relaxed);
  }

  // 創(chuàng)建一個(gè)新結(jié)點(diǎn)
  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
    // NoBarrier_SetNext() suffices since we will add a barrier when
    // we publish a pointer to "x" in prev[i].
    // 
    // 插入新結(jié)點(diǎn)，即：
    // new_node->next = pre->next;
    // pre->next = new_node;
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

并發(fā)處理

LevelDB 的跳表實(shí)現(xiàn)支持單線程寫疲扎、多線程讀昵时，為了滿足該特點(diǎn)，LevelDB 在更新和讀取時(shí)需要注意 C++ memory_order 的設(shè)置椒丧。

在講解 LevelDB 跳表中的 memory_order 之前需要先介紹相關(guān)的基礎(chǔ)知識(shí)壹甥。

原子性

原子寓意著「不可再分的最小單位」，固計(jì)算機(jī)領(lǐng)域提及的原子性操作指的是那些「不可或不該再被切分（或中斷）的操作」壶熏。

而關(guān)于原子性句柠，我們應(yīng)當(dāng)具有一個(gè)基本的認(rèn)知：高級(jí)語言層面，單條語句并不能保證對(duì)應(yīng)的操作具有原子性棒假。

在使用 C溯职、C++、Java 等各種高級(jí)語言編寫代碼時(shí)帽哑，不少人會(huì)下意識(shí)的認(rèn)為一條不可再分的單條語句具有原子性谜酒，例如常見 i++。

// 偽碼

int i = 0;

void increase() {
  i++;
}

int main() {
  /* 創(chuàng)建兩個(gè)線程妻枕，每個(gè)線程循環(huán)進(jìn)行 100 次 increase */
  // 線程 1
  Thread thread1 = new Thread(
    run() {
      for (int i = 0; i < 100; i++) increase();
    }
  );
  // 線程 2
  Thread thread2 = new Thread(
    run() {
      for (int i = 0; i < 100; i++) increase();
    }
  );
}

如果 i++ 是原子操作僻族，則上述偽碼中的 i 最終結(jié)果為 200。但實(shí)際上每次運(yùn)行結(jié)果可能都不相同屡谐，且通常小于 200述么。

之所以出現(xiàn)這樣的情況是因?yàn)?i++ 在執(zhí)行時(shí)通常還會(huì)繼續(xù)劃分為多條 CPU 指令。以 Java 為例愕掏，i++ 編譯將形成四條字節(jié)碼指令度秘，如下所示：

// Java 字節(jié)碼指令
0:  getstatic
1:  iconst_1
2:  iadd
3:  putstatic

而上述四條指令的執(zhí)行并不保證原子性，即執(zhí)行過程可被打斷亭珍》蠹兀考慮如下 CPU 執(zhí)行序列：

1. 線程 1 執(zhí)行 getstatic 指令，獲得 i = 1
2. CPU 切換到線程 2肄梨，也執(zhí)行了 getstatic 指令阻荒，獲得 i = 1。
3. CPU 切回線程 1 執(zhí)行剩下指令众羡，此時(shí) i = 2
4. CPU 切到線程 2侨赡，由于步驟 2 讀到的是 i = 1，固執(zhí)行剩下指令最終只會(huì)得到 i = 2

以上四條指令是 Java 虛擬機(jī)中的字節(jié)碼指令，字節(jié)碼指令是 JVM 執(zhí)行的指令羊壹。實(shí)際每條字節(jié)碼指令還可以繼續(xù)劃分為更底層的機(jī)器指令蓖宦。但字節(jié)碼指令已經(jīng)足夠演示原子性的含義了

如果對(duì)底層 CPU 層面如何實(shí)現(xiàn)機(jī)器指令的原子操作^[1]感興趣，可查閱 Spinlock油猫、MESI protocol 等資料稠茂。

^[1] 一條 CPU 指令可能需要涉及到緩存、內(nèi)存等多個(gè)單元的交互情妖，而在多核 CPU 的場(chǎng)景下并會(huì)存在與高層次多線程類似的問題睬关。固需要一些機(jī)制和策略才可實(shí)現(xiàn)機(jī)器指令的原子操作。

有序性

上述已經(jīng)提到 CPU 的一條指令執(zhí)行時(shí)毡证，通常會(huì)有多個(gè)步驟电爹，如取指IF 即從主存儲(chǔ)器中取出指令、ID 譯碼即翻譯指令料睛、EX 執(zhí)行指令丐箩、存儲(chǔ)器訪問 MEM 取數(shù)、WB 寫回恤煞。

即指令執(zhí)行將經(jīng)歷：IF屎勘、ID、EX阱州、MEM挑秉、WB 階段。

現(xiàn)在考慮 CPU 在執(zhí)行一條又一條指令時(shí)該如何完成上述步驟苔货？最容易想到并是順序串行犀概，指令 1 依次完成上述五個(gè)步驟，完成之后夜惭，指令 2 再開始依次完成上述步驟姻灶。這種方式簡(jiǎn)單直接，但執(zhí)行效率顯然存在很大的優(yōu)化空間诈茧。

思考一種流水線工作：

指令1   IF ID EX MEM WB
指令2      IF ID EX MEM WB
指令3         IF ID EX MEM WB

采用這種流水線的工作方式产喉，將避免 CPU 、存儲(chǔ)器中各個(gè)器件的空閑敢会，從而充分利用每個(gè)器件曾沈，提升性能。

同時(shí)注意到由于每條指令執(zhí)行的情況有所不同鸥昏，指令執(zhí)行的先后順序?qū)?huì)影響到這條流水線的負(fù)載情況塞俱，而我們的目標(biāo)則是讓整個(gè)流水線滿載緊湊的運(yùn)行。

為此 CPU 又實(shí)現(xiàn)了「指令重排」技術(shù)吏垮，CPU 將有選擇性的對(duì)部分指令進(jìn)行重排來提高 CPU 執(zhí)行的性能和效率障涯。例如：

x = 100;    // #1
y = 200;    // #2
z = x + y;  // #3

雖然上述高級(jí)語言的語句會(huì)編譯成多條機(jī)器指令罐旗，多條機(jī)器指令還會(huì)進(jìn)行「指令重排」，#1 語句與 #2 語句完全有可能被 CPU 重新排序唯蝶，所以程序?qū)嶋H運(yùn)行時(shí)可能會(huì)先執(zhí)行 y = 200; 然后再執(zhí)行 x = 100;

但另一方面九秀，指令重排的前提是不會(huì)影響線程內(nèi)程序的串行語義，CPU 在重排指令時(shí)必須保證線程內(nèi)語義不變粘我，例如：

x = 0; // #1
x = 1; // #2
y = x; // #3

上述的 y 一定會(huì)按照正常的串行邏輯被賦值為 1鼓蜒。

但不幸的是，CPU 只能保證線程內(nèi)的串行語義涂滴。在多線程的視角下友酱，「指令重排」造成的影響需要程序員自己關(guān)注晴音。

// 公共資源
int x = 0;
int y = 0;
int z = 0;

Thread_1:             Thread_2:
x = 100;              while (y != 200);
y = 200;              print x
z = x + y;

如果 CPU 不進(jìn)行「亂序優(yōu)化」執(zhí)行柔纵，那么 y = 200 時(shí)，x 已經(jīng)被賦值為 100锤躁，此時(shí)線程 2 輸出 x = 200搁料。

但實(shí)際運(yùn)行時(shí)，線程 1 可能先執(zhí)行 y = 200系羞，此時(shí) x 還是初始值 0郭计。線程 2 觀察到 y = 200 后，退出循環(huán)椒振，輸出 x = 0;

C++ 中的 atomic 和 memory_order

C++ 提供了 std::atomic 類模板昭伸，以保證操作原子性。同時(shí)也提供了內(nèi)存順序模型 memory_order指定內(nèi)存訪問澎迎，以便提供有序性和可見性庐杨。

其中 memory_order 共有六種，如下表所示：

六種 memory_order 可以組合出四種順序：

1. Relaxed ordering 寬松順序

Thread1: 
y.load(std::memory_order_relaxed);

Thread2:
y.store(h, std::memory_order_relaxed);

寬松順序只保證原子變量的原子性（變量操作的機(jī)器指令不進(jìn)行重排序），但無其他同步操作鸟辅，不保證多線程的有序性氛什。

1. Release-Acquire ordering 釋放獲得順序

 
std::atomic<std::string*> ptr;
int data;
 
void producer()
{
    std::string* p  = new std::string("Hello"); // #1
    data = 42;  // #2
    ptr.store(p, std::memory_order_release);
}
 
void consumer()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_acquire)))
        ;
    assert(*p2 == "Hello"); // 絕無問題 #3
    assert(data == 42); // 絕無問題 #4
}
 
int main()
{
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join(); t2.join();
}

如例子所示，store 使用 memory_order_release匪凉，load 使用 memory_order_acquire枪眉，CPU 將保證如下兩點(diǎn)：

• store 之前的語句不允許被重排序到 store 之后（例子中的 #1 和 #2 語句一定在 store 之前執(zhí)行）
• load 之后的語句不允許被重排序到 load 之前（例子中的 #3 和 #4 一定在 load 之后執(zhí)行）

同時(shí) CPU 將保證 store 之前的語句比 load 之后的語句「先行發(fā)生」，即先執(zhí)行 #1洒缀、#2瑰谜，然后執(zhí)行 #3欺冀、#4。這實(shí)際上就意味著線程 1 中 store 之前的讀寫操作對(duì)線程 2 中 load 執(zhí)行后是可見的萨脑。

注意是所有操作都同步了隐轩，不管 #3 是否依賴了 #1 或 #2

值得關(guān)注的是這種順序模型在一些強(qiáng)順序系統(tǒng)例如 x86、SPARC TSO渤早、IBM 主框架上是自動(dòng)進(jìn)行的职车。但在另外一些系統(tǒng)如 ARM、Power PC 等需要額外指令來保障鹊杖。

3. Release-Consume ordering 釋放消費(fèi)順序
   理解了釋放獲得順序順序后悴灵，就非常容易理解釋放消費(fèi)順序，因?yàn)閮烧呤诸愃啤?/li>

 
std::atomic<std::string*> ptr;
int data;
 
void producer()
{
    std::string* p  = new std::string("Hello"); // #1
    data = 42; // #2
    ptr.store(p, std::memory_order_release);
}
 
void consumer()
{
    std::string* p2;
    while (!(p2 = ptr.load(std::memory_order_consume)))
        ;
    assert(*p2 == "Hello"); // #3 絕無出錯(cuò)： *p2 從 ptr 攜帶依賴
    assert(data == 42); // #4 可能也可能不會(huì)出錯(cuò)： data 不從 ptr 攜帶依賴
}
 
int main()
{
    std::thread t1(producer);
    std::thread t2(consumer);
    t1.join(); t2.join();
}

store 使用 memory_order_release骂蓖，load 使用 memory_order_consume雪标。其效果與 Release-Acquire ordering 釋放獲得順序類似，唯一不同的是并不是所有操作都同步（不夠高效）筋岛，而是只對(duì)依賴操作進(jìn)行同步淹冰，保證其有序性上例就是 #3 一定發(fā)生在 #1 之后，因?yàn)檫@兩個(gè)操作依賴于 ptr被芳。但不會(huì)保證 #4 一定發(fā)生在 #2 之后（注意「釋放獲得順序」可以保證這一點(diǎn)）缰贝。

4. Sequential consistency 序列一致順序
   理解上述幾種順序后，Sequential consistency 就很好理解了畔濒。

「釋放獲得順序」是對(duì)某一個(gè)變量進(jìn)行同步剩晴，Sequential consistency 序列一致順序則是對(duì)所有變量的所有操作都進(jìn)行同步。

store 和 load 都使用 memory_order_seq_cst侵状，可以理解對(duì)每個(gè)變量都進(jìn)行 Release-Acquire 操作赞弥。所以這也是最慢的一種順序模型。

LevelDB 跳表的并發(fā)處理

在 LevelDB 的 skiplist.h 中壹将，涉及到了 atomic 和 memory_order嗤攻，我們結(jié)合上文的介紹來理解其中的實(shí)現(xiàn)邏輯。

首先對(duì)跳表的最大高度 max_height_ 設(shè)置了 atomic诽俯，并采用 memory_order_relaxed 進(jìn)行讀寫：

// 確保在所有平臺(tái)下以及內(nèi)存對(duì)齊或非對(duì)齊情況下
// 對(duì) max_height_ 的讀寫都是原子性的
std::atomic<int> max_height_;

// ....

// store 和 load 都采用了 memory_order_relaxed
// 即采用 Relaxed ordering 寬松順序
// 即對(duì)多線程有序性不做保證
max_height_.store(height, std::memory_order_relaxed);

// ...

max_height_.load(std::memory_order_relaxed);

max_height_ 如同實(shí)現(xiàn)一個(gè)計(jì)數(shù)器 i++ 一樣妇菱，如果多線程讀不是原子性的，那么就會(huì)造成類似某個(gè)線程讀到舊數(shù)據(jù)或不完整數(shù)據(jù)的局面暴区。

其次對(duì)跳表結(jié)點(diǎn)的索引結(jié)點(diǎn)也進(jìn)行了 atomic 的處理闯团，如下所示：

std::atomic<Node*> next_[1];

// ...

// 插入結(jié)點(diǎn)時(shí)
next_[n].store(x, std::memory_order_release);

// ...

// 讀取結(jié)點(diǎn)時(shí)
next_[n].load(std::memory_order_acquire);

從中可知，對(duì) next_[n] 使用了 Release-Acquire ordering 釋放獲得順序仙粱，其可以保證某個(gè)線程進(jìn)行 store 后房交，其他所有執(zhí)行 load 的讀線程都將讀到 store 的最新數(shù)據(jù)。因?yàn)獒尫奴@得順序保證了 先 store 后 load 的執(zhí)行順序伐割。

這也正是 LevelDB 的跳表支持多線程讀的原因候味。

值得注意的是其中還實(shí)現(xiàn)了 NoBarrier_SetNext 和 NoBarrier_Next刃唤。這兩個(gè)沒有內(nèi)存屏障的操作實(shí)際就是使用了寬松順序?qū)?next_[n] 進(jìn)行讀寫。這種操作是線程不安全的白群，為什么需要這種操作尚胞？

void SkipList<Key, Comparator>::Insert(const Key& key) {
  // ... 

  // 插入新結(jié)點(diǎn)
  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
    // 這兩句相當(dāng)于：
    // new_node->next = pre->next;
    // pre->next = new_node;
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

在一個(gè)鏈表中插入一個(gè)結(jié)點(diǎn)的步驟實(shí)際就是：

new_node->next = pre->next;
pre->next = new_node;

而 new_node->next = pre->next; 這一步賦值不必立馬對(duì)所有讀線程可見，因?yàn)榇藭r(shí)還未完全插入結(jié)點(diǎn)帜慢，并不影響讀線程的讀取笼裳。如下圖所示：

concurrency.png

為什么要特意使用 NoBarrier_SetNext ？因?yàn)閷捤身樞蛐矢吡涣幔梢钥吹?LevelDB 的跳表實(shí)現(xiàn)為了性能已經(jīng)優(yōu)化到了如此變態(tài)的地步躬柬。

附錄

源碼注解

對(duì) LevelDB 中跳表 skiplist.h 的源碼實(shí)現(xiàn)做了詳細(xì)注解，可見源碼注解抽减。

操作樣例

1. 創(chuàng)建一個(gè) SkipList允青，數(shù)據(jù)結(jié)構(gòu)初始化如下圖所示：

implement_0.png

1. 新增一個(gè)結(jié)點(diǎn)，且設(shè) key = 10胯甩，隨機(jī) height = 4,則數(shù)據(jù)結(jié)構(gòu)如下圖所示：

implement_1.png

1. 繼續(xù)新增一個(gè)結(jié)點(diǎn)昧廷，且設(shè) key = 5，隨機(jī) height= 3偎箫，則數(shù)據(jù)結(jié)構(gòu)如下圖所示：

implement_2.png

1. 繼續(xù)新增一個(gè)結(jié)點(diǎn)，且設(shè) key = 4皆串，隨機(jī) height = 5淹办，則數(shù)據(jù)結(jié)構(gòu)如下圖所示：
   
   implement_3.png

參考資料

跳躍列表 Wikipedia
Skip list Wikipedia
Skip Lists: A Probabilistic Alternative to Balanced Trees
Atomic_semantics Wikipedia
Spinlock Wikipedia
MESI_protocol Wikipedia
CPU的工作過程
std::memory_order
周志明.2011.深入理解 Java 虛擬機(jī)
葛一鳴，郭超.2015.Java高并發(fā)程序設(shè)計(jì)

汪

汪