前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Redis 字典结构细谈

Redis 字典结构细谈

作者头像
WindWant
发布2020-10-27 17:21:58
8090
发布2020-10-27 17:21:58
举报
文章被收录于专栏:后端码事

Redis 字典底层基于哈希表实现。

一、哈希表结构

1、dictht:

代码语言:javascript
复制
typedef struct dictht {
  dictEntry **table; //哈希表数组,存储具体的键值对元素,对象类型 dictEntry
  unsigned long size; //哈希表容量
  unsigned long sizemask; //哈希表大小掩码,计算索引使用
  unsigned long used; //已使用容量
} dictht

2、示例数据:

二、哈希表节点

1、dictEntry:

代码语言:javascript
复制
typedef struct dictEntry {
  void *key; //键值对 key
  union{  //键值对 value 三种类型
    void *val;
    uint64_tu64;
    int64_ts64;
  } v;
  struct dictEntry *next;  //下一个节点指针
} dictEntry;

说明:next 为指向下一个节点的指针,是我们熟悉的链表节点结构,单向链表,用于处理键哈希冲突问题。

相同哈希值的键的键值对会以链表的形式存在同一位置。

2、示例数据:

三、Redis 字典

1、dict:

代码语言:javascript
复制
typedef struct dict{
  dictType *type; //类型特定函数
  void *privdata; //私有数据
  dictht ht[2]; //哈希表数组,类型为dictht,ht[0]为实际存储数据使用,ht[1] 为rehash时使用
  int rehashidx; //rehash进度标志,-1 代表当前不在 rehash
} dict

2、示例数据:

四、添加元素

向字典中添加元素主要涉及一下几步操作:

1、计算键值对键的哈希值

hash:dict->type->hashFunction(key)

使用dictType内部的哈希函数得到键哈希值

2、计算需要放入的位置索引

index:hash&dict->ht[0].sizemask

使用上一步计算得到的哈希值与哈希表的sizemask属性进行与操作得到需要放入的位置索引值

3、键冲突解决

没有完美的哈希函数,哈希冲突往往无法避免,当多个键被所引导同一个位置时,这种现象,我们称之为键冲突。

解决间冲突,Redis 采用链地址法,也即将冲突的键值对组成一条链条放到同一个哈希位置上。上面第二节我们介绍过 dictEntry的结构,其中包含一个指向另一个节点的指针next。

这里需要说明的一点是,冲突节点插入时,是插入到链表的头部,这样只需要执行操作一次操作即可,也即时间复杂度为O(1)。

如下图:(k2,v2)与(k1,v1)发生冲突,直接将(k2,v2)插入到链表头部:

五、rehash

rehash过程是在重新规划哈希表占用空间时发生的。

负载因子 load_factor:已保存节点数量(dict.ht[0].used)/ 哈希表容量(dict.ht[0].size)

负载因子用以表名当前哈希表的使用状态,它需要保持在一个合理的范围,以保障资源的最优利用。通常需要适时的对哈希表进行扩展或者收缩来对负载因子进行维护,而这个过程,我们称之为 rehash。

这里涉及到一个问题,就是什么时候需要进行伸缩维护?

1、扩展时机:

当前无bgsave及bgrewriteaop操作,load_factor >= 1

当前存在bgsave及bgrewriteaop操作,load_factor >= 5

Redis服务器通过fork子进程形式执行bgsave及bgrewriteaop操作,此时整个服务的资源耗费较大,为了避免可能发生的rehash带来额外的资源压力,此期间,服务器会调高触发执行扩展操作的负载因子界限。

2、收缩时机:

load_factor < 0.1

3、rehash 基本操作:

a) 为dict.ht[1]分配空间:

空间大小计算如下:

扩展:最小n满足2n >= dict.ht[0].used * 2

收缩:最小n满足2n >= dict.ht[0].used

如下图:ht[0].used = 3,假定无bg相关任务,则h[1]大小需要计算:2n >= 3 * 2 = 6

n = 3,ht[1].size = 23 = 8

b) rehash

对于dict.ht[0] 中的元素,依据dict.ht[1]特性(sizemask)重新计算索引值,并放置到dict.ht[1]中。

c) 当所有元素迁移完毕,释放dict.ht[0],并将dict.ht[1]设置为dict.ht[0],重新在dict.ht[1]上创建空的哈希表。

六、渐进式rehash

所谓渐进式,是针对大数据量字典数据。直接一次性的执行rehash会导致服务资源的集中占用,影响正常的服务响应。因此需要进行分而治之。

这里会用到上面我们介绍的dict字典结构中的 rehashidx属性,用以标识当前rehash进度。

首先将rehashidx置0,标示rehash开始,每次rehash一个元素,rehashidx值增加1,当最终所有元素rehash完成,将rehashidx置-1。

这里需要说明下rehash中对正常的服务请求的处理:

1、删除、查找、更新:

会涉及到两个哈希表(ht[0]、ht[1])操作,如查找元素,首先尝试在ht[0]上查找,找不到,则继续在h[1]上查找。

2、添加

添加元素只会在h[1]上操作,h[0]上只减不增。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-10-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 一、哈希表结构
    • 1、dictht:
      • 2、示例数据:
      • 二、哈希表节点
        • 1、dictEntry:
          • 2、示例数据:
          • 三、Redis 字典
            • 1、dict:
              • 2、示例数据:
              • 四、添加元素
                • 1、计算键值对键的哈希值
                  • 2、计算需要放入的位置索引
                    • 3、键冲突解决
                    • 五、rehash
                      • 1、扩展时机:
                        • 2、收缩时机:
                          • 3、rehash 基本操作:
                          • 六、渐进式rehash
                            • 1、删除、查找、更新:
                              • 2、添加
                              相关产品与服务
                              云数据库 Redis
                              腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
                              领券
                              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档