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

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

【专栏简介】

随着数据需求的迅猛增长,持久化和数据查询技术的重要性日益凸显。关系型数据库已不再是唯一选择,数据的处理方式正变得日益多样化。在众多新兴的解决方案与工具中,Redis凭借其独特的优势脱颖而出。

【技术大纲】

为何Redis备受瞩目?原因在于其学习曲线平缓,短时间内便能对Redis有初步了解。同时,Redis在处理特定问题时展现出卓越的通用性,专注于其擅长的领域。深入了解Redis后,您将能够明确哪些任务适合由Redis承担,哪些则不适宜。这一经验对开发人员来说是一笔宝贵的财富。

在这个专栏中,我们将专注于Redis的6.2版本进行深入分析和介绍。Redis 6.2不仅是我个人特别偏爱的一个版本,而且在实际应用中也被广泛认为是稳定性和性能表现都相当出色的版本

【专栏目标】

本专栏深入浅出地传授Redis的基础知识,旨在助力读者掌握其核心概念与技能。深入剖析了Redis的大多数功能以及全部多机功能的实现原理,详细展示了这些功能的核心数据结构和关键算法思想。读者将能够快速且有效地理解Redis的内部构造和运作机制,这些知识将助力读者更好地运用Redis,提升其使用效率。

将聚焦于Redis的五大数据结构,深入剖析各种数据建模方法,并分享关键的管理细节与调试技巧。

【目标人群】

Redis技术进阶之路专栏:目标人群与受众对象,对于希望深入了解Redis实现原理底层细节的人群

1. Redis爱好者与社区成员

Redis技术有浓厚兴趣,经常参与社区讨论,希望深入研究Redis内部机制、性能优化和扩展性的读者。

2. 后端开发和系统架构师

在日常工作中经常使用Redis作为数据存储和缓存工具,他们在项目中需要利用Redis进行数据存储、缓存、消息队列等操作时,此专栏将为他们提供有力的技术支撑。

3. 计算机专业的本科生及研究生

对于学习计算机科学、软件工程、数据分析等相关专业的在校学生,以及对Redis技术感兴趣的教育工作者,此专栏可以作为他们的学习资料和教学参考。

无论是初学者还是资深专家,无论是从业者还是学生,只要对Redis技术感兴趣并希望深入了解其原理和实践,都是此专栏的目标人群和受众对象

让我们携手踏上学习Redis的旅程,探索其无尽的可能性!


字典

字典,作为一种抽象数据结构,常常被我们程序员称之为Hash或者映射,主要用于存储键值对。在字典中,每个键都是唯一的,与之对应着一个值,这种

键与值的配对关系被称为键值对。


凭借这种键值对的关系,程序能够轻松地在字典中根据键查找对应的值,或者通过键来更新值,甚至删除整个键值对。这种灵活的操作方式使得字典在编程中发挥着重要的作用。

虽然许多高级编程语言内置了字典这种数据结构,但Redis所使用的C语言却并未提供内置支持。因此,Redis为了实现其高效的数据存储和操作需求,自行构建了字典数据结构。

这种设计旨在优化数据存储和访问效率,确保在复杂数据场景下,Redis 依然能够保持高效稳定的性能表现。通过深度整合字典数据结构,Redis 成功实现了对大量键值对的高效管理,进一步提升了其在各种应用场景中的实用价值。

字典和Hash的结构关系

字典作为哈希键的底层实现之一,在特定情况下发挥着关键作用。当哈希键中包含的键值对数量庞大,或者键值对中的元素为较长字符串时,Redis 会选择采用字典作为其底层实现。

Hash结构的实现

Redis 成功构建了一个强大而灵活的 Hash 表实现,为存储和检索键值对提供了高效的支持。无论是简单的数据操作还是复杂的查询任务,Redis 的 Hash 源码都能够满足需求,展现出其出色的性能和稳定性。

源码分析

Hash 源码主要由两部分组成:dict.hdict.c

  • dict.h 文件主要负责定义 Hash 表的结构、哈希项,以及声明了一系列针对 Hash 表的操作函数。这些定义和声明为开发者提供了一个清晰的接口,使他们能够了解和使用 Hash 表的功能。
  • dict.c 文件则是对这些函数的具体实现。它包含了 Hash 表创建、查找、插入、删除等操作的实现细节,确保 Hash 表能够高效、稳定地运行。
Hash数据结构

dict.h 文件中,Hash 表是通过一个(dictEntry **table)来构建的,这种设计使得哈希表的实现更加高效且灵活。总体个人认为分为数据结构模型+行为操作模型两个大部分:


Redis字典结构定义

dict结构通过dictType指针抽象键值对类型及操作,实现多样化处理。采用双哈希表实现渐进式rehashing,确保扩容缩容平稳进行,减少性能损耗。下面是对应的dict的源码,我在其中加入了注释,进行介绍对应的含义:

c

复制代码

struct dict {  
    // 指向 dictType 结构体的指针,包含与字典相关的类型特定函数和操作  
    dictType *type;  
    // 字典的哈希表数组,用于支持渐进式 rehashing,包含两个哈希表  
    dictEntry **ht_table[2];  
    // 哈希表已使用的槽位数量数组  
    unsigned long ht_used[2];  
    // rehashing 索引,如果 rehashing 未进行,则值为 -1  
    long rehashidx;   
    // 暂停rehashing的标志位,大于0时暂停rehashing,小于0表示代码错误  
    int16_t pauserehash;   
    // 哈希表大小的指数(size = 1 << exp),包含两个哈希表的大小指数  
    signed char ht_size_exp[2];   
    // 暂停自动调整大小的标志位,大于 0 时禁用自动调整大小,小于 0 表示代码错误  
    int16_t pauseAutoResize;   
    // 柔性数组,用于存储与字典相关的元数据,在标准的 Redis 实现中可能并未使用  
    void *metadata[];  
};
  • dictEntry **ht_table[2]:dictEntry **table 是个二维数组,其中第一维是 bucket,每一行就是 bucket 指向的元素列表(因为键哈希冲突,Redis 采用了链式哈希)。
  • ht_used[2]:这是一个数组,记录了每个哈希表当前已使用的槽位数量。这对于管理哈希表的容量和进行rehashing操作非常重要。提供字典了解当前哈希表的使用情况,以便在必要时进行扩容或缩容。
  • rehashidx:这是一个索引值,用于指示当前 rehashing 操作的进度。如果 rehashing 未进行,则值为 -1。在渐进式 rehashing 过程中,该值会逐渐从 0 增加到旧哈希表的长度,表示已经迁移了多少个键值对。使得字典可以在多个操作之间保持 rehashing 的状态。
dictType结构体的指针

dictType与字典紧密相关的特定类型函数和操作,这些函数和操作定义了字典的行为,确保它能够有效地处理各种与字典相关的任务。支持的功能如下图所示:


下面展示的是Redis的源代码片段,我结合个人理解,为其添加了详尽的注释,旨在帮助大家更好地把握其深层含义,促进代码的解读与理解。

c

复制代码

typedef struct dictType {  
    /* 回调函数组 */  
    /* 哈希函数,用于将键(key)转化为哈希值 */  
    uint64_t (*hashFunction)(const void *key);  
    /* 键的复制函数,用于在字典中创建键的副本 */  
    void *(*keyDup)(dict *d, const void *key);  
    /* 值的复制函数,用于在字典中创建值的副本 */  
    void *(*valDup)(dict *d, const void *obj);  
    /* 键的比较函数,用于比较两个键是否相等 */  
    int (*keyCompare)(dict *d, const void *key1, const void *key2);  
    /* 键的析构函数,用于释放键所占用的内存 */  
    void (*keyDestructor)(dict *d, void *key);  
    /* 值的析构函数,用于释放值所占用的内存 */  
    void (*valDestructor)(dict *d, void *obj);  
    /* 是否允许调整字典大小的函数,基于更多的内存需求和当前使用比率 */  
    int (*resizeAllowed)(size_t moreMem, double usedRatio);  
    /* 在字典初始化或重新哈希开始时调用的函数(旧的和新的哈希表已经创建) */  
    void (*rehashingStarted)(dict *d);  
    /* 在字典初始化或所有条目从旧哈希表到新哈希表重新哈希完成时调用的函数。两个哈希表都还存在,  
     * 并在此回调函数之后被清理。 */  
    void (*rehashingCompleted)(dict *d);  
    /* 允许字典携带额外的调用者定义的元数据。当分配字典时,额外的内存被初始化为0。 */  
    size_t (*dictMetadataBytes)(dict *d);  
    /* 数据 */  
    /* 用户自定义数据,可以在字典中使用 */  
    void *userdata;  
    /* 标志位 */  
    /* 'no_value'标志位,如果设置,表示不使用值,即字典是一个集合(set)。  
     * 当此标志位设置时,无法访问dictEntry的值,也无法使用dictSetKey()。  
     * 同样,也无法使用条目元数据。 */  
    unsigned int no_value:1;  
    /* 如果no_value = 1且所有键都是奇数(最低有效位=1),设置keys_are_odd = 1  
     * 可以启用另一个优化:在不分配dictEntry的情况下存储键。 
     */  
    unsigned int keys_are_odd:1;  
    /* TODO: 添加一个'keys_are_even'标志位,并在设置该标志位时使用类似的优化。 */  
} dictType;

希望这些注释能为大家的学习和工作提供便利,大家对于源码的头文件的理解,主要要集中于有哪些方法以及支持哪些操作即可。

dictEntry二维数组

dictEntry **table 作为一个二维数组,其第一维代表的是不同的 bucket(桶)。每个 bucket 内部则通过指针链接了一系列元素,形成链表结构。



如上图所示,对应的dicEntity数组中每个元素都是一个指向 dictEntry 链表的指针。


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


相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
6天前
|
存储 C语言
数据结构中的线性表链式存储介绍及其基本操作
链式存储是线性表的一种重要存储方式,它通过节点和指针的结构,实现了灵活的动态存储管理。本文介绍了单向链表的基本操作,并提供了相应的C语言代码示例。理解和掌握链表的操作对学习和应用数据结构具有重要意义。希望这篇博客能帮助你更好地理解线性表的链式存储。
17 2
|
6天前
|
弹性计算 负载均衡 监控
防御DDoS攻击:策略与技术深度解析
【6月更文挑战第12天】本文深入探讨了防御DDoS攻击的策略和技术。DDoS攻击通过僵尸网络耗尽目标系统资源,特点是分布式、高流量和隐蔽性。防御策略包括监控预警、流量清洗、负载均衡、弹性伸缩及灾备恢复。技术手段涉及IP信誉系统、深度包检测、行为分析、流量镜像与回放及云防护服务。综合运用这些方法能有效提升抗DDoS攻击能力,保障网络安全。
|
1天前
|
机器学习/深度学习 搜索推荐 PyTorch
【机器学习】图神经网络:深度解析图神经网络的基本构成和原理以及关键技术
【机器学习】图神经网络:深度解析图神经网络的基本构成和原理以及关键技术
15 2
|
1天前
|
机器学习/深度学习 人工智能 算法
【机器学习】深度探索:从基础概念到深度学习关键技术的全面解析——梯度下降、激活函数、正则化与批量归一化
【机器学习】深度探索:从基础概念到深度学习关键技术的全面解析——梯度下降、激活函数、正则化与批量归一化
12 3
|
4天前
|
人工智能 计算机视觉 Python
人工智能视觉:基于OpenCV的人脸识别技术的深度解析
人工智能视觉:基于OpenCV的人脸识别技术的深度解析
|
4天前
|
SQL NoSQL 关系型数据库
数据库技术深度解析与未来趋势展望
一、引言 数据库技术是信息时代的基石,它支撑着无数应用的正常运行,并为企业和组织提供了强大的数据管理能力
|
4天前
|
存储 SQL NoSQL
数据库技术深度解析:从基础到前沿应用
一、引言 在当今信息化社会,数据已成为企业运营和决策的核心
|
4天前
|
存储 SQL 数据管理
数据库技术深度解析:原理、应用与未来展望
一、引言 数据库技术作为现代信息技术的基石,承载着数据存储、管理、检索和分析的重任
|
5天前
|
SQL 存储 多模数据库
数据库技术:从基础到前沿应用的全面解析
一、引言 随着信息技术的迅猛发展,数据已经成为企业和组织最重要的资产之一
|
7天前
|
算法 安全 网络安全
【区块链】深入解析Proof of Work (PoW): 区块链技术的核心驱动力
在区块链技术的宏伟蓝图中,Proof of Work(工作量证明,简称PoW)算法扮演着基石的角色。自比特币白皮书发布以来,PoW已成为确保去中心化网络安全、维护数据完整性的关键机制。本文将深入探讨PoW的工作原理、优势、挑战以及其对区块链生态系统的影响,力求为读者提供一个全面而深入的理解。
8 0

热门文章

最新文章

推荐镜像

更多