LevelDB源码之一SkipList - 安全编程 -- 电脑知识与技术互动沟通平台.docx
LevelDB源码之一SkipList-安全编程-次元立方网-电脑知识与技术互动沟通平台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相比仍然无明显差异，内存使用上也是如此。看如下代码：templatetypenameKey,classComparatorintSkipListKey,Comparator:RandomHeight()/Increaseheightwithprobability1inkBranchingstaticconstunsignedintkBranching=4;intheight=1;while(heightkMaxHeight(rnd_.Next()%kBranching)=0)height+;assert(heightassert(height=kMaxHeight);returnheight;其中的关键在于粗体的kBranching及(rnd_.Next()%kBranching。这使得上层节点的数量约为下层的1/4。那么，当设定MaxHeight=12时，根节点为1时，约可均匀包容Key的数量为411=4194304(约为400W)。当单独增大MaxHeight时，并不会使得SkipList的层级提升。MaxHeight=12为经历值，在百万数据规模时，尤为适用。2.读写并发读值本身并不会改变SkipList的构造，因而多个读之间不存在并发问题。而当读、写同时存在时，SkipList通过AtomicPointer(原子指针)及构造调整上的小技巧到达无锁并发。SkipListKey,Comparator:Node首先，节点一旦被添加到SkipList中，其层级构造将不再发生变化，Node中的唯一成员：port:AtomicPointernext_1大小不会再发生改变。port:AtomicPointernext_1;用于站位，实际的数组大小和本节点的Height一致，Node创立代码如下：1templatetypenameKey,classComparator2typenameSkipListKey,Comparator:Node*3SkipListKey,Comparator:NewNode(constKeykey,intheight)4char*mem=arena_-AllocateAligned(5sizeof(Node)+sizeof(port:AtomicPointer)*(height-1);6returnnew(mem)Node(key);7其中，Line4根据height创立真正大小的Node，Line6显示调用构造函数，完成Node创立(这种用法并不常见)。再来看Node的四个成员函数：1/Accessors/mutatorsforlinks.Wrappedinmethodssowecan2/addtheappropriatebarriersasnecessary.3Node*Next(intn);4voidSetNext(intn,Node*x);6/No-barriervariantsthatcanbesafelyusedinafewlocations.7Node*NoBarrier_Next(intn);8voidNoBarrier_SetNext(intn,Node*x);上面两组为线程安全访问操作，下面两组为非线程安全访问操作。后两组函数是作者追求极致性能时，降低了对封装的要求。templatetypenameKey,classComparatorclassSkipList读操作时的并发处理主要体如今：使用Next成员函数执行原子的下一条查找动作。写操作的并发处理稍复杂，下面为Insert代码：1templatetypenameKey,classComparator2voidSkipListKey,Comparator:Insert(constKeykey)3/TODO(opt):Wecanuseabarrier-freevariantofFindGreaterOrEqual()4/heresinceInsert()isexternallysynchronized.5Node*prevkMaxHeight;6Node*x=FindGreaterOrEqual(key,prev);8/Ourdatastructuredoesnotallowduplicateinsertion9assert(x=NULL|!Equal(key,x-key);11intheight=RandomHeight();12if(heightGetMaxHeight()13for(inti=GetMaxHeight();iheight;i+)14previ=head_;16/fprintf(stderr,"Changeheightfrom%dto%dn",max_height_,height);18/Itisoktomutatemax_height_withoutanysynchronization19/withconcurrentreaders.Aconcurrentreaderthatobserves20/thenewvalueofmax_height_willseeeithertheoldvalueof21/newlevelpointersfromhead_(NULL),oranewvaluesetin22/theloopbelow.Intheformercasethereaderwill23/immediatelydroptothenextlevelsinceNULLsortsafterall24/keys.Inthelattercasethereaderwillusethenewnode.25max_height_.NoBarrier_Store(reinterpret_castvoid*(height);28x=NewNode(key,height);29for(inti=0;iheight;i+)30/NoBarrier_SetNext()sufficessincewewilladdabarrierwhen31/wepublishapointerto"x"inprevi.32x-NoBarrier_SetNext(i,previ-NoBarrier_Next(i);/为性能及并发考虑的深度优化，这里的两个NoBarrier33previ-SetNext(i,x);3515行之前用于查找插入的位置，25行执行了第一个状态变更：设置当前的max_height_。作者的注释指明了并发读时可能存在的两种情况，但完好描绘应该如下：1.读到旧的max_height_，而后写线程更新了max_height_并正在进行或完成节点插入2.读到新的max_height_，而写线程正在进行或完成节点插入对于上述两种(其实是多种，这里为细分)情况，作者讲明并不存在并发问题，为何呢？关键在于28-34行插入方式：28x=NewNode(key,height);29for(inti=0;iheight;i+)30/NoBarrier_SetNext()sufficessincewewilladdabarrierwhen31/wepublishapointerto"x"inprevi.32x-NoBarrier_SetNext(i,previ-NoBarrier_Next(i);/为性能及并发考虑的深度优化，这里的两个NoBarrier33previ-SetNext(i,x);34关键在哪里？两点：29行的for循环顺序及33行的SetNext.1.由最下层向上插入能够保证当前层一旦插入后，其下层状态已经更新。2.SetNext为原子操作，保证读线程在调用Next查找节点时不存在并发问题额外需注意的是，32行中，作者为了保证性能最优在x的SetNext及prev的Next均采用了非线程安全的方式。当然，多个写之间的并发SkipList时非线程安全的，在LevelDB的MemTable中采用了另外的技巧来处理写并发问题。templatetypenameKey,classComparatorclassSkipListKey,Comparator:IteratorSkipList的迭代器，支持双向遍历，其实现本身并无十分之处，只不过是SkipList的一个封装，略。Insert:1252072Contains:1296074
