Redis Hashes 数据类型简述

Redis Hashes 是我们日常使用中比较高频的 Redis 数据类型,内部使用 Redis 字典结构存储,底层实现之一为哈希表结构。

下面从哈希表节点,哈下表结构,Redis 字典,Redis 字典元素操作,Redis rehash 几点来简要概述。

一、Redis 哈希表节点

Redis 内部定义哈希表节点 dictEntry,用于存储具体的数据,其主要包括键 key,值 v,及外向指针。

1、dictEntry 具体定义

typedef struct dictEntry {

  void *key;

  union{

    void *val;

    uint64_t u64;

    int64_t s64;

  } v;

struct dictEntry *next; //下一个节点指针

} dictEntry;

key:键值对 key

v:键值对 value,可以是指向指针,或者具体的类型。

next:为指向下一个节点的指针,用于处理键哈希冲突问题。 相同哈希值键的键值对会以链表的形式存在同一位置

2、示例哈希表节点数据

如下,哈希表容量 size 为 4,掩码 sizemask 为 3 ,内部存储了两个键值对(k1、v1)、(k2、v2),已使用容量 used 为 2:

Redis Hashes 数据类型简述

二、Redis 哈希表结构

Redis 内部定义哈希表结构 dictht,用于存储实际的(k、v)键值对,其主要包括哈希表数组,容量、已使用容量及掩码。

1、dictht 具体定义

typedef struct dictht {

  dictEntry **table;

  unsigned long size;

  unsigned long sizemask;

  unsigned long used;

} dictht

table:哈希表键值对存储容器,元素类型 dictEntry。

size:哈希表容量, 规划申请的容量

sizemask:哈希表大小掩码,用于 索引计算,计算方式为 size – 1

used:已使用容量, 实际存储的(k、v)键值对数

2、示例哈希表数据

如下,哈希表容量 size 为 4,掩码 sizemask 为 3 ,内部存储了一个键值对(k1、v1),已使用容量 used 为 1:

Redis Hashes 数据类型简述

三、Redis 字典实现

Redis 字典基于上述的哈希表实现,其主要包括内部特定类型函数、私有数据、哈希表数组及 rehash 进度标识等数据。

1、dict:

typedef struct dict{

  dictType *type;

  void *privdata;

  dictht ht[2];

  int rehashidx;

} dict

type:类型为dictType,保存了用于操作特定类型键的函数,和 privdata 共同服务于构建 Redis 多态字典

privdate:和type协同使用,为需要传递给特定类型函数的 可选参数

ht:哈希表数组,类型为dictht,ht[0] 为实际存储数据使用,ht[1] 为 rehash 时使用。

ehashidx: rehash 进度标志,-1 代表当前不在 rehash 进程中。

2、Redis 字典示例数据

如下,包含两个元素的 Redis 字典:

Redis Hashes 数据类型简述

四、Redis 字典添加元素

向字 Redis 典中添加元素主要涉及以下几步操作:

1、计算键值对键的哈希值

hash = dict->type->hashFunction(key)

上面第三节我们提到过 Redis 字典的属性 type,应用其内部的哈希函数得到键哈希值。

2、计算需要放入的位置索引

index = hash & dict->ht[0].sizemask

使用上一步计算得到的哈希值与哈希表的 sizemask 属性进行【 与操作】得到需要放入的位置索引值

3、键冲突解决

没有完美的哈希函数,哈希冲突无法避免,实际应用中,多个键往往会被索引到同一个位置时,这种现象,我们称之为 键冲突

Redis 采用 链地址法解决键冲突:也即将冲突的键值对组成一个链表放到同一个哈希位置上。

上面第二节我们介绍过 dictEntry 的结构,其中包含一个指向另一个节点的指针 next。

这里需要说明的一点是:冲突节点插入时,是 插入到链表的头部,这样只需要执行操作一次操作即可,也即 时间复杂度为 O(1)

如下图:(k2,v2)与(k1,v1)发生冲突,直接将(k2,v2)插入到链表头部:

Redis Hashes 数据类型简述

五、Redis rehash

Redis rehash 是指 Redis 字典重新规划哈希表空间占用的过程。Redis 字典往往伴随着元素的增删改等操作,随着元素的增多或减少,需要适时地进行 Redis 字典容量的重新规划。

1、负载因子

哈希表使用 负载因子(load_factor)来标识当前哈希表的使用状态,计算公式为:已保存节点数量(dict.ht[0].used)/ 哈希表容量(dict.ht[0].size)。它需要保持在一个合理的范围,以保障资源的最优利用。通常需要适时的对哈希表进行扩展或者收缩来对负载因子进行维护。

这里涉及到一个问题,就是什么时候需要进行伸缩维护?

a)扩展时机:

触发 rehash 实际收到 当前 Redis 服务器状态影响,即有无后台 bgsave 及 bgrewriteaop 操作:

  • 无操作,则触发 load_factor 标准为 >= 1
  • 当前有操作,则触发 load_factor 标准为 *>= 5

附:

(1)为什么 load_factor 值可以大于等于 1 ?因为哈希结构的【不可避免哈希冲突存在】特性,一个位置保存的节点数量 【>= 1】。

(2)Redis 服务器通过 fork 子进程形式执行 bgsave 及 bgrewriteaop 操作,此期间整个服务的资源耗费较大,为了避免可能发生的 rehash 带来额外的资源压力,服务器往往会 调高触发执行 rehash 操作的负载因子界限,以降低触发 rehash 的频率。

b)收缩时机:

load_factor < 0.1

2、Redis rehash 基本过程

Redis rehash 过程主要包括空间分配、rehash 执行、重定向三个过程

a) 空间分配:

空间分配是指 为 dict.ht[1] 分配空间

所需要的空间大小计算如下:

扩展:最小n满足2n >= dict.ht[0].used * 2

收缩:最小n满足2n >= dict.ht[0].used

如下图:ht[0].used = 3,假定无bg相关任务,则h[1]大小需要计算:2n >= 3 * 2 = 6

n = 3,ht[1].size = 23 = 8

Redis Hashes 数据类型简述

b) rehash 执行

此过程会逐一对 dict.ht[0] 中的元素,依据dict.ht[1] 特性(sizemask)重新计算索引值,并放置到 dict.ht[1] 中。

如下图:h[0] 中的元素以被完全 rehash 到 h[1] 中存储:

Redis Hashes 数据类型简述

c) 重定向

当所有元素迁移完毕后,Redis 会释放调 dict.ht[0] 的空间占用,并将 dict.ht[1] 设置为 dict.ht[0],并重新在 dict.ht[1] 上创建空的哈希表,以用于下次 rehash 使用。

如下图:重新指向完毕,并创建了新的 ht[1]:

Redis Hashes 数据类型简述

六、Redis rehash 并非一蹴而就

针对实际存储中 不同容量的字典数据,Redis 采用不同的措施进行 rehash 执行:对于数据量较小的字典可以直接一次性的执行rehash;而对于数据量较大的字典数据,直接一次性的执行 rehash 会导致服务资源的集中占用,影响正常的服务响应。因此需要进行分而治之,采用 渐进式执行过程。

渐进式 rehash 会用到上面第三节我们介绍的 dict 字典结构中的 rehashidx 属性,用以 标识当前 rehash 进度

关于渐进式 rehash 过程中 rehashidx 操作如下:

  • 首先将rehashidx置0,标示rehash开始
  • 每次rehash一个元素,rehashidx值增加1
  • 当最终所有元素rehash完成,将rehashidx置-1。

渐进式 rehash 进程中对正常的服务请求的处理如下:

1、删除、查找、更新:

会涉及到两个哈希表(ht[0]、ht[1])操作,如查找元素,首先尝试在ht[0]上查找,找不到,则继续在h[1]上查找。

2、添加

添加元素只会在h[1]上操作,h[0] 上元素此过程保持只减不增。

七、附加订阅

Original: https://www.cnblogs.com/niejunlei/p/13839678.html
Author: WindWant
Title: Redis Hashes 数据类型简述

原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/529334/

转载文章受原作者版权保护。转载请注明原作者出处!

(0)

大家都在看

  • 数据结构 二叉树

    cpp;gutter:true;</p> <h1>include</h1> <p>using namespace std;</…

    Linux 2023年6月13日
    084
  • SPRINGBOOT(38)整合(9)redis

    博客园 :当前访问的博文已被密码保护 请输入阅读密码: Original: https://www.cnblogs.com/qiu-hua/p/16552545.htmlAutho…

    Linux 2023年5月28日
    0103
  • WPF 调试依赖属性变更方法

    本文告诉大家如何调试 WPF 的某个依赖属性被变更的方法 在 WPF 里面,所有的依赖属性都有带通知的功能,通过带通知的功能,可以在通知里加上断点,通过调用堆栈了解是哪个模块调用的…

    Linux 2023年6月6日
    098
  • 😊🙈使用unicode字符集显示emoji表情

    无意中看到Github上很多readme.md用了漂亮又有趣的表情符号,想着是怎么实现。开始我还以为是什么emoji的插件,查着查着才知道,原来unicode字符集已经加入了emo…

    Linux 2023年6月13日
    0106
  • numpy.pad

    浅谈pad用法 numpy.pad(array, pad_width, mode=’constant’, **kwargs) 参数 array 需要进行填充的矩阵 pad_widt…

    Linux 2023年6月7日
    0110
  • Redis核心技术与实战:学习总结目录

    1 Redis学习路径 在《Redis核心技术与实战》课程的学习中,我经常看到一位课代表的发言,他就是Kaito,他总结了一份 Redis学习路径脑图(建议收藏),将Redis的知…

    Linux 2023年5月28日
    090
  • Xbox分辨率突然变成640p

    今天XBox突然抽风还是发什么神经,输出分辨率突然变得非常模糊。一开始以为是HDMI线出现问题,后来用一条新的也是一样,所以就怀疑系统出了什么幺蛾子。 进入【电视和显示选项】——【…

    Linux 2023年6月13日
    0134
  • HTML基础笔记整理

    「学习笔记」HTML基础 勤做笔记不仅可以让自己学的扎实,更重要的是可以让自己少走弯路。有人说:”再次翻开笔记是什么感觉”,我的回答是:”初恋般…

    Linux 2023年6月13日
    086
  • shell中 $() $(()) $[] ${} $[[]] 区别

    $( ) &#x4E0E; (&#x53CD;&#x5F15;&#x53F7;) &#x5728; bash shell &#x4E…

    Linux 2023年5月28日
    0100
  • linux inode 详解 / 线上inode爆满解决方案

    linux inode 详解 / 线上inode爆满解决方案 本文大量参考阮一峰大神博客,整理笔记 &#x4E4B;&#x6240;&#x4EE5;&amp…

    Linux 2023年6月7日
    0118
  • python爬虫爬取国家科技报告服务系统数据,共计30余万条

    python爬虫爬取国家科技报告服务系统数据,共计30余万条 按学科分类【中图分类】 共计三十余万条科技报告数据 爬取的网址:https://www.nstrs.cn/kjbg/n…

    Linux 2023年6月14日
    080
  • 模拟MBR Grub故障修复

    1. MBR故障修复 破坏mrb 重启后镜像界面显示找不到引导系统, 连接光驱,进入紧急救援模式到shell字符界面还原备份 挂载硬盘并备份groub.conf文件 破坏grub并…

    Linux 2023年6月8日
    0100
  • Linux CURL的安装和使用

    –获得安装包,从网上直接下载或者其他途径,这里直接wgetwget http://curl.haxx.se/download/curl-7.17.1.tar.gz&#8…

    Linux 2023年6月13日
    088
  • redis用法介绍

    Jedis常用方法API Redis命令用scan代替keys、smembers等命令 Java Spring 与 Redis 操作封装源码 Redis API 必杀解读:引入Re…

    Linux 2023年5月28日
    0103
  • Redis AOF重写

    AOF 持久化是通过保存被执行的写命令来记录数据库状态的,所以AOF文件的大小随着时间的流逝一定会越来越大;影响包括但不限于:对于Redis服务器,计算机的存储压力;AOF还原出数…

    Linux 2023年5月28日
    0110
  • 性能测试—性能监控

    性能测试中,首先需要确定需求 测什么?怎么测?达到什么标准?。确定好性能测试的需要之后选择性能测试工具,jmeter或者LoadRunner。 分析是否需要分布式压测,如果需要分布…

    Linux 2023年6月8日
    085
亲爱的 Coder【最近整理,可免费获取】👉 最新必读书单  | 👏 面试题下载  | 🌎 免费的AI知识星球