从源码的角度来熟悉redis的渐进式rehash

发表于

这是我参与更文挑战的第3天，活动详情查看： 更文挑战

概述

前两天整理了redis中字典的实现==》字典终极篇。强烈建议没看的XDM可以先去看一遍（看一遍 看一遍 看一遍 重要的事情说三遍😄），字典底层使用到哈希表，字典终极篇 这里也提到当哈希表需要扩展或者收缩的时候会将我们ht[0]里面的数据rehash到ht[1]中，而这个过程并不是一下完成的，而是一个多次 渐进的过程。好优雅的设计 崇拜～

渐进式的原因

分多次进行的原因是，如果我们的ht[0]中保存的键值对是十几或者几百这种较小的值，我们一次rehash是没有问题的，但是如果是几十万几百万呢？一次想要把这些key value rehash到ht[1]是需要一定的时间的，redis服务短时间不可用。这当然是不允许的哈～（redis不可用，那我们的服务请求不就都打到mysql了 导致mysql服务被打挂 然后我们的服务直接全是500 哇！不敢想象。。）

文字描述rehash的过程

  1. 根据字典终极篇中我们提到的ht[1]分配策略进行内存分配，此时同时存在ht[0]和ht[1]两个哈希表。
  2. 这个时候将我们字典结构上的rehashidx设置为0表示我们的rehash正式开始（之前是-1）。
  3. 在rehash进行期间，定时任务会每次都会对ht[0]上的100 * n个key（这个为什么是100*n呢？下面看下源码xdm就知道了），我们对字典的增删改查会进行一个非空key的rehash。每完成一个key都会将rehashidx的值加1
  4. 随着字典操作的不断进行 ht[0]上的所有键值都rehash到ht[1]后 ht[0]是一个空的哈希表。将ht[0]指向ht[1],ht[1]指向null，这个时候rehashidx设置成-1 表示rehash完成。

渐进式rehash的好处是采用了分而治之的方法，将rehash的过程分散到每个对字典的操作中去，避免了一起rehash庞大的计算量。

不多叨叨，来看下源码

我们来看下这个dictRehashMilliseconds方法，这个方法会在redis的定时任务中databasesCron进行调用的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
ini复制代码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;
}

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

在这个地方有一个死循环，只有时间超时才会break，也就是说单次的rehash每次最多是100ms,但是xdm有没有发现一个bug，就是如果dictRehash(d,100)这个方法执行超过100ms 这次就会超过100ms了。（redis其实自己是默认每次哈希100个key的时间是小于100ms的）,这个地方就是上边说的为什么是100*n个key了

1
2
3
4
kotlin复制代码 while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }

接下来我们看一下最核心的dictRehash方法，这个就是核心的rehash方法。empty_visits也是一个非常非常优雅的设计，如果累计访问的null值是我们要rehash数的10倍就直接return，也是为了防止我们哈希表中null很多的情况下rehash过程花费太多的时间（这个设计真的优雅到我了）

我们在对字典进行操作的时候也会对字典进行dictRehash的操作，不过这种只会操作一个非空的key。

最后这个地方的逻辑就是rehash完成的实现：

1
2
3
4
5
6
7
ini复制代码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;
   }

我们可以发现

rehashidx的作用很重要，他会记录我们当前dict的rehash所进行到的索引值（我们可以分治的重要字段），也是我们当前dict是否在rehash的判断标志。

总结

当我们在rehash过程中对字典进行增删改查操作会是什么情况呢？

  1. 更新：先查询ht[0]上有没有如果有则更新，如果没有则去ht[1]上进行查询更新（查询、删除也是这个逻辑）。
  2. 新增：新增的话会直接操作ht[1]，这样可以保证ht[0]上不会再新增了。

xdm redis的rehash到这就完成了，设计的真的是相当的优雅，我们可以将这种思想运用到我们的日常设计开发中，让我们的代码都优雅起来～

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%