【Redis深入】字典rehash图解

2024-02-07 06:38

本文主要是介绍【Redis深入】字典rehash图解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

引入

在讲rehash之前,我们先回顾一下字典的结构

1.字典dict.h/dict的源码

/** 字典*/
typedef struct dict {// 类型特定函数dictType *type;// 私有数据void *privdata;// 哈希表dictht ht[2];// rehash 索引// 当 rehash 不在进行时,值为 -1int rehashidx; /* rehashing not in progress if rehashidx == -1 */// 目前正在运行的安全迭代器的数量int iterators; /* number of iterators currently running */} dict;

2.哈希表dict.h/dictht的源码

/* This is our hash table structure. Every dictionary has two of this as we* implement incremental rehashing, for the old to the new table. */
/** 哈希表** 每个字典都使用两个哈希表,从而实现渐进式 rehash 。*/
typedef struct dictht {// 哈希表数组dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小掩码,用于计算索引值// 总是等于 size - 1unsigned long sizemask;// 该哈希表已有节点的数量unsigned long used;} dictht;

3.哈希表节点dict.h/dictEntry的源码

/** 哈希表节点*/
typedef struct dictEntry {// 键void *key;// 值union {void *val;uint64_t u64;int64_t s64;} v;// 指向下个哈希表节点,形成链表struct dictEntry *next;} dictEntry;

4.一个普通的字典结构(没有进行rehash)

这里写图片描述

rehash过程图解

1.进行rehash的原因

随着操作的不断进行,哈希表保存的键值对会逐渐的增多或减少,为了让哈希表的负载因子维持在一个合理的范围内,当哈希表保存的键值对数量太多或太少,就对哈希表进行扩展或收缩。

2.rehash的步骤

(1)为字典的ht[1]哈希表分配空间

  • 若是扩展操作,那么ht[1]的大小为>=ht[0].used*2的2^n
  • 若是收缩操作,那么ht[1]的大小为>=ht[0].used的2^n

(2)将保存在ht[0]中的所有键值对rehash到ht[1]中,rehash指重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上。

(3)当ht[0]的所有键值对都迁移到了ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],新建空白的哈希表ht[1],以备下次rehash使用。

3.rehash图解

(1)执行rehash之前的字典

这里写图片描述

(2)ht[0].used的值为4,而4*2=8,大于等于它的2^n是8,所以将ht[1]的大小设置为8

这里写图片描述

(3)将ht[0]的四个键值对都rehash到ht[1]中,这时ht[0]为null

这里写图片描述

(4)释放ht[0],并将ht[1]设置为ht[0],然后为ht[1]分配一个空白的哈希表,哈希表大小由4扩容为8

这里写图片描述

4.扩展与收缩的条件

  • 当以下条件满足任意一个时,程序就会对哈希表进行扩展操作

    • 服务器目前没有执行bgsave或bgrewriteaof命令,并且哈希表的负载因子>=1
    • 服务器目前正在执行bgsave或bgrewriteaof命令,并且哈希表的负载因子>=5
  • 负载因子的计算
    load_factor=ht[0].used/ht[0].size

  • 当负载因子的值小于0.1时,程序就会对哈希表进行收缩操作

渐进式rehash

1.渐进式rehash的原因

整个rehash过程并不是一步完成的,而是分多次、渐进式的完成。如果哈希表中保存着数量巨大的键值对时,若一次进行rehash,很有可能会导致服务器宕机。

2.渐进式rehash的步骤

  • 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表
  • 维持索引计数器变量rehashidx,并将它的值设置为0,表示rehash开始
  • 每次对字典执行增删改查时,将ht[0]的rehashidx索引上的所有键值对rehash到ht[1],将rehashidx值+1。
  • 当ht[0]的所有键值对都被rehash到ht[1]中,程序将rehashidx的值设置为-1,表示rehash操作完成

注:渐进式rehash的好处在于它采取分为而治的方式,将rehash键值对的计算均摊到每个字典增删改查操作,避免了集中式rehash的庞大计算量。

3.渐进式rehash图解

  • 渐进式rehash之前的字典

这里写图片描述

  • rehash索引0上的键值对

这里写图片描述

  • rehash索引1上的键值对

这里写图片描述

  • rehash索引2上的键值对

这里写图片描述

  • rehash索引3上的键值对

这里写图片描述

  • 渐进式rehash完成

这里写图片描述



本人才疏学浅,若有错,请指出,谢谢!
如果你有更好的建议,可以留言我们一起讨论,共同进步!
衷心的感谢您能耐心的读完本篇博文!

参考书籍:《Redis设计与实现(第二版)》—黄健宏

 

 

 

文章转自: https://blog.csdn.net/baiye_xing/article/details/76088425

这篇关于【Redis深入】字典rehash图解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/686829

相关文章

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

Redis 中的热点键和数据倾斜示例详解

《Redis中的热点键和数据倾斜示例详解》热点键是指在Redis中被频繁访问的特定键,这些键由于其高访问频率,可能导致Redis服务器的性能问题,尤其是在高并发场景下,本文给大家介绍Redis中的热... 目录Redis 中的热点键和数据倾斜热点键(Hot Key)定义特点应对策略示例数据倾斜(Data S

redis+lua实现分布式限流的示例

《redis+lua实现分布式限流的示例》本文主要介绍了redis+lua实现分布式限流的示例,可以实现复杂的限流逻辑,如滑动窗口限流,并且避免了多步操作导致的并发问题,具有一定的参考价值,感兴趣的可... 目录为什么使用Redis+Lua实现分布式限流使用ZSET也可以实现限流,为什么选择lua的方式实现

Redis中管道操作pipeline的实现

《Redis中管道操作pipeline的实现》RedisPipeline是一种优化客户端与服务器通信的技术,通过批量发送和接收命令减少网络往返次数,提高命令执行效率,本文就来介绍一下Redis中管道操... 目录什么是pipeline场景一:我要向Redis新增大批量的数据分批处理事务( MULTI/EXE

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

Redis中的常用的五种数据类型详解

《Redis中的常用的五种数据类型详解》:本文主要介绍Redis中的常用的五种数据类型详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Redis常用的五种数据类型一、字符串(String)简介常用命令应用场景二、哈希(Hash)简介常用命令应用场景三、列表(L

Redis解决缓存击穿问题的两种方法

《Redis解决缓存击穿问题的两种方法》缓存击穿问题也叫热点Key问题,就是⼀个被高并发访问并且缓存重建业务较复杂的key突然失效了,无数的请求访问会在瞬间给数据库带来巨大的冲击,本文给大家介绍了Re... 目录引言解决办法互斥锁(强一致,性能差)逻辑过期(高可用,性能优)设计逻辑过期时间引言缓存击穿:给

一文带你深入了解Python中的GeneratorExit异常处理

《一文带你深入了解Python中的GeneratorExit异常处理》GeneratorExit是Python内置的异常,当生成器或协程被强制关闭时,Python解释器会向其发送这个异常,下面我们来看... 目录GeneratorExit:协程世界的死亡通知书什么是GeneratorExit实际中的问题案例

Redis中如何实现商品秒杀

《Redis中如何实现商品秒杀》:本文主要介绍Redis中如何实现商品秒杀问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录技术栈功能实现步骤步骤一:准备商品库存数据步骤二:实现商品秒杀步骤三:优化Redis性能技术讲解Redis的List类型Redis的Set

Redis如何实现刷票过滤

《Redis如何实现刷票过滤》:本文主要介绍Redis如何实现刷票过滤问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录引言一、概述二、技术选型三、搭建开发环境四、使用Redis存储数据四、使用SpringBoot开发应用五、 实现同一IP每天刷票不得超过次数六