请选择 进入手机版 | 继续访问电脑版

[Redis] Redis字典实现、Hash键冲突及渐进式rehash详解

[复制链接]
查看142 | 回复35 | 2021-9-14 01:50:43 | 显示全部楼层 |阅读模式
目次

本笔记参考《Redis计划 与实现》 P24~ 37

Redis字典实现

哈希表节点布局

  1. typedef struct dictEntry
  2. {
  3. // 键
  4. void *key;
  5. // 值 : 可以是一个指针,或者是一个uint64/int64 的整数
  6. union {
  7. void *val;
  8. uint64_t u64;
  9. int64_t s64
  10. } v;
  11. // 指向下一个哈希表节点,形成链表 : 该指针可以将多个哈希值相同的键值对连接在一起,以此解决键冲突的问题。
  12. struct dictEntry *next;
  13. } dictEntry;
复制代码

哈希表布局

  1. typedef struct dictht
  2. {
  3. // 哈希表数据
  4. dictEntry **table;
  5. // 哈希表集合大小
  6. unsigned long size;
  7. // 哈希表大小掩码,用于计算索引值
  8. // 总是等于 size - 1
  9. unsigned long sizemask;
  10. // 哈希表已有节点数量
  11. unsigned long used;
  12. } dictht;
复制代码

字典

  1. typedef struct dict
  2. {
  3. // 类型特定函数
  4. dicType *type;
  5. // 私有数据
  6. void *privdata;
  7. // 哈希表
  8. dictht ht[2];
  9. // rehash 索引
  10. // 当rehash不在进行时, 值为-1
  11. int rehashidx;
  12. } dict;
复制代码

type属性和privdata属性针对不同范例 的键值对,为多态字典而设置。
ht是包含两个项的数组,每个元素都是一个dictht哈希表,一样平常 环境 下字典之是哟个ht[0],ht[1]会在对ht[0]举行 rehash的时间 使用 。
rehashidx记录了rehash如今 的进度,假如 如今 没有在举行 rehash,值为-1。

哈希算法

  • 使用 字典设置的哈希函数,计算key的hashvalue

hash = dict->type->hashFunction(key);

  • 使用 哈希表的sizemask属性和哈希值,计算出索引值
  • 根据不同的环境 ,ht[x]可以是ht[0]或ht[1]

index = hash & dict->ht[x].sizemask;

redis使用 的是MurmurHash算法,长处 是:输入的键是有规律的时间 ,算法仍旧 能给出很好的随机分布性,计算速率 也快。

办理 hash冲突

当有两个或以上的key分配到了hash table数组的同一个index上,称为发生了collision。
Redis采用链地址法办理 冲突,每个hash table节点都有一个next指针,多个hash table节点可以用next指针构成一个单向链表。为了速率 思量 ,程序总是会将新节点插入到链表头位置。

rehash

随着操作不断实行 ,哈希表保存的key value对会渐渐 增长 和减少。哈希表有一个统计参数load factor,即负载因子,公式如下:

  1. # 负载因子 = 哈希表已经保存的节点数量 / 哈希表大小
  2. load_factor = ht[0].used / ht[0].size;
复制代码

为了维持负载因子在一个合理的范围,程序会对哈希表的大小举行 相应的扩展或紧缩 ,条件如下:

1、服务器如今 没有实行 BGSAVE下令 或者BGREWRITEAOF下令 ,并且哈希表的负载因子 >= 1

2、服务器正在实行 BGSAVE下令 或者BGREWRITEAOF下令 ,且负载因子 >= 5

  • 在实行 BGSAVE下令 或者BGREWRITEAOF下令 过程中,Redis必要 创建当前服务器进程 的子进程 ,大多的OS采用写时复制技术优化子进程 的使用 服从 ,以是 子进程 存在期间,**服务器会进步 实行 扩展操作的负载因子,避免在子进程 存在期间举行 哈希表的扩展操作,避免不必要的内存写入操作,最大限度节省 内存。**当负载因子小于0.1时,程序自动 对哈希表举行 紧缩 操作。
  • 此时就会举行 扩展紧缩 ,规则如下:
  • 这里就是rehash(重新散列)操作了:
  • 1、为字典的ht[1]哈希表分配内存空间,空间大小取决于要实行 的操作,以及ht[0]当前包含的键值对数量 (ht[0].used)
  • 假如 是扩展操作,ht[1]的大小为 >= ht[0].used * 2的 2的幂次方
  • 假如 是紧缩 操作,ht[1]的大小为 >= ht[0].used 的 2的幂次方
  • 2、将保存在ht[0]中的全部 键值对rehash到ht[1]上:即重新计算key的hashValue以及indexValue,然后将键值对放到ht[1]的指定位置
  • 3、当ht[0]包含的全部 键值对都迁徙 到ht[1]之后,ht[0]变为空表,开释 ht[0],将ht[1]置为ht[0],在ht[1]重新分配一个空缺 的哈希表,为下一次rehash做准备

渐进式hash

rehash的动作并不是一次性集中完成的,而是分多次渐进完成。
假如 哈希表中村的键值对数量 很多,一次性将键值对全部rehash到ht[1]的计算量非常 巨大 ,大概 会导致服务器在一段时间内克制 服务。
渐进式rehash采取分而治之的方法,将rehash键值对所必要 的计算工作分摊到每次对字典的CRUD操作上,从而避免了集中式rehash带来的巨大 计算量。
详细 步骤如下:
1、为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表
2、在字典中维护一个索引计数器:rehashidx,将值设置为0,表示rehash工作正式开始。
3、在rehash举行 期间,每次对字典的CRUD操作,程序除了实行 指定操作以外,顺带将ht[0]哈希表在rehashidx索引上的全部 键值对rehash到ht[1]上,当rehash操作完成后,程序将rehashidx值++
4、重复迭代操作实行 后,ht[0]的数据全部rehash到ht[1]上,将rehashidx设为-1,表明rehash操作已经完成

必要 留意 的地方
在rehash的过程中,对于字典的删除、查找、更新操作会在两个哈希表上实行 。如想要查找一个键,如今 ht[0]中找,没有找到再去ht[1]
对于insert操作来说,新添加到字典的键值对会同等 保存到ht[1]中,不然还得多一次搬运。

到此这篇关于Redis字典实现、Hash键冲突以及渐进式rehash的文章就先容 到这了,更多干系 Redis 渐进式rehash内容请搜刮 脚本之家从前 的文章或继续欣赏 下面的干系 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

avatar 钟情695 | 2021-9-14 04:30:17 | 显示全部楼层
东方不败外加灭绝师太啊!
回复

使用道具 举报

avatar 123457875 | 2021-9-18 08:15:25 | 显示全部楼层
admin楼主练了葵花宝典吧?
回复

使用道具 举报

avatar fys24680 | 2021-9-18 23:11:49 | 显示全部楼层
十分赞同admin楼主!
回复

使用道具 举报

avatar 恋爱的棉被缀 | 2021-9-25 20:52:07 | 显示全部楼层
赞一个!
回复

使用道具 举报

avatar V刘晨曦 | 2021-9-26 13:43:35 | 显示全部楼层
看在admin楼主的面子上,认真回帖!
回复

使用道具 举报

avatar 123457665 | 2021-9-26 23:29:44 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,影视频道的网站所有电影和连续剧都可以免费看的。访问地址:http://tv.mxswl.com
回复

使用道具 举报

avatar 阿威来自山西 | 2021-9-27 21:17:58 | 显示全部楼层
admin楼主是好人!
回复

使用道具 举报

avatar 123456825 | 2021-9-29 10:21:43 | 显示全部楼层
admin楼主该去看心理医生了!
回复

使用道具 举报

avatar 李焕发 | 2021-10-1 22:11:16 | 显示全部楼层
收藏了,admin楼主加油!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则