【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)(二)

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)

【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)(一)https://developer.aliyun.com/article/1471152


dictEntry模型

Redis的dictEntry 结构体不仅包含了指向键和值的指针,还巧妙地设计了一个指向下一个哈希项的指针next。这个指针 next 的存在,使得当多个键的哈希值发生冲突时,Redis 能够将这些键以链表的形式连接在一起,从而有效地解决了哈希冲突问题。



  • key:用于存储键值对中键的部分
  • value:承载着键值对中对应的值。既可以是一个指向其他数据结构的指针,也可以是一个uint64_t类型的无符号64位整数,或是一个int64_t类型的有符号64位整数。
  • next:扮演着链接哈希表节点的角色,它是一个指向另一个哈希表节点的指针。当多个键值对的哈希值相同时,即发生了所谓的键冲突,这些具有相同哈希值的键值对会通过next指针串联起来,形成一个链表结构。

通过设计哈希函数和链表的维护策略,哈希表能够在平均情况下实现近乎O(1)的查找、插入和删除操作。

dictEntry的结构体源码

dictEntry结构体表示字典中的一个键值对,源码如下所示:

c

复制代码

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    /* Next entry in the same hash bucket. */    
    struct dictEntry *next;    
};
typedef struct {
    void *key;
    dictEntry *next;
} dictEntryNoValue;
dictEntry **ht_table[2]

dictEntry **ht_table[2]:一个包含两个项的数组,其中每个项都代表一个dict哈希表结构。



在正常情况下,我们主要使用ht[0]这个哈希表进行数据存储和检索操作。而ht[1]哈希表的存在,主要是为了在需要对ht[0]进行rehash操作时提供一个临时的存储空间。

两个哈希表支持rehashing

在 Redis 中,当哈希表的大小需要调整时(例如,因为哈希表已满或空闲空间太多),它不会一次性重新分配整个哈希表,而是会同时使用两个哈希表:一个旧的和一个新的,类似于COW模式进行处理,Copy And Write机制。

随着键值对的插入和删除,旧的哈希表中的数据会逐渐迁移到新的哈希表中,直到旧的哈希表为空,然后旧的哈希表会被释放,新的哈希表成为主哈希表。接下来我们要开始分析和研究hash的机制和原理、最后到了对应的rehashing能力。

哈希算法

我们先来看一下哈希算法,当需要将一个新的键值对添加至字典时,程序会首先根据该键值对的键进行哈希计算,得出相应的哈希值。随后,利用这个哈希值,进一步计算出在哈希表数组中的具体索引位置。

计算哈希值和索引值

使用字典设置的哈希函数,计算键key的哈希值,使用哈希表的mask值和size值,计算出素引值,根据情况不同,ht[x]可以是ht[0]或者ht[1]。

c

复制代码

#define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp))
#define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)

上面定义的C语言的两个宏通常一起使用。

c

复制代码

#define dictHashKey(d, key) ((d)->type->hashFunction(key))
#define dictBuckets(d) (DICTHT_SIZE((d)->ht_size_exp[0])+DICTHT_SIZE((d)->ht_size_exp[1]))
#define dictSize(d) ((d)->ht_used[0]+(d)->ht_used[1])

当想要计算一个键值对的哈希值对应的哈希表索引时,会先使用哈希函数计算出一个原始的哈希值,然后使用 DICTHT_SIZE_MASK(exp) 宏将这个哈希值限制在哈希表大小的范围内。这样,就可以确保计算出的索引不会超出哈希表的边界。最终,将包含新键值对的哈希表节点精准地放置在哈希表数组指定索引的位置上。

案例分析

举个例子,对于下图所示的字典来说,如果我们要将一个键值对w添加到字典里面:


那么程序会先使用语句:#define dictHashKey(d, key) ((d)->type->hashFunction(key)),计算键w的哈希值。假设计算得出的哈希值为100,那么程序会继续使用语句:#define dictBuckets(d) (DICTHT_SIZE((d)->ht_size_exp[0])+DICTHT_SIZE((d)->ht_size_exp[1])),计算出键w的索引值6,这表示包含键值对w的节点应该被放置到哈希表数组的索引6位置上。

解决键冲突

当多个键被哈希函数映射到哈希表数组的同一索引位置时,这种现象被称为键冲突。

链地址法

在Redis的哈希表实现中,采用了链地址法来有效处理这种冲突。每个哈希表节点都包含一个next指针,使得多个哈希表节点能够通过next指针串联成一个单向链表。因此,当多个键被分配到相同的索引位置时,这些节点可以通过这个单向链表相互连接,从而巧妙地解决了键冲突问题。


以图示为例,假设我们拥有一个哈希表,并且程序需要将键值对w插入其中。经过哈希函数的计算,我们得知w的索引值为4。然而,在这个特定的索引位置,已存在其他键(如cd),这就引发了键冲突问题。

Rehash操作和处理执行

为了确保哈希表的负载因子维持在一个适宜的水平,程序会根据哈希表当前的键值对数量来灵活调整其大小,这种动态调整的策略有助于确保哈希表始终保持在高效运行的状态。

扩展和收缩

扩展和收缩哈希表的工作可通过执行rehash(重新散列)操作得以实现。在此过程中,字典巧妙地利用ht[0]和ht[1]这两个哈希表来共同存储键值对,确保了操作的顺畅进行。当满足以下任一条件时,程序将自动触发哈希表的扩展操作:

  • 【键值对数量过多】导致负载因子偏高时,程序会执行扩展操作,增大哈希表容量,以提高查询效率并避免过多的冲突。
  • 【键值对数量过少】负载因子偏低,程序则会进行收缩操作,减小哈希表的大小,以节省内存资源。
负载因子

负载因子 = 即键值对数量/哈希表大小。

c

复制代码

load_factor = ht[0/1].used / ht[0/1].size
案例分析
  • 哈希表的大小为6,包含6个键值对的哈希表来说,这个哈希表的负载因子为:6/6 =1,结果为1。
  • 哈希表的大小为100,包含200个键值对的哈希表来说,这个哈希表的负载因子为:200 / 100=2
  • 哈希表的大小为100,包含50个键值对的哈希表来说,这个哈希表的负载因子为:50 / 100=0.5
RDB和AOF与Rehash的关系

Redis在执行BGSAVE或BGREWRITEAOF命令时,会根据子进程的存在与否调整哈希表扩展操作的负载因子阈值。这主要是为了避免在子进程运行时进行不必要的哈希表扩展,进而减少内存写入,提高内存利用效率。

  • 未执行BGSAVE或BGREWRITEAOF命令,并且哈希表的负载因子达到或超过1时,程序会自动启动哈希表的扩展操作。
  • 正在执行BGSAVE或BGREWRITEAOF命令,且哈希表的负载因子不低于5,程序将自动触发哈希表的扩展流程。

哈希表执行rehash的步骤

  1. 分配h1的哈希表空间:当哈希表需要扩容时,为ht[1]分配新的存储空间,其大小是经过精确计算的,确保至少是当前ht[0]中键值对数量(即ht[0].used的值)的两倍,并且是一个2的n次方幂。
  2. Rehash重新散列,这一过程涉及到将ht[0]中所有的键值对,按照新的哈希算法计算出的哈希值和索引值,精确无误地迁移至ht[1]中。
  3. 数据键值转移:所有键值对成功从ht[0]转移至ht[1]
  4. 释放原有哈希表空间:立即释放ht[0]占用的内存空间,以优化内存使用。

最后,将ht[1]提升为新的ht[0],并初始化一个新的空白哈希表作为新的ht[1],以备将来可能再次触发的重新散列操作。


执行rehash的时候业务操作

在进行rehash操作时,字典的删除、查找和更新等操作都需要在这两个哈希表上进行,注意没有新增哦!具体来说,当我们需要在字典中查找一个键时,程序会首先在ht[0]中进行搜索。如果未能在ht[0]中找到相应的键,程序则会继续转向ht[1]进行查找,以确保不会遗漏任何可能的键值对。


注意,在rehash操作进行的过程中,所有新添加的键值对都会被统一存储于ht[1]哈希表中,而ht[0]则不再承担新键值对的添加任务

最后总结

字典是Redis实现多样化功能的核心组件,尤其在数据库和哈希键的构造中发挥着至关重要的作用。Redis精心设计了其字典结构,以哈希表作为基石,确保高效且稳健的数据存取。

  • 双哈希表:每个Redis字典都巧妙地配备了两个哈希表,一个负责日常运作,而另一个则专门用于rehash操作,这种双表机制显著提升了字典在数据变动时的性能表现。
  • 解决冲突:在哈希表中,为了解决这一冲突,Redis巧妙地运用了next指针机制。它将新键值对w对应的节点通过next指针链接到已存在的d节点之前,从而构建了一个链表结构。通过这种方式,Redis不仅有效地解决了键冲突问题,还保证了哈希表在数据插入时的灵活性和高效性。
  • Rehash控制:当哈希表需要进行扩展或收缩以适应数据量的变化时,Redis并非一蹴而就地完成整个rehash过程。相反,它采取了渐进式的策略,逐步将旧哈希表中的键值对迁移到新表中,从而确保了rehash操作对系统性能的影响最小化。
相关文章
|
6月前
|
传感器 人工智能 物联网
穿戴科技新风尚:智能服装设计与技术全解析
穿戴科技新风尚:智能服装设计与技术全解析
531 85
|
6月前
|
人工智能 API 语音技术
HarmonyOS Next~鸿蒙AI功能开发:Core Speech Kit与Core Vision Kit的技术解析与实践
本文深入解析鸿蒙操作系统(HarmonyOS)中的Core Speech Kit与Core Vision Kit,探讨其在AI功能开发中的核心能力与实践方法。Core Speech Kit聚焦语音交互,提供语音识别、合成等功能,支持多场景应用;Core Vision Kit专注视觉处理,涵盖人脸检测、OCR等技术。文章还分析了两者的协同应用及生态发展趋势,展望未来AI技术与鸿蒙系统结合带来的智能交互新阶段。
364 31
|
6月前
|
编解码 监控 网络协议
RTSP协议规范与SmartMediaKit播放器技术解析
RTSP协议是实时流媒体传输的重要规范,大牛直播SDK的rtsp播放器基于此构建,具备跨平台支持、超低延迟(100-300ms)、多实例播放、高效资源利用、音视频同步等优势。它广泛应用于安防监控、远程教学等领域,提供实时录像、快照等功能,优化网络传输与解码效率,并通过事件回调机制保障稳定性。作为高性能解决方案,它推动了实时流媒体技术的发展。
331 5
|
6月前
|
存储 人工智能 索引
Python数据结构:列表、元组、字典、集合
Python 中的列表、元组、字典和集合是常用数据结构。列表(List)是有序可变集合,支持增删改查操作;元组(Tuple)与列表类似但不可变,适合存储固定数据;字典(Dictionary)以键值对形式存储,无序可变,便于快速查找和修改;集合(Set)为无序不重复集合,支持高效集合运算如并集、交集等。根据需求选择合适的数据结构,可提升代码效率与可读性。
|
6月前
|
数据采集 机器学习/深度学习 存储
可穿戴设备如何重塑医疗健康:技术解析与应用实战
可穿戴设备如何重塑医疗健康:技术解析与应用实战
223 4
|
6月前
|
机器学习/深度学习 人工智能 自然语言处理
AI技术如何重塑客服系统?解析合力亿捷AI智能客服系统实践案例
本文探讨了人工智能技术在客服系统中的应用,涵盖技术架构、关键技术和优化策略。通过感知层、认知层、决策层和执行层的协同工作,结合自然语言处理、知识库构建和多模态交互技术,合力亿捷客服系统实现了智能化服务。文章还提出了用户体验优化、服务质量提升和系统性能改进的方法,并展望了未来发展方向,强调其在客户服务领域的核心价值与潜力。
320 6
|
6月前
|
存储 NoSQL 算法
Redis分片集群中数据是怎么存储和读取的 ?
Redis集群采用的算法是哈希槽分区算法。Redis集群中有16384个哈希槽(槽的范围是 0 -16383,哈希槽),将不同的哈希槽分布在不同的Redis节点上面进行管理,也就是说每个Redis节点只负责一部分的哈希槽。在对数据进行操作的时候,集群会对使用CRC16算法对key进行计算并对16384取模(slot = CRC16(key)%16383),得到的结果就是 Key-Value 所放入的槽,通过这个值,去找到对应的槽所对应的Redis节点,然后直接到这个对应的节点上进行存取操作
|
6月前
|
监控 负载均衡 安全
静态IP代理与动态IP代理:提升速度与保障隐私的技术解析
本文探讨了静态IP代理和动态IP代理的特性和应用场景。静态IP代理通过高质量服务提供商、网络设置优化、定期更换IP与负载均衡及性能监控提升网络访问速度;动态IP代理则通过隐藏真实IP、增强安全性、绕过封锁和提供独立IP保障用户隐私。结合实际案例与代码示例,展示了两者在不同场景下的优势,帮助用户根据需求选择合适的代理服务以实现高效、安全的网络访问。
211 1
|
10月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
217 59
|
3月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
47 0
栈区的非法访问导致的死循环(x64)

推荐镜像

更多
  • DNS