荣耀彩票代理

  • 热门专题

LevelDB源码之一SkipList

作者:音符、时间、走走停停  发布日期:2015-09-14 22:21:50
  • 荣耀彩票代理SkipListCHENGZHIWEITIAOBIAO,KESHIXIANLog(n)JIBIEDECHARU、SHANCHU。HEMap、setDENGDIANXINGDESHUJUJIEGOUXIANGBI,QIWENTIZAIYUXINGNENGYUCHARUSHUJUDESUIJIXINGYOUGUAN,ZHEIHEQ-SortYUMerge-SrotLEISI。

    LevelDBZUOWEIDANJISHUJUKUCUNCHUXITONG,ZHENGCHANGCAOZUOXIA,ZHENGTI(SUIJIDUXIE、SHUNXUDUXIE)XINGNENGSHANGMINGXIANYOUYUTONGLEIXINGDESQLiteDENGSHUJUKU,ZHEIYUNEICUNSHUJUCAIYONGDESkipListCUNCHUFANGSHIMIQIEXIANGGUAN。

    BENWENZHUYAOZHENDUILevelDBZHONGDESkipListDESHEJI、SHIXIANDEYIXIETEDIANZUOBEIWANG。

    1. SkipListCENGJIJIANDEJUNYUNFENBU,MaxHeight = 12, RandomHeight()

    荣耀彩票代理MaxHeightWEISkipListDEGUANJIANCANSHU,YUXINGNENGZHIJIEXIANGGUAN。

    CHENGXUZHONGXIUGAIMaxHeightSHI,ZAISHUZHIBIANXIAOSHI,XINGNENGSHANGYOUMINGXIANXIAJIANG,DANDANGSHUZHIZENGDASHI,SHENZHIZENGDADAO10000SHI,HEMORENDEMaxHeight=12XIANGBIRENGJIUWUMINGXIANCHAYI,NEICUNSHIYONGSHANGYESHIRUCI。

    KANRUXIADAIMA:

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

    DANGDANDUZENGDAMaxHeightSHI,BINGBUHUISHIDESkipListDECENGJITISHENG。MaxHeight=12WEIJINGYANZHI,ZAIBAIWANSHUJUGUIMOSHI,YOUWEISHIYONG。

    2. DUXIEBINGFA

    荣耀彩票代理DUZHIBENSHENBINGBUHUIGAIBIANSkipListDEJIEGOU,YINCIDUOGEDUZHIJIANBUCUNZAIBINGFAWENTI。

    荣耀彩票代理ERDANGDU、XIETONGSHICUNZAISHI,SkipListTONGGUOAtomicPointer(YUANZIZHIZHEN)JIJIEGOUDIAOZHENGSHANGDEXIAOJIQIAODADAO“WUSUO”BINGFA。

    SkipList<Key, Comparator>::Node

    荣耀彩票代理SHOUXIAN,JIEDIANYIDANBEITIANJIADAOSkipListZHONG,QICENGJIJIEGOUJIANGBUZAIFASHENGBIANHUA,NodeZHONGDEWEIYICHENGYUAN:port::AtomicPointer next_[1] DAXIAOBUHUIZAIFASHENGGAIBIAN。

    port::AtomicPointer next_[1];YONGYUZHANWEI,SHIJIDESHUZUDAXIAOHEBENJIEDIANDEHeightYIZHI,NodeCHUANGJIANDAIMARUXIA:

    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     }

    QIZHONG,Line4GENJUheightCHUANGJIANZHENZHENGDAXIAODENode,Line6XIANSHIDIAOYONGGOUZAOHANSHU,WANCHENGNodeCHUANGJIAN(ZHEIZHONGYONGFABINGBUCHANGJIAN)。

    荣耀彩票代理ZAILAIKANNodeDESIGECHENGYUANHANSHU:

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

    荣耀彩票代理SHANGMIANLIANGZUWEIXIANCHENGANQUANFANGWENCAOZUO,XIAMIANLIANGZUWEIFEIXIANCHENGANQUANFANGWENCAOZUO。HOULIANGZUHANSHUSHIZUOZHEZHUIQIUJIZHIXINGNENGSHI,JIANGDILEDUIFENGZHUANGDEYAOQIU。

    template<typename Key, class Comparator> class SkipList 

    DUCAOZUOSHIDEBINGFACHULIZHUYAOTIXIANZAI:SHIYONGNextCHENGYUANHANSHUZHIXINGYUANZIDEXIAYITIAOCHAZHAODONGZUO。

    荣耀彩票代理XIECAOZUODEBINGFACHULISHAOFUZA,XIAMIANWEIInsertDAIMA:

     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     }

    荣耀彩票代理15XINGZHIQIANYONGYUCHAZHAOCHARUDEWEIZHI,25XINGZHIXINGLEDIYIGEZHUANGTAIBIANGENG:SHEZHIDANGQIANDEmax_height_。

    ZUOZHEDEZHUSHIZHIMINGLEBINGFADUSHIKENENGCUNZAIDELIANGZHONGQINGKUANG,DANWANZHENGMIAOSHUYINGGAIRUXIA:

    荣耀彩票代理1. DUDAOJIUDEmax_height_,ERHOUXIEXIANCHENGGENGXINLEmax_height_BINGZHENGZAIJINXINGHUOWANCHENGJIEDIANCHARU

    2. DUDAOXINDEmax_height_,ERXIEXIANCHENGZHENGZAIJINXINGHUOWANCHENGJIEDIANCHARU

    DUIYUSHANGSHULIANGZHONG(QISHISHIDUOZHONG,ZHEILIWEIXIFEN)QINGKUANG,ZUOZHESHUOMINGBINGBUCUNZAIBINGFAWENTI,WEIHENI?

    GUANJIANZAIYU28-34XINGCHARUFANGSHI:

    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 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规