乐趣区

Redis5源码学习20190419-字典dict

baiyan

全部视频:【每日学习记录】使用录像设备记录每天的学习

字典是啥

dict,即字典,也被称为哈希表 hashtable。在 redis 的五大数据结构中,有如下两种情形会使用 dict 结构:

  • hash:数据量小的时候使用 ziplist,量大时使用 dict
  • zset:数据量小的时候使用 ziplist,数据量大的时候使用 skiplist + dict

结合以上两种情况,我们可以看出,dict 也是一种较为复杂的数据结构,通常用在数据量大的情形中。通常情况下,一个 dict 长这样:

在这个哈希表中,每个存储单元被称为一个桶(bucket)。我们向这个 dict(hashtable)中插入一个 ”name” => “baiyan” 的 key-value 对,假设对这个 key“name”做哈希运算结果为 3,那么我们寻找这个 hashtable 中下标为 3 的位置并将其插入进去,得到如图所示的情形。我们可以看到,dict 最大的优势就在于其查找的时间复杂度为 O(1),是任何其它数据结构所不能比拟的。我们在查找的时候,首先对 key”name“进行哈希运算,得到结果 3,我们直接去 dict 索引为 3 的位置进行查找,即可得到 value”baiyan“,时间复杂度为 O(1),是相当快的。

redis 中的字典

基本结构

在 redis 中,在普通字典的基础上,为了方便进行扩容与缩容,增加了一些描述字段。还是以上面的例子为基础,在 redis 中存储结构如下图所示:

dictht 的结构如下:

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

在 dictht 中,真正存储数据的地方是 **table 这个 dictEntry 类型二级指针。我们可以把它拆分来看,首先第一个指针可以代表一个数组,即哈希表。而后面的指针代表,在每个在哈希表的存储单元中,存储的都是一个 dictEntry 类型指针,这个指针就指向我们存储 key-value 对的 dictEntry 类型结构的所在位置,如上图所示。
存储最终 key-value 对的 dictEntry 的结构如下:

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

一个存储 key-value 对的 entry,最主要还是这里的 key 和 value 字段。由于存储在 dict 中的 key 和 value 可以是字符串、也可以是整数等等,所以在这里均用一个 void * 指针来表示。我们注意到最后有一个也是同类型 dictEntry 的 next 指针,它就是用来解决我们经常说的 哈希冲突 问题。

哈希冲突

当我们对不同的 key 进行哈希运算之后结果相同时,就碰到了哈希冲突的问题。常用的两种哈希冲突的解决方案有两种:开放定址法与链地址法。redis 使用的是后者。通过这个 next 指针,我们就可以将哈希值相同的元素都串联起来,解决哈希冲突的问题。注意在 redis 的源码实现中,在往 dict 插入元素的时使用的是链表的 头插法,即将新元素插到链表的头部,这样就不用每次遍历到链表的末尾进行插入,降低了插入的时间复杂度。

链地址法所带来的问题

假设我们一直往 dict 中插入元素,那么这个哈希表的所有 bucket 都会被占满,而且在链地址法解决哈希冲突的过程中,每个 bucket 后面的链表会非常长。这样一来,这个链表的时间复杂度就会逐渐退化成 O(n)。对于整体的 dict 而言,其查询效率就会大大降低。为了解决数据量过大导致 dict 性能下降的问题,我们需要对其进行 扩容,来满足后续插入元素的存储需要。

分而治之的 rehash

  • 在通常情况下,我们会对哈希表做一个 2 倍的扩容,即由 2 ->4,4->8 等等。假设我们的一个 dict 中已经存储了好多数据,我们还需要向这个 dict 中插入一大堆数据。在后续插入大量数据的过程中,由于我们需要解决 dict 性能下降的问题,我们需要对其进行扩容。由于扩容的时候,需要对所有 key-value 对重新进行哈希运算,并重新分配到相应的 bucket 位置上,我们称这个过程为为rehash
  • 在 rehash 过程中,需要做大量的哈希运算操作,其开销是相当大、而且花费的时间是相当长的。由于 redis 是单进程、单线程的架构,在执行 rehash 的过程中,由于其开销大、时间长,会导致 redis 进程阻塞,进而无法为线上提供数据存储服务,对外部会返回 redis 服务不可用。为了解决一次性 rehash 所导致的 redis 进程阻塞的问题,利用 分而治之 的编程思想,将一次 rehash 操作分散到多个步骤当中去减小 rehash 给 redis 进程带来的资源占用。举一个例子,可能会在后续的 get、set 操作中,进行一次 rehash 操作。为了实现这种操作,redis 其实设计了 两个哈希表 ,一个就是我们之前讲过的对外部提供存取服务的哈希表,而另一个就专门用来做 rehash 操作。这种分而治之的思想,将一次大数据量的 rehash 操作分散到多次完成,叫做 渐进式 rehash

  • 目前是刚刚要进行 rehash 的状态。我们可以看到,在之前画的图的基础上,我们加入了一个新的结构 dict,其中的 ht[2]字段就负责指向两个哈希表。下面一个哈希表的大小为之前的大小 8 *2=16,没有任何元素。关于 dict 的结构如下:
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehash 进程标识。如果值为 - 1 则不在 rehash,否则在进行 rehash */
    unsigned long iterators; /* number of iterators currently running */
} dict;
  • 注意其中的 rehashidx 字段,它代表我们进行 rehash 的进程。注意我们每次进行 get 或 set 等命令的时候,rehash 就会进行一次,即把一个在原来哈希表 ht[0]上的元素挪到新哈希表 ht[1]中,注意一次只移动一个元素,移动完成之后,rehashidx 就会 +1,直到原来哈希表上所有的元素都挪到新哈希表上为止。rehash 完成之后,新哈希表 ht[1]就会被置为 ht[0],为线上提供服务。而原来的哈希表 ht[0]就会被销毁。rehash 的源码如下:
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];
        /* 将老的哈希表 ht[0]中的元素移动到新哈希表 ht[1]中 */
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* 计算新哈希表 ht[1]的索引下标 */
            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 完成,若完成则置 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;
    }

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

rehash 过程中可能存在的问题

rehash 对查找的影响

如果在 rehash 的过程中(例如容量由 4 扩容到 8),如果需要查找一个元素。首先我们会计算哈希值(假设为 3)去找老的哈希表 ht[0],如果我们发现位置 3 上已经没有了元素,说明这个元素已经被 rehash 过了,到新的哈希表上对应的位置 3 或 7 上寻找即可。

rehash 对遍历的影响

问题

试想这么一种情况:在 rehash 之前,我们使用 SCAN 命令对 dict 进行第一次遍历;而 rehash 结束之后我们进行第二次 SCAN 遍历,会发生什么情况?
在讨论这个问题之前,我们先熟悉一下 SCAN 命令。我们知道在我们执行 keys 这种返回所有 key 值的命令,由于所有 key 加在一块是相当多的,如果一次性全部把它遍历完成,能够让单进程的 redis 阻塞相当长的时间,在这段时间里都无法对外提供服务。为了解决这个问题,SCAN 命令横空出世。它并不是一次性将所有的 key 都返回,而是每次返回一部分 key 并记录一下当前遍历的进度,这里用一个游标去记录。下次再次运行 SCAN 命令的时候,redis 会从游标的位置开始继续往下遍历。SCAN 命令实际上也是一种分而治之的思想,这样一次遍历一小部分,直到遍历完成。SCAN 命令官方解释如下:

SCAN 命令是一个基于游标的 迭代器:SCAN 命令每次被调用之后,都会向用户返回一个新的游标,用户在下次迭代时需要使用这个新游标作为 SCAN 命令的游标参数,以此来延续之前的迭代过程。

SCAN 命令的使用方法如下:

redis 127.0.0.1:6379> scan 0
1) "17"
2)  1) "key:12"
    2) "key:8"
    3) "key:4"
    4) "key:14"
    5) "key:16"
    6) "key:17"
    7) "key:15"
    8) "key:10"
    9) "key:3"
    10) "key:7"
    11) "key:1"

redis 127.0.0.1:6379> scan 17
1) "0"
2) 1) "key:5"
   2) "key:18"
   3) "key:0"
   4) "key:2"
   5) "key:19"
   6) "key:13"
   7) "key:6"
   8) "key:9"
   9) "key:11"
    • 在上面这个例子中,第一次迭代使用 0 作为游标,表示开始一次新的迭代。第二次迭代使用的是第一次迭代时返回的游标,也即是命令回复第一个元素的值 17。
    • 从上面的示例可以看到,SCAN 命令的回复是一个包含两个元素的数组,第一个数组元素是用于进行下一次迭代的新游标,而第二个数组元素则是一个数组,这个数组中包含了所有被迭代的元素。
    • 在第二次调用 SCAN 命令时,命令返回了游标 0,这表示迭代已经结束,整个数据集(collection)已经被完整遍历过了。
    • 以 0 作为游标开始一次新的迭代,一直调用 SCAN 命令,直到命令返回游标 0,我们称这个过程为一次完整遍历。

    回到正题,我们来解决之前的问题。我们简化一下 dict 的结构,只留下两个基本的哈希表结构,我们现在有 4 个元素:12、13、14、15,假设哈希算法为取余。

    • 假设现在我们在没有 rehash 之前,对其使用 SCAN 命令,基于我们之前讲过的知识点,由于 SCAN 是基于游标的增量遍历,我们假设这个 SCAN 命令只遍历到游标为 1 的位置就停止了:

    • 我们得到第一次遍历的结果为:12
    • 开始进行 rehash。
    • rehash 结束,我们再次使用 SCAN 命令对其进行遍历。由于上次返回的游标为 1,我们从 1 的位置继续遍历,只不过这次要在新的哈希表中进行遍历了:

    • 第二次 SCAN 命令遍历的结果为:12、13、14、15

    那么我们将两次 SCAN 的结果合起来,为 12、12、13、14、15。我们发现,元素 12 被多遍历了一次,与我们的预期不符。所以我们得出结论:在 rehash 过程中执行 SCAN 命令会导致遍历结果出现冗余

    解决方案

    为了解决扩容和缩容进行 rehash 的过程中重复遍历的问题,redis 对哈希表的下标做出了如下变化(v 就是哈希表的下标):

    v = rev(v);
    v++;
    v = rev(v);

    首先将游标倒置,加一后,再倒置,也就是我们所说的“高位 ++”的操作。这里的这几步操作是来通过前一个下标,计算出哈希表下一个 bucket 的下标。举一个例子:最开始 00 这个 bucket 不用动,之前经过正常的低位 ++ 之后,00 的后面应该为 01。然而现在是高位 ++,原来 01 的位置的下标就会变成 10……. 以此类推。最终,哈希表的下标就会由原来顺序的 00、01、10、11 变成了 00、10、01、11,如图所示:

    这样就能够保证我们多次执行 SCAN 命令就不会重复遍历了吗?接下来就是见证奇迹的时刻:

    • 首先还是没进行 rehash 之前,对其进行 SCAN。同样的,我们假设这个 SCAN 命令只遍历到游标为 1 的位置就停止了:

    • 我们得到第一次遍历的结果:12
    • 开始进行 rehash

      • rehash 结束,我们再次使用 SCAN 命令对其进行遍历。注意这里,上次返回的游标为 2,我们从 2 的位置继续遍历,也是要在新的哈希表中进行遍历了:

    • 我们可以看到,经过一个小的下标的修改,就能够解决 rehash 所带来的 SCAN 重复遍历的问题。对 dict 进行遍历的源码如下:
    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;
    
       // 如果 SCAN 的时候没有进行 rehash
       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) { // 遍历同一个 bucket 上后面挂接的链表
               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++; // 反转之后即为高位 ++
           v = rev(v); // 再反转回来,得到下一个游标值
    
        // 如果 SCAN 的时候正在进行 rehash
       } 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) { // 遍历同一个 bucket 上后面挂接的链表
               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) { // 遍历同一个 bucket 上后面挂接的链表
                   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++; // 反转之后即为高位 ++
               v = rev(v); // 再反转回来,得到下一个游标值
    
               /* Continue while bits covered by mask difference is non-zero */
           } while (v & (m0 ^ m1));
       }
    
       return v;
    }

    有关 rehash 过程对 SCAN 的影响,限于篇幅仅仅展示这种情况。更多的情形请参考:Redis scan 命令原理

    退出移动版