浅析Redis底层数据结构Dict

Dict 优点在于，它能以 O(1) 的复杂度快速查询数据。怎么做到的呢？将 key 通过 Hash 函数的计算，就能定位数据在表中的位置，因为哈希表实际上是数组，所以可以通过索引值快速查询到数据。

但是存在的风险也是有，在哈希表大小固定的情况下，随着数据不断增多，那么哈希冲突的可能性也会越高。

解决哈希冲突的方式，有很多种。

Redis 采用了「链式哈希」来解决哈希冲突，在不扩容哈希表的前提下，将具有相同哈希值的数据串起来，形成链接起，以便这些数据在表中仍然可以被查询到。

接下来，详细说说 Dict 的结构设计

Dict 的结构

Dict 由三部分组成，分别是：dict、dictht、dicEntry

dictht

dictht 的结构如下：

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

• dictEntry **table，哈希表数组
• unsigned long size，哈希表大小（取值为 2n2^n2n）
• unsigned long sizemask，哈希表大小掩码，用于计算索引值，总是等于 size−1size - 1size−1
• unsigned long used，该哈希表已有的节点数量

dicEntry

dicEntry 结构如下

void *key;/*键*/
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; /*值*/
    struct dictEntry *next;/*下一个 entry 的指针*/
} dictEntry;

• dicEntry 和 dictht 之间的组织方式如下图所示

• 当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置。我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1&3 = 1，因此 k1=v1 要存储到数组角标 1 位置。
• 如果计算出来的数组角标值相同，也就是说，出现了 *哈希冲突，redis 采用 ”链式哈希“ 的方式，将具有相同哈希值的数据串起来，形成链结构，这也就是为什么会有 struct dictEntry next 这个成员变量存在

???? 为什么是 h & sizemask ？ 在根据 hash 值（h）来计算应该把 entry 放在哪个数组下标位置时，你可能会好奇，为什么不是使用 h%size ，而是使用 h&sizemask，而他们为什么可以得出一样的结果。
实际上，当散列表的大小为 2n2^n2n 时，h%sizemask 的结果与 h%size 是相同的（这里不做证明）。让我们以 size 为 8 的散列表为例：

• size = 8，对应的 sizemask = 7 (111的二进制表示)
• h = 18 (10010的二进制表示)
• h%size = 18%8 = 2
• h&sizemask = 18&7 = 2

dict

在实际使用哈希表时，Redis 没有使用 dictht ，而是定义一个 dict 结构体，如下

typedef struct dict {
    dictType *type; /* dict类型，内置不同的hash函数 */
    void *privdata; /* 私有数据，在做特殊hash运算时用 */
    dictht ht[2] ;/* 个Dict包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash时使用 */
    long rehashidx; /* rehash的进度，-1表示未进行 */
    int16_t pauserehash; /* rehash是否暂停，1则暂停，0则继续 */
} dict;

• 在上面这个结构体中，我们发现，type 、privdata 是跟哈希运算有关系的，但是其他三个成员变量，又是用来做什么的呢？为什么又要定义两个 dictht 呢？这跟我们下面要说的 rehash 操作有关系

Dict 的 rehash

前面我们提到，redis 使用链式哈希来解决 hash 冲突问题。但是，链式哈希也存在局限性，那就是随着链表长度的增加，Hash 表在一个位置上查询哈希项的耗时就会增加，从而增加了 Hash 表的整体查询时间，这样也会导致 Hash 表的性能下降。这时，redis 使用 rehash 来解决这个问题。

Redis 如何实现 rehash

Redis 实现 rehash 的基本思路是这样的：

• 首先，Redis 准备了两个哈希表，用于 rehash 时交替保存数据。

  • 前面我们提到，redis 在实际使用时，定义了一个 dict 结构体。这个结构体中有一个数组（*ht[2] *），包含了两个 Hash 表（dictht ） *ht[0] *和 *ht[1] *。

• 其次，在正常服务请求阶段，所有的键值对写入哈希表 ht[0]。

• 接着，当进行 rehash 时，键值对被迁移到哈希表 ht[1]中。

• 最后，当迁移完成后，ht[0]的空间会被释放，并把 ht[1] 的地址赋值给 ht[0]，ht[1] 的表大小设置为 0。这样一来，又回到了正常服务请求的阶段，ht[0] 接收和服务请求，ht[1] 作为下一次 rehash 时的迁移表。

什么时候进行 rehash

• 当我们往 Redis 中写入新的键值对或是修改键值对时，Redis 都会判断下是否需要进行 rehash。而 rehash 的触发条件则是

  • 条件 1 ：ht[0] 承载的元素个数已经超过了 ht[0] 的大小，也即d->ht[0].used >= d->ht[0].size，同时 Hash 表可以进行扩容。
  • 条件 2 ：ht[0] 承载的元素个数，是 ht[0] 的大小的 dict_force_resize_ratio 倍，也即 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio 其中，dict_force_resize_ratio 的默认值是 5。

rehash 的新 size 是多大?

如果是扩容，则新 size 为第一个大于等于 dict.ht[0].used+1 的2n2^n2n 如果是收缩，则新 size 为第一个大于等于 dict.ht[0].used 的 2n2^n2n（不得小于4）

渐进式 rehash

• Hash 表在执行 rehash 时，由于 Hash 表空间扩大，原本映射到某一位置的键可能会被映射到一个新的位置上，因此，很多键就需要从原来的位置拷贝到新的位置。而在键拷贝时，由于 Redis 主线程无法执行其他请求，所以键拷贝会阻塞主线程，这样就会产生rehash 开销。为了降低 rehash 开销，Redis 就提出了渐进式 rehash 的方法。

rehash 的步骤

• 给 ht[1] 分配空间；
• 在 rehash 进行期间，在rehash过程中，新增操作，则直接写入 ht[1]，查询、修改和删除则会在dict.ht[0] 和 dict.ht[1] 依次查找并执行。这样可以确保 ht[0] 的数据只减不增。
• 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把 ht[0] 的所有 key-value 迁移到 ht[1]，从而完成 rehash 操作。

这样就巧妙地把一次性大量数据迁移工作的开销，分摊到了多次处理请求的过程中，避免了一次性 rehash 的耗时操作。

以上就是浅析Redis底层数据结构Dict的详细内容，更多关于Redis数据结构Dict的资料请关注萤火虫技术其它相关文章！