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

站长

2024年03月19日 18:43 · 阅读数 4

【专栏简介】

随着数据需求的迅猛增长，持久化和数据查询技术的重要性日益凸显。关系型数据库已不再是唯一选择，数据的处理方式正变得日益多样化。在众多新兴的解决方案与工具中，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技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）凭借这种键值对的关系，程序能够轻松地在字典中根据键查找对应的值，或者通过键来更新值，甚至删除整个键值对。这种灵活的操作方式使得字典在编程中发挥着重要的作用。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）虽然许多高级编程语言内置了字典这种数据结构，但Redis所使用的C语言却并未提供内置支持。因此，Redis为了实现其高效的数据存储和操作需求，自行构建了字典数据结构。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）

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

字典和Hash的结构关系

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

Hash结构的实现

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

源码分析

Hash 源码主要由两部分组成：dict.h 和 dict.c。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）

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

Hash数据结构

在 dict.h 文件中，Hash 表是通过一个（dictEntry **table）来构建的，这种设计使得哈希表的实现更加高效且灵活。总体个人认为分为数据结构模型+行为操作模型两个大部分：【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）

Redis字典结构定义

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

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技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）下面展示的是Redis的源代码片段，我结合个人理解，为其添加了详尽的注释，旨在帮助大家更好地把握其深层含义，促进代码的解读与理解。

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 内部则通过指针链接了一系列元素，形成链表结构。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）如上图所示，对应的dicEntity数组中每个元素都是一个指向 dictEntry 链表的指针。

dictEntry模型

Redis的dictEntry 结构体不仅包含了指向键和值的指针，还巧妙地设计了一个指向下一个哈希项的指针next。这个指针 next 的存在，使得当多个键的哈希值发生冲突时，Redis 能够将这些键以链表的形式连接在一起，从而有效地解决了哈希冲突问题。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）

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

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

dictEntry的结构体源码

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

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哈希表结构。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）在正常情况下，我们主要使用ht[0]这个哈希表进行数据存储和检索操作。而ht[1]哈希表的存在，主要是为了在需要对ht[0]进行rehash操作时提供一个临时的存储空间。

两个哈希表支持rehashing

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

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

哈希算法

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

计算哈希值和索引值

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

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

上面定义的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添加到字典里面：【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）那么程序会先使用语句：#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指针串联成一个单向链表。因此，当多个键被分配到相同的索引位置时，这些节点可以通过这个单向链表相互连接，从而巧妙地解决了键冲突问题。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）以图示为例，假设我们拥有一个哈希表，并且程序需要将键值对w插入其中。经过哈希函数的计算，我们得知w的索引值为4。然而，在这个特定的索引位置，已存在其他键（如c和d），这就引发了键冲突问题。

Rehash操作和处理执行

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

扩展和收缩

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

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

负载因子

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

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的步骤

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

最后，将ht[1]提升为新的ht[0]，并初始化一个新的空白哈希表作为新的ht[1]，以备将来可能再次触发的重新散列操作。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）

执行rehash的时候业务操作

在进行rehash操作时，字典的删除、查找和更新等操作都需要在这两个哈希表上进行，注意没有新增哦！具体来说，当我们需要在字典中查找一个键时，程序会首先在ht[0]中进行搜索。如果未能在ht[0]中找到相应的键，程序则会继续转向ht[1]进行查找，以确保不会遗漏任何可能的键值对。【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（字典）

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

最后总结

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

双哈希表：每个Redis字典都巧妙地配备了两个哈希表，一个负责日常运作，而另一个则专门用于rehash操作，这种双表机制显著提升了字典在数据变动时的性能表现。
解决冲突：在哈希表中，为了解决这一冲突，Redis巧妙地运用了next指针机制。它将新键值对w对应的节点通过next指针链接到已存在的d节点之前，从而构建了一个链表结构。通过这种方式，Redis不仅有效地解决了键冲突问题，还保证了哈希表在数据插入时的灵活性和高效性。
Rehash控制：当哈希表需要进行扩展或收缩以适应数据量的变化时，Redis并非一蹴而就地完成整个rehash过程。相反，它采取了渐进式的策略，逐步将旧哈希表中的键值对迁移到新表中，从而确保了rehash操作对系统性能的影响最小化。