Redis源码分析之字典dict

　　一、dict的使用场景
　　redis数据结构set，zset，hash，string类型的会用到dict。zset，hash类型在数据量少的时候会在ziplist，数据量大时，zset使用dictskiplist的数据结构，dict来存储value和score的映射关系。set在集合元素全部为int这种特殊情况下会使用intset，通过二叉查找来查找数据。
　　其他场景例如集群模式中用来存储ip：port与clusterNode的映射关系。二、dict的数据结构
　　核心数据结构定义如下有：
　　2。1dictEntrytypedefstructdictEntry｛voidkey；union｛voidval；uint64tu64；int64ts64；doubled；｝v；structdictEntrynext；｝dictEntry；
　　2。2dicthttypedefstructdictht｛dictEntrytable；tablesizeunsignedlongsize；用于将哈希值映射到table的位置索引size1，hash（key）sizemask来计算落到table的那个bucket上unsignedlongsizemask；dict中数据个数，usedsize的比值就是装载因子｝dictht；
　　2。3dicttypedefstructdict｛dictTypetype；voidprivdata；dicththt〔2〕；表示rehash的步骤，rehashidx1当前没有进行rehashlongrehashidx；numberofiteratorscurrentlyrunningunsignedlongiterators；｝dict；
　　2。4dictTypetypedefstructdictType｛uint64t（hashFunction）（constvoidkey）；void（keyDup）（voidprivdata，constvoidkey）；void（valDup）（voidprivdata，constvoidobj）；int（keyCompare）（voidprivdata，constvoidkey1，constvoidkey2）；void（keyDestructor）（voidprivdata，voidkey）；void（valDestructor）（voidprivdata，voidobj）；｝dictType；
　　层属关系代码看着不太直观，我们换成图：
　　redisdict核心数据结构模型三、dict的核心API
　　dict在需要扩展内存时避免一次性对所有key进行rehash，而是将rehash操作分散到对于dict的各个增删改查的操作中去。这种方法能做到每次只对一小部分key进行重哈希，而每次重哈希之间不影响dict的操作。这是为了避免rehash期间单个请求的响应时间剧烈增加。
　　判断是否进行rehashstaticintdictExpandIfNeeded（dictd）｛判定是否当前处于rehash的状态。if（dictIsRehashing（d））returnDICTOK；初始设置，tablesize4if（dht〔0〕。size0）returndictExpand（d，DICTHTINITIALSIZE）；Ifwereachedthe1：1ratio，andweareallowedtoresizethehashtable（globalsetting）orweshouldavoiditbuttheratiobetweenelementsbucketsisoverthesafethreshold，weresizedoublingthenumberofbuckets。if（dht〔0〕。useddht〔0〕。size（dictcanresize数据量超过tablesize的5倍dht〔0〕。useddht〔0〕。sizedictforceresizeratio））｛根据当前dict元素数量的2倍进行扩展returndictExpand（d，dht〔0〕。used2）；｝returnDICTOK；｝
　　dict扩展逻辑intdictExpand（dictd，unsignedlongsize）｛thesizeisinvalidifitissmallerthanthenumberofelementsalreadyinsidethehashtableif（dictIsRehashing（d）dht〔0〕。usedsize）returnDICTERR；dicthtn；thenewhashtableunsignedlongrealsizedictNextPower（size）；Rehashingtothesametablesizeisnotuseful。if（realsizedht〔0〕。size）returnDICTERR；根据新的size重新分配一个hashtablen。sizerealsize；n。sizemaskrealsize1；n。tablezcalloc（realsizesizeof（dictEntry））；n。used0；Isthisthefirstinitialization？Ifsoitsnotreallyarehashingwejustsetthefirsthashtablesothatitcanacceptkeys。if（dht〔0〕。tableNULL）｛dht〔0〕n；returnDICTOK；｝重新分配的hashtable置于ht〔1〕dht〔1〕n；开始渐进rehash的标记drehashidx0；returnDICTOK；｝如果2nused2返回2n，hashtable的size一定是2nstaticunsignedlongdictNextPower（unsignedlongsize）｛unsignedlongiDICTHTINITIALSIZE；if（sizeLONGMAX）returnLONGMAX1LU；while（1）｛if（isize）returni；i2；｝｝
　　开启渐进式rehash
　　什么时候开启渐进式rehash，在每次从hashtable中定位key的时候，代码如下staticlongdictKeyIndex（dictd，constvoidkey，uint64thash，dictEntryexisting）｛unsignedlongidx，table；dictEntryhe；if（existing）existingNULL；判断是否需要扩展if（dictExpandIfNeeded（d）DICTERR）return1；拉链法遍历hashtable，遍历两个hashtableht〔0〕，ht〔1〕，如果当前没有在rehash，则只遍历ht〔0〕for（table0；table1；table）｛计算数据所在bucket位置，找到链表第一个entryidxhashdht〔table〕。sizemask；Searchifthisslotdoesnotalreadycontainthegivenkeyhedht〔table〕。table〔idx〕；遍历链表，比较key值while（he）｛if（keyhekeydictCompareKeys（d，key，hekey））｛if（existing）existinghe；return1；｝hehenext；｝if（！dictIsRehashing（d））break；｝returnidx；｝
　　分步渐进rehash
　　什么时候进行分步渐进rehash，在每一个add，get操作中：dictEntrydictAddRaw（dictd，voidkey，dictEntryexisting）｛longindex；dictEntryentry；dicththt；进行分步rehashif（dictIsRehashing（d））dictRehashStep（d）；Gettheindexofthenewelement，or1iftheelementalreadyexists。if（（indexdictKeyIndex（d，key，dictHashKey（d，key），existing））1）returnNULL；Allocatethememoryandstorethenewentry。Inserttheelementintop，withtheassumptionthatinadatabasesystemitismorelikelythatrecentlyaddedentriesareaccessedmorefrequently。rehash时，数据存入ht〔1〕htdictIsRehashing（d）？dht〔1〕：dht〔0〕；entryzmalloc（sizeof（entry））；entrynexthttable〔index〕；httable〔index〕entry；htused；设置key，返回entrydictSetKey（d，entry，key）；returnentry；｝
　　分步rehash过程staticvoiddictRehashStep（dictd）｛if（diterators0）dictRehash（d，1）；｝intdictRehash（dictd，intn）｛intemptyvisitsn10；Maxnumberofemptybucketstovisit。if（！dictIsRehashing（d））return0；while（ndht〔0〕。used！0）｛dictEntryde，nextde；Notethatrehashidxcantoverflowaswearesuretherearemoreelementsbecauseht〔0〕。used！0assert（dht〔0〕。size（unsignedlong）drehashidx）；如果table中存在bucket为空时，检查10个bucket后都为空则返回，等下一次再处理while（dht〔0〕。table〔drehashidx〕NULL）｛drehashidx；if（emptyvisits0）return1；｝dedht〔0〕。table〔drehashidx〕；一次处理table中的一个bucketMoveallthekeysinthisbucketfromtheoldtothenewhashHTwhile（de）｛uint64th；nextdedenext；GettheindexinthenewhashtablehdictHashKey（d，dekey）dht〔1〕。sizemask；denextdht〔1〕。table〔h〕；dht〔1〕。table〔h〕de；dht〔0〕。used；dht〔1〕。used；denextde；｝dht〔0〕。table〔drehashidx〕NULL；drehashidx；｝Checkifwealreadyrehashedthewholetable。。。if（dht〔0〕。used0）｛zfree（dht〔0〕。table）；dht〔0〕dht〔1〕；dictReset（dht〔1〕）；drehashidx1；return0；｝Moretorehash。。。return1；｝
　　redisdict的缩小的触发存在两种情况hash，set，zset这三类数据使用的dict，在删除元素的时候会尝试rehash另一种是定时尝试进行rehash
　　尝试触发的代码如下当usedsize10时进行开启缩容rehash。inthtNeedsResize（dictdict）｛longlongsize，used；sizedictSlots（dict）；useddictSize（dict）；return（sizeDICTHTINITIALSIZE（used100sizeHASHTABLEMINFILL））；｝IfthepercentageofusedslotsintheHTreachesHASHTABLEMINFILLweresizethehashtabletosavememoryvoidtryResizeHashTables（intdbid）｛if（htNeedsResize（server。db〔dbid〕。dict））dictResize（server。db〔dbid〕。dict）；if（htNeedsResize（server。db〔dbid〕。expires））dictResize（server。db〔dbid〕。expires）；｝
　　由于rehash时需要分配内存，此部分内存是从redismaxmemory中的一部分，因此当bucket比较大时，rehash生成ht〔1〕时会使用大量内存。如果ht〔1〕占用的内存原来的内存超过maxmeory，则会发生key逐出。由于sizeof（dictEntry）8byte，因此当ht〔0〕size为4时，ht〔1〕扩展2倍，ht〔1〕占用内存为84264byte，当size2n时，ht〔1〕占用的内存为822n。
　　三、dictscan
　　redis中dict是有状态的，dict存在四种状态：
　　1正常状态
　　2正在rehash状态
　　3rehash扩容完成状态
　　4rehash缩容完成状态
　　由于redis中dict是有状态的，只有在正常状态下可以完整的扫描字典中的所有的key。当dict在进行扩容和缩容时可能会存在扫描key的遗漏或者重复扫描。由于redis的dict中存在两个hashtable，分别为ht〔0〕，ht〔1〕。rehash的过程是将ht〔0〕的key重新hash到ht〔1〕。这时redis的所有key其实存在于两个hashtable中。redis针对四种情况的方案如下：Dicttablesize保持不变，稳定的状态下，直接顺序遍历即可DictResize，dict扩大了，如果还是按照顺序遍历，就会导致扫描大量重复Key。比如tablesize从8变成了16，假设之前访问的是3号桶，那么表扩展后则是继续访问415号桶；但是，原先的03号桶中的数据在Dict长度变大后被迁移到811号桶中，因此，遍历811号桶的时候会有大量的重复Key被返回。DictResize，dict缩小了，如果还是按照顺序遍历，就会导致大量的Key被遗漏。比如tablesize从8变成了4，假设当前访问的是3号桶，那么下一次则会直接返回遍历结束了；但是之前47号桶中的数据在缩容后迁移带可03号桶中，因此这部分Key就无法扫描到。字典正在rehash，这种情况如（2）和（3）情况一下，要么大量重复扫描、要么遗漏很多Key。
　　在redis正在rehash时，采用hash桶掩码的高位序访问来解决。如下图
　　hash桶掩码的高位序访问
　　高位序访问即按照dictsizemask（掩码），在有效位（上图中dictsizemask为00000111）上从高位开始加一枚举（右边图的）；低位则按照有效位的低位逐步加一枚举（左边的图）。
　　高位序遍历路径：04261537
　　低位序遍历路径：01234567
　　redis采用掩码高位序访问的原因是在rehash时尽量少的重复扫描key。为什么从高位掩码访问会减少重复扫描。由于rehash最终计算bucket位置时是取模操作（vsizemask），举个例子：
　　针对v00101011，原来sizemask为00000111，取模000001110010101100000011
　　当sizemask为00001111，取模000011110010101100001011
　　可以看出取模后的两个值存在相同的后缀011。sizemask变大后，生成的结果只是高位发生变化。原来落到bucket〔00000011〕的key，tablesize从816时，sizemask从0000011100001111时会落到〔00000011〕和〔00001011〕中，高位变化，低位不变，此时再看一遍从高位序访问的图
　　看一个redis进行scan操作的例子，如下图。
　　redis从左边hashtablebucket0开始遍历，到遍历bucket6时发生了rehash。bucket长度为8扩展到16，redis的scan路径就会按照61419513311715来完成，这里存在一个隐藏逻辑，一定是先遍历小hashtable，再变了大的hashtable。
　　hashtablebucket
　　从图上可以看出高位序scan在dictrehash时即可以避免重复遍历，又能完整返回原始的所有Key。同理，字典缩容时也一样，字典缩容可以看出是反向扩容。
　　来看一下redisscan源码unsignedlongdictScan（dictd，unsignedlongv，dictScanFunctionfn，dictScanBucketFunctionbucketfn，voidprivdata）｛dicthtt0，t1；constdictEntryde，next；unsignedlongm0，m1；if（dictSize（d）0）return0；没有进行rehash的情况if（！dictIsRehashing（d））｛t0（dht〔0〕）；m0t0sizemask；Emitentriesatcursorif（bucketfn）bucketfn（privdata，t0table〔vm0〕）；det0table〔vm0〕；while（de）｛nextdenext；fn（privdata，de）；denext；｝高位序遍历计算出下一个cursorvm0；Incrementthereversecursorvrev（v）；v；vrev（v）；｝else｛进行rehash的情况t0dht〔0〕；t1dht〔1〕；确保t0为小hashtable，t1为大的hashtableif（t0sizet1size）｛t0dht〔1〕；t1dht〔0〕；｝m0t0sizemask；m1t1sizemask；先根据cursor遍历小的hashtableif（bucketfn）bucketfn（privdata，t0table〔vm0〕）；det0table〔vm0〕；while（de）｛nextdenext；fn（privdata，de）；denext；｝再变了大的hashtable，大的hashtable会遍历多个bucketdo｛Emitentriesatcursorif（bucketfn）bucketfn（privdata，t1table〔vm1〕）；det1table〔vm1〕；while（de）｛nextdenext；fn（privdata，de）；denext；｝反向二进制迭代算法来计算出下一个cursorvm1；vrev（v）；v；vrev（v）；Continuewhilebitscoveredbymaskdifferenceisnonzero｝while（v（m0m1））；｝returnv；｝反向二进制迭代算法1。对游标进行二进制翻转（原来的高位变成低位）2。低位1（对原来的高位进行1，进位等操作）3。再进行一次二进制翻转（恢复原来的高位，此时完成高位1迭代）
　　作者介绍：互联网十年交易支付搜索等架构和研发经验，擅长架构设计百亿级流量系统和高并发性能调优，目前专注做卫星通信卫星遥感的研发工作，努力拥抱商业航天的星辰大海。公众号：无量云颠
　　欢迎一起交流技术！