redis 哈希表的 rehash 分析

大家都比较了解哈希表，以及类似 php、redis 等的内部 hash 实现。但是本文着力介绍 redis 中的 rehash 的实现，供大家参考学习。

引言

redis 的性能优越，应用普遍，可以存储键值个数大到可以存储上亿条记录依然保持较高的效率。作为一个内存数据库，redis 内部采用了字典的数据结构实现了键值对的存储，字典也就是我们平时所说的哈希表。随着数据量的不断增加，数据必然会产生 hash 碰撞，而 redis 采用链地址法解决 hash 冲突。我们知道如果哈希表数据量达到了一个很大的量级，那么冲突的链的元素数量就会很大，这时查询效率就会变慢，因为取值的时候 redis 会遍历链表。而随着数据量的缩减，也会产生一定的内存浪费。redis 在设计时充分考虑了字典的增加和缩减，为了优化数据量增加时的查询效率和缩减时的内存利用率，redis 进行了一系列操作，而处理的这个过程被称作 rehash。

两个 hashtable

我们先来看一下字典在 redis 源码中的定义

// 哈希表定义typedef struct dictht {    dictEntry **table;    unsigned long size;    unsigned long sizemask;    unsigned long used; } dictht;
// 字典定义typedef struct dict {    dictType *type;    void *privdata;    dictht ht[2]; /* 两个hashtable */    long rehashidx; /* rehashing 如果没有进行则 rehashidx == -1  否则 rehash则表示rehash进行到的索引位置 */     unsigned long iterators; /* number of iterators currently running */} dict;

从结构上看每个字典中都包含了两个 hashtable。那么为什么一个字典会需要两个 hashtable？首先 redis 在正常读写时会用到一个 hashtable，而另一个 hashtable 的作用实际上是作为字典在进行 rehash 时的一个临时载体。我们可以这么理解，redis 开始只会用一个 hashtable 去读写，如果这个 hashtable 的数据量增加或者缩减到某个值，到达了 rehash 的条件，redis 便会开始根据数据量和链（bucket）的个数初始化那个备用的 hashtable，来使这个 hashtable 从容量上满足后续的使用，并开始把之前的 hashtable 的数据迁移到这个新的 hashtable 上来，当然这种迁移是对每个节点值进行一次 hash 运算。等到数据全部迁移完成，再进行一次 hashtable 的地址更名，把这个备用的 hashtable 为正式的 hashtable，同时清空另一个 hashtable 以供下一次 rehash 使用。

1 rehash 的条件

hashtable 元素总个数 / 字典的链个数 = 每个链平均存储的元素个数(load_factor)

1.服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，load_factor >= 1，dict 就会触发扩大操作 rehash

2.服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，load_factor >= 5，dict 就会触发扩大操作 rehash

3.load_factor < 0.1，dict 就会触发缩减操作 rehash

2 rehash 的过程

我们假设 ht[0]为正在使用的 hashtable，ht[1]为 rehash 之后的备用 hashtable

步骤如下：

• 为字典的备用哈希表分配空间：

• 如果执行的是扩展操作，那么备用哈希表的大小为第一个大于等于(已用节点个数)*2 的 2n（2 的 n 次方幂）

• 如果执行的是收缩操作，那么备用哈希表的大小为第一个大于等于(已用节点个数)的 2n

• 在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为 0，表示 rehash 工作正式开始（为-1 时表示没有进行 rehash）。

• rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0]哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当一次 rehash 工作完成之后，程序将 rehashidx 属性的值+1。同时在 serverCron 中调用 rehash 相关函数，在 1ms 的时间内，进行 rehash 处理，每次仅处理少量的转移任务(100 个元素)。

• 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被 rehash 至 ht[1]，这时程序将 rehashidx 属性的值设为-1，表示 rehash 操作已完成。

rehash 部分源码：

int dictRehash(dict *d, int n) {    int empty_visits = n*10; /* Max number of empty buckets to visit. */ /* 判断字典是否在进行rehash */    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);          /* 找到不为空的hashtable的索引位置        while(d->ht[0].table[d->rehashidx] == NULL) {            d->rehashidx++;            if (--empty_visits == 0) return 1;        }        de = d->ht[0].table[d->rehashidx];        /* 将bucket从旧的哈希表迁移（hash）到新的哈希表 */        while(de) {            uint64_t h;            nextde = de->next;            /* 获得节点在新hashtable的哈希索引值 */            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++;    }
    /* 检查rehash是否全部完成，如果完成则将旧的hashtable释放并作新旧表更名，同时rehashidx置-1 */    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;    }
    /* rehash没有完成返回1，继续....... */     return 1;}

举个例子

rehash 开始，初始化 ht[1]

对 k2 进行 rehash

rehash 完成

总结

这种渐进式的 rehash 避免了集中式 rehash 带来的庞大计算量和内存操作，但是需要注意的是 redis 在进行 rehash 的时候，正常的访问请求可能需要做多要访问两次 hashtable（ht[0]， ht[1]），例如键值被 rehash 到新 ht[1]，则需要先访问 ht[0]，如果 ht[0]中找不到，则去 ht[1]中找。

本文转载自公众号 360 云计算（ID：hulktalk）。

原文链接：

https://mp.weixin.qq.com/s/rBMmJVOcryrCEW8ZrKKVig