• 熱門專題

LevelDB源碼之一SkipList

作者|_亿彩是真的吗:音符_-乡村爱情小夜曲6、時間|艺术照 明伟、走走停停  發布日期--永胜国际app:2015-09-14 22:21:50
Tag標簽_为啥人们啪啪后会感到悲伤:源碼  
  • SkipList稱之為跳表|_艾希tv,可實現Log(n)級別的插入_|_银泉酒家、刪除|-注册送300娱乐网址。和Map--下载手机qq2009、set等典型的數據結構相比--下载手机qq2010,其問題在於性能與插入數據的隨機性有關|-_永盛彩票线路,這和Q-Sort於Merge-Srot類似_-|汤唯在韩国视频。

    LevelDB做為單機數據庫存儲係統|_霍启文,正常操作下-|长明灯打一字,整體(隨機讀寫||-网络购物服务规范、順序讀寫)性能上明顯優於同類型的SQLite等數據庫||_卡发短信平台,這與內存數據采用的SkipList存儲方式密切相關||卓易彩票怎么不能买了。

    本文主要針對LevelDB中的SkipList的設計-|18彩app官方下载、實現的一些特點做備忘_|-电视剧军刺。

    1. SkipList層級間的均勻分布-宋茜微博,MaxHeight = 12||众发娱乐赌博, RandomHeight()

    MaxHeight為SkipList的關鍵參數-_永旺28彩票,與性能直接相關|九年级数学教学工作总结。

    程序中修改MaxHeight時|-_小小懒虫在异世,在數值變小時-||花千树 歌词,性能上有明顯下降|辣妈牛奶,但當數值增大時168开奖网,甚至增大到10000時-|众赢国际是传销吗,和默認的MaxHeight=12相比仍舊無明顯差異|258钱管家彩票官网,內存使用上也是如此|安全生产漫画。

    看如下代碼|2019年福彩3d北斗预测:

    	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_-008彩票论坛!。那麼_相信未来朗诵,當設定MaxHeight=12時_|118彩票手机版苹果,根節點為1時_-|易富彩票注册,約可均勻容納Key的數量為4^11=4194304(約為400W)_-3550幸运彩票网址。

    當單獨增大MaxHeight時|__psp维修,並不會使得SkipList的層級提升||露x连体裤。MaxHeight=12為經驗值_-金枝玉叶花卉,在百萬數據規模時___郫县薰衣草基地,尤為適用_-诺基亚7070拆机视频。

    2. 讀寫並發

    讀值本身並不會改變SkipList的結構|-薄樱鬼同人羁绊,因此多個讀之間不存在並發問題|--云顶娱乐官方下载16。

    而當讀--|038彩票app下载苹果、寫同時存在時_-|七k七k小游戏,SkipList通過AtomicPointer(原子指針)及結構調整上的小技巧達到“無鎖”並發--_2628彩票网页。

    SkipList<Key, Comparator>::Node

    首先-_-0567好彩官方版苹果,節點一旦被添加到SkipList中-_致青春 台词,其層級結構將不再發生變化-四川卫视参数,Node中的唯一成員_--兔瓣影院:port::AtomicPointer next_[1] 大小不會再發生改變||-女相 陆贞传奇txt。

    port::AtomicPointer next_[1];用於站位||-22选5好运3中奖规则,實際的數組大小和本節點的Height一致_-诺基亚 3110c,Node創建代碼如下-|198彩注册平台官网:

    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創建(這種用法並不常見)|_自由们7 59官方下载。

    再來看Node的四個成員函數|--365天天彩票快三:

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

    上麵兩組為線程安全訪問操作-|国青队名单,下麵兩組為非線程安全訪問操作__-铁锁连环。後兩組函數是作者追求極致性能時-|-4466k最近,降低了對封裝的要求_-|诺基亚ovi套件官方下载。

    template<typename Key, class Comparator> class SkipList 

    讀操作時的並發處理主要體現在-铂晶豪庭:使用Next成員函數執行原子的下一條查找動作_-陇南市人民政府网站。

    寫操作的並發處理稍複雜-3721助手,下麵為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_--璀璨人生里的歌曲。

    作者的注釋指明了並發讀時可能存在的兩種情況-3cp平台上彩下载,但完整描述應該如下-|-中国水产网:

    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. 由最下層向上插入可以保證當前層一旦插入後|-|mgcc恶意程序,其下層狀態已經更新_-郭美美死了。
    2. SetNext為原子操作-|永胜国际APP,保證讀線程在調用Next查找節點時不存在並發問題
    額外需注意的是|-盈彩在线是不是诈骗,32行中--|北京甘露寺,作者為了保證性能最優在x的SetNext及prev的Next均采用了非線程安全的方式-_妇女的定义。

    當然__云胡不喜 爱读屋,多個寫之間的並發SkipList時非線程安全的|-|圣伊依,在LevelDB的MemTable中采用了另外的技巧來處理寫並發問題--_盐都政府网。

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

    SkipList的迭代器-|政府最新打击云联惠,支持雙向遍曆_-|易彩娱乐,其實現本身並無特別之處-|联想a60手机游戏下载,隻不過是SkipList的一個封裝_||盈博娱乐国际,略_|-北京市市委书记。

        Insert:         1252072    Contains:       1296074

延伸閱讀-_永宁政府公众网:

About IT165 - 廣告服務 - 隱私聲明 - 版權申明 - 免責條款 - 網站地圖 - 網友投稿 - 聯係方式
本站內容來自於互聯網,僅供用於網絡技術學習,學習中請遵循相關法律法規
众发彩票快乐时时彩盈众彩票一品彩票秒速时时彩盛世彩票

免责声明: 本站资料及图片来源互联网文章,本网不承担任何由内容信息所引起的争议和法律责任。所有作品版权归原创作者所有,与本站立场无关,如用户分享不慎侵犯了您的权益,请联系我们告知,我们将做删除处理!