Redis中的哈希结构（Dict）

前语

哈希结构是一个在计算机中非常常见的结构。哈希结构能够让咱们在O(1)时刻复杂度查找元素而且对其操作，而且增删改查功能并不会随着数据量的增多而改动。反而数据量的增大，会呈现两个关键问题，一个是哈希冲突，另一个是rehash。而在Redis中，运用拉链法来处理哈希冲突，运用渐进式rehash来降低rehash的功能开销。

Redis中的Dict结构

在Redis 6.2.4中，dict.h是这样界说的。

typedef struct dictEntry {
    void *key;
    //只能为其间任意的一个
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;
/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
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];
    long rehashidx; //-1未进行rehash 
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

它们的联系是这样的

什么是哈希冲突

咱们把存储数据的当地当作一个个桶（Bucket），当数据量超出桶容量或许Hash函数给出的桶号相同的时分，便会呈现哈希冲突。 处理办法便是，选用链表的方式，将同一个Bucket方位上的元素连接起来。这样也会有一个坏处，链表太长，开销又大了起来。所以必定不会无休止的链下去，一定要做rehash。

Redis的渐进式rehash

Hash 表在履行 rehash 时，因为 Hash 表空间扩大，原本映射到某一方位的键可能会被映射到一个新的方位上，因此，很多键就需求从原来的方位复制到新的方位。而在键复制时，因为 Redis 主线程无法履行其他恳求，所以键复制会堵塞主线程，这样就会发生 rehash 开销。而为了降低 rehash 开销，Redis 就提出了渐进式 rehash 的方法。调查dict结构，它存储了两个相同的dictht， 在正常情况下，一切的数据都存储在ht[0]中。在进行rehash时，会先将数据搬迁到ht[1]中，比及一切数据都搬迁完结时，将ht[1] 赋值给ht[0]，而且开释掉ht[0]空间。

rehash的触发条件

Redis 用来判别是否触发 rehash 的函数是**_dictExpandIfNeeded**。所以接下来咱们就先看看，_dictExpandIfNeeded 函数中进行扩容的触发条件；

//假如Hash表为空，将Hash表扩为初始巨细
if (d->ht[0].size == 0) 
   return dictExpand(d, DICT_HT_INITIAL_SIZE);
//假如Hash表承载的元素个数超越其当时巨细，而且能够进行扩容，或许Hash表承载的元素个数已是当时巨细的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);
}

• 哈希表的 LoadFactor >= 1，而且服务器没有履行 BGSAVE（RDB快照） 或许 BGREWRITEAOF（AOF重写） 等后台进程；
• 哈希表的 LoadFactor > 5 ，表明当时的负载太严峻了，需求当即进行扩容； （LoadFactor = used / size）

咱们再来看下 Redis 会在哪些函数中，调用 _dictExpandIfNeeded 进行判别。 通过在dict.c文件中查看 _dictExpandIfNeeded 的被调用联系，咱们能够发现，_dictExpandIfNeeded 是被 _dictKeyIndex 函数调用的，而 _dictKeyIndex 函数又会被 dictAddRaw 函数调用，然后 dictAddRaw 会被以下三个函数调用。

• dictAdd：用交游 Hash 表中添加一个键值对。
• dictReplace：用交游 Hash 表中添加一个键值对，或许键值对存在时，修正键值对。
• dictAddorFind：直接调用 dictAddRaw。

因此，当咱们往 Redis 中写入新的键值对或是修正键值对时，Redis 都会判别下是否需求进行 rehash。

扩容扩多大？

在 Redis 中，rehash 对 Hash 表空间的扩容是通过调用 dictExpand 函数来完结的。dictExpand 函数的参数有两个，一个是要扩容的 Hash 表，另一个是要扩到的容量，下面的代码就展现了 dictExpand 函数的原型界说：

int dictExpand(dict *d, unsigned long size);

那么，对于一个 Hash 表来说，咱们就能够依据前面说到的 _dictExpandIfNeeded 函数，来判别是否要对其进行扩容。而一旦判别要扩容，Redis 在履行 rehash 操作时，对 Hash 表扩容的思路也很简单，便是假如当时表的已用空间巨细为 size，那么就将表扩容到 size2 的巨细。

如下所示，当 _dictExpandIfNeeded 函数在判别了需求进行 rehash 后，就调用 dictExpand 进行扩容。这儿你能够看到，rehash 的扩容巨细是当时 ht[0]已运用巨细的 2 倍。

dictExpand(d, d->ht[0].used*2);

而在 dictExpand 函数中，详细履行是由 _dictNextPower 函数完结的，以下代码显现的 Hash 表扩容的操作，便是从 Hash 表的初始巨细（DICT_HT_INITIAL_SIZE），不停地乘以 2，直到达到方针巨细。

static unsigned long _dictNextPower(unsigned long size)
{
    //哈希表的初始巨细
    unsigned long i = DICT_HT_INITIAL_SIZE;
    //假如要扩容的巨细现已超越最大值，则回来最大值加1
    if (size >= LONG_MAX) return LONG_MAX + 1LU;
    //死循环直到找到不大于的最小值
    while(1) {
        //假如扩容巨细大于等于最大值，就回来到当时扩到的巨细
        if (i >= size)
            return i;
        //每一步扩容都在现有巨细基础上乘以2
        i *= 2;
    }
}

为什么叫渐进式

渐进式 rehash 的意思便是 Redis 并不会一次性把当时 Hash 表中的一切键，都复制到新方位，而是会分批复制，每次的键复制只复制 Hash 表中一个 bucket 中的哈希项。这样一来，每次键复制的时长有限，对主线程的影响也就有限了。

详细过程

关键函数dictRehash部分代码

//入参：dict , 需求搬迁的元素个数
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;
	//搬迁元素，直到搬迁结束或许搬迁完n个
    while(n-- && d->ht[0].used != 0) {
        //....这段代码在下面剖析
    }
    /* Check if we already rehashed the whole table... */
    //判别搬迁是否完结
    if (d->ht[0].used == 0) {
    	//开释ht[0]
        zfree(d->ht[0].table);
        //将ht[0] 指向 ht[1]
        d->ht[0] = d->ht[1];
        //让ht[1]从头指向null
        _dictReset(&d->ht[1]);
        //表明rehash暂停
        d->rehashidx = -1;
        //回来搬迁完结
        return 0;
    }
	//还需求持续搬迁
    /* More to rehash... */
    return 1;
}

那么，每次搬迁几个元素呢？

这就要说到rehashidx了。 rehashidx 变量表明的是当时 rehash 在对哪个 bucket 做数据搬迁。比方，当 rehashidx 等于 0 时，表明对 ht[0]中的第一个 bucket 进行数据搬迁；当 rehashidx 等于 1 时，表明对 ht[0]中的第二个 bucket 进行数据搬迁，以此类推。

而 dictRehash 函数的主循环，首先会判别 rehashidx 指向的 bucket 是否为空，假如为空，那就将 rehashidx 的值加 1，查看下一个 bucket。

所以，渐进式 rehash 在履行时设置了一个变量 empty_visits，用来表明现已查看过的空 bucket，当查看了一定数量的空 bucket 后，这一轮的 rehash 就中止履行，转而持续处理外来恳求，避免了对 Redis 功能的影响。下面的代码显现了这部分逻辑。

while(n-- && d->ht[0].used != 0) {
    //假如当时要搬迁的bucket中没有元素
    while(d->ht[0].table[d->rehashidx] == NULL) {
        //
        d->rehashidx++;
        if (--empty_visits == 0) return 1;
    }
    ...
}

而假如 rehashidx 指向的 bucket 有数据能够搬迁，那么 Redis 就会把这个 bucket 中的哈希项顺次取出来，并依据 ht[1]的表空间巨细，从头计算哈希项在 ht[1]中的 bucket 方位，然后把这个哈希项赋值到 ht[1]对应 bucket 中。

这样，每做完一个哈希项的搬迁，ht[0]和 ht[1]用来表明承载哈希项多少的变量 used，就会分别减一和加一。当然，假如当时 rehashidx 指向的 bucket 中数据都搬迁完了，rehashidx 就会递添加 1，指向下一个 bucket。下面的代码显现了这一搬迁过程。

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

还有一个问题，n的巨细是多少?从下面这个函数能够看到，是1。每次只是搬迁一个元素，之后变去履行主要操作。

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

看看有哪些函数调用了_dictRehashStep，Ctrl+F找一下。它们发现分别是：dictAddRaw，dictGenericDelete，dictFind，dictGetRandomKey，dictGetSomeKeys。 其间，dictAddRaw 和 dictGenericDelete 函数，分别对应了往 Redis 中添加和删去键值对，然后三个函数则对应了在 Redis 中进行查询操作。调用联系如下图。

总结

• 什么是渐进式rehash？为什么要规划两个ht？
  Redis中心命令履行是单线程的，所以一次性搬迁悉数数据开销很大而且会堵塞服务。在需求rehash的时分，不会当行将悉数数据进行搬迁，而是通过辅佐表来渐渐进行搬迁，每次搬迁1个元素，进行正常服务的时分，在ht[1]中进行添加操作，其他操作在ht[0]和ht[1]中一起进行。
• rehashidx有什么用？
  为-1的时分表明没有rehash，为0的时分表明要搬迁ht[0]中0号元素到ht[1]中，后续顺次类推
• rehash触发条件？
  扩容或许缩短

dict的伸缩：

• 当LoadFactor大于5或许LoadFactor大于1而且没有子进程任务时，Dict扩容
• 当LoadFactor小于0.1时，Dict缩短
• 扩容巨细为第一个大于等于used + 1的2^n
• 缩短巨细为第一个大于等于used 的2^n
• dict选用渐进式rehash，每次拜访Dict时履行一次rehash