Redis的哈希表—rehash详细讲解

Redis的性能优越，应用普遍，可以存储的键值个数大到上亿条记录，依然保持较高的效率。作为一个内存数据库，Redis内部采用了字典（哈希表）的数据结构实现了键值对的存储。随着数据量的不断增加，数据必然会产生hash碰撞，而Redis采用链地址法解决hash冲突。我们知道如果哈希表数据量达到了一个很大的量级，那么冲突的链的元素数量就会很大，这时查询效率就会变慢，因为取值的时候Redis会遍历链表。而随着数据量的缩减，也会产生一定的内存浪费。Redis在设计时充分考虑了字典的增加和缩减，为了优化数据量增加时的查询效率和缩减时的内存利用率，Redis进行了一系列操作，而处理的这个过程被称作rehash。Redis是在插入新节点之前判断是否需要进行扩容，如果不需要，则直接插入，否则需要先扩容，再插入新节点。
为了避免对服务器性能造成影响，Redis使用了一种渐进式哈希的机制来提高字典的缩放效率。渐进式rehash的好处是它采取分而治之的方式，将rehash键值所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash带来的庞大计算量。比如：如果哈希表中的数据量达到上百万级别，进行一次rehash会消耗大量的时间，可能导致服务器在一段时间内停止服务。

存储结构

在Redis中，键值对存储方式是由字典(dict)保存的，而字典底层是通过哈希表来实现。通过哈希表中的节点保存字典中的键值对。

hash表的底层数据结构定义：

//字典定义
typedef struct  dict{
    dictType *type;  //type和privdata是针对不同类型的键值对，为创建多态字典而设置的
    void *privdata;
    dictht ht[2];  //两个hashtable，用于存储和rehash
    long rehashidx;  //如果没有进行rehash，则值为-1，否则，rehash表示rehash进行到的索引位置
    unsigning long iterators;
}dict;

//哈希表定义
typedef struct dictht {
    dictEntry **table;  //指针，指向一个哈希桶bucket
    unsigning long size;  //哈希表的大小
    unsigning long sizemask;  //总是size-1，这个值和哈希值一起决定元素应该定位到桶中的什么位置
    unsigning long used;  //已使用的桶数量
}dictht;

//具体键值对定义
typedef struct dictEntry{
    void *key;   //键值
    union{
        void *val;  //value值
        unint64_tu64;
        int64_ts64;
    }v;
    struct dictEntry *next;  //指向下一个键值对的指针，用于解决哈希冲突问题
}dictEntry;

为什么每个字典中包含两个hashtable？

1. 首先Redis在正常读写时会用到一个hashtable；
2. 另一个hashtable的作用实际上是作为哈希表进行rehash时的一个临时载体。

当需要进行扩容时，redis会根据数据量和桶的个数初始化那个备用的hashtable，来使这个hashtable从容量上满足后续的使用，并开始把之前的hashtable的数据迁移到这个新的hashtable上（重新计算哈希值），等到数据全部迁移完毕，再进行一次HashTable的地址更名，把这个备用的HashTable更名为正式的HashTable，同时清空另一个HashTable，以供下一次rehash的使用。然后将rehashidx赋值为0，打开渐进式rehash标志。同时该值也标志渐进式rehash当前已经进行到哪个hash值。

扩容的条件

负载因子 = 哈希表保存的key的数量 / 哈希表的大小

1. 当前哈希表中保存的key的数量超过了哈希表的大小size，并且redis服务当前允许执行rehash（指的是当前没有子进程在执行AOF文件重写或者生成RDB文件《持久化操作》）；
2. 或者保存的节点数与哈希表的大小的比例超过了安全阈值（默认为5）.

即，当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

1. 服务器目前没有在执行BGSAVE命令或者BGREWRITEAPF命令，并且哈希表的负载因子>=1；
2. 服务器目前正在执行BGSAVE命令或者BGREWRITEAPF命令，并且哈希表的负载因子>=5;。

如果程序正在进行持久化，这个时候进行rehash会导致数据不一致。

缩容的条件

元素个数低于数组长度的10%.
缩容不会考虑Redis是否正在做bgsave。

渐进式rehash初始化

不管是扩容（包含初始化）还是缩容，最终都是调用dictExpand函数来完成。
这个函数完成的任务：

1. 判断：如果当前正在rehash或者传进来的扩容参数<当前哈希表中已使用的元素个数，则返回错误；
2. 计算新的hash表大小，使得新的hash表的大小为一个2的n次方：>= size(传进来的参数)的第一个2的n次方；
3. 判断：如果扩容后的大小 == 原来表的大小，则返回错误；
4. 初始化ht[1]，并且将rehashidx的值设置为0，返回正确；

操作辅助rehash（每当客户端请求时，rehash一个槽）

在redis中，每一个增、删、改、查命令中都会判断哈希表是否正在进行扩容，如果是则帮助执行一次，调用_dictRehashStep(dict *d)函数。
  此函数仅执行一步hash表的重散列，并且仅当没有安全迭代器绑定到哈希表时。这是因为当我们在重新散列中有迭代器时，我们不能混淆打算两个哈希表的数据，否则某些元素可能被遗漏或者重复遍历。

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

定时辅助rehash（每次rehash100个槽，但是占用CPU的时间不能超过1ms，超过则直接退出）

虽然redis实现了在读写操作时，服务器辅助进行渐进式rehash操作，但是如果服务器比较空闲，redis数据库将很长时间内都一直使用两个哈希表。所以在redis周期函数中，如果发现有字典正在进行渐进式rehash操作，则会花费1毫秒的时间，帮助一起进行渐进式rehash操作。

/* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;

    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

渐进式rehash实现

不管是在操作中辅助rehash执行，还是在周期函数中辅助执行，最终都是在调用dictRehash函数：

/* Performs N steps of incremental rehashing. Returns 1 if there are still
 * keys to move from the old to the new hash table, otherwise 0 is returned.
 *
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;  //对这个链表中的每个节点，采用头插入法加入到新哈希表的链表中。
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

rehash的步骤

假设ht[0]为正在使用的hashtable，ht[1]为备用的hashtable。

1. 为字典的备用哈希表ht[1]分配空间（初始化）：

• 如果进行的是扩展操作，那么ht[1]的大小为第一个>= 已使用节点数 * 2的2^n(2的n次方)。
• 如果进行的收缩操作，那么ht[1]的大小为第一个>= 已使用节点数 * 2的2^n(2的n次方)。

2. 在字典中维持一个索引计数器变量rehashidx，并将其值设置为0，表示rehash工作正式开始（为-1时表示没有进行rehash）；
3. rehash进行期间，每次对字典进行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对（这个桶中的链表）rehash到ht[1]，当一次rehash工作完成之后，程序将rehashidx属性的值+1。同时Redis会设置一个定时任务，在1ms的时间内，进行rehash处理，每次仅仅处理少量的转移任务。
4. 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1]上，这时程序将rehashidx属性的值设置为-1，表示rehash操作已经完成。

渐进式rehash执行期间的哈希表操作

因为在rehash的过程中，字典会同时使用两个哈希表，所以在rehash期间，字典的删除、查找、更新、增加等操作会在两个哈希表中进行。比如：

• 要在字典中查找某一个键，程序会现在ht[0]里面进行查找，如果没找到，就会继续到ht[1]里面进行查找。
• 如果是添加操作，则新添加的键值对会一律被保存到ht[1]中，而ht[0]不再进行任何添加操作：这一措施保证ht[0]中的键值对数量只减不增，并且随着操作的执行，最终变成空表。

渐进式rehash带来的问题

渐进式rehash避免了redis阻塞（原来进行一次put操作，要等到rehash全部结束，这个操作才会返回，现在则只需要辅助rehash一步），但是由于在rehash时，需要分配一个新的hash表，在rehash期间，同时有两个hash表在使用，会使得redis内存使用量瞬间突增，在Redis 满容状态下由于Rehash会导致大量Key驱逐。

与HashMap的扩容对比

1. HashMap采用的不是渐进式扩容，而是在哈希表插入元素之后，检查哈希表是否需要扩容，如果需要的话，就进行扩容，扩容完成之后，返回；

2. HashMap只有一个哈希表，没有备用的；

3. HashMap进行扩容的标准是：当表中元素的总数量>哈希表的大小×负载因子（默认0.75）时，对表进行扩容，扩容之后大小为原表大小的2倍；

4. HashMap中引入了红黑树，当链表长度大于8时，将链表改为红黑树结构，提高查找效率（从O(n)->O(logn)）；

5. HashMap是在加入新节点之后，才判断是否需要扩容；而Redis是在加入节点之前进行判断。

   
   

读者分享

在这给大家推荐一个微信公众号，那里每天都会有技术干货、技术动向、职业生涯、行业热点、职场趣事等一切有关于程序员的内容分享。更有海量Java架构、移动互联网架构相关源码视频，面试资料，电子书籍截止于4月28日免费发放。我看了觉得资源还不错，如果你们有需要的话，扫描下方二维码关注wx公众号免费获取↓↓↓

资源大本营↓↓↓

Java架构资料
Java源码解析，到各种框架学习，再到项目实战，一应俱全，包括但不限于：Spring、Mybatis等源码、Java进阶、Java架构师、虚拟机、性能优化、并发编程、数据结构和算法。

Java架构视频资料
Java架构视频资料
java架构面试专题资料

移动互联网架构资料
Android进阶、Android架构、APP开发、NDK模块开发、小程序开发、微信开发。

Android架构资料