首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >[Redis] 哈希表的Rehash机制

[Redis] 哈希表的Rehash机制

作者头像
唯一Chat
发布2020-12-21 11:28:33
2.1K0
发布2020-12-21 11:28:33
举报
文章被收录于专栏:陶士涵的菜地陶士涵的菜地

哈希表的完整结构 , 因为他是多个哈希一层层嵌套的 , 所以会是这样的结构

触发rehash的时机

字典类型容量变化过程叫做rehash,需要满足一定的条件才能触发扩容机制 服务器当前没有进行BGWRITEAOF或者BGSAVE命令,且当前键值对个数超过一维数组的大小,才会触发扩容。

如果当前键值对个数超过一维数组大小的五倍,无论是否在进行BGWRITEAOF或者BGSAVE命令,都会强制扩容。 Hash类型扩容后数组的长度为原来的二倍

缩容机制:如果当前键值对个数少于一维数组大小的十分之一,则触发缩容过程。缩容不会考虑当前服务器是否在进行BGWRITEAOF或者BGSAVE命令

渐进式rehash的过程

利用了两个哈希表进行的 , 有点类似数据库的迁移 , 读的时候先读旧库 , 读不到读新库 , 写的时候只写新库 ; 其他旧数据一点点的往新库上搬

当触发扩容的时候,Redis会首先为ht[1] 分配一块内存空间。如果当前字典是一个比较大的字典,那么整个扩容过程的时间复杂度为O(n),直接完整进行扩容机制可能会导致Redis一段时间内停止服务。为了避免停止服务的情况,Redis的设计团队采用了渐进式rehash的策略,每次只对原哈希表中的一小部分进行搬迁,这样渐进式的进行,直到全部键值对都迁移到新的哈希表中。

首先,对于key的查询,我们需要到原来的哈希表中进行查找,如果找到对应的value,直接返回就可以了。如果没有找到,那么只有两种可能,一个是这个键值对已经搬迁到新的哈希表了,另外一种可能是根本就不存在这个键值对,无论是哪种可能,我们都需要再去新哈希表中对他进行查找,如果找到了就返回,如果找不到说明这个键值对不存在。

步骤如下:
1.为字典的备用哈希表分配空间:
如果执行的是扩展操作,那么备用哈希表的大小为第一个大于等于(已用节点个数)*2的2n(2的n次方幂)
如果执行的是收缩操作,那么备用哈希表的大小为第一个大于等于(已用节点个数)的2n
2.在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始(为-1时表示没有进行rehash)。
3.rehash进行期间,每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当一次rehash工作完成之后,程序将rehashidx属性的值+1。同时在serverCron中调用rehash相关函数,在1ms的时间内,进行rehash处理,每次仅处理少量的转移任务(100个元素)。
随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作已完成。

初始化ht[1] 0-7 , ht[0]是旧的有数据 0-3

开始搬迁 , 把就ht[0] 0上的数据 , 搬到了新的ht[1] 的4的部分

rehash完成 , 把ht[0]上的全都搬到ht[1]上了

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

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档