Skiplist原理

skiplist示意圖

內(nèi)存屏障

內(nèi)存屏障，也稱內(nèi)存柵欄，內(nèi)存柵障，屏障指令等，是一類同步屏障指令，是CPU或編譯器在對內(nèi)存隨機(jī)訪問的操作中的一個(gè)同步點(diǎn)，使得此點(diǎn)之前的所有讀寫操作都執(zhí)行后才可以開始執(zhí)行此點(diǎn)之后的操作。更多細(xì)節(jié)

leveldb支持多線程操作，但skiplist中并沒有使用鎖，信號量來實(shí)現(xiàn)同步控制，因?yàn)殒i機(jī)制導(dǎo)致某個(gè)線程占有資源，其他線程阻塞的情況，導(dǎo)致系統(tǒng)資源利用率降低。所以leveldb采用的是內(nèi)存屏障來實(shí)現(xiàn)同步機(jī)制。

class AtomicPointer {
 private:
  void* rep_;
 public:
  AtomicPointer() { }
  explicit AtomicPointer(void* p) : rep_(p) {}
  inline void* NoBarrier_Load() const { return rep_; }
  inline void NoBarrier_Store(void* v) { rep_ = v; }
  inline void* Acquire_Load() const {
    void* result = rep_;
    MemoryBarrier();//內(nèi)存屏障
    return result;
  }
  inline void Release_Store(void* v) {
    MemoryBarrier();
    rep_ = v;
  }
};

關(guān)于內(nèi)存屏障的實(shí)現(xiàn)，各個(gè)平臺不同。。我就沒有具體研究了，感興趣的朋友可以去自己搜搜資料。

Node

template<typename Key, class Comparator>
struct SkipList<Key,Comparator>::Node {
  explicit Node(const Key& k) : key(k) { }
  Key const key;
  // Accessors/mutators for links.  Wrapped in methods so we can
  // add the appropriate barriers as necessary.
  Node* Next(int n) {
    assert(n >= 0);
    // Use an 'acquire load' so that we observe a fully initialized
    // version of the returned Node.
    return reinterpret_cast<Node*>(next_[n].Acquire_Load());
  }
  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].Release_Store(x);
  }
  // No-barrier variants that can be safely used in a few locations.
  Node* NoBarrier_Next(int n) {
    assert(n >= 0);
    return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());
  }
  void NoBarrier_SetNext(int n, Node* x) {
    assert(n >= 0);
    next_[n].NoBarrier_Store(x);
  }
 private:
  // Array of length equal to the node height.  next_[0] is lowest level link.
  port::AtomicPointer next_[1]; // 占位用
};

剛開始看到port::AtomicPointer next_[1];這句我整個(gè)人是懵逼的=。=，心想這在函數(shù)調(diào)用中不是特么越界么，后來發(fā)現(xiàn)大佬還是大佬，我還是too young too simple，看下面這個(gè)申請Node的函數(shù)

template<typename Key, class Comparator>
typename SkipList<Key,Comparator>::Node*
SkipList<Key,Comparator>::NewNode(const Key& key, int height) {
  char* mem = arena_->AllocateAligned(
      sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
  return new (mem) Node(key);
}

這樣就可以理解了，實(shí)際上這是一個(gè)技巧性的作法，利用port::AtomicPointer next_[1]來占位，然后在申請內(nèi)存的時(shí)候，實(shí)際的數(shù)組大小和本節(jié)點(diǎn)的的height一致。

插入&&查詢

leveldb中為skiplist自身僅實(shí)現(xiàn)了insert和contain兩個(gè)公開的函數(shù)接口。
查詢邏輯相當(dāng)簡單，直接上代碼

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

leveldb中skiplist的核心操作當(dāng)屬insert先上代碼然后再具體分析

template<typename Key, class Comparator>
void SkipList<Key,Comparator>::Insert(const Key& key) {
  Node* prev[kMaxHeight];
  Node* x = FindGreaterOrEqual(key, prev);

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

  int height = RandomHeight();
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
  }

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

思想是，在插入高度為height的節(jié)點(diǎn)時(shí)，首先要找到這個(gè)節(jié)點(diǎn)height個(gè)前節(jié)點(diǎn)，然后插入就和普通的鏈表插入一樣。

max_height更新的兩種情況：

1. 讀到舊的max_height_，而后寫線程更新了max_height_并正在進(jìn)行或完成節(jié)點(diǎn)插入
2. 讀到新的max_height_，而寫線程正在進(jìn)行或完成節(jié)點(diǎn)插入

對于上述兩種情況，作者說明并不存在并發(fā)問題，為何呢？
不存在并發(fā)的關(guān)鍵在于最后的for循環(huán)中，由最下層向上插入可以保證當(dāng)前層一旦插入后，其下層狀態(tài)已經(jīng)更新。 SetNext為原子操作，保證讀線程在調(diào)用Next查找節(jié)點(diǎn)時(shí)不存在并發(fā)問題。
當(dāng)然，多個(gè)寫之間的并發(fā)skiplist時(shí)非線程安全的，在leveldb的memtable中采用了另外的技巧來處理寫并發(fā)問題。

同樣leveldb中沒有提供顯式的刪除節(jié)點(diǎn)操作，但實(shí)際上是可以刪除的，因?yàn)楫?dāng)我們插入數(shù)據(jù)時(shí)，key的形式為key:value，當(dāng)刪除數(shù)據(jù)時(shí)，則插入key:deleted類似刪除的標(biāo)記，等到Compaction再刪除。

leveldb中還自己封裝了一個(gè)雙向迭代器，很簡單的實(shí)現(xiàn)，不具體分析了。