前文回顧

• LevelDB 完全解析（0）：基本原理和整體架構(gòu)

MemTable 介紹

MemTable奈辰，顧名思議，就是內(nèi)存表。每個(gè) LevelDB 實(shí)例最多會(huì)維護(hù)兩個(gè) MemTable： mem_ 和 imm_。mem_ 可以讀寫，imm_ 只讀埠胖。

在 LevelDB 中，最新寫入的數(shù)據(jù)都會(huì)保存到 mem_ 中淳玩。當(dāng) mem_ 的大小超過 write_buffer_size 時(shí)直撤，LevelDB 就會(huì)將其切換成 imm_，并生成新的 mem_蜕着。
LevelDB 的后臺線程會(huì)將 imm_ compact 成 SSTable 保存在磁盤上谋竖。
如果前臺的寫入速度很快，有可能出現(xiàn) mem_ 的大小已經(jīng)超過 write_buffer_size，但是前一個(gè) imm_ 還沒有被 compact 到磁盤上圈盔，無法切換 MemTable豹芯，此時(shí)就會(huì)出現(xiàn) stall write（阻塞寫請求）。

leveldb::MemTable 主要支持的操作有：

• 插入單條記錄：Add驱敲。
• 查詢單條記錄：Get铁蹈。
• 遍歷（范圍查詢）：MemTableIterator。

LevelDB 的 MemTable 的主要功能是將內(nèi)部編碼众眨、內(nèi)存分配（Arena）和 SkipList 封裝在一起握牧。

MemTable 的內(nèi)部編碼

MemTable 中保存的數(shù)據(jù)是 key 和 value 編碼成的一個(gè)字符串，由四個(gè)部分組成：

1. klength: 變長的 32 位整數(shù)（varint 的編碼）娩梨，表示 internal key 的長度沿腰。
2. internal key: 長度為 klength 的字符串。
3. vlength: 變長的 32 位整數(shù)狈定，表示 value 的長度颂龙。
4. value: 長度為 vlength 的字符串。因?yàn)?value 沒有參與排序纽什，所以相關(guān)的討論暫時(shí)可以忽略措嵌。

MemTable 的 KeyComparator 負(fù)責(zé)從 memkey 中提取出 internalkey，最終排序邏輯是使用 InternalKeyComparator 進(jìn)行比較芦缰，排序規(guī)則如下：

1. 優(yōu)先按照 user key 進(jìn)行排序企巢。
2. User key 相同的按照 seq 降序排序。
3. User key 和 seq 相同的按照 type 降序排序（邏輯上不會(huì)達(dá)到這一步让蕾，因?yàn)橐粋€(gè) LevelDB 的 sequence 是單調(diào)遞增的）浪规。

所以，在一個(gè) MemTable 中探孝，相同的 user key 的多個(gè)版本笋婿，新的排在前面，舊的排在后面再姑。

MemTable 的內(nèi)存分配

MemTable 通過 Arena 進(jìn)行內(nèi)存分配和使用統(tǒng)計(jì)萌抵。Arena 其實(shí)就是一個(gè)簡化的內(nèi)存池找御。它只提供分配內(nèi)存的接口元镀，不提供釋放內(nèi)存的接口。只有當(dāng)整個(gè) Arena 對象銷毀的時(shí)候才會(huì)將之前申請的內(nèi)存釋放掉霎桅。
Arena 提供了兩個(gè)內(nèi)存分配接口：

1. Allocate(size_t bytes)
2. AllocateAligned(size_t bytes)

一般情況下栖疑，Allocate 每次從操作系統(tǒng)申請一塊大小為 kBlockSize 的內(nèi)存，默認(rèn)是 4KB滔驶。之后遇革，在 block 剩余內(nèi)存足夠的情況下，內(nèi)存申請都可以直接從這個(gè) block 劃一部分出去（參考代碼）。如果 block 剩余的內(nèi)存不夠萝快，并且申請的內(nèi)存大于 kBlockSize / 4锻霎，則直接 new 一塊內(nèi)存給這個(gè)請求（參考代碼），避免造成太多的內(nèi)部碎片揪漩。否則旋恼，就直接再申請一個(gè) block，并從這個(gè) block 劃分一部分（參考代碼）奄容。

因?yàn)?SkipList 中會(huì)涉及一些原子操作冰更，所以 AllocateAligned 分配的內(nèi)存需要和指針的大小（一般是 8 字節(jié)）對齊昂勒。其他邏輯和 Allocate 一樣蜀细。

Skip List

Skip List 簡介

skip list

1990 年，William Pugh 發(fā)表了 skip list 的論文：Skip Lists: A Probabilistic Alternative to
Balanced Trees戈盈。

Skip list 是一種可以用于替代查找樹的內(nèi)存數(shù)據(jù)結(jié)構(gòu)奠衔，其基本原理是在一個(gè)有序的鏈表之上增加一些索引，通過一個(gè)隨機(jī)規(guī)則（保證一定概率）來“模擬”二分查找塘娶。
直觀上可以將整個(gè) skip list 看成是一條地鐵線涣觉。每個(gè)節(jié)點(diǎn)就是一個(gè)地鐵站，比如上圖的 1~10血柳。假設(shè) (1) 是始發(fā)站官册，(NIL) 是終點(diǎn)站。這條地鐵線有多種快車难捌、慢車的線路膝宁，每個(gè)條線路經(jīng)停的地鐵站都不一樣。比如上圖就有四種不同線路（用向右的箭頭表示）根吁，從上往下：
線路1：只停始發(fā)站(1) 和終點(diǎn)站(NIL)
線路2：始發(fā)站(1) => (4) => (6) => 終點(diǎn)站(NIL)
線路3：始發(fā)站(1) => (3) => (4) => (6) => (9) =>終點(diǎn)站(NIL)
線路4：每一站都停员淫。
注意，skip list 這里的主要成本是經(jīng)過的站點(diǎn)數(shù)量击敌，而在某個(gè)站點(diǎn)進(jìn)行轉(zhuǎn)線的成本是零介返。我們可以合理轉(zhuǎn)換不同線路來減少經(jīng)過的站點(diǎn)數(shù)量。假如我們要去地鐵站(9)沃斤，可以先坐線路 2 到地鐵站(6)圣蝎，再轉(zhuǎn)線路 3 到地鐵站(9)：經(jīng)過的站點(diǎn)有 (1)、(4)衡瓶、(6)徘公、(9)。

Skip List 原理

image

Skip list 的基礎(chǔ)是一個(gè)有序的鏈表哮针。但是因?yàn)殒湵碓趦?nèi)存中是離散存儲(chǔ)的关面，我們無法在一個(gè)有序鏈表上執(zhí)行二分查找坦袍。

image

所以，我們決定在這個(gè)有序的鏈表上增加一層索引等太，用于將這個(gè)有序鏈表一分為二捂齐。通過第一層索引可以將查找量減少一半。

image

Skip list 放棄了精確控制每個(gè)節(jié)點(diǎn)的索引高度來實(shí)現(xiàn)“二分查找”和屎，轉(zhuǎn)而采用一個(gè)隨機(jī)概率規(guī)則來確定一個(gè)節(jié)點(diǎn)的高度拴驮。這樣，一個(gè)節(jié)點(diǎn)的插入和刪除柴信，只會(huì)和它的相鄰節(jié)點(diǎn)有關(guān)套啤，邏輯簡單，并且修改范圍非常有限（鎖粒度可以做到很細(xì)）随常，可以實(shí)現(xiàn)更高的并發(fā)潜沦。
要實(shí)現(xiàn)隨機(jī)近似二分查找，我們需要保證一個(gè)高度為 h 的節(jié)點(diǎn)绪氛，有 1/2 的概率是高度為 h+1 的節(jié)點(diǎn) ：

1. 高度 >= 1 的節(jié)點(diǎn)概率為 1唆鸡。
2. 高度 >= 2 的節(jié)點(diǎn)概率為 1/2。
3. 高度 >= 3 的節(jié)點(diǎn)概率為 1/4枣察。
4. ...
5. 高度 >= h 的節(jié)點(diǎn)概率為 1 / 2^(h-1)争占。

更通用一點(diǎn)，假設(shè)一個(gè)高度為 h 的節(jié)點(diǎn)序目，有概率 p 是高度為 h+1 的節(jié)點(diǎn)臂痕。那么一個(gè)長度為 n 的 skip list，需要的指針數(shù)量為：N = p^0 * n + p^1 * n + p^2 * n + ... = n * (p^0 + p^1 + p^2 + ....) = n*(1-p^n) / (1 - p)<br />因?yàn)?p < 1宛琅，當(dāng) n 趨近無窮的時(shí)候刻蟹，p^n 趨近于 0逗旁，因此 N = n/(1-p)嘿辟。Skip list 的空間復(fù)雜度是 O(n)舆瘪。
如果我們想節(jié)省內(nèi)存空間，可以適當(dāng)?shù)恼{(diào)低 1/2 這個(gè)概率红伦，比如 1/3英古、1/4，從而減少索引指針個(gè)數(shù)昙读。

LevelDB 的 SkipList 實(shí)現(xiàn)

LevelDB 的 SkipList 支持無鎖的一寫多讀召调，并且只支持查找和插入。LevelDB 通過維護(hù)一個(gè)寫隊(duì)列來保證同一時(shí)刻只有一個(gè)線程會(huì)寫 MemTable蛮浑。
根據(jù) RandomHeight 的實(shí)現(xiàn)唠叛，LevelDB 將上面分析的每個(gè)元素高度增長的概率設(shè)置為 1/4 ，以節(jié)省內(nèi)存沮稚。

template <typename Key, class Comparator>
int SkipList<Key, Comparator>::RandomHeight() {
  // Increase height with probability 1 in kBranching
  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;
}

FindGreaterOrEqual 查找并返回第一個(gè)大于等于 key 的節(jié)點(diǎn)艺沼。如果是查找后需要進(jìn)行插入，需要記錄下這個(gè)節(jié)點(diǎn)的 prev 指針蕴掏。

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);
    if (KeyIsAfterNode(key, next)) {
      // Keep searching in this list
      x = next;
    } else {
      if (prev != nullptr) prev[level] = x;
      if (level == 0) {
        return next;
      } else {
        // Switch to next list
        level--;
      }
    }
  }
}

FindLessThan 查找并返回最后一個(gè)小于 key 的節(jié)點(diǎn)障般。
FindLast 查找并返回最后一個(gè)節(jié)點(diǎn)。
Contains 查找 SkipList 是否包含某個(gè) key盛杰。
Insert 插入一個(gè) key挽荡。前面說了，LevelDB 保證這里同一時(shí)刻只會(huì)有一個(gè)線程在寫入即供，并通過原子地修改指針（SetNext）來保證不影響并發(fā)執(zhí)行的讀請求定拟。

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];
  Node* x = FindGreaterOrEqual(key, prev);

  // Our data structure does not allow duplicate insertion
  assert(x == nullptr || !Equal(key, x->key));

  int height = RandomHeight();
  if (height > GetMaxHeight()) {
    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);
  }

  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].
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

  void SetNext(int n, Node* x) {
    assert(n >= 0);
    // Use a 'release store' so that anybody who reads through this
    // pointer observes a fully initialized version of the inserted node.
    next_[n].store(x, std::memory_order_release);
  }