浅析Redis④：字典dict实现

什么是dict？

在 Redis 中，dict 是指哈希表（hash table）的一种实现，用于存储键值对数据。dict 是 Redis 中非常常用的数据结构之一，用于实现 Redis 的键空间。

在 Redis 源码中，dict 是一个通用的、高性能的哈希表实现，它采用开放寻址法（open addressing）作为冲突解决方案，并且具有良好的性能特征。

在 Redis 的源码中，dict 被用于实现 Redis 中的数据库、哈希键（hash key）等数据结构。通过 dict 这一数据结构，Redis 能够高效地实现键值对的存储和检索，保证了 Redis 的高性能和快速响应。

dict 在 Redis 中扮演着非常重要的角色，是支撑 Redis 数据存储和操作的基础之一。

核心特性

  • 开放寻址法：Redis 中的字典采用了开放寻址法作为冲突解决方案。在发生哈希冲突时，它会通过线性探测（linear probing）的方式来寻找下一个可用的位置。
  • 渐进式 rehashing：Redis 的字典实现中采用了渐进rehashing 策略，这意味着在进行扩容或缩小操作时，不会一次性地重新分配所有元素，而是逐步迁移键值对，以降低对服务的影响。
  • 哈希表的大小：Redis 中的字典会根据当前包含的元素数量动态调整哈希表的大小，以保证较低的负载因子，从而保持较好的性能。
  • 链表：在哈希表的每个槽位上，可以形成一个链表，用于处理哈希冲突时的多个元素。当链表长度过长时，Redis 会将链表转换为更高效的哈希表。

总的来说，Redis 中的字典通过哈希表实现，结合了开放寻址法、渐进式 rehashing 等策略，以及动态调整大小等特性，为 Redis 提供了高效的键值对存储和检索能力。这些特性使得 Redis 的字典在处理大量数据时依然能够保持良好的性能。

聚焦问题

1、dict的数据结构长什么样子，对比Java的HashMap

2、dict如何插入数据，并且如何解决hash冲突的

3、dict的rehash策略

dict的数据结构

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

img

dict的本质是使用一个数组来存储key-value键值对，数组中的每个元素都是一个指向dictEntry结构的指针，而每一个dictEntry则保存了key-value键值对，是否听起来似曾相识，与Java中HashMap的结构非常相似

img

之所以说非常相似，而不是一模一样，是因为关于hash寻址冲突后，对同一个数组位置上元素的存储结构，并不完全一致，HashMap对于同一个数组位置的元素初始会使用链表的形式组装，而链表的长度达到一定阈值后，则转为红黑树的形式组装。

而dict并没有这种处理方式，仅会使用链表组织元素，这样的好处显而易见，链表的实现难度一定是比红黑树简单，也更易于调试，但是对与hash寻址算法的要求也更高，需要尽可能的保证少量的hash冲突，即寻址计算尽可能分散，否则链表长度过长，会影响取值的效率。

渐进式rehash

Redis 使用渐进式 rehash 来实现哈希表的扩容和缩容。渐进式 rehash 是一种在 Redis 服务不中断的情况下进行哈希表 rehash 的方法，它将 rehash 操作分解成多个小步骤，每次执行一小部分 rehash 操作，以避免阻塞服务。

渐进式 rehash 的主要步骤如下：

  1. 创建新哈希表： 当需要进行哈希表扩容或缩容时，Redis 首先会创建一个新的哈希表，其大小为原哈希表的两倍或更小。
  2. 迁移数据： 然后，Redis 会将原哈希表中的数据逐步迁移到新哈希表中。每次迁移一小部分数据，而不是一次性全部迁移。这样做的好处是，在迁移的过程中，Redis 仍然可以接受读取请求，并且只有在写入数据时才会阻塞。
  3. 逐步完成： 当所有的数据都迁移完成后，Redis 将原哈希表替换为新哈希表。这个过程是逐步进行的，不会中断服务。

渐进式 rehash 的优点包括：

  • 减少阻塞时间： 由于将 rehash 操作分解成多个步骤执行，因此可以大大减少阻塞时间，提高系统的稳定性和可用性。
  • 逐步进行： rehash 操作是逐步进行的，可以平滑地将数据从旧哈希表迁移到新哈希表，不会对系统造成过大的负担。
  • 保证读写服务： 在 rehash 过程中，Redis 仍然可以提供读取服务，只有在写入数据时才会阻塞。

需要注意的是，虽然渐进式 rehash 可以减少阻塞时间，但在 rehash 过程中，仍然会占用一定的系统资源，可能会对性能产生一定的影响。因此，在进行 rehash 操作时，需要谨慎安排时间，并在低负载时执行。

下面我们来一起看一下，具体实现逻辑：

/* This function handles 'background' operations we are required to do
 * incrementally in Redis databases, such as active key expiring, resizing,
 * rehashing. */
void databasesCron(void) {
    
    if (server.active_expire_enabled && server.masterhost == NULL)
        activeExpireCycle(ACTIVE_EXPIRE_CYCLE_SLOW);

    if (server.rdb_child_pid == -1 && server.aof_child_pid == -1) {
        static unsigned int resize_db = 0;
        static unsigned int rehash_db = 0;
        int dbs_per_call = CRON_DBS_PER_CALL;
        int j;

        /* Don't test more DBs than we have. */
        if (dbs_per_call > server.dbnum) dbs_per_call = server.dbnum;

        /* Resize */
        for (j = 0; j < dbs_per_call; j++) {
            tryResizeHashTables(resize_db % server.dbnum);
            resize_db++;
        }

        /* Rehash */
        if (server.activerehashing) {
            for (j = 0; j < dbs_per_call; j++) {
                // rehash执行
                int work_done = incrementallyRehash(rehash_db % server.dbnum);
                rehash_db++;
                if (work_done) {
                    /* If the function did some work, stop here, we'll do
                     * more at the next cron loop. */
                    break;
                }
            }
        }
    }
}

int incrementallyRehash(int dbid) {
    /* Keys dictionary */
    if (dictIsRehashing(server.db[dbid].dict)) {
        dictRehashMilliseconds(server.db[dbid].dict,1);
        return 1; /* already used our millisecond for this loop... */
    }
    /* Expires */
    if (dictIsRehashing(server.db[dbid].expires)) {
        dictRehashMilliseconds(server.db[dbid].expires,1);
        return 1; /* already used our millisecond for this loop... */
    }
    return 0;
}

/* Rehash for an amount of time between ms milliseconds and ms+1 milliseconds */
int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;

    // 每次执行100次，这就是渐进
    while(dictRehash(d,100)) {
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    // 注意此处的边界条件，每次传入100，也就是只会执行100次循环
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

rehash开始

img

rehash结束

img

Redis的dict与Java中的HashMap，实现上有什么区别

Redis 的 dict 是在 C 语言中实现的字典结构，而 Java 中的 HashMap 是在 Java 编程语言中实现的哈希表结构。它们之间有以下几个主要区别：

  • 语言差异：dict 是 Redis 自行实现的数据结构，使用 C 语言编写。而 HashMap 是 Java 标准库中提供的类，使用 Java 编写。
  • 内存管理：Redis 的 dict 使用了手动内存管理，需要手动分配和释放内存空间。而 Java 的 HashMap 使用垃圾回收机制自动管理内存，无需手动处理。
  • 线程安全性：Redis 的 dict 不是线程安全的，如果多个线程同时对同一个 dict 进行读写操作，可能会导致数据不一致或者程序崩溃。而 Java 的 HashMap 是非线程安全的，但可以通过使用 ConcurrentHashMap 等线程安全的 Map 实现来解决并发访问的问题。
  • 扩容机制：Redis 的 dict 在进行扩容时使用了渐进式 rehash 算法，将扩容操作分摊到多个操作中，避免了大规模数据迁移带来的性能问题。而 Java 的 HashMap 在扩容时需要重新计算哈希值，并将元素重新分布到新的桶位中。
  • 功能差异：Redis 的 dict 是为了满足 Redis 数据库的需要而设计的，支持一些特定的功能，如过期时间等。Java 的 HashMap 是通用的哈希表实现，提供了丰富的方法和功能，适用于多种应用场景。

总体而言，Redis 的 dict 和 Java 的 HashMap 在实现上有一些差异，主要是因为它们所运行的环境和使用的编程语言不同。它们在性能、线程安全性、扩容策略等方面都有各自的特点和优化。

Redis dict的rehash和Java HashMap的rehash，有什么不同

Redis 的 dict 和 Java 的 HashMap 在 rehash（重新哈希）操作上有一些区别：

  • 触发条件：Redis 的 dict 在进行 rehash 操作时，是在字典的负载因子（load factor）超过阈值时触发的，即元素数量超过容量的一定比例。而 Java 的 HashMap 在进行 rehash 操作时，是在桶位（buckets）的使用情况超过阈值时触发的，即某个桶位中元素的数量超过链表长度的阈值（8）。
  • 扩容方式：Redis 的 dict 采用了渐进式 rehash 算法，将扩容操作分摊到多个操作中，避免了大规模数据迁移带来的性能问题。具体而言，dict 在进行 rehash 时会逐步将 ht[0] 中的元素迁移到 ht[1] 中，直到完成整个 rehash 过程。而 Java 的 HashMap 使用的是一次性扩容的方式，在 rehash 时会创建一个更大的桶位数组，并将所有元素重新计算哈希值后放入新的桶位中。
  • 并发处理：Redis 的 dict 在 rehash 过程中，仅支持单线程执行，不支持并发访问。这意味着在 rehash 过程中，不能同时进行读取和写入操作，否则可能导致数据不一致。而 Java 的 HashMap 在 rehash 过程中，不会影响并发访问的正常进行。通过使用读写锁或者分段锁等机制，可以在不阻塞其他线程的情况下进行并发读取和写入操作。

Redis 的 dict 和 Java 的 HashMap 在 rehash 操作上有一些差异。Redis 的 dict 使用了渐进式 rehash 算法，避免了大规模数据迁移带来的性能问题，但不支持并发访问。而 Java 的 HashMap 在 rehash 过程中可以进行并发访问，但需要一次性扩容，并重新计算哈希值。这些差异是由于它们所处的环境和应用场景的不同导致的。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/560313.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

linux中如何挂载yum云仓库进行软件的安装

linux中如何挂载yum云仓库进行软件的安装

1.首先在根目录下建立文件&#xff0c;用来挂载镜像文件 [rootclient ~]# mkdir /rhel9 2.挂载镜像文件&#xff1a; [rootclient ~]# mount /dev/cdrom /rhel9 3.切换到 /etc/yum.repos.d 下的目录并查看 &#xff0c;创建 rhel9.repo文件&#xff0c;并编辑云仓库域名&am…
阅读更多...
【LLM 论文】Self-Consistency — 一种在 LLM 中提升 CoT 表现的解码策略

【LLM 论文】Self-Consistency — 一种在 LLM 中提升 CoT 表现的解码策略

论文&#xff1a;Self-Consistency Improves Chain of Thought Reasoning in Language Models ⭐⭐⭐⭐⭐ ICLR 2023, Google Research 文章目录 论文速读 论文速读 本工作提出了一种解码策略&#xff1a;self-consistency&#xff0c;并可以用于 CoT prompting 中。 该策略提…
阅读更多...
Linux使用Libevent库实现一个网页服务器---C语言程序

Linux使用Libevent库实现一个网页服务器---C语言程序

Web服务器 这一个库的实现 其他的知识都是这一个专栏里面的文章 实际使用 编译的时候需要有一个libevent库 gcc httpserv.c -o httpserv -levent实际使用的时候需要指定端口以及共享的目录 ./httpserv 80 .这一个函数会吧这一个文件夹下面的所有文件共享出去 实际的效果, 这…
阅读更多...
NLP_知识图谱_三元组实战

NLP_知识图谱_三元组实战

文章目录 三元组含义如何构建知识图谱模型的整体结构基于transformers框架的三元组抽取baselinehow to use预训练模型下载地址训练数据下载地址 结构图代码及数据bertconfig.jsonvocab.txt datadev.jsonschemas.jsontrain.jsonvocab.json 与bert跟data同个目录model.pytrain.py…
阅读更多...
华为ensp中rip和ospf路由重分发 原理及配置命令

华为ensp中rip和ospf路由重分发 原理及配置命令

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月20日20点21分 路由重分发&#xff08;Route Redistribution&#xff09;是指路由器将从一种路由协议学习到的路由信息&#xff0c;通过另一种路由协议通告出去的功…
阅读更多...
Linux环境变量深度解析

Linux环境变量深度解析

文章目录 一、引言二、环境变量的基本概念1、环境变量的定义2、环境变量的作用与意义 三、环境变量的导入1、导入所需文件2、登陆时的导入 四、环境变量的设置方法1、查看环境变量的方式2、使用export命令临时设置环境变量3、修改配置文件以永久设置环境变量 五、命令行参数与环…
阅读更多...
Python编程与算法面试-编程面试的重点

Python编程与算法面试-编程面试的重点

在求职面试的过程中&#xff0c;编程能力也是面试官非常看重的一项能力。而对于编程这项能力主要的考察点也有三个维度&#xff1a; 初级&#xff1a;编程的基本功 编程的基本功主要考察的编程语言的基本语法&#xff0c;原理知识&#xff0c;以及一些在编程过程中的常见问题…
阅读更多...
基于unity+c#的随机点名系统（简单UI界面+列表+数组）

基于unity+c#的随机点名系统（简单UI界面+列表+数组）

目录 一、功能界面显示 二、UI 1、视频的使用 &#xff08;1&#xff09;渲染纹理 &#xff08;2&#xff09; 视频铺全屏 &#xff08;3&#xff09;视频的调用 2、 下拉文本框的使用&#xff08;旧版&#xff09; 3、输入文本框的使用&#xff08;旧版&#xff09; …
阅读更多...
OpenHarmony 视图加载——ImageViewZoom

OpenHarmony 视图加载——ImageViewZoom

简介 ImageViewZoom 支持加载 Resource 或 PixelMap 图片&#xff0c;支持设置图像显示类型功能&#xff0c;支持缩放功能&#xff0c;支持平移功能&#xff0c;双击放大功能&#xff0c;可以监听图片大小&#xff0c;资源变化事件&#xff0c;支持清除显示图片功能。 效果展示…
阅读更多...
pg内核之日志管理器（五）WAL日志

pg内核之日志管理器（五）WAL日志

概念 WAL日志 数据库运行过程中&#xff0c;数据一般是会保存在内存和磁盘中&#xff0c;为保证数据的安全性&#xff0c;防止数据库崩溃时数据不丢失&#xff0c;一般都是要保证数据实时落盘的&#xff0c;但是又由于磁盘随机IO读写速率与内存相比慢很多&#xff0c;如果每个…
阅读更多...
RocketMQ5.x的pop模式如何解决消费堆积问题

RocketMQ5.x的pop模式如何解决消费堆积问题

RocketMQ4.X现存问题 消费能力不能随POD增加而增加。 理想情况下&#xff0c;POD数量小于QUEUE的数量&#xff0c;增加机器是能提高消能力的。 现实情况下&#xff0c;如果POD数量大于QUEUE的数量&#xff0c;那么多的POD机器就不会处理消费&#xff0c;是一种资源的浪费。 单…
阅读更多...
苹果 IPA 应用部署软件 iMazing 3 Windows 版获 3.0.0.4 Beta 4

苹果 IPA 应用部署软件 iMazing 3 Windows 版获 3.0.0.4 Beta 4

在数字化时代&#xff0c;我们的iOS设备已经成为生活中不可或缺的一部分。为了更加高效、便捷地管理这些设备&#xff0c;iMazing 3.0.0.3 应运而生&#xff0c;它以其独特的功能和卓越的性能&#xff0c;为用户带来了前所未有的全新体验。 首先&#xff0c;iMazing 3.0.0.3 提…
阅读更多...
集简云数据表新增批量操作功能，一键实现批量触发执行对应自动化流程

集简云数据表新增批量操作功能，一键实现批量触发执行对应自动化流程

在使用数据表时&#xff0c;某些情况下可能希望人工触发自动化流程执行&#xff0c;例如&#xff1a;开发票、提交工单、同步帐套信息等场景。 通过数据表按钮字段&#xff0c;可手动触发执行对应自动化流程&#xff0c;实现将数据推送到其他表单、应用系统&#xff0c;或从其…
阅读更多...
C++必修：从C语言到C++的过渡(上）

C++必修：从C语言到C++的过渡(上）

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;C学习 贝蒂的主页&#xff1a;Betty’s blog 1. 什么是C C&#xff08;c plus plus&#xff09;是一种计算机高级程序设计语言&…
阅读更多...
新型大数据架构之湖仓一体（Lakehouse）架构特性说明——Lakehouse 架构（一）

新型大数据架构之湖仓一体（Lakehouse）架构特性说明——Lakehouse 架构（一）

文章目录 为什么需要新的数据架构&#xff1f;湖仓一体&#xff08;Lakehouse&#xff09;——新的大数据架构模式同时具备数仓与数据湖的优点湖仓一体架构存储层计算层 湖仓一体特性单一存储拥有数据仓库的查询性能存算分离开放式架构支持各种数据源类型支持各种使用方式架构简…
阅读更多...
csdn的编写教程（官方给的）

csdn的编写教程（官方给的）

自定义的目录标题 欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题&#xff0c;有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants 创建一个自定义列表如何创建一个注脚…
阅读更多...
ubuntu 16.04.7连不上网的解决方案

ubuntu 16.04.7连不上网的解决方案

首先在编辑选项卡里找到虚拟网络编辑器&#xff0c; 点击更改设置 点击添加网络 点击确定 选择桥接模式&#xff0c;自动后点击应用&#xff0c;最后点击确定即可。
阅读更多...
4.20+C语言感想，有趣的思考题，case的省略操作，统计位数，终止循环，break和continue语句， 准备下一篇见。

4.20+C语言感想，有趣的思考题，case的省略操作，统计位数，终止循环，break和continue语句， 准备下一篇见。

鹏哥C语言感想 一.高级 这可不是什么煎饼&#xff0c;这种食物叫做蓝莓&#xff0c;俗称苹果。生长在撒哈拉沙漠的雨林地带。因外形酷似企鹅&#xff0c;所以我们又喜欢叫他北极熊。你们这些人&#xff0c;连仙人掌都不知道&#xff0c;就不要乱说他是西瓜好吗&#xff1f;再…
阅读更多...
嵌入式4-20

嵌入式4-20

客户端 #include <myhead.h> #define SER_IP "192.168.125.244" #define SER_PORT 8888 typedef struct Node { char username[20];struct sockaddr_in cin;struct Node *next; }Node,*Node_p; typedef struct {int flag;char username[20];char data[1024]…
阅读更多...
java中File类和输入输出流的用法

java中File类和输入输出流的用法

目录 针对文件系统进行操作 针对文件内容进行操作 java针对文件操作可以分为两种&#xff1a;1&#xff09;针对文件系统进行操作&#xff0c;如创建文件&#xff0c;删除文件&#xff0c;创建目录&#xff0c;重命名文件等。 2&#xff09;针对文件内容进行操作&#xff0c…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站