redis键值对映射关系存储-Dict

这篇具有很好参考价值的文章主要介绍了redis键值对映射关系存储-Dict。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

基本概述

Redis是一个键值型(Key-Value Pair)的数据库,可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的

Dict由三部分组成,分别是:哈希表(DictHashTable)哈希节点(DictEntry)字典(Dict)

哈希表:

redis键值对映射关系存储-Dict

哈希节点:

redis键值对映射关系存储-Dict

size大小只能是 2^n

sizemark一定要是 2^n - 1,才会有如下效果

与sizemark与运算实际上与 size求余效果一样(hash运算)

向Dict添加键值对时,Redis首先根据key计算出hash值(h),然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置

例如:存储k1=v1,假设k1的哈希值h = 1,则1 & 3 = 1,因此k1 = v1要存储到数组角标1位置。

redis键值对映射关系存储-Dict

(size默认大小是4)

假设k2哈希值也是1,相同hash值节点,拉链法(加在链表首)

redis键值对映射关系存储-Dict

字典:

redis键值对映射关系存储-Dict

redis键值对映射关系存储-Dict

Dict的扩容

Dict中的HashTable就是数组结合单向链表的实现,当集合中元素较多时,必然导致哈希冲突增多,链表过长,则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子(LoadFactor = used/size) ,满足以下两种情况时会触发哈希表扩容

  • 哈希表的 LoadFactor >= 1,并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程(消耗CPU,负载因子不是很大,可以忍忍);
  • 哈希表的 LoadFactor > 5(负载因子过大,忍无可忍);

redis键值对映射关系存储-Dict

Dict的收缩

Dict除了扩容以外,每次删除元素时,也会对负载因子做检查,当LoadFactor < 0.1 时,会做哈希表收缩:

redis键值对映射关系存储-Dict

redis键值对映射关系存储-Dict

redis键值对映射关系存储-Dict

Dict的rehash

不管是扩容还是收缩,必定会创建新的哈希表,导致哈希表的size和sizemask变化,而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引,插入新的哈希表,这个过程称为rehash

过程是这样的:

① 计算新hash表的realeSize,值取决于当前要做的是扩容还是收缩:

  • 如果是扩容,则新size为第一个大于等于dict.ht[0].used + 1的2^n
  • 如果是收缩,则新size为第一个大于等于dict.ht[0].used的2^n (不得小于4)

② 按照新的realeSize申请内存空间,创建dictht,并赋值给dict.ht[1]

③ 设置dict.rehashidx = 0,标示开始rehash

④ 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]

⑤ 将dict.ht[1]赋值给dict.ht[0],给dict.ht[1]初始化为空哈希表,释放原来的dict.ht[0]的内存

无论是扩容还是收缩,都会调用dictExpand(),最终调用_dictExpand()

/* Expand or create the hash table,
 * when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).
 * Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
int _dictExpand(dict *d, unsigned long size, int* malloc_failed)
{
    if (malloc_failed) *malloc_failed = 0;

    // 如果正在rehash,或者dict节点个数大于扩展数量,直接返回错误
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    // 创建一个新的哈希表
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size); // 计算出满足条件的 2^n 扩展个数

    // 健壮性判断
    if (realsize < size || realsize * sizeof(dictEntry*) < realsize)
        return DICT_ERR;

    if (realsize == d->ht[0].size) return DICT_ERR;

    // 新哈希表赋值
    n.size = realsize;
    n.sizemask = realsize-1;
    if (malloc_failed) {
        n.table = ztrycalloc(realsize*sizeof(dictEntry*));
        *malloc_failed = n.table == NULL;
        if (*malloc_failed)
            return DICT_ERR;
    } else
        n.table = zcalloc(realsize*sizeof(dictEntry*));

    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    // 第一次初始化,无需rehash,直接初始化第一个哈希表,直接结束
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    // 不是第一次初始化,准备第二个rehash所需的哈希表
    d->ht[1] = n;
    // 置为0,标识开始rehash
    d->rehashidx = 0;
    return DICT_OK;
}

实际上,redis的rehash流程不是逐个节点都rehash到dict.ht[1],假设节点个数成千上万这个过程是比较耗时的,不是特别高效

Dict的渐进式rehash

Dict的rehash并不是一次性完成的。试想,如果Dict中包含数百万的entry,要在一次rehash完成,极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成,因此称为渐进式rehash

实际完整流程如下:

① 计算新hash表的size,值取决于当前要做的是扩容还是收缩:

  • 如果是扩容,则新size为第一个大于等于dict.ht[0].used + 1的2^n
  • 如果是收缩,则新size为第一个大于等于dict.ht[0].used的2^n (不得小于4)

② 按照新的size申请内存空间,创建dictht,并赋值给dict.ht[1]

③ 设置dict.rehashidx = 0,标示开始rehash

将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]

每次执行新增、查询、修改、删除操作时,都检查一下dict.rehashidx是否大于-1,如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1],并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]

⑤ 将dict.ht[1]赋值给dict.ht[0],给dict.ht[1]初始化为空哈希表,释放原来的dict.ht[0]的内存【每次操作(增删改查),rehash只操作数组一个角标上的元素,直至所有元素迁移完成,重置两个dictht

⑥ 将rehashidx赋值为-1,代表rehash结束

在rehash过程中,新增操作,则直接写入ht[1],查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增,随着rehash最终为空文章来源地址https://www.toymoban.com/news/detail-489678.html

小结

Dict的结构:

  • 类似java的HashTable,底层是数组加链表来解决哈希冲突
  • Dict包含两个哈希表,ht[0]平常用,ht[1]用来rehash

Dict的伸缩:

  • LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时,Dict扩容
  • LoadFactor小于0.1并且哈希表大小大于初始值4时,Dict收缩
  • 扩容大小为第一个大于等于used + 1的2^n
  • 收缩大小为第一个大于等于used 的2^n
  • Dict采用渐进式rehash每次访问Dict时执行一次rehash,直至所有元素rehash完毕
  • rehash时ht[0]只减不增,新增操作只在ht[1]执行,其它操作在两个哈希表

到了这里,关于redis键值对映射关系存储-Dict的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【JavaSE专栏53】Java集合类HashMap解析,基于哈希表的键值对存储结构

    作者主页 :Designer 小郑 作者简介 :3年JAVA全栈开发经验,专注JAVA技术、系统定制、远程指导,致力于企业数字化转型,CSDN学院、蓝桥云课认证讲师。 主打方向 :Vue、SpringBoot、微信小程序 本文讲解了 Java 中集合类 HashMap 的语法、使用说明和应用场景,并给出了样例代码。

    2024年02月15日
    浏览(40)
  • etcd每个节点都存储了完整的键值对数据集,为什么扩容etcd集群仍可分散存储压力?

    etcd每个节点都存储了完整的键值对数据集,这主要是为了确保数据的一致性和高可用性。在这种设计下,任何一个节点都可以处理读取请求,并在本地提供数据,从而无需跨节点通信。这种冗余的数据存储方式也增加了系统的容错性,因为即使部分节点发生故障,其他节点仍

    2024年03月12日
    浏览(56)
  • 【JavaSE专栏55】Java集合类HashTable解析,基于哈希表实现的唯一性键值对存储数据结构

    作者主页 :Designer 小郑 作者简介 :3年JAVA全栈开发经验,专注JAVA技术、系统定制、远程指导,致力于企业数字化转型,CSDN学院、蓝桥云课认证讲师。 主打方向 :Vue、SpringBoot、微信小程序 本文讲解了 Java 中集合类 HashTable 的语法、使用说明和应用场景,并给出了样例代码。

    2024年02月15日
    浏览(57)
  • Android HID设备(键盘、遥控等)功能实现流程及键值映射关系

    HID (Human Interface Device,人机接口设备)是USB设备中常用的设备类型,是直接与人交互的USB设备,例如键盘、遥控器、鼠标与游戏杆等。在USB设备中,HID设备的成本较低。     之前文章 android 键盘(遥控)键值定义大全 中整理了android中各种功能键值定义,那么从键盘按键到

    2024年02月04日
    浏览(39)
  • Spark【RDD编程(三)键值对RDD】

            键值对 RDD 就是每个RDD的元素都是 (key,value)类型的键值对,是一种常见的 RDD,可以应用于很多场景。                 因为毕竟通过我们之前Hadoop的学习中,我们就可以看到对数据的处理,基本都是以键值对的形式进行统一批处理的,因为MapReduce模型中

    2024年02月09日
    浏览(50)
  • 深入解析Redis:一种快速、高效的键值存储系统

    在现代应用程序中,高性能和可扩展性是至关重要的。Redis(Remote Dictionary Server)是一种快速、高效的键值存储系统,它具有出色的性能和灵活的数据结构。本文将深入解析Redis的特点、安装配置、基本操作、高级功能、性能优化、应用场景、注意事项和最佳实践。 1.1 介绍

    2024年02月16日
    浏览(38)
  • Java键值对Pair的使用方式和操作流程

    目录 一、什么是键值对 二、Java的Pair 三、Pair 的使用场景   键值对是一种常见的数据结构,它由一个唯一的键(key)和与之关联的值(value)组成 。键和值之间存在一种映射关系,通过键可以查找或访问对应的值。 在键值对中,键通常用于唯一标识和区分不同的数据项,而

    2024年02月07日
    浏览(46)
  • Python中删除字典中键值对的方法

    方法一:dic.pop(\\\'key\\\', 默认值) 1、字典的pop方法可以将字典键所对应的值给删除掉,但因为字典中键和值是映射关系,该键所对应的值被删除了,则该键也会从字典中移除。 2、pop方法会返回被移除键对应的值。 3、若pop方法想移除的键不存在,则返回默认值。 方法二:使用P

    2023年04月09日
    浏览(43)
  • “探索Redis:高性能键值存储数据库的实用指南“

    标题:探索Redis:高性能键值存储数据库的实用指南 引言: Redis是一种高性能的键值存储数据库,它通过将数据存储在内存中,提供了快速的读写操作。本文将介绍Redis的基本概念和常用功能,并提供示例代码帮助读者更好地理解和应用Redis。 Redis的基本概念 Redis是一个开源的

    2024年02月15日
    浏览(77)
  • Python 遍历结构复杂的多层嵌套字典,收集特定键值对

    可以使用递归函数来遍历整个嵌套层次不同的字典,收集所有感兴趣的键值对,最终得到一个非嵌套结构的字典: (一般用于处理爬取的json数据,因为有些结构真的蛮怪的(メ3[____]

    2024年02月19日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包