【Redis】Redis 数据存储原理和结构

一、Redis 存储结构

1.1 KV结构

  • Redis 本质上是一个 Key-Value(键值对,KV)数据库,在它丰富多样的数据结构底层,都基于一种统一的键值对存储结构来进行数据的管理和操作

  • Redis 使用一个全局的哈希表来管理所有的键值对,这个哈希表就像是一个大字典,通过键(Key)能快速定位到对应的值(Value)。

  • 从用户视角看,用户使用各种命令操作不同类型的数据结构(如 String、Hash、List 等),但从底层实现角度,它们都是以键值对形式存储在这个哈希表中。

  • Redis的存储分类的目的是,在数据量小的时候,追求存储效率高;在数据量大的时候,追求运行速度快。

在这里插入图片描述

数据类型(Value 所属类型)编码方式触发条件
stringint字符串长度 ≤ 20 且可转换为整数(如 "123"
embstr字符串长度 ≤ 44
raw字符串长度 > 44
cpu 缓存行优化(补充逻辑,基于缓存行 64 字节设计,辅助提升访问效率,非独立编码类型)
listquicklistRedis 3.2+ 默认实现,是 ziplist + 双向链表的混合结构(动态适配数据量)
ziplist数据量小时被 quicklist 间接使用(紧凑存储小列表)
hashziplist节点数量 ≤ 512(hash-max-ziplist-entries)且字符串长度 ≤ 64(hash-max-ziplist-value
dict节点数量 > 512 或字符串长度 > 64
setintset元素全为整数且数量 ≤ 512(set-max-intset-entries
dict元素含非整数或数量 > 512
zsetziplist子节点数量 ≤ 128(zset-max-ziplist-entries)且字符串长度 ≤ 64(zset-max-ziplist-value
skiplist子节点数量 > 128 或字符串长度 > 64

1.2 字典(dict)

Redis 中的字典(dict) 是一种高效的键值对存储结构,广泛用于实现 Redis 核心的 KV 存储(全局键值对)以及 Hash 类型在数据量较大时的底层存储(当 Hash 节点数>512 或字符串长度>64 时)。其设计借鉴了哈希表的思想,通过链地址法处理冲突,并支持动态扩容(重哈希)以保证性能

字典数据结构组成

字典由三个核心结构体组成,层层嵌套实现哈希表的功能:

1. dictEntry哈希表节点

存储单个键值对(key-value),next 指针用于连接哈希冲突的节点(形成链表)

typedef struct dictEntry {void *key;                  // 键(字符串类型)union {                     // 值(支持多种类型)void *val;              // 指针类型(如复杂数据结构)uint64_t u64;           // 无符号整数int64_t s64;            // 有符号整数double d;               // 浮点数} v;struct dictEntry *next;     // 下一个节点指针(处理哈希冲突的链表)
} dictEntry;
2. dictht 哈希表

管理哈希表数组,table 是存放 dictEntry 指针的数组,sizemask 用于快速计算键的索引(替代取余运算)。

typedef struct dictht {dictEntry **table;          // 哈希表数组(存储dictEntry指针)unsigned long size;         // 数组长度(必须是2的幂,如4、8、16...)unsigned long sizemask;     // 掩码,值为 size-1(用于计算数组索引)unsigned long used;         // 已存储的节点数量(key-value总数)
} dictht;
3. dict字典顶层结构

通过 ht[2] 支持渐进式重哈希(避免一次性扩容的性能波动),rehashidx 跟踪重哈希进度。

typedef struct dict {dictType *type;             // 字典类型(包含哈希函数、键值复制/释放函数等)void *privdata;             // 私有数据(供type中的函数使用)dictht ht[2];               // 两个哈希表(ht[0]:当前使用;ht[1]:重哈希时使用)long rehashidx;             // 重哈希索引(-1表示未进行重哈希;≥0表示当前迁移进度)int16_t pauserehash;        // 重哈希暂停标记(>0表示暂停,避免遍历期间干扰)
} dict;

在这里插入图片描述

哈希运算与索引映射

字典通过哈希函数将 key 映射到哈希表数组的索引,步骤如下:

  1. 计算哈希值:对 key(字符串)执行哈希函数(如 siphash),得到一个 64 位整数哈希值。

    • 特性:相同 key 必然得到相同哈希值(确定性);不同 key 可能得到相同哈希值(哈希冲突)。
  2. 映射到数组索引:利用 sizemasksize-1)对哈希值进行位运算(哈希值 & sizemask),得到数组索引。

    • 示例:若 size=4(2 的幂),则 sizemask=3(二进制 11)。哈希值 5(二进制 101)与 3 做 & 运算,结果为 1(二进制 01),即索引为 1。

    • 优势:位运算(&)比取余运算(%)效率更高,且当 size 是 2 的幂时,哈希值 % size 等价于 哈希值 & sizemask

哈希冲突的处理

由于哈希值范围(64 位)远大于哈希表数组长度(size),根据抽屉原理(n+1 个苹果放入 n 个抽屉,至少一个抽屉有 2 个),必然存在不同 key 映射到同一索引的情况(哈希冲突)。

字典采用链地址法解决冲突:

  • 每个 dictEntry 节点通过 next 指针形成单向链表,同一索引的所有冲突节点串联在链表中。
  • 查找时:先通过索引定位到链表头,再遍历链表比较 key 以找到目标节点(时间复杂度:理想 O (1),冲突严重时 O (n))。

渐进式重哈希(扩容 / 缩容)

当哈希表的负载因子used / size)过高(扩容)或过低(缩容)时,需要调整数组大小以优化性能:

  • 扩容触发:负载因子>1(默认),size 扩大为当前的 2 倍(仍为 2 的幂)。
  • 缩容触发:负载因子<0.1,size 缩小为大于 used 的最小 2 的幂。
    在这里插入图片描述

在这里插入图片描述

为避免一次性迁移所有节点导致的性能阻塞,字典采用渐进式重哈希

  1. 初始化:创建 ht[1] 并设置新 size(如扩容为 ht[0].size * 2),rehashidx 设为 0(开始重哈希)。

  2. 渐进式迁移

    • 每次对字典执行增删改查时,顺带将 ht[0]rehashidx 索引的所有节点迁移到 ht[1],并将 rehashidx 递增 1。
    • 遍历操作(如 HGETALL)时,会暂停重哈希(pauserehash 标记),避免遍历期间节点迁移导致数据不一致。
  3. 完成迁移:当 ht[0].used 变为 0 时,释放 ht[0],将 ht[1] 赋值给 ht[0]ht[1] 重置为空,rehashidx 设为 - 1(重哈希结束)。

scan

Redis 的 scan 命令是用于渐进式遍历集合类数据(如键空间、哈希表、集合等)的命令,主要解决了 keys 命令因一次性全量遍历导致服务器阻塞的问题

实现目标

  • 实现对 scan 开始时刻已存在的数据 进行遍历,保证 不重复、不遗漏
  • 不阻塞服务器,通过分批次、渐进式的方式遍历,每次返回部分结果,避免一次性处理大量数据导致的性能波动。

遍历机制

  • 遍历顺序:采用 高位进位加法 的遍历顺序。这种方式的优势是,在哈希表发生扩容 / 缩容(rehash)时,新旧哈希表的槽位在遍历顺序上是相邻的,确保遍历过程能适配哈希表结构的动态变化,维持遍历的连续性。
  • 游标机制:通过游标(cursor)记录每次遍历的位置。首次调用时游标为 0,每次返回部分元素和新游标,当游标为 0 时表示遍历结束。

在这里插入图片描述

  • Redis 的哈希表(如字典)会因数据量变化发生扩容或缩容(rehash),导致键的映射算法(槽位计算方式)改变。
  • 借助 高位进位加法 的遍历顺序,即使 rehash 过程中映射关系变化,scan 仍能正确遍历 scan 开始时已存在的数据,不会因 rehash 导致重复或遗漏。

1.3 Expire 机制

Redis 的 expire 机制用于管理设置了过期时间的键(key),通过两种核心策略结合,在 “内存占用” 与 “性能消耗” 之间平衡,确保过期键能被及时清理

1. 惰性删除(Lazy Expiration)
  • 触发时机:当执行任何涉及该 key 的命令(如 GETSET 等)时,Redis 会先检查 key 是否过期。

  • 执行逻辑

    • 若 key 已过期,立即删除该 key,再执行后续命令;
    • 若未过期,直接执行命令。
  • 特点

    • 优势:“按需删除”,不占用额外 CPU 资源(仅在访问时检查);
    • 劣势:若过期 key 长期未被访问,会占用内存(内存泄漏风险)。
  • 适用范围:仅支持对最外层 key 设置过期时间(如 Hash、List 等结构的内部字段无法单独设置过期时间)。

  • 相关命令

    • expire key seconds:设置 key 的过期时间(秒);
    • pexpire key milliseconds:设置 key 的过期时间(毫秒);
    • ttl key:返回 key 剩余过期时间(秒,-1 表示永不过期,-2 表示已过期);
    • pttl key:返回 key 剩余过期时间(毫秒)。
2. 定时删除(Active Expiration)

为弥补惰性删除的内存泄漏问题,Redis 同时采用定时删除策略,主动清理部分过期 key。

  • 触发机制:由后台定时器定期执行,每次检查一定数量的过期 key。

  • 核心配置与逻辑

    • 默认每次检查 25 个 key(由 ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP 定义);
    • 可通过 effort 参数调整检查强度(默认 1,最大 10),计算公式为:config_keys_per_loop = 20 + 20/4*effort(effort 越大,每次检查的 key 越多);
    • 执行函数 activeExpireCycleTryExpire 负责具体的过期检查与删除。
    #define ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP 20 /*
    Keys for each DB loop. */
    /*The default effort is 1, and the maximum
    configurable effort* is 10. */
    config_keys_per_loop =
    ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP +ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP/4*effort,
    int activeExpireCycleTryExpire(redisDb *db,
    dictEntry *de, long long now);
    
  • 特点

    • 优势:主动清理长期未访问的过期 key,减少内存占用;
    • 劣势:若检查过于频繁,会消耗 CPU 资源(Redis 通过控制检查频率和数量避免性能波动)。

惰性删除保证 “访问时过期键必被清理”,避免无效数据干扰;定时删除主动清理 “长期未访问的过期键”,防止内存溢出。两者结合,既保证了性能,又控制了内存占用

1.4 大Key

“大 Key” 指 Redis 中存储的体积过大的对象(如包含数万字段的 Hash、百万元素的 ZSet 等),这类 key 会导致明显的性能问题

1. 大 Key 的危害

  • 扩容卡顿:大 Key 所在的哈希表或数据结构(如 Hash、ZSet)扩容时,需要一次性申请大量内存(如从 1MB 扩容到 2MB),可能导致 Redis 短暂阻塞;
  • 删除卡顿:删除大 Key 时,Redis 需要一次性释放大量内存,触发内存回收机制,同样会导致卡顿;
  • 内存波动:大 Key 的创建 / 删除会导致 Redis 内存使用 “大起大落”,容易触发内存告警或 OOM(内存溢出)。

大Key 的检测

通过 Redis 自带的 redis-cli --bigkeys 命令检测大 Key,该命令基于 SCAN 遍历所有键,统计不同类型中体积最大的键。

redis-cli -h 127.0.0.1 --bigkeys -i 0.1
  • --bigkeys:开启大 Key 检测;
  • -i 0.1:每执行 100 条 SCAN 命令后,暂停 0.1 秒,避免检测过程阻塞 Redis 服务。

解决方案

  • 拆分大 Key:将大 Hash 拆分为多个小 Hash,大 ZSet 按范围拆分为多个小 ZSet;
  • 避免批量操作:对大 Key 避免使用 HGETALLZRANGE 0 -1 等全量查询命令;
  • 异步删除:Redis 4.0+ 支持 UNLINK 命令(异步删除),替代 DEL,减少删除时的卡顿。

1.5 跳表

Redis 中的跳表(Skiplist)是一种多层级有序链表结构,主要用于实现有序集合(ZSet),支持高效的范围查询(如 ZRANGEZREVRANGE)和排序操作。其设计兼顾了查询性能与实现复杂度,通过 “空间换时间” 的思路,在保证平均时间复杂度接近平衡树的同时,避免了复杂的节点分裂 / 重构操作

在这里插入图片描述

为什么使用跳表?

跳表的诞生是为了解决 “有序集合的高效查询与修改” 问题:

  • 有序数组通过二分查找可实现 O (logN) 查询,但插入 / 删除需移动元素(O (N) 复杂度);

  • 平衡二叉树(如 B+ 树)可实现 O (logN) 操作,但节点分裂 / 合并逻辑复杂,不适合 Redis 对 “简单高效” 的需求;

  • 跳表通过多层级链表模拟 “跳跃式查询”,兼顾查询效率(接近 O (logN))和实现简单性(插入 / 删除无需复杂重构),成为 ZSet 的理想底层结构。

跳表时间复杂度分析

  1. 理想跳表的逻辑
    理想情况下,跳表每间隔一个节点生成一个 “高层级节点”,模拟二叉树结构(如第 1 层每 2 个节点有 1 个高层节点,第 2 层每 4 个节点有 1 个高层节点),此时查询时间复杂度为 O(logN)。但这种结构在插入 / 删除后难以维护(重构成本极高)。

  2. 概率化跳表(实际实现)
    为避免重构,跳表采用概率化层级生成

    • 每个新节点有 25%(Redis 中为 ZSKIPLIST_P=0.25)的概率增加 1 个层级,25%×25% 的概率增加 2 个层级,以此类推(最高层级有限制)。
    • 当数据量足够大(如 ≥128)时,概率化生成的跳表结构趋向于理想跳表,查询、插入、删除的平均时间复杂度仍为 O(logN),且无需复杂重构。

在这里插入图片描述

跳表的实现

  • 最高层级ZSKIPLIST_MAXLEVEL=32(足够支持 2^64 个元素),避免层级过高导致的内存浪费。
  • 层级概率ZSKIPLIST_P=0.25(1/4),即每个节点晋升到下一层的概率为 25%,平衡层级数量与内存占用。

Redis 跳表通过 zskiplistNode(节点)和 zskiplist(跳表顶层结构)实现,配合 zset 结构体与字典(dict)协同工作

// 跳表节点
typedef struct zskiplistNode {sds ele;               // 元素值(字符串)double score;          // 排序分数(仅支持浮点数)struct zskiplistNode *backward; // 后退指针(用于反向遍历)struct zskiplistLevel {struct zskiplistNode *forward; // 前进指针(当前层级的下一个节点)unsigned long span;            // 跨度(当前节点到下一个节点的元素数量,用于计算排名 ZRANK)} level[];             // 动态层级数组(长度为节点实际层级)
} zskiplistNode;// 跳表顶层结构
typedef struct zskiplist {struct zskiplistNode *header, *tail; // 头节点、尾节点unsigned long length;                // 元素总数(对应 ZCARD 命令)int level;                           // 当前跳表的最高层级
} zskiplist;// ZSet 结构体(结合跳表与字典)
typedef struct zset {dict *dict;            // 字典:key=元素值,value=分数(快速查询元素分数)zskiplist *zsl;        // 跳表:按分数排序,支持范围查询
} zset;

在这里插入图片描述

更多资料:https://github.com/0voice

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/bicheng/90945.shtml
繁体地址,请注明出处:http://hk.pswp.cn/bicheng/90945.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【RAG优化】深度剖析OCR错误,从根源修复RAG应用的识别问题

1. 引言:OCR——RAG系统中的关键问题 当我们将一个包含扫描页面的PDF或一张报告截图扔给RAG系统时,我们期望它能“读懂”里面的内容。这个“读懂”的第一步,就是OCR。然而,OCR过程并非100%准确,它受到图像质量、文字布局、字体、语言等多种因素的影响。 一个看似微不足道…

【第六节】方法与事件处理器

方法与事件处理器 方法处理器 可以用 v-on 指令监听 DOM 事件: <div id="example"> <button v-on:click="greet">Greet</button></div>绑定一个单击事件处理器到一个方法 greet 。下面在 Vue 实例中定义这个方法 var vm=new V…

大语言模型Claude 4简介

Anthropic公司成立于2021年&#xff0c;由一群OpenAI前员工组成。他们最新发布的大语言模型(Large Language Model, LLM) Claude 4系列包括两个版本&#xff1a;Claude Opus 4和Claude Sonnet 4&#xff1a;(1).Claude Sonnet 4&#xff1a;是Claude Sonnet 3.7的升级&#xff…

国产化PDF处理控件Spire.PDF教程:Python 将 PDF 转换为 Markdown (含批量转换示例)

PDF 是数字文档管理的普遍格式&#xff0c;但其固定布局特性限制了在需要灵活编辑、更新或现代工作流集成场景下的应用。相比之下&#xff0c;Markdown&#xff08;.md&#xff09;语法轻量、易读&#xff0c;非常适合网页发布、文档编写和版本控制。 E-iceblue旗下Spire系列产…

PDF转Markdown - Python 实现方案与代码

PDF作为广泛使用的文档格式&#xff0c;转换为轻量级标记语言Markdown后&#xff0c;可无缝集成到技术文档、博客平台和版本控制系统中&#xff0c;提高内容的可编辑性和可访问性。本文将详细介绍如何使用国产Spire.PDF for Python 库将 PDF 文档转换为 Markdown 格式。 技术优…

深度解析 inaSpeechSegmenter:高效音频语音分割与检测开源工具

项目简介 inaSpeechSegmenter 是法国国家视听研究院(INA)开源的音频分割与检测工具,专为广播、播客、采访、影视等多媒体内容的自动化处理设计。它能够高效地将长音频自动分割为语音、音乐、噪声、静音等片段,并支持性别检测(男声/女声),为后续的语音识别、内容检索、转…

VirtualBox安装Ubuntu 22.04后终端无法打开的解决方案

问题现象在VirtualBox中使用"快速安装"模式安装Ubuntu 22.04后图形终端&#xff08;gnome-terminal&#xff09;无法通过图标或快捷键(CtrlAltT)启动系统其他功能正常根本原因语言环境(Locale)配置异常导致&#xff1a;快速安装模式可能跳过Locale生成步骤gnome-term…

java磁盘操作与IO流(序列化、Properties类)

目录 一、磁盘操作 1、File类&#xff1a; &#xff08;1&#xff09;创建File对象&#xff1a; &#xff08;2&#xff09;获取文件信息&#xff1a; &#xff08;3&#xff09;判断文件 &#xff08;4&#xff09;删除文件 &#xff08;5&#xff09;创建文件&#xff…

【WPF】WPF Prism 开发经验总结:菜单命令删除项时报 InvalidCastException 的问题分析与解决

WPF Prism 开发经验总结&#xff1a;菜单命令删除项时报 InvalidCastException 的问题分析与解决 在 WPF Prism 项目中使用 ContextMenu 执行删除操作时&#xff0c;遇到一个令人疑惑的问题&#xff1a;命令绑定本身没有问题&#xff0c;但点击“删除”菜单后&#xff0c;程序抛…

《WebGL打造高性能3D粒子特效系统:从0到1的技术探秘》

在游戏里,爆炸时四溅的火花、魔法释放时闪烁的光晕;在可视化项目中,数据流动时呈现的璀璨光河,这些令人惊叹的效果,背后离不开强大的技术支撑。而WebGL,作为在浏览器端实现硬件加速3D图形渲染的技术,为我们开启了构建高性能3D粒子特效系统的大门。 WebGL的渲染管线是整…

全国计算机等级考试二级题库【C语言】:程序填空题型——结构体 自制答案详解合辑

二级C语言程序填空题型简介 1、/**********found**********/紧跟的下面一行的程序设空,一般为3个空; 2、常见错误: (1) (2) 3、做题推荐步骤: (1) (2) ---------------一、结构体--------------- 2、题目要求【结构体】 程序通过定义学生结构体变量,存储了学生…

人工智能与城市:城市生活的集成智能

1. 智慧城市的核心价值&#xff1a;从 “硬件堆砌” 到 “智能协同”1.1 传统城市的治理困境全球 55% 的人口居住在城市&#xff0c;到 2050 年这一比例将升至 68%。传统城市管理面临多重挑战&#xff1a;资源分配失衡&#xff1a;早晚高峰主干道拥堵率达 80%&#xff0c;而支线…

Linux下挂载磁盘报superblock错误

Linux下挂载磁盘报superblock错误背景问题现象1、使用fdisk查询设备文件信息2、挂载磁盘&#xff0c;报出fs type错误解决办法1、使用e2fsk命令检查整个磁盘2、resize2fs 命令调整文件系统块大小和物理磁盘块大小3、挂载磁盘&#xff0c;确认修复结果问题思考1、rclone命令做数…

Http证书体系及证书加密流程(通信流程)

一、HTTPS 证书体系&#xff1a;信任的基石 HTTPS 证书体系是保障网络通信安全的核心机制&#xff0c;其本质是一套基于公钥基础设施&#xff08;PKI&#xff0c;Public Key Infrastructure&#xff09; 的信任体系&#xff0c;通过数字证书实现通信双方的身份验证和数据加密&…

【分布式架构】学习路径概述:了解分布式系统的核心问题、解决方案与实战说明

文章目录零、前言一、分布式系统理论1、 分布式系统的一致性问题1.1、一致性问题理论&#xff08;CAP/BASE&#xff09;1.2、 一致性协议与算法&#xff08;Paxos/Raft&#xff09;&#xff1a;选主、分布式锁1.3、 分布式事务(2PC\3PC\TCC)&#xff1a;服务一致性保障与性能2、…

C# 密封类_密封方法 (seadled 关键字)

C#允许将类声明为密封类&#xff0c;密封类不能被继承在什么场景用&#xff1f;答&#xff1a;防止重写某些类导致代码混乱密封类seadled 声明密封类的关键字//seadled 声明密封类的关键字 //密封类不能被继承 sealed class Class1 {public int age;public string name;publi…

深度学习(鱼书)day04--手写数字识别项目实战

深度学习&#xff08;鱼书&#xff09;day04–手写数字识别项目实战 鱼书的相关源代码下载&#xff1a; 点击链接&#xff1a;http://www.ituring.com.cn/book/1921 点击“随书下载” 第三项就是源代码&#xff1a; 解压后&#xff0c;在pycharm&#xff08;或其它IDE&#…

【自用】NLP算法面经(6)

一、FlashAttention 1、Tile-Based计算 将q,k,v分块为小块&#xff0c;每次仅处理一小块&#xff1a; 利用gpu的片上SRAM完成QK^T和softmax避免中间结果写入HBM 标准attention的计算算法如下&#xff1a;标准attention实现大量中间结果需要频繁访问HBM&#xff0c;而HBM的访问速…

Vue页面卡顿优化:从理论到实战的全面解释

目录 1. 理解Vue页面卡顿的幕后黑手 1.1 响应式系统的“双刃剑” 1.2 虚拟DOM的“隐藏成本” 1.3 浏览器渲染的“性能陷阱” 实战案例:一个“罪魁祸首”的排查 2. 优化响应式系统:让数据“轻装上阵” 2.1 使用v-if和v-show控制渲染 2.2 冻结静态数据 2.3 精细化响应式…

从0开始学linux韦东山教程Linux驱动入门实验班(6)

本人从0开始学习linux&#xff0c;使用的是韦东山的教程&#xff0c;在跟着课程学习的情况下的所遇到的问题的总结,理论虽枯燥但是是基础。本人将前几章的内容大致学完之后&#xff0c;考虑到后续驱动方面得更多的开始实操&#xff0c;后续的内容将以韦东山教程Linux驱动入门实…