<返回更多

一文读懂Redis的dict字典数据结构

2022-04-18    小一明日记
加入收藏

概览

redis 本质是 K-V 键值对数据库,底层通过字典 dict 存储键值映射关系,除此之外,dict 还作为 Redis hash 结构底层的实现之一。

讨论 Redis 的数据结构,可以从两个层面出发。

第一个层面从使用者角度出发,即 Redis 暴露给外部调用的 Api:

•string

•list

•hash

•set

•sorted set

第二个层面是 Redis 的内部实现角度出发,是更为底层的数据结构实现:

•dict

•sds

•ziplist

•quicklist

•skiplist

Redis 这么做的目的还是基于高性能的考虑,在不同的场景下使用不同的底层数据结构实现,最大程度提升内存操作的效率。

例如当 sorted set,hash 存储的数据规模较小时,底层都是通过 ziplist 实现,而当数据规模达到一定量时,sorted set 会转换成 dict + skiplist 的底层实现,hash 会转换成 dict 的底层实现。

本文主要讨论是 Redis 关于 dict 这一底层数据结构的实现原理。

实现

dict 的实现与 JAVA jdk 中 hashmap 的实现有许多相似之处:

•关于哈希映射,key 的索引计算公式为 hash & (n - 1),其中 hash 为 key 对应的 hash 值(Redis 通过 MurmurHash 算法计算得出),n 为哈希数组的大小•关于哈希冲突,Redis 同样也是采用链地址法解决冲突

dict 在扩缩容的情况下,采用的是渐进式的 rehash 方式,这是它的特殊之处,下文会主要讲到。

dict 的数据结构如下:

•type属性是一个指向dictType结构的指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数,Redis会为用途不同的字典设置不同的类型特定函数

•privdata属性则保存了需要传给那些类型特定函数的可选参数

•ht[2] 数组中存放了两张哈希表,只有在 rehash 的过程中,ht[0] ht[1] 才都有效;正常情况下只有 ht[0] 有效,ht[1] 中没有任何数据

•rehashidx 用来表示 rehash 过程到了哪一个索引位置,正常情况下 rehashidx = -1,表示当前没有进行 rehash

一文读懂Redis的dict字典数据结构

 

dictht 的数据结构如下:

•dictEntry 数组,用来存放键值对

•size 表示当前 dictEntry 数组的大小

•sizemask,值为 size - 1,在计算 key 的索引位置时用到, index = hash & sizemask

•used 记录现有 dict 的数据个数

一文读懂Redis的dict字典数据结构

 

正常情况下,dict 整体的数据结构如下图所示:

一文读懂Redis的dict字典数据结构

 

rehash

随着操作不断执行,哈希表中的键值对会逐渐增加或减少,为了让哈希表的负载因子(负载因子 = 已保存节点数量/哈希表大小)维持在一个合理的范围内,当哈希表中节点数量过多或者过少时,Redis 会对哈希表进行相应的扩容或缩容,这一过程称为 rehash。

在 rehash 操作开始前,首先要为哈希表 ht[1] 分配内存,ht[1] 之前一直是空闲状态,终于要派上用场了,具体内存分配策略如下:

•如果是扩容操作,ht[1]的大小为第一个大于等于ht[0].used*2的2^n(2的n次方幂),举个例子 ht[0].used = 5,触发了扩容操作,即 ht[1].size = 5 * 2 = 10,但 10 不符合 2^n 要求,则继续往下找到第一个符合要求的数 16,即 ht[1].size = 16

•如果是缩容操作,ht[1]的大小为第一个大于等于ht[0].used的2^n(2的n次方幂),举个例子 ht[0].used = 5,触发了缩容操作,则 ht[1].size = 8

ht[1] 分配完内存之后,接着进行如下操作:

•将 ht[0] 的中的节点重新计算哈希值和索引值,映射到 ht[1] 上

•当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备

哈希表触发扩容的时机如下:

•服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于1

•服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于5,这么做的原因是避免在子进程存在期间进行哈希表扩容操作,从而避免不必要的内存写入操作,最大限度节省内存

负载因子的计算公式:

一文读懂Redis的dict字典数据结构

 

当负载因子小于 0.1 时,触发缩容操作。

渐进式rehash

值得注意的是 rehash 的过程,Redis 并不是一次性将所有元素集中式地 rehash 到 ht[1] 中,而是分多次,渐进式地完成。

这么做的原因是如果当哈希表中存放的键值对数量如果是千万级,甚至亿级,一次性完成所有键值的 rehash 操作,可能会导致 Redis 一段时间内对外不可用。

以下是渐进式 rehash 的具体步骤:

•为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表

•在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始

•在rehash进行期间,每次对字典执行添删改查操作时,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成之后,程序将rehashidx属性的值增一

•随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1,表示此次rehash操作已完成

下面展示一次完整 rehash 的过程,首先初始化 dict,准备开始 rehash;

一文读懂Redis的dict字典数据结构

 

rehashidx = 0,rehash 索引0对应的键值对,rehashidx + 1;

一文读懂Redis的dict字典数据结构

 

rehashidx = 1,rehash 索引1对应的键值对,rehashidx + 1;

一文读懂Redis的dict字典数据结构

 

rehashidx = 2,rehash 索引2对应的键值对,rehashidx + 1;

一文读懂Redis的dict字典数据结构

 

最终完成 rehash 过程。

一文读懂Redis的dict字典数据结构

 

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>