<small id='XCx0'></small> <noframes id='7msO4d'>

  • <tfoot id='gDMyJ'></tfoot>

      <legend id='4GVHD0i'><style id='cZ1xj'><dir id='gY8hO3Fc'><q id='f8ly'></q></dir></style></legend>
      <i id='GkqrLtzP'><tr id='ywlOmRKdk5'><dt id='MIDCjapSR'><q id='W8M3z'><span id='SPdNpig'><b id='zH3Jyu2'><form id='5HWLcu8'><ins id='W3IE7sF'></ins><ul id='7W8IyA'></ul><sub id='W5B8o'></sub></form><legend id='1gwLlF4'></legend><bdo id='5Shue96o'><pre id='oPYA5X'><center id='Q1b8JYC'></center></pre></bdo></b><th id='oZynrixwHs'></th></span></q></dt></tr></i><div id='r9gSTWs'><tfoot id='5WGso'></tfoot><dl id='Jx0FuOm'><fieldset id='3wFYgpB'></fieldset></dl></div>

          <bdo id='JYQDxLOTH2'></bdo><ul id='ImdB5NCqX'></ul>

          1. <li id='QrXV5njb8O'></li>
            登陆

            美团针对Redis Rehash机制的探究和实践

            admin 2019-05-24 449人围观 ,发现0个评论

            布景

            Squirrel(松鼠)是美团技能团队依据Redis Cluster打造的缓存体系。经过不断的迭代研制,现在已构成一整套主动化运维体系,包含一键运维集群、细粒度的监控、支撑主动扩缩容以及热门Key监控等完好的处理方案。一起服务端经过Docker进行布置,最大程度的进步运维的灵活性。分布式缓存Squirrel产品自2015年上线至今,已在美团内部广泛运用,存储容量超越60T,日均调用量也超越万亿次,逐渐成为美团现在最首要的缓存体系之一。

            跟着运用的量和场景不断深化,Squirrel团队也不断发现Redis的若干"坑"和缺乏,因而也在持续的改善Redis以支撑美团内部快速开展的事务需求。本文测验分享在运维进程中踩过的Redis Rehash机制的一些坑以及咱们的处理方案。

            事例

            Redis 满容状况下因为Rehash导致许多Key驱赶


            咱们先来看一张监控图(上图,咱们线上实在事例),Redis在满容有驱赶战略的状况下,Master/Slave 均有许多的Key驱赶筛选,导致Master/Slave 主从不一致。

            Root Cause 定位

            因为Slave内存区域比Master少一个repl-backlog buffer(线上一般装备为128M),正常状况下Master抵达满容后依据驱赶战略筛选Key并同步给Slave。所以Slave这种状况下不会因满容触发驱赶。

            依照以往经历,排查思路首要聚集在形成Slave内存猛增的问题上,包含客户端衔接、输入/输出缓冲区、事务数据存取拜访、网路颤动等导致Redis内存猛增的一切外部要素,经过Redis监控和事务链路监控均没有定位成功。

            所以,经过整理Redis源码,咱们测验将目光投向了Redis会占用内存开支的一个重要机制——Redis Rehash。

            Redis Rehash 内部完结

            在Redis中,键值对(Key-Value Pair)存储方法是由字典(Dict)保存的,而字典底层是经过哈希表来完结的。经过哈希表中的节点保存字典中的键值对。相似Java中的HashMap,将Key经过哈希函数映射到哈希表节点方位。

            接下来咱们一步步来剖析Redis Dict Reash的机制和进程。

            (1) Redis 哈希表结构体:

            /* hash表结构界说 */
            typedef struct dictht {
            dictEntry **table; // 哈希表数组
            unsigned long size; // 哈希表的巨细
            unsigned long sizemask; // 哈希表巨细掩码
            unsigned long used; // 哈希体现有节点的数量
            } dictht;

            实体化一下,美团针对Redis Rehash机制的探究和实践如下图所指一个巨细为4的空哈希表(Redis默许初始化值为4):

            (2) Redis 哈希桶

            Redis 哈希表中的table数组存放着哈希桶结构(dictEntry),里边便是Redis的键值对;相似Java完结的HashMap,Redis的dictEntry也是经过链表(next指针)方法来处理hash抵触:

            /* 哈希桶 */
            typedef struct dictEntry {
            void *key; // 键界说
            // 值界说
            union {
            void *val; // 自界说类型
            uint64_t u64; // 无符号整形
            int64_t s64; // 有符号整形
            double d; // 浮点型
            } v;
            struct dictEntry *next; //指向下一个哈希表节点
            } dictEntry;


            (3) 字典

            Redis Dict 中界说了两张哈希表,是为了后续字典的扩展作Rehash之用:

            /* 字典结构界说 */
            typedef struct dict {
            dictType *type; // 字典类型
            void *privdata; // 私有数据
            dictht ht[2]; // 哈希表[两个]
            long rehashidx; // 记载rehash 进展的标志,值为-1表明rehash未进行
            int iterators; // 当时正在迭代的迭代器数
            } dict;


            总结一下:

            • 在Cluster形式下,一个Redis实例对应一个RedisDB(db0);
            • 一个RedisDB对应一个Dict;
            • 一个Dict对应2个Dictht,正常状况只用到ht[0];ht[1] 在Rehash时运用。

            如上,咱们回忆了一下Redis KV存储的完结。(Redis内部还有其他结构体,因为跟Rehash不触及,不再赘述)

            咱们知道当HashMap中因为Hash抵触(负载因子)超越某个阈值时,出于链表功能的考虑,会进行Resize的操作。Redis也相同【Redis中经过dictExpand()完结】。咱们看一下Redis中的完结方法:

            /* 依据相关触发条件扩展字典 */
            static int _dictExpandIfNeeded(dict *d)
            {
            if (dictIsRehashing(d)) return DICT_OK; // 假如正在进行Rehash,则直接回来
            if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE); // 假如ht[0]字典为空,则创立并初始化ht[0]
            /* (ht[0].used/ht[0].size)>=1前提下,
            当满意dict_can_resize=1或ht[0].used/t[0].size>5时,便对字典进行扩展 */
            if (d->ht[0].used >= d->ht[0].size &&
            (dict_can_resize ||
            d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
            {
            return dictExpand(d, d->ht[0].used*2); // 扩展字典为本来的2倍
            }
            return DICT_OK;
            }
            ...
            /* 核算存储Key的bucket的方位 */
            static int _dictKeyIndex(dict *d, const void *key)
            {
            unsigned int h, idx, table;
            dictEntry *he;
            /* 查看是否需求扩展哈希表,缺乏则扩展 */
            if (_dictExpandIfNeeded(d) == DICT_ERR)
            return -1;
            /* 核算Key的哈希值 */
            h = dictHashKey(d, key);
            for (table = 0; table <= 1; table++) {
            idx = h & d->ht[table].sizemask; //核算Key的bucket方位
            /* 查看节点上是否存在新增的Key */
            he = d->ht[table].table[idx];
            /* 在节点链表查看 */
            while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
            return -1;
            he = he->next;
            }
            if (!dictIsRehashing(d)) break; // 扫完ht[0]后,假如哈希表不在rehashing,则无需再扫ht[1]
            }
            return idx;
            }
            ...
            /* 将Key刺进哈希表 */
            dictEntry *dictAddRaw(dict *d, void *key)
            {
            int index;
            dictEntry *entry;
            dictht *ht;
            if (dictIsRehashing(d)) _dictRehashStep(d); // 假如哈希表在rehashing,则履行单步rehash
            /* 调用_dictKeyIndex() 查看键是否存在,假如存在则回来NULL */
            if ((index = _dictKeyIndex(d, key)) == -1)
            return NULL;
            ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
            entry = zmalloc(sizeof(*entry)); // 为新增的节点分配内存
            entry->next = ht->table[index]; // 将节点刺进链表表头
            ht->table[index] = entry; // 更新节点和桶信息
            ht->used++; // 更新ht
            /* 设置新节点的键 */
            dictSetKey(d, entry, key);
            return entry;
            }
            ...
            /* 添加新键值对 */
            int dictAdd(dict *d, void *key, void *val)
            {
            dictEntry *entry = dictAddRaw(d,key); // 添加新键
            if (!entry) return DICT_ERR; // 假如键存在,则回来失利
            dictSetVal(d, entry, val); // 键不存在,则设置节点值
            return DICT_OK;
            }

            持续dictExpand的源码完结:

            int dictExpand(dict *d, unsigned long size) 
            {
            dictht n; // 新哈希表
            unsigned long realsize = _dictNextPower(size); // 核算扩展或缩放新哈希表的巨细(调用下面函数_dictNextPower())
            /* 假如正在rehash或许新哈希表的巨细小于现已运用,则回来error */
            if (dictIsRehashing(d) || d->ht[0].used > size)
            return DICT_ERR;
            /* 假如核算出哈希表size与现哈希表巨细相同,也回来error */
            if (realsize == d->ht[0].size) return DICT_ERR;
            /* 初始化新哈希表 */
            n.size = realsize;
            n.sizemask = realsize-1;
            n.table = zcalloc(realsize*sizeof(dictEntry*)); // 为table指向dictEntry 分配内存
            n.used = 0;
            /* 假如ht[0] 为空,则初始化ht[0]为当时键值对的哈希表 */
            if (d->ht[0].table == NULL) {
            d->ht[0] = n;
            return DICT_OK;
            }
            /* 假如ht[0]不为空,则初始化ht[1]为当时键值对的哈希表,并敞开渐进式rehash形式 */
            d->ht[1] = n;
            d->rehashidx = 0;
            return DICT_OK;
            }
            ...
            static unsigned long _dictNextPower(unsigned long size) {
            unsigned long i = DICT_HT_INITIAL_SIZE; // 哈希表的初始值:4
            if (size >= LONG_MAX) return LONG_MAX;
            /* 核算新哈希表的巨细:榜首个大于等于size的2的N 次方的数值 */
            while(1) {
            if (i >= size)
            return i;
            i *= 2;
            }
            }

            总结一下具体逻辑完结:

            可以承认当Redis Hash抵触抵达某个条件时就会触发dictExpand()函数来扩展HashTable。

            DICT_HT_INITIAL_SIZE初始化值为4,经过上述表达式,取当4*2^n >= ht[0].used*2的值作为字典扩展的size巨细。即为:ht[1].size 的值等于榜首个大于等于ht[0].used*2的2^n的数值。

            Redis经过dictCreate()创立词典,在初始化中,table指针为Null,所以两个哈希表ht[0].table和ht[1].table都未真实分配内存空间。只需在dictExpand()字典扩展时才给table分配指向dictEntry的内存。

            由上可知,当Redis触发Resize后,就会动态分配一块内存,终究由ht[1].table指向,动态分配的内存巨细为:realsize*sizeof(dictEntry*),table指向dictEntry*的一个指针,巨细为8bytes(64位OS),即ht[1].table需分配的内存巨细为:8*2*2^n (n大于等于2)。

            整理一下哈希表巨细和内存请求巨细的对应联系:

            复现验证

            咱们经过测验环境数据来验证一下,当Redis Rehash进程中,内存真实的占用状况。

            上述两幅图中,Redis Key个数打破Redis Resize的临界点,当Key总数安稳且Rehash完结后,Redis内存(Slave)从3586M降至为3522M:3586-3522=64M。即验证上述Redis在Resize至完结的中间状况,会坚持一段时间内存耗费,且占用内存的值为上文列表相应的内存空间。

            进一步调查一下Redis内部核算信息:

            /* Redis节点800万左右Key时分的Dict状况信息:只需ht[0]信息。*/
            "[Dictionary HT]
            Hash table 0 stats (main hash table):
            table size: 8388608
            number of elements: 8003582
            different slots: 5156314
            max chain length: 9
            avg chain length (counted): 1.55
            avg chain length (computed): 1.55
            Chain length distribution:
            0: 3232294 (38.53%)
            1: 3080243 (36.72%)
            2: 1471920 (17.55%)
            3: 466676 (5.56%)
            4: 112320 (1.34%)
            5: 21301 (0.25%)
            6: 3361 (0.04%)
            7: 427 (0.01%)
            8: 63 (0.00%)
            9: 3 (0.00%)
            "
            /* Redis节点840万左右Key时分的Dict状况信息正在Rehasing中,包含了ht[0]和ht[1]信息。*/
            "[Dictionary HT]
            [Dictionary HT]
            Hash table 0 stats (main hash table):
            table size: 8388608
            number of elements: 8019739
            different slots: 5067892
            max chain length: 9
            avg chain length (counted): 1.58
            avg chain length (computed): 1.58
            Chain length distribution:
            0: 3320716 (39.59%)
            1: 2948053 (35.14%)美团针对Redis Rehash机制的探究和实践
            2: 1475756 (17.59%)
            3: 491069 (5.85%)
            4: 123594 (1.47%)
            5: 24650 (0.29%)
            6: 4135 (0.05%)
            7: 553 (0.01%)
            8: 78 (0.00%)
            9: 4 (0.00%)
            Hash table 1 stats (rehashing target):
            table size: 16777216
            number of elements: 384321
            different slots: 305472
            max chain length: 6
            avg chain length (counted): 1.26
            avg chain length (computed): 1.26
            Chain length distribution:
            0: 16471744 (98.18%)
            1: 238752 (1.42%)
            2: 56041 (0.33%)
            3: 9378 (0.06%)
            4: 1167 (0.01%)
            5: 119 (0.00%)
            6: 15 (0.00%)
            "
            /* Redis节点840万左右Key时分的Dict状况信息(Rehash完结后);ht[0].size从8388608扩展到了16777216。*/
            "[Dictionary HT]
            Hash table 0 stats (main hash table):
            table size: 16777216
            number of elements: 8404060
            different slots: 6609691emotiona什么意思
            max chain length: 7
            avg chain length (counted): 1.27
            avg chain length (computed): 1.27
            Chain length distribution:
            0: 10167525 (60.60%)
            1: 5091002 (30.34%美团针对Redis Rehash机制的探究和实践)
            2: 1275938 (7.61%)
            3: 213024 (1.27%)
            4: 26812 (0.16%)
            5: 2653 (0.02%)
            6: 237 (0.00%)
            7: 25 (0.00%)
            "

            经过Redis Rehash内部机制的深化、Redis状况监控和Redis内部核算信息,咱们可以得出结论:

            当Redis 节点中的Key总量抵达临界点后,Redis就会触发Dict的扩展,进行Rehash。请求扩展后相应的内存空间巨细。

            如上,Redis在满容驱赶状况下,Redis Rehash是导致Redis Master和Slave许多触发驱赶筛选的根本原因。

            除了导致满容驱赶筛选,Redis Rehash还会引起其他一些问美团针对Redis Rehash机制的探究和实践题:

            • 在tablesize等级与现有Keys数量不在同一个区间内,主从切换后,因为Redis全量同步,从库tablesize降为与现有Key匹配值,导致内存歪斜;
            • Redis Cluster下的某个分片因为Key数量相对较多提早Resize,导致集群分片内存不均。
            • 等等…

            Redis Rehash机制优化

            那么针对在Redis满容驱赶状况下,怎么防止因Rehash而导致Redis颤动的这种问题。

            • 咱们在Redis Rehash源码完结的逻辑上,加上了一个判别条件,假如现有的剩下内存不行触发Rehash操作所需请求的内存巨细,即不进行Resize操作;
            • 经过提早运营进行躲避,比方容量预估时将Rehash占用的内存考虑在内,或许经过监控守时扩容。

            Redis Rehash机制除了会影响上述内存办理和运用外,也会影响Redis其他内部与之相相关的功能模块。下面咱们分享一下因为Rehash机制而踩到的第二个坑。

            Redis运用Scan整理Key因为Rehash导致整理数据不彻底

            Squirrel渠道供给给事务整理Key的API后台逻辑,是经过Scan来完结的。实践线上运转作用并不是每次都能彻底整理洁净。即经过Scan扫描整理相匹配的Key,较低频率会有遗失、Key未被悉数整理掉的现象。有了前几次的相关经历后,咱们直接从原理下手。

            Scan原理

            为了高效地匹配出数据库中一切契合给定形式的Key,Redis供给了Scan指令。该指令会在每次调用的时分回来契合规矩的部分Key以及一个游标值Cursor(初始值运用0),运用每次回来Cursor不断迭代,直到Cursor的回来值为0代表遍历结束。

            Redis官方界说Scan特色如下:

            1. 整个遍历从开端到结束期间, 一向存在于Redis数据集内的且契合匹配形式的一切Key都会被回来;
            2. 假如发作了rehash,同一个元素或许会被回来屡次,遍历进程中新增或许删去的Key或许会被回来,也或许不会。

            具体完结

            上述提及Redis的Keys是以Dict方法来存储的,正常只需一次遍历Dict中一切Hash桶就可以完好扫描出一切Key。可是在实践运用中,Redis Dict是有状况的,会跟着Key的增删不断改变。

            接下来依据Dict四种状况来剖析一下Scan的不同完结。

            Dict的四种状况场景:

            1. 字典tablesize坚持不变,没有扩缩容;
            2. 字典Resize,Dict扩展了(完结状况);
            3. 字典Resize,Dict缩小了(完结状况);
            4. 字典正在Rehashing(扩展或缩短)。

            (1) 字典tablesize坚持不变,在Redis Dict安稳的状况下,直接次序遍历即可。

            (2) 字典Resize,Dict扩展了,假如仍是依照次序遍历,就会导致扫描许多重复Key。比方字典tablesize从8变成了16,假定之前拜访的是3号桶,那么表扩展后则是持续拜访4~15号桶;可是,原先的0~3号桶中的数据在Dict长度变大后被搬迁到8~11号桶中,因而,遍历8~11号桶的时分会有许多的重复Key被回来。

            (3) 字典Resize,Dict缩小了,假如仍是依照次序遍历,就会导致许多的Key被遗失。比方字典tablesize从8变成了4,假定当时拜访的是3号桶,那么下一次则会直接回来遍历结束了;可是之前4~7号桶中的数据在缩容后搬迁带可0~3号桶中,因而这部分Key就无法扫描到。

            (4) 字典正在Rehashing,这种状况如(2)和(3)状况一下,要么许多重复扫描、要么遗失许多Key。

            那么在Dict非安稳状况,即发作Rehash的状况下,Scan要怎么保证原有的Key都能遍历出来,又尽少或许重复扫描呢?Redis Scan经过Hash桶掩码的高位次序拜访来处理。

            高位次序拜访即依照Dict sizemask(掩码),在有用位(上图中Dict sizemask为3)上从高位开端加一枚举;低位则依照有用位的低位逐渐加一拜访。

            低位序:0→1→2→3→4→5→6→7

            高位序:0→4→2→6→1→5→3→7

            Scan选用高位序拜访的原因,便是为了完结Redis Dict在Rehash时尽或许少重复扫描回来Key。

            举个比方,假如Dict的tablesize从8扩展到了16,整理一下Scan扫描方法:

            1. Dict(8) 从Cursor 0开端扫描;
            2. 预备扫描Cursor 6时发作Resize,扩展为之前的2倍,并完结Rehash;
            3. 客户端这时开端从Dict(16)的Cursor 6持续迭代;
            4. 这时依照 6→14→1→9→5→13→3→11→7→15 Scan完结。


            可以看出,高位序Scan在Dict Rehash时即可以防止重复遍历,又能完好回来原始的一切Key。同理,字典缩容时也相同,字典缩容可以看出是反向扩容。

            上述是Scan的理论基础,咱们看一下Redis源码怎么完结。

            (1) 非Rehashing 状况下的完结:

             if (!dictIsRehashing(d)) { // 判别是否正在rehashing,假如不在则只需ht[0]
            t0 = &(d->ht[0]); // ht[0]
            m0 = t0->sizemask; // 掩码
            /* Emit entries at cursor */
            de = t0->table[v & m0]; // 方针桶
            while (de) {
            fn(privdata, de);
            de = de->next; // 遍历桶中一切节点,并经过回调函数fn()回来
            }
            ...
            /* 反向二进制迭代算法具体完结逻辑——游标完结的精华 */
            /* Set unmasked bits so incrementing the reversed cursor
            * operates on the masked bits of the smaller table */
            v |= ~m0;
            /* Increment the reverse cursor */
            v = rev(v);
            v++;
            v = rev(v);
            return v;
            }

            源码中Redis将Cursor的核算经过Reverse Binary Iteration(反向二进制迭代算法)来完结上述的高位序扫描方法。

            (2) Rehashing 状况下的完结:

            ...
            else { // 不然阐明正在rehashing,就存在两个哈希表ht[0]、ht[1]
            t0 = &d->ht[0];
            t1 = &d->ht[1]; // 指向两个哈希表
            /* Make sure t0 is the smaller and t1 is the bigger table */
            if (t0->size > t1->size) { 保证t0小于t1
            t0 = &d->ht[1];
            t1 = &d->ht[0];
            }
            m0 = t0->sizemask;
            m1 = t1->sizemask; // 相对应的掩码
            /* Emit entries at cursor */
            /* 迭代(小表)t0桶中的一切节点 */
            de = t0->table[v & m0];
            while (de) {
            fn(privdata, de);
            de = de->next;
            }
            /* Iterate over indices in larger table that are the expansion
            * of the index pointed to by the cursor in the smaller table */
            /* */
            do {
            /* Emit entries at cursor */
            /* 迭代(大表)t1 中一切节点,循环迭代,会把小表没有掩盖的slot悉数扫描美团针对Redis Rehash机制的探究和实践一遍 */
            de = t1->table[v & m1];
            while (de) {
            fn(privdata, de);
            de = de->next;
            }
            /* Increment bits not covered by the smaller mask */
            v = (((v | m0) + 1) & ~m0) | (v & m0);
            /* Continue while bits covered by mask difference is non-zero */
            } while (v & (m0 ^ m1));
            }
            /* Set unmasked bits so incrementing the reversed cursor
            * operates on the masked bits of the smaller table */
            v |= ~m0;
            /* Increment the reverse cursor */
            v = rev(v);
            v++;
            v = rev(v);
            return v;

            如上Rehashing时,Redis 经过else分支完结该进程中对两张Hash表进行扫描拜访。

            整理一下逻辑流程:

            Redis在处理dictScan()时,上面细分的四个场景的完结分成了两个逻辑:

            1. 此刻不在Rehashing的状况:
            2. 这种状况,即Dict是停止的。针对这种状况下的上述三种场景,Redis选用上述的Reverse Binary Iteration(反向二进制迭代算法):
            3. Ⅰ. 首要对游标(Cursor)二进制位翻转;
            4. Ⅱ. 再对翻转后的值加1;
            5. Ⅲ. 最终再次对Ⅱ的成果进行翻转。

            经过穷举高位,顺次向低位推动的方法(即高位序拜访的完结)来保证一切元素都会被遍历到。

            这种算法现已尽或许削减重复元素的回来,可是实践完结和逻辑中仍是会有或许存在重复回来,比方在Dict缩容时,高位合并到低位桶中,低位桶中的元素就会被重复取出。

            1. 正在Rehashing的状况:
            2. Redis在Rehashing状况的时分,dictScan()完结经过一次性扫描现有的两种字典表,防止中间状况无法保护。
            3. 具体完结便是在遍历完小表Cursor方位后,将小表Cursor方位或许Rehash到的大表一切方位悉数遍历一遍,然后再回来遍历元素和下一个小表遍历方位。

            Root Cause 定位

            Rehashing状况时,游标迭代首要逻辑代码完结:

             /* Increment bits not covered by the smaller mask */
            v = (((v | m0) + 1) & ~m0) | (v & m0); //BUG

            Ⅰ. v低位加1向高位进位;

            Ⅱ. 去掉v最前面和最终面的部分,只保存v相较于m0的高位部分;

            Ⅲ. 保存v的低位,高位不断加1。即低位不变,高位不断加1,完结了小表到大表桶的相关。

            举个比方,假如Dict的tablesize从8扩展到了32,整理一下Scan扫描方法:

            1. Dict(8) 从Cursor 0开端扫描;
            2. 预备扫描Cursor 4时发作Resize,扩展为之前的4倍,Rehashing;
            3. 客户端先拜访Dict(8)中的4号桶,然后再到Dict(32)上拜访:4→20→12→28;
            4. 然后再到Dict(32)上拜访:4→20→12→28。

            这儿可以看到大表的相关桶的次序并非是依照之前所述的二进制高位序,实践上是依照低位序来遍历大表中高出小表的有用位。

            大表t1高位都是从低位加1核算得出的,扫描的次序却是从低位加1,向高位进位。Redis针对Rehashing时这种逻辑完结在扩容时是可以运转正常的,可是在缩容时高位序和低位序的遍历在巨细表上的混用在必定条件下会出现问题。

            再次示例,Dict的tablesize从32缩容到8:

            1. Dict(32) 从Cursor 0开端扫描;
            2. 预备扫描Cursor 20时发作Resize,缩容至本来的四分之一即tablesize为8,Rehashing;
            3. 客户端建议Cursor 20,首要拜访Dict(8)中的4号桶;
            4. 再到Dict(32)上拜访:20→28;
            5. 最终回来Cursor = 2。

            可以看出大表中的12号桶没有被拜访到,即遍历大表时,依照低位序拜访会遗失对某些桶的拜访。

            上述这种状况发作需求具有必定的条件:

            1. 在Dict缩容Rehash时Scan;
            2. Dict缩容至至少原Dict tablesize的四分之一,只需在这种状况下,大表相对小表的有用位才会高出二位以上,然后触发越过某个桶的状况;
            3. 假如在Rehash开端前回来的Cursor是在小表能表明的范围内(即不超越7),那么在进行高位有用位的加一操作时,必定都是从0开端核算,每次加一也必定可以拜访的全一切的相关桶;假如在Rehash开端前回来的cursor不在小表能表明的范围内(比方20),那么在进行高位有用位加一操作的时分,就有或许越过 ,或许重复拜访某些桶的状况。

            可见,只需满意上述三种状况才会发作Scan遍历进程中漏掉了一些Key的状况。在履行整理Key的时分,假如整理的Key数量很大,导致了Redis内部的Hash表缩容至少原Dict tablesize的四分之一,就或许存在一些Key被漏掉的危险。

            Scan源码优化

            修正逻辑便是悉数都从高位开端添加进行遍历,即巨细表都运用高位序拜访,修正源码如下:

            unsigned long dictScan(dict *d,
            unsigned long v,
            dictScanFunction *fn,
            dictScanBucketFunction* bucketfn,
            void *privdata)
            {
            dictht *t0, *t1;
            const dictEntry *de, *next;
            unsigned long m0, m1;
            if (dictSize(d) == 0) return 0;
            if (!dictIsRehashing(d)) {
            t0 = &(d->ht[0]);
            m0 = t0->sizemask;
            /* Emit entries at cursor */
            if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
            de = t0->table[v & m0];
            while (de) {
            next = de->next;
            fn(privdata, de);
            de = next;
            }
            /* Set unmasked bits so incrementing the reversed cursor
            * operates on the masked bits */
            v |= ~m0;
            /* Increment the reverse cursor */
            v = rev(v);
            v++;
            v = rev(v);
            } else {
            t0 = &d->ht[0];
            t1 = &d->ht[1];
            /* Make sure t0 is the smaller and t1 is the bigger table */
            if (t0->size > t1->size) {
            t0 = &d->ht[1];
            t1 = &d->ht[0];
            }
            m0 = t0->sizemask;
            m1 = t1->sizemask;
            /* Emit entries at cursor */
            if (bucketfn) bucketfn(privdata, &t0->table[v & m0]);
            de = t0->table[v & m0];
            while (de) {
            next = de->next;
            fn(privdata, de);
            de = next;
            }
            /* Iterate over indices in larger table that are the expansion
            * of the index pointed to by the cursor in the smaller table */
            do {
            /* Emit entries at cursor */
            if (bucketfn) bucketfn(privdata, &t1->table[v & m1]);
            de = t1->table[v & m1];
            while (de) {
            next = de->next;
            fn(privdata, de);
            de = next;
            }
            /* Increment the reverse cursor not covered by the smaller mask.*/
            v |= ~m1;
            v = rev(v);
            v++;
            v = rev(v);
            /* Continue while bits covered by mask difference is non-zero */
            } while (v & (m0 ^ m1));
            }
            return v;
            }

            至此,依据Redis Rehash以及Scan完结中触及Rehash的两个机制现已根本了解和优化完结。

            总结

            本文首要论述了因Redis的Rehash机制踩到的两个坑,从现象到原理进行了具体的介绍。这儿简略总结一下,榜首个事例会形成线上集群进行许多筛选,并且发作主从不一致的状况,在事务层面也会发作许多超时,影响事务可用性,问题严峻,十分值得我们重视;第二个事例会形成数据整理无法彻底整理,可是可以再利用Scan整理一遍也可以整理结束。

            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP