Redis面试题系列:讲一讲 rehash 的过程

2024-04-09 20:58

本文主要是介绍Redis面试题系列:讲一讲 rehash 的过程,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

字典是什么

字典,又称为符号表(Symbol table),关联数组(associative array)或映射(map),是一种用来保存键值对(key-value-pair)的抽象数据结构。字典中的键不会重复。
接下来会分析Redis中字典的实现方式,哈希算法,解决键冲突的方法及rehash的过程。文中展示的 Redis 源码均来自 3.0.4 版本。

字典的实现

Redis 的字典使用哈希表作为底层实现,一个哈希表里面可以有多个结点,每个结点保存了一个键值对。

typedef struct dictht {// hash表结点数组// 每个 table[i] 其实是一个链表的头节点dictEntry **table;// hash表结点数组的大小,总是为 2^nunsigned long size;// 用于计算索引值的掩码,总是等于 size-1unsigned long sizemask;// 该hash表中的结点数量unsigned long used;
} dictht;

table 是一个数组,数组中每个元素其实都是一个链表的头指针。链表中每个结点都保存着一个键值对。
size 属性记录了table数组的大小,Redis的扩容和收缩机制,保证了 size 总是为 2^n。
sizemask 是用于计算索引值的掩码,总是等于 size-1。
used 记录了哈希表中结点的数量,即所有链表中结点的总数。

哈希算法

当要将一个新的键值添加到字典里面时,程序会先先根据键值对的键计算出哈希值和索引值,然后再根据索引值,将包含新键值对的节点放到哈希表数组(table)的指定索引上面。
Redis 通常使用 MurmurHash2 计算键的哈希值。该算法由 Austin Appleby 于 2008 年发明,这种算法的优点在于,即使输入的键是有规律的,算法仍能给出一个很好的随机分布性,并且算法的计算速度也非常快。
而索引值计算则非常简单:将哈希值和 dictht::sizemask 做与运算的结果即为索引值。
比如,哈希值为 6,sizemask 为 3,则索引值为 6&3 = 2。

解决键冲突

当有两个或以上数量的键被分配到了同一个索引上面时,我们称这些键发生了冲突。比如上图中 k2 和 k0。
Redis 使用链地址法解决冲突。每个节点都有一个 next 指针,多个冲突的结点通过 next 指针构成一个单向链表,这样就解决了键冲突的问题。

Rehash

负载因子:哈希表中单向链表的平均长度。

随着增删操作的进行,Redis 通过 rehash 操作将负载因子维持在一个合理的范围内。Rehash操作分为两种:

  • 扩展:当负载因子较大时,应该扩大 dictht::size 以降低平均长度,加快查询速度。
  • 收缩:当负载因子较小时,应该减小 dictht::size 以减少对内存的浪费。
typedef struct dict {//哈希表dictht ht[2];//rehashidx 记录了rehash 的进度。//当没有进行 rehash 时为 -1。int rehashidx; // 其他数据成员....
};

rehash 过程如下:

  • 为字典的ht[1]哈希表分配空间,ht[1].size 的大小取决于要执行的操作,以及ht[0].used 的值。
    • 如果执行的是扩展操作:那么 ht[1].size 为最小的且不小于 ht[0].used*2 的 2 的 n 次方。比如 ht[0].size 为 5,那么 ht[1].size 为 16。
    • 如果执行的是收缩操作:那么 ht[1].size 为最小的且不小于 ht[0].used 的 2 的 n 次方。比如 ht[0].size 为 5,ht[1].size 为 8。
  • 将 ht[0] 中所有键值对移动到 ht[1] 中:根据 ht[1].sizemask 重新计算哈希值与索引值;根据新的索引值将键值对插入到 ht[1] 中;将键值对从 ht[0] 中删除。
  • 当 ht[0] 中所有键值对移动到 ht[1] 之后开始执行清理工作:释放 ht[0] 占用的内存;将 ht[1] 赋值给 ht[0];为 ht[1] 分配一个空的哈希表,为下一次 rehash 做准备。
    在这里插入图片描述

渐进式 rehash

扩展或收缩哈希表需要将 ht[0] 的所有键值对移动到 ht[1] 当中。这个动作是分多次,渐进式地完成的。原因在于当键值对过多时,一次性移动所有键值对会导致Redis在一段时间内无法对外提供服务
渐进式 rehash 步骤如下:

  • 为 ht[1] 分配空间,此时字典同时存在两个哈希表。
  • 将 dict::rehashidx 置为 0,rehash 工作正式开始。
  • 在 rehash 进行期间,每次对字典执行增删改查操作时,程序在执行指定操作之外,还会将 ht[0] 在 rehashidx 索引上的所有键值对rehash 到 ht[1],然后将 rehashidx 的值加一。
  • 随着字典操作的不断执行,ht[0] 的所有键值对最终会全部移动到 ht[1],此时程序会将 rehashidx 设为 -1,表示 rehash 操作已完成。

特别的,在渐进式 rehash 操作过程中,因为同时存在两个哈希表,所以字典的删除,查找,更新操作会在两个哈希表上进行。程序会先尝试在 ht[0] 中寻找目标键值对,如果没有找到则会在 ht[1] 再次进行寻找,然后进行具体操作。但是新增操作只会在 ht[1] 上进行,这保证了 ht[0] 中的已经被清空的单向链表不会新增元素。

这篇关于Redis面试题系列:讲一讲 rehash 的过程的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

JSON Web Token在登陆中的使用过程

《JSONWebToken在登陆中的使用过程》:本文主要介绍JSONWebToken在登陆中的使用过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录JWT 介绍微服务架构中的 JWT 使用结合微服务网关的 JWT 验证1. 用户登录,生成 JWT2. 自定义过滤

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

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

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

SpringCloud之LoadBalancer负载均衡服务调用过程

《SpringCloud之LoadBalancer负载均衡服务调用过程》:本文主要介绍SpringCloud之LoadBalancer负载均衡服务调用过程,具有很好的参考价值,希望对大家有所帮助,... 目录前言一、LoadBalancer是什么?二、使用步骤1、启动consul2、客户端加入依赖3、以服务

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