• 熱門專題

LevelDB源碼之一SkipList

作者:音符、時間、走走停停  發布日期:2015-09-14 22:21:50
Tag標簽:源碼  
  • SkipList稱之為跳表,可實現Log(n)級別的插入、刪除。和Map、set等典型的數據結構相比,其問題在于性能與插入數據的隨機性有關,這和Q-Sort于Merge-Srot類似。

    LevelDB做為單機數據庫存儲系統,正常操作下,整體(隨機讀寫、順序讀寫)性能上明顯優于同類型的SQLite等數據庫,這與內存數據采用的SkipList存儲方式密切相關。

    本文主要針對LevelDB中的SkipList的設計、實現的一些特點做備忘。

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

    MaxHeight為SkipList的關鍵參數,與性能直接相關。

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

    看如下代碼:

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

    其中的關鍵在于粗體的kBranching及(rnd_.Next() % kBranching。這使得上層節點的數量約為下層的1/4。那么,當設定MaxHeight=12時,根節點為1時,約可均勻容納Key的數量為4^11=4194304(約為400W)。

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

    2. 讀寫并發

    讀值本身并不會改變SkipList的結構,因此多個讀之間不存在并發問題。

    而當讀、寫同時存在時,SkipList通過AtomicPointer(原子指針)及結構調整上的小技巧達到“無鎖”并發。

    SkipList<Key, Comparator>::Node

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

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

    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     }

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

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

    1         // Accessors/mutators for links.  Wrapped in methods so we can
    2         // 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);

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

    template<typename Key, class Comparator> class SkipList 

    讀操作時的并發處理主要體現在:使用Next成員函數執行原子的下一條查找動作。

    寫操作的并發處理稍復雜,下面為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 synchronization
    19             // with concurrent readers.  A concurrent reader that observes
    20             // the new value of max_height_ will see either the old value of
    21             // new level pointers from head_ (NULL), or a new value set in
    22             // the loop below.  In the former case the reader will
    23             // immediately drop to the next level since NULL sorts after all
    24             // 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 when
    31             // we publish a pointer to "x" in prev[i].
    32             x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));    //為性能及并發考慮的深度優化,這里的兩個NoBarrier
    33             prev[i]->SetNext(i, x);
    34         }
    35     }

    15行之前用于查找插入的位置,25行執行了第一個狀態變更:設置當前的max_height_。

    作者的注釋指明了并發讀時可能存在的兩種情況,但完整描述應該如下:

    1. 讀到舊的max_height_,而后寫線程更新了max_height_并正在進行或完成節點插入

    2. 讀到新的max_height_,而寫線程正在進行或完成節點插入

    對于上述兩種(其實是多種,這里為細分)情況,作者說明并不存在并發問題,為何呢?

    關鍵在于28-34行插入方式:

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

    當然,多個寫之間的并發SkipList時非線程安全的,在LevelDB的MemTable中采用了另外的技巧來處理寫并發問題。

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

    SkipList的迭代器,支持雙向遍歷,其實現本身并無特別之處,只不過是SkipList的一個封裝,略。

        Insert:         1252072    Contains:       1296074

延伸閱讀:

About IT165 - 廣告服務 - 隱私聲明 - 版權申明 - 免責條款 - 網站地圖 - 網友投稿 - 聯系方式
本站內容來自于互聯網,僅供用于網絡技術學習,學習中請遵循相關法律法規
彩票联盟网站新邵县| 类乌齐县|