摘要

在平时线上 Redis 维护工作中，有时候需要从 Redis 实例成千上万的 key 中找出特定前缀的 key 列表来手动处理数据，可能是修改它的值，也可能是删除 key。这里就有一个问题，如何从海量的 key 中找出满足特定前缀的 key 列表来？Redis 提供了一个简单暴力的指令 keys 用来列出所有满足特定正则字符串规则的 key。这个指令使用非常简单，提供一个简单的正则字符串即可，但是有很明显的两个缺点。

• 没有 offset、limit 参数，一次性吐出所有满足条件的 key，万一实例中有几百 w 个 key 满足条件，当你看到满屏的字符串刷的没有尽头时，你就知道难受了。
• keys 算法是遍历算法，复杂度是 O(n)，如果实例中有千万级以上的 key，这个指令就会导致 Redis 服务卡顿，所有读写 Redis 的其它的指令都会被延后甚至会超时报错，因为 Redis 是单线程程序，顺序执行所有指令，其它指令必须等到当前的 keys 指令执行完了才可以继续。

一、Redis的scan原理与实战

Redis 为了解决这个问题，它在 2.8 版本中加入了大海捞针的指令——scan。scan 相比 keys 具备有以下特点:

• 复杂度虽然也是 O(n)，但是它是通过游标分步进行的，不会阻塞线程;
• 提供 limit 参数，可以控制每次返回结果的最大条数，limit 只是一个 hint，返回的结果可多可少;
• 同 keys 一样，它也提供模式匹配功能;
• 服务器不需要为游标保存状态，游标的唯一状态就是 scan 返回给客户端的游标整数;
• 返回的结果可能会有重复，需要客户端去重复，这点非常重要;
• 遍历的过程中如果有数据修改，改动后的数据能不能遍历到是不确定的;
• 单次返回的结果是空的并不意味着遍历结束，而要看返回的游标值是否为零;

1.1 Scan的原理

在 Redis 中所有的 key都存储在一个很大的字典中，这个字典的结构和 Java 中的 HashMap 一样，是一维数组+二维链表结构，第一维数组的大小总是 2^n(n>=0)，扩容一次数组大小空间加倍，也就是 n++。

scan 指令返回的游标就是第一维数组的位置索引，我们将这个位置索引称为槽 (slot)。如果不考虑字典的扩容缩容，直接按数组下标挨个遍历就行了。limit 参数就表示需要遍历的槽位数，之所以返回的结果可能多可能少，是因为不是所有的槽位上都会挂接链表，有些槽位可能是空的，还有些槽位上挂接的链表上的元素可能会有多个。每一次遍历都会将 limit 数量的槽位上挂接的所有链表元素进行模式匹配过滤后，一次性返回给客户端。

scan 的遍历顺序非常特别。它不是从第一维数组的第 0 位一直遍历到末尾，而是采用了高位进位加法来遍历。之所以使用这样特殊的方式进行遍历，是考虑到字典的扩容和缩容时避免槽位的遍历重复和遗漏。普通加法和高位进位加法的区别：高位进位法从左边加，进位往右边移动，同普通加法正好相反。但是最终它们都会遍历所有的槽位并且没有重复。

1.2 Scan的实战

scan 参数提供了三个参数，第一个是 cursor 整数值，第二个是 key 的正则模式，第三个是遍历的 limit hint。第一次遍历时，cursor 值为 0，然后将返回结果中第一个整数值作为下一次遍历的 cursor。一直遍历到返回的 cursor 值为 0 时结束。

127.0.0.1:6379> scan 0 match key99* count 1000
1) "13976"
2) 1) "key9911"
2) "key9974"
3) "key9994"
4) "key9910"
5) "key9907"
6) "key9989"
7) "key9971"
8) "key99"
9) "key9966"
10) "key992"
11) "key9903"
12) "key9905"

127.0.0.1:6379> scan 13976 match key99* count 1000
1) "1996"
2) 1) "key9982"
2) "key9997"
3) "key9963"
4) "key996"
5) "key9912"
6) "key9999"
7) "key9921"
8) "key994"
9) "key9956"
10) "key9919"

127.0.0.1:6379> scan 1996 match key99* count 1000
1) "12594"
2) 1) "key9939"
2) "key9941"
3) "key9967"
4) "key9938"
5) "key9906"
6) "key999"
7) "key9909"
8) "key9933"
9) "key9992"
......

127.0.0.1:6379> scan 11687 match key99* count 1000
1) "0"
2) 1) "key9969"
2) "key998"
3) "key9986"
4) "key9968"
5) "key9965"
6) "key9990"
7) "key9915"
8) "key9928"
9) "key9908"
10) "key9929"
11) "key9944"


从上面的过程可以看到虽然提供的 limit 是 1000，但是返回的结果只有 10 个左右。因为这个 limit 不是限定返回结果的数量，而是限定服务器单次遍历的字典槽位数量(约等于)。如果将 limit 设置为 10，你会发现返回结果是空的，但是游标值不为零，意味着遍历还没结束。

127.0.0.1:6379> scan 0 match key99* count 10
1) "3072"
2) (empty list or set)

1.4  reverse binary iteration

Redis Scan 命令最终使用的是 reverse binary iteration 算法。这个算法简单来说就是：依次从高位（有效位）开始，不断尝试将当前高位设置为1，然后变动更高位为不同组合，以此来扫描整个字典数组。其最大的优势在于，从高位扫描的时候，如果槽位是2^N个,扫描的临近的2个元素都是与2^(N-1)相关的就是说同模的，比如槽位8时，0%4 == 4%4， 1%4 == 5%4 ， 因此想到其实hash的时候，跟模是很相关的。

float Q_rsqrt( float number ) 
{ 
    long i; 
    float x2, y; 
    const float threehalfs = 1.5F ;
    x2 = number * 0.5F ; 
    y = number ; 
    i = * ( long * ) &y; // evil floating point bit level hacking 
    i = 0x5f3759df - ( i >> 1 ); // what the fuck? 
    y = * ( float * ) &i; 
    y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration 
//  y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
    return y ;
}

比如当整个字典大小只有4的时候，一个元素计算出的整数为5， 那么计算他的hash值需要模4，也就是hash(n) == 5%4 == 1 , 元素存放在第1个槽位中。当字典扩容的时候，字典大小变为8， 此时计算hash的时候为5%8 == 5 ， 该元素从1号slot迁移到了5号，1和5是对应的，我们称之为同模或者对应。同模的槽位的元素最容易出现合并或者拆分了。因此在迭代的时候只要及时的扫描这些相关的槽位，这样就不会造成大面积的重复扫描。

迭代哈希表时，有以下三种情况：

• 从迭代开始到结束，哈希表不 Rehash；
• 从迭代开始到结束，哈希表Rehash，但每次迭代，哈希表要么不开始 Rehash，要么已经结束 Rehash；
• 从一次迭代开始到结束，哈希表在一次或多次迭代中 Rehash。即再 Rehash 过程中，执行 Scan 命令，这时数据可能只迁移了一部分。

第一种情况比较简单。假设redis的hash表大小为4，第一个游标为0，读取第一个bucket的数据，然后游标返回2，下次读取bucket 2 ，依次遍历。

第二种情况更复杂。假设redis的hash表大小为4，如果rehash后大小变成8。如果如上返回游标(即返回2)，则显示下图：

假设bucket 0读取后返回到cursor 2，当客户端再次Scan cursor 2时，hash表已经被rehash，大小翻倍到8，redis计算一个key bucket如下：

hash(key)&(size-1)

即如果大小为4，hash(key)&11，如果大小为8，hash(key)&111。所以当size从4扩大到8时，2 号bucket中的原始数据会被分散到2 (010) 和 6 (110) 这两个 bucket中。从二进制来看，size为4时，在hash(key)之后，取低两位，即hash(key)&11，如果size为8，bucket位置为hash(key) & 111，即取低三个位。所以依旧不会出现漏掉数据的情况。

第三种情况，如果返回游标2时正在进行rehash，则Hash表1的bucket 2中的一些数据可能已经rehash到了的Hash表2 的bucket[2]或bucket[6]，那么必须完全遍历 哈希表2的 bucket 2 和 6，否则可能会丢失数据。Redis 全局有两个Hash表，扩容时会渐进式的将表1的数据迁移到表2，查询时程序会先在 ht[0] 里面进行查找， 如果没找到， 就会继续到 ht[1] 里面进行查找。

具体游标计算代码如下：Scan 命令中的游标，其实就是 Redis 内部的 bucket。

v |= ~m0; // 将游标v的unmarsked 比特都置为1

v = rev(v);// 反转v

v++; //这个是关键，加1，对一个数加1，其实就是将这个数的低位的连续1变为0，然后将最低的一个0变为1，其实就是将最低的一个0变为1

v = rev(v);//再次反转，即得到下一个游标值

• 大小为 4 时，游标状态转换为 0-2-1-3。
• 当大小为 8 时，游标状态转换为 0-4-2-6-1-5-3-7。

可以看出，当size由小变大时，所有原来的游标都能在大hashTable中找到对应的位置，并且顺序一致，不会重复读取，也不会被遗漏。总结一下：redis在rehash 扩容的时候，不会重复或者漏掉数据。但缩容，可能会造成重复但不会漏掉数据。

缩容处理：之所以会出现重复数据，其实就是为了保证缩容后数据不丢。

假设当前 hash 大小为 8：

• 1）第一次先遍历了 0 号槽，返回游标为 4；
• 2）准备遍历 4 号槽，然后此时发生了缩容，4 号槽的元素也进到 0 号槽了。
• 3）但是0 号槽之前已经被遍历过了，此时会丢数据吗？

do {//扫描大点的表里面的槽位，注意这里是个循环，会将小表没有覆盖的slot全部扫描一次的
    /* Emit entries at cursor */
    de = t1->table[v & m1];
    while (de) {
        fn(privdata, de);
        de = de->next;
    }
 
    /* Increment bits not covered by the smaller mask */
    //下面的意思是，还需要扩展小点的表，将其后缀固定，然后看高位可以怎么扩充。
    //其实就是想扫描一下小表里面的元素可能会扩充到哪些地方，需要将那些地方处理一遍。
    //后面的(v & m0)是保留v在小表里面的后缀。
    //((v | m0) + 1) & ~m0) 是想给v的扩展部分的二进制位不断的加1，来造成高位不断增加的效果。
    v = (((v | m0) + 1) & ~m0) | (v & m0);
 
    /* Continue while bits covered by mask difference is non-zero */
} while (v & (m0 ^ m1));//终止条件是 v的高位区别位没有1了，其实就是说到头了。

v = (((v | m0) + 1) & ~m0) | (v & m0);

右边的下半部分是v，左边的上半部分是v。 (v&m0) 取出v的低位，例如size=4时v&00000011。

左半边(v|m0) + 1 将V 的低位设置为1，然后+1 将进位到v 的高位，再次&m0，V 的高位将被取出。

假设游标返回2并且正在rehashing，大小从4变为8，那么M0 = 00000011 v = 00000010。

根据公式计算的下一个光标是 ((00000010 | 00000011) +1) & (11111111100) | (00000010 & 00000011) = (00000100) & (11111111100) | (00000000010) = (000000000110) 正好是 6。

Scan的原理总结

• Scan Count 参数限制的是遍历的 bucket 数，而不是限制的返回的元素个数。由于不同 bucket 中的元素个数不同，其中满足条件的个数也不同，每次 Scan 返回元素也不一定相同
• Count 越大，Scan 总耗时越短，但是单次耗时越大，即阻塞Redis 时间边长
  • 推荐 Count 大小为 1W左右
  • 当 Count = Redis Key 总数时，Scan 和 Keys 效果一致
• Scan 采用 逆二进制迭代法来计算游标，主要为了兼容Rehash的情况。
• Scan 为了兼容缩容后不漏掉数据，会出现重复遍历。即客户端需要做去重处理

二、Redis中有关于Rehash问题

2.1 大 key 扫描

有时候会因为业务人员使用不当，在 Redis 实例中会形成很大的对象，比如一个很大的 hash，一个很大的 zset 这都是经常出现的。这样的对象对 Redis 的集群数据迁移带来了很大的问题，因为在集群环境下，如果某个 key 太大，会数据导致迁移卡顿。另外在内存分配上，如果一个 key 太大，那么当它需要扩容时，会一次性申请更大的一块内存，这也会导致卡顿。如果这个大 key 被删除，内存会一次性回收，卡顿现象会再一次产生。

在平时的业务开发中，要尽量避免大 key 的产生。

如果你观察到 Redis 的内存大起大落，这极有可能是因为大 key 导致的，这时候你就需要定位出具体是那个 key，进一步定位出具体的业务来源，然后再改进相关业务代码设计。

那如何定位大 key 呢？

为了避免对线上 Redis 带来卡顿，这就要用到 scan 指令，对于扫描出来的每一个 key，使用 type 指令获得 key 的类型，然后使用相应数据结构的 size 或者 len 方法来得到它的大小，对于每一种类型，保留大小的前 N 名作为扫描结果展示出来。

redis-cli 指令中提供了这样的扫描功能

redis-cli -h 127.0.0.1 -p 7001 –-bigkeys

如果你担心这个指令会大幅抬升 Redis 的 ops 导致线上报警，还可以增加一个休眠参数。

redis-cli -h 127.0.0.1 -p 7001 –-bigkeys -i 0.1

2.2 针对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通过哈希函数映射到哈希表节点位置。

/* hash表结构定义 */
typedef struct dictht { 
    dictEntry **table;   // 哈希表数组
    unsigned long size;  // 哈希表的大小
    unsigned long sizemask; // 哈希表大小掩码
    unsigned long used;  // 哈希表现有节点的数量
} dictht; 

实体化一下，如下图所指一个大小为4的空哈希表（Redis默认初始化值为4）：

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;

 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时使用。

我们知道当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）。

梳理一下哈希表大小和内存申请大小的对应关系：

ht[0].size	触发Resize时，ht[1]需分配的内存
4	64bytes
8	128bytes
16	256bytes
…	…
65536	1024K
…	…
8388608	128M
16777216	256M
33554432	512M
67108864	1024M
…	…

复现验证

我们通过测试环境数据来验证一下，当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%)
   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: 6609691
 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%)
   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还会引起其他一些问题：

• 在tablesize级别与现有Keys数量不在同一个区间内，主从切换后，由于Redis全量同步，从库tablesize降为与现有Key匹配值，导致内存倾斜；

• Redis Cluster下的某个分片由于Key数量相对较多提前Resize，导致集群分片内存不均。

• 等等…

Redis Rehash机制优化

那么针对在Redis满容驱逐状态下，如何避免因Rehash而导致Redis抖动的这种问题。

• 我们在Redis Rehash源码实现的逻辑上，加上了一个判断条件，如果现有的剩余内存不够触发Rehash操作所需申请的内存大小，即不进行Resize操作；

• 通过提前运营进行规避，比如容量预估时将Rehash占用的内存考虑在内，或者通过监控定时扩容。

Redis Rehash机制除了会影响上述内存管理和使用外，也会影响Redis其他内部与之相关联的功能模块。下面我们分享一下由于Rehash机制而踩到的第二个坑。

2.3 Scan清理Key由于Rehash导致清理数据不彻底

为了高效地匹配出数据库中所有符合给定模式的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的四种状态场景：

1. 字典tablesize保持不变，没有扩缩容；

2. 字典Resize，Dict扩大了（完成状态）；

3. 字典Resize，Dict缩小了（完成状态）；

4. 字典正在Rehashing（扩展或收缩）。

• 字典tablesize保持不变，在Redis Dict稳定的状态下，直接顺序遍历即可。
• 字典Resize，Dict扩大了，如果还是按照顺序遍历，就会导致扫描大量重复Key。比如字典tablesize从8变成了16，假设之前访问的是3号桶，那么表扩展后则是继续访问4~15号桶；但是，原先的0~3号桶中的数据在Dict长度变大后被迁移到8~11号桶中，因此，遍历8~11号桶的时候会有大量的重复Key被返回。
• 字典Resize，Dict缩小了，如果还是按照顺序遍历，就会导致大量的Key被遗漏。比如字典tablesize从8变成了4，假设当前访问的是3号桶，那么下一次则会直接返回遍历结束了；但是之前4~7号桶中的数据在缩容后迁移带可0~3号桶中，因此这部分Key就无法扫描到。
• 字典正在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采用高位序访问的原因，就是为了实现Redis Dict在Rehash时尽可能少重复扫描返回Key。高位序Scan在Dict Rehash时即可以避免重复遍历，又能完整返回原始的所有Key。同理，字典缩容时也一样，字典缩容可以看出是反向扩容。

非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;
}

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全部扫描一遍 */ 
            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的状态：
   这种状态，即Dict是静止的。针对这种状态下的上述三种场景，Redis采用上述的Reverse Binary Iteration（反向二进制迭代算法）：
   Ⅰ. 首先对游标（Cursor）二进制位翻转；
   Ⅱ. 再对翻转后的值加1；
   Ⅲ. 最后再次对Ⅱ的结果进行翻转。

通过穷举高位，依次向低位推进的方式（即高位序访问的实现）来确保所有元素都会被遍历到。

这种算法已经尽可能减少重复元素的返回，但是实际实现和逻辑中还是会有可能存在重复返回，比如在Dict缩容时，高位合并到低位桶中，低位桶中的元素就会被重复取出。

1. 正在Rehashing的状态：
   Redis在Rehashing状态的时候，dictScan()实现通过一次性扫描现有的两种字典表，避免中间状态无法维护。
   具体实现就是在遍历完小表Cursor位置后，将小表Cursor位置可能Rehash到的大表所有位置全部遍历一遍，然后再返回遍历元素和下一个小表遍历位置。

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机制的探索和实践

美团配送资金安全治理之对账体系建设