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

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

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

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

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

Dict 的结构

Dict 由三部分组成,分别是:dictdicthtdicEntry

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的资料请关注萤火虫技术其它相关文章!

点赞(159) 打赏

评论列表 共有 0 条评论

暂无评论

微信小程序

微信扫一扫体验

立即
投稿

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部