• 大发百人牛牛官网

  • 大发百人牛牛官网

  • 大发百人牛牛官网

  • 大发百人牛牛官网

大发百人牛牛官网

作者︰音(yin)符(fu)、時間、走走停停  發布日期︰2020-02-25 23:04:50
Tag標簽︰源碼  
  • SkipList稱之為跳表,可實現(xian)Log(n)級別的插(cha)入、刪(shan)除。和Map、set等(deng)典型的數據(ju)結(jie)構相(xiang)比,其問(wen)題在于(yu)性能與(yu)插(cha)入數據(ju)的隨機性za)泄兀 zhe)和Q-Sort于(yu)Merge-Srot類似。

    LevelDB做(zuo)為單(dan)機數據(ju)庫存儲(chu)系統,正常操作下,整體(隨機讀寫(xie)chu)?承xu)讀寫(xie))性能上(shang)明(ming)顯za)龐yu)同類型的SQLite等(deng)數據(ju)庫,這(zhe)與(yu)內存數據(ju)采用的SkipList存儲(chu)方式密切相(xiang)關。

    本文主(zhu)要(yao)針對(dui)LevelDB中(zhong)的SkipList的設計、實現(xian)的一些特(te)點做(zuo)備(bei)忘(wang)。

    1. SkipList層級間的均(jun)勻分布,MaxHeight = 12, RandomHeight()

    MaxHeight為SkipList的關鍵(jian)參wen) yu)性能直(zhi)接相(xiang)關。

    程序(xu)中(zhong)修改MaxHeight時,在數值變小時,性能上(shang)有明(ming)顯下降,但當數值增大時,甚至增大到10000時,和默認的MaxHeight=12相(xiang)比仍舊(jiu)無明(ming)顯差異,內存使用上(shang)也是如(ru)此。

    看如(ru)下代碼︰

    template<typename Key, class Comparator>int SkipList<Key, Comparator>::RandomHeight() {// Increase height with probability 1 in kBranchingstatic const unsigned int kBranching = 4;int height = 1;while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {height++;}assert(height > 0);assert(height <= kMaxHeight);return height;}

    其中(zhong)的關鍵(jian)在于(yu)粗(cu)體的kBranching及(rnd_.Next() % kBranching。這(zhe)使得上(shang)層節(jie)點的數量約(yue)為下層的1/4。那麼,當設定(ding)MaxHeight=12時,根節(jie)點為1時,約(yue)可shan)熱rong)納Key的數量為4^11=4194304(約(yue)為400W)。

    當單(dan)獨增大MaxHeight時,並(bing)不會使得SkipList的層級提(ti)升。MaxHeight=12為經驗值,在百萬數據(ju)規模時,尤為適用。

    2. 讀寫(xie)並(bing)發

    讀值本jiu)聿bing)不會改變SkipList的結(jie)構,因此多個讀之間不存在並(bing)發問(wen)題。

    而當讀、寫(xie)同時存在時,SkipList通過AtomicPointer(原子(zi)指針)及結(jie)構調整上(shang)的小技ji)紗da)到“無鎖”並(bing)發。

    SkipList<Key, Comparator>::Node

    首(shou)先,節(jie)點一旦被添加到SkipList中(zhong),其層級結(jie)構將不再發生(sheng)變化(hua),Node中(zhong)的唯一成員︰port::AtomicPointer next_[1] 大小不會再發生(sheng)改變。

    port::AtomicPointer next_[1];用于(yu)站位(wei),實際的數組大小和本節(jie)點的Height一致,Node創(chuang)建代碼如(ru)下︰

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

    其中(zhong),Line4根據(ju)height創(chuang)建真正大小的Node,Line6顯示調用構造函數,完(wan)成Node創(chuang)建(這(zhe)種用法並(bing)不常見)。

    再來看Node的四個成員函數︰

    1  // Accessors/mutators for links. Wrapped in methods so we can2  // add the appropriate barriers as necessary.3  Node* Next(int n);4  void SetNext(int n, Node* x) ;5 6  // No-barrier variants that can be safely used in a few locations.7  Node* NoBarrier_Next(int n);8  void NoBarrier_SetNext(int n, Node* x);

    上(shang)面兩(liang)組為線程安全訪問(wen)操作,下面兩(liang)組為非線程安全訪問(wen)操作。後兩(liang)組函數是作者追求極致性能時,降低了對(dui)封裝的要(yao)求。

    template<typename Key, class Comparator> class SkipList 

    讀操作時的並(bing)發處理主(zhu)要(yao)體現(xian)在︰使用Next成員函數執行原子(zi)的下一條查(cha)找(zhao)動作。

    寫(xie)操作的並(bing)發處理稍復雜(za),下面為Insert代碼︰

     1 template<typename Key, class Comparator> 2 void SkipList<Key, Comparator>::Insert(const Key& key) { 3  // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual() 4  // here since Insert() is externally synchronized. 5  Node* prev[kMaxHeight]; 6  Node* x = FindGreaterOrEqual(key, prev); 7 8  // Our data structure does not allow duplicate insertion 9  assert(x == NULL !Equal(key, x->key));10 11  int height = RandomHeight();12  if (height > GetMaxHeight()) {13  for (int i = GetMaxHeight(); i < height; i++) {14   prev[i] = head_;15  }16  //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);17 18  // It is ok to mutate max_height_ without any synchronization19  // with concurrent readers. A concurrent reader that observes20  // the new value of max_height_ will see either the old value of21  // new level pointers from head_ (NULL), or a new value set in22  // the loop below. In the former case the reader will23  // immediately drop to the next level since NULL sorts after all24  // keys. In the latter case the reader will use the new node.25  max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));26  }27 28  x = NewNode(key, height);29  for (int i = 0; i < height; i++) {30  // NoBarrier_SetNext() suffices since we will add a barrier when31  // we publish a pointer to "x" in prev[i].32  x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i)); //為性能及並(bing)發考(kao)慮(lv)的深度優化(hua),這(zhe)里的兩(liang)個NoBarrier33  prev[i]->SetNext(i, x);34  }35 }

    15行之前用于(yu)查(cha)找(zhao)插(cha)入的位(wei)置(zhi),25行執行了第一個狀態變更︰設置(zhi)當前的max_height_。

    作者的注釋指明(ming)了並(bing)發讀時可能存在的兩(liang)種情(qing)況,但完(wan)整描述應該如(ru)下︰

    1. 讀到舊(jiu)的max_height_,而後寫(xie)線程更新了max_height_並(bing)正在進行或(huo)完(wan)成節(jie)點插(cha)入

    2. 讀到新的max_height_,而寫(xie)線程正在進行或(huo)完(wan)成節(jie)點插(cha)入

    對(dui)za)諫shang)述兩(liang)種(其實是qian)嘀鄭 zhe)里為細(xi)分)情(qing)況,作者說明(ming)並(bing)不存在並(bing)發問(wen)題,為何呢?

    關鍵(jian)在于(yu)28-34行插(cha)入方式︰

    28  x = NewNode(key, height);29  for (int i = 0; i < height; i++) {30  // NoBarrier_SetNext() suffices since we will add a barrier when31  // we publish a pointer to "x" in prev[i].32  x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i)); //為性能及並(bing)發考(kao)慮(lv)的深度優化(hua),這(zhe)里的兩(liang)個NoBarrier33  prev[i]->SetNext(i, x);34  }
    關鍵(jian)在哪里?兩(liang)點︰29行的for循環(huan)順序(xu)及33行的SetNext.
    1. 由(you)最下層向上(shang)插(cha)入可以保證當前層一旦插(cha)入後,其下層狀態已經更新。
    2. SetNext為原子(zi)操作,保證讀線程在調用Next查(cha)找(zhao)節(jie)點時不存在並(bing)發問(wen)題
    額外需注意的是,32行中(zhong),作者為了保證性能最優在x的SetNext及prev的Next均(jun)采用了非線程安全的方式。

    當然,多個寫(xie)之間的並(bing)發SkipList時非線程安全的,在LevelDB的MemTable中(zhong)采用了另外的技ji)衫創(chuang)  xie)並(bing)發問(wen)題。

    template<typename Key, class Comparator> class SkipList<Key, Comparator>::Iterator 

    SkipList的迭代器(qi),支持雙向遍歷,其實現(xian)zhi)舊(jiu)聿bing)無特(te)別之處,只不過是SkipList的一個封裝,略(lue)。

        Insert:         1252072    Contains:       1296074

延you)煸畝粒/h3>

About IT165 -廣告(gao)服(fu)務 -隱(yin)私聲明(ming) -版權申明(ming) -免責條款 -網站地圖 -網友投稿 -聯系方式
本站內容(rong)來自za)諢hu)聯網,僅供(gong)用于(yu)網絡技術學習,學習中(zhong)請遵循相(xiang)關法律法規
大发百人牛牛官网 | 下一页