Redis设计与实现笔记 - 数据结构篇

Redis设计与实现笔记 - 数据结构篇

相信在我们日常使用中,会经常跟 Redis 打交道。数据结构 String、Hash、List、Set 和 ZSet 都是常用的数据类型。对于使用场景,我们可以滔滔不绝地说很多,但是我们从来就没有关心过它们的底层实现,到底它们的数据是怎么存储的,代码是怎么实现的,使用上有什么值得注意的地方。带着这些疑问,我去查看了相关的书籍,对于实现有了大致的认识。希望你看完后也有所收获。

先统一名词:我们常用的 String、Hash、List、Set 和 ZSet 叫做对象(Object)。它们由如 SDS、LinkList、Skiplist 等基础数据结构组成。

数据结构

简单动态字符串 - SDS

struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; /* 已使用的长度 */uint64_t alloc; /* 分配的长度 不包含头部和空终止符号 */unsigned char flags; /* 3位最低有效位表示类型, 其余5个比特位未被使用 */char buf[];
};
  1. 常数复杂度获取字符串长度。C 语言中的传统字符串类型需要遍历整个字符串才能获取字符串长度,时间复杂度为 O(n),而 SDS 可以直接获取字符串长度,时间复杂度为 O(1)。

  2. 杜绝缓冲区溢出。SDS 在字符串末尾预留了额外的空间,当字符串长度增加时,可以直接使用预留的空间,避免了缓冲区溢出的问题。

  3. 减少修改字符串长度时带来的内存重分配次数。SDS 采用了空间预分配和惰性空间释放等策略,可以减少修改字符串长度时带来的内存重分配次数,提高性能。

  4. 可含有空字符等特殊字符

主要用于字符串对象的底层实现

链表

/* 双端链表节点 */
typedef struct listNode {/* 指向前驱节点的指针 */
struct listNode *prev;/* 指向后继节点的指针 */
struct listNode *next;/* void * 指针,指向具体的元素,节点可以是任意类型 */
void *value;
} listNode;/* 双端链表迭代器 */
typedef struct listIter {/* 指向遍历的下一个节点的指针 */listNode *next;/* 遍历的方向:从表头遍历还是从表尾遍历 */int direction;
} listIter;/* 双端链表* 有记录头尾两节点,支持从链表头部或者尾部进行遍历,是早期列表键 PUSH/POP 实现高效的关键* 每个链表节点有记录前驱节点和后继节点的指针,可以使得列表键支持往后或者往前进行遍历* 有额外用 len 存储链表长度,O(1) 的时间复杂度获取节点个数,是 LLEN 命令高效的关键 */
typedef struct list {/* 指向链表头节点的指针,支持从表头开始遍历 */listNode *head;/* 指向链表尾节点的指针,支持从表尾开始遍历 */listNode *tail;/* 各种类型的链表可以定义自己的复制函数 / 释放函数 / 比较函数 */void *(*dup)(void *ptr);void (*free)(void *ptr);int (*match)(void *ptr, void *key);/* 链表长度,即链表节点数量,O(1) 时间复杂度获取 */unsigned long len;
} list;
  1. 常数复杂度获取链表长度

  2. 双端链表实现

  3. 多态实现,各种类型的链表可以自己定义各自的复制函数 / 释放函数 / 比较函数

主要用于列表对象的底层实现

字典

typedef struct dictEntry {/* void * 类型的 key,可以指向任意类型的键 */void *key;/* 联合体 v 中包含了指向实际值的指针 *val、无符号的 64 位整数、有符号的 64 位整数,以及 double 双精度浮点数。* 这是一种节省内存的方式,因为当值为整数或者双精度浮点数时,由于它们本身就是 64 位的,void *val 指针也是占用 64 位(64 操作系统下),* 所以它们可以直接存在键值对的结构体中,避免再使用一个指针,从而节省内存开销(8 个字节)* 当然也可以是 void *,存储任何类型的数据,最早 redis1.0 版本就只是 void* */union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;     /* Next entry in the same hash bucket. *//* 同一个 hash 桶中的下一个条目.* 通过形成一个链表解决桶内的哈希冲突. */void *metadata[];           /* An arbitrary number of bytes (starting at a* pointer-aligned address) of size as returned* by dictType's dictEntryMetadataBytes(). *//* 一块任意长度的数据 (按 void* 的大小对齐),* 具体长度由 'dictType' 中的* dictEntryMetadataBytes() 返回. */
} dictEntry;typedef struct dict dict;/* 字典类型,因为我们会将字典用在各个地方,例如键空间、过期字典等等等,只要是想用字典(哈希表)的场景都可以用* 这样的话每种类型的字典,它对应的 key / value 肯定类型是不一致的,这就需要有一些自定义的方法,例如键值对复制、析构等 */
typedef struct dictType {/* 字典里哈希表的哈希算法,目前使用的是基于 DJB 实现的字符串哈希算法* 比较出名的有 siphash,redis 4.0 中引进了它。3.0 之前使用的是 DJBX33A,3.0 - 4.0 使用的是 MurmurHash2 */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 (*expandAllowed)(size_t moreMem, double usedRatio);/* Allow a dictEntry to carry extra caller-defined metadata.  The* extra memory is initialized to 0 when a dictEntry is allocated. *//* 允许调用者向条目 (dictEntry) 中添加额外的元信息.* 这段额外信息的内存会在条目分配时被零初始化. */size_t (*dictEntryMetadataBytes)(dict *d);
} dictType;/* 通过指数计算哈希表的大小,见下面 exp,哈希表大小目前是严格的 2 的幂 */
#define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp))
/* 计算掩码,哈希表的长度 - 1,用于计算键在哈希表中的位置(下标索引) */
#define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)/* 7.0 版本之前的字典结构
typedef struct dictht {dictEntry **table; // 8 bytesunsigned long size; // 8 bytesunsigned long sizemask; // 8 bytesunsigned long used; // 8 bytes
} dictht;typedef struct dict {dictType *type; // 8 bytesvoid *privdata; // 8 bytesdictht ht[2]; // 32 bytes * 2 = 64 byteslong rehashidx; // 8 bytesint16_t pauserehash; // 2 bytes
} dict;** 做的优化大概是这样的:* 1. 从字典结构里删除 privdata (这个扩展其实一直是个 dead code,会影响很多行,社区里的做法都是想尽量减少 diff 变更,避免说破坏 git blame log)* 2. 将 dictht 字典哈希表结构融合进 dict 字典结构里,相关元数据直接放到了 dict 中* 3. 去掉 sizemark 字段,这个值可以通过 size - 1 计算得到,这样就可以少 8 字节* 4. 将 size 字段转变为 size_exp(就是 2 的 n 次方,指数),因为 size 目前是严格都是 2 的幂,size_exp 存储指数而不是具体数值,size 内存占用从 8 字节降到了 1 字节** 内存方面:*   默认情况下通过 sizeof 我们是可以看到新 dict 是 56 个字节*   dict:一个指针 + 两个指针 + 两个 unsigned long + 一个 long + 一个 int16_t + 两个 char,总共实际上是 52 个字节,但是因为 jemalloc 内存分配机制,实际会分配 56 个字节*   而实际上因为对齐,最后的 int16_t pauserehash 和 char ht_size_exp[2] 加起来是占用 8 个字节,代码注释也有说,将小变量放到最后来获得最小的填充。*/struct dict {/* 字典类型,8 bytes */dictType *type;/* 字典中使用了两个哈希表,* (看看那些以 'ht_' 为前缀的成员, 它们都是一个长度为 2 的数组)** 我们可以将它们视为* struct{*   ht_table[2];*   ht_used[2];*   ht_size_exp[2];* } hash_table[2];* 为了优化字典的内存结构,* 减少对齐产生的空洞,* 我们将这些数据分散于整个结构体中.** 平时只使用下标为 0 的哈希表.* 当需要进行 rehash 时 ('rehashidx' != -1),* 下标为 1 的一组数据会作为一组新的哈希表,* 渐进地进行 rehash 避免一次性 rehash 造成长时间的阻塞.* 当 rehash 完成时, 将新的哈希表置入下标为 0 的组别中,* 同时将 'rehashidx' 置为 -1.*/dictEntry **ht_table[2];/* 哈希表存储的键数量,它与哈希表的大小 size 的比值就是 load factor 负载因子,* 值越大说明哈希碰撞的可能性也越大,字典的平均查找效率也越低* 理论上负载因子 <=1 的时候,字典能保持平均 O(1) 的时间复杂度查询* 当负载因子等于哈希表大小的时候,说明哈希表退化成链表了,此时查询的时间复杂度退化为 O(N)* redis 会监控字典的负载因子,在负载因子变大的时候,会对哈希表进行扩容,后面会提到的渐进式 rehash */unsigned long ht_used[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 *//* rehash 的进度.* 如果此变量值为 -1, 则当前未进行 rehash. *//* Keep small vars at end for optimal (minimal) struct padding *//* 将小尺寸的变量置于结构体的尾部, 减少对齐产生的额外空间开销. */int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) *//* 如果此变量值 >0 表示 rehash 暂停* (<0 表示编写的代码出错了). *//* 存储哈希表大小的指数表示,通过这个可以直接计算出哈希表的大小,例如 exp = 10, size = 2 ** 10* 能避免说直接存储 size 的实际值,以前 8 字节存储的数值现在变成 1 字节进行存储 */signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) *//* 哈希表大小的指数表示.* (以 2 为底, 大小 = 1 << 指数) */
};

结构体有点长,简单展示就是如下

  1. dictEntry 存的是一个链表,因为redis解决hash冲突的方式是使用链地址法,其他解决方法可参考  解决哈希冲突的常用方法分析 - 腾讯云

  2. 这里注意一下ht这个字段,正常来说一个ht[1]是不会使用的,只有在rehash过程中才会有值

rehash

字典的负载因子(load factor)超过一定阈值时就会启动rehash, 在过程中对于字典的增删改查都会先查一遍ht[0],然后把值迁移到ht[1],等到ht[0]迁移完毕就会释放ht[0],将ht[1]设置成ht[0]

主要用于哈希对象和数据库的底层实现,对,没错,整个数据库也是一个大哈希实现

跳表

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {sds ele;double score;struct zskiplistNode *backward;struct zskiplistLevel {struct zskiplistNode *forward;unsigned long span;} level[];
} zskiplistNode;typedef struct zskiplist {struct zskiplistNode *header, *tail;unsigned long length;int level;
} zskiplist;
  1. zskiplist 使用双端链表实现

  2. 在遍历操作时只需要用到 forward 前行指针,查找过程

    1. 如果下一个节点比目标节点大,则移动到下一个节点

    2. 否则移动到下一层

    3. 重复以上步骤,直到找到目标值

跳表与字典结合作为有序集合的底层实现

整数集合

/* 整数集合 * 记录不包含重复元素的各个整数(由小到大的顺序) * 底层数组默认是 int16_t 类型, 可能随着新增元素的大小升级至 int32_t 或 int64_t 类型*/
typedef struct intset {/* 编码, 记录整数集合底层数组(contents)的类型*/uint32_t encoding;/* 记录整数集合包含的元素个数 */uint32_t length;/* 整数集合的底层实现, 虽声明为 int8_t 类型,但真正的类型取决于 encoding */int8_t contents[];
} intset;
  1. 支持类型 int16_t, int32_t, int64_t

  2. 在插入一个不同当前编码的值就会触发升级,遍历所有value转换类型,且不支持降级

原本 1, 2, 3

0-15位

16-31位

32-48位

48-127位

元素

1

2

3

新分配空间

插入 65535

0-31位

32-63位

64-95位

96-127位

元素

1

2

3

65535

用于当value都是整数,并且个数不超过512的集合底层实现

压缩列表

ziplist 压缩列表是由一系列字节数组表示的,每个字节数组可以表示一个节点的信息,包括节点的类型、长度和值等信息。

压缩列表的布局如下:

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>

属性

类型

长度

用途

zlbytes

uint32_t

4字节

记录整个压缩列表占用的内存字节数:在对压缩列表进行内存重分配
或者计算zlend 的位置时使用

zltail

uint32_t

4字节

或者计算zlend 的位置时使用 记录压缩列表表尾节点西商压缩列表的起始地址有多少字节:通过这个
偏移量,程序无须遮历整个压缩列表就可以确定表尾节点的地址

zllen

uint16_t

2字节

记录了压缩列表包含的节点数量:当这个属性的值小于(65535)时,这个属性的值就是压缩列表包含节点的数量:当这个值等于 UINT16_MAx 时,节点的真实数量需要追历整个压缩列表才能计算得出

entry

列表节点

不定

压缩列表包含的各个节点,节点的长度由节点保存的内容决定

zlend

uint8_t

1字节

特殊值O x FF(十进制255),用于标记压缩列表的末端。

entry的布局如下

属性

用途

previous_entry_iength

前置节点长度记录了前一个节点的字节数,它的长度可以是 1 个字节或 5 个字节,具体占用的字节数取决于前一个节点的字节数,用于支持列表的反向遍历

encoding

节点类型记录了该节点存储的数据类型,它的长度为 1 个字节,

  • 字符串节点的类型为 0xc0,二进制表示为 11000000;

  • 整数节点的类型为 0x00,二进制表示为 00000000。

content

节点值记录了该节点存储的数据,它的长度为节点长度所记录的字节数。如果该节点是字符串节点,则节点值存储的是字符串的值;如果该节点是整数节点,则节点值存储的是整数的值。

连锁更新

由于previous_entry_length的长度是1或5,取决于前一个节点的长度,如果有个列表,每个节点的长度都是250-253之间,那么当第一个节点增加了长度,后续每一个节点需要增加长度,作者称这种现象为连锁更新,需要o(n)复杂度去更新每一个节点

为了解决这个问题, 后续在Redis7.0全面使用listpack代替了ziplist, 详细参与: Redis7.0代码分析:底层数据结构listpack实现原理 - 掘金

用于列表和哈希的底层实现

后续….

Redis3.2之后引入quicklist

引用

redis7源码中文注释

Redis设计与实现

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

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

相关文章

RSTP详解:对比STP,到底改进了什么?

一、RSTP概述 IEEE 802.1W中定义的RSTP可以视为STP的改进版本&#xff0c;RSTP在许多方面对STP进行了优化&#xff0c;它的收敛速度更快&#xff0c;而且能够兼容STP。 二、RSTP对STP的改进 改进点1&#xff1a;端口角色 、 改进点2&#xff1a;端口状态 RSTP的状态规范缩…

信息系统项目管理师有什么用?

导语&#xff1a; 在当今数字化时代&#xff0c;信息系统项目管理师扮演着至关重要的角色。他们负责规划、组织和管理信息系统项目&#xff0c;确保项目按时、按质、按预算完成。本文将探讨信息系统项目管理师的重要性和作用&#xff0c;以及他们对组织和项目成功的贡献。 一、…

数据库系列之MySQL中Join语句优化问题

最近使用MySQL 8.0.25版本时候遇到一个SQL问题&#xff0c;两张表做等值Join操作执行很慢&#xff0c;当对Join连接字段添加索引优化后&#xff0c;执行效率反而变得更差&#xff0c;其中的原因值得分析。因此本文介绍下MySQL中常见的Join算法&#xff0c;并对比使用不同Join算…

百度文心一言 4.0 :如何申请百度文心一言 4.0

本心、输入输出、结果 文章目录 百度文心一言 4.0 &#xff1a;如何申请百度文心一言 4.0前言文心一言 4.0 ERNIE-Bot 4.0 &#xff1a;ERNIE-Bot 4.0 大模型深度测试体验报告如何申请千帆大模型试用百度文心一言 4.0 主要功能介绍配套发布的十余款AI原生应用插件、API 生态 百…

图论相关算法

一、迪杰斯特拉(Dijkstra)算法 迪杰斯特拉算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。这是一个贪心算法。 1.核心思想 &#xff08;1&#xff09;每次选中一个点&#xff0c;这个点满足两个条件&#xff1a; 未被选过距离最短 &#xff08;2&#xf…

如何使用 MiniGPT-v2

MiniGPT-v2 是一个基于视觉语言模型&#xff08;LLM&#xff09;的多任务学习系统。它可以用于各种视觉语言任务&#xff0c;包括图像描述、图像识别、图像-文本对话等。 本文将介绍如何使用 MiniGPT-v2。 MiniGPT-v2 提供了一个简单的在线演示&#xff0c;可以用于测试模型。…

ENVI IDL:对于GEOTIFF结构体的说明

Tag标签-前言 其中最关键的只有两个标签Tag&#xff0c;一个是MODELPIXELSCALETAG&#xff0c;一个是MODELTIEPOINTTAG。 至于ModelTransformationTag我没用过不了解&#xff0c;但是应该是关于仿射变换相关的&#xff0c;用于将像素坐标与地理/投影坐标进行转换的矩阵。 对于…

k8s kubernetes 1.23.6 + flannel公网环境安装

准备环境&#xff0c;必须是同一个云服务厂商&#xff0c;如&#xff1a;华为&#xff0c;阿里、腾讯等&#xff0c;不要存在跨平台安装K8S&#xff0c;跨平台安装需要处理网络隧道才能实现所有节点在一个网络集群中&#xff0c;这里推荐使用同一家云服务厂商安装即可 这里使用…

黄金眼PAAS化数据服务DIFF测试工具的建设实践 | 京东云技术团队

一、背景介绍 黄金眼PAAS化数据服务是一系列实现相同指标服务协议的数据服务&#xff0c;各个服务间按照所生产指标的主题作划分&#xff0c;比如交易实时服务提供实时交易指标的查询&#xff0c;财务离线服务提供离线财务指标的查询。黄金眼PAAS化数据服务支撑了黄金眼APP、黄…

用Python获取网络数据

用Python获取网络数据 网络数据采集是 Python 语言非常擅长的领域&#xff0c;上节课我们讲到&#xff0c;实现网络数据采集的程序通常称之为网络爬虫或蜘蛛程序。即便是在大数据时代&#xff0c;数据对于中小企业来说仍然是硬伤和短板&#xff0c;有些数据需要通过开放或付费…

b树和b+树

二叉树和平衡二叉树 二叉树&#xff0c;每个节点支持两个分支的树结构&#xff0c;相比于单向链表&#xff0c;多了一个分支。 二叉查找树&#xff0c;在二叉树的基础上增加了一个规则&#xff0c;左子树的所有节点的值都小于它的根 节点&#xff0c;右子树的所有子节点都大于它…

了解活动聊天机器人如何革新活动行业

在如今快节奏的时代&#xff0c;活动策划和管理对于任何活动的成功变得至关重要。无论是会议、展览会还是企业聚会&#xff0c;组织者都努力为参与者创造难忘的体验&#xff0c;同时确保幕后的顺利执行。然而&#xff0c;由于有许多任务需要处理且资源有限&#xff0c;管理活动…

双指针——盛水最多的容器

一, 题目要求 给定一个长度为 n 的整数数组 height 。有 n 条垂线&#xff0c;第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线&#xff0c;使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 说明&#xff1a;你不能倾斜容…

Django小白开发指南

文章目录 HTTP协议socket实现一个web服务器WSGI实现一个web服务器WSGI实现支持多URL的web服务器WSGI实现图片显示的web服务器MVC && MTV1.MVC2.MTV3.总结 一、创建Django项目1.创建项目2.创建app3.第一次django 请求 二、模板1.配置settings.py2.模板语法3.继承模板 三…

LLM ReAct: 将推理和行为相结合的通用范式 学习记录

LLM ReAct 什么是ReAct? LLM ReAct 是一种将推理和行为相结合的通用范式,可以让大型语言模型(LLM)根据逻辑推理(Reason),构建完整系列行动(Act),从而达成期望目标。LLM ReAct 可以应用于多种语言和决策任务,例如问答、事实验证、交互式决策等,提高了 LLM 的效率、…

小程序搭建OA项目首页布局界面

首先让我们来学习以下Flex布局 一&#xff0c;Flex布局简介 布局的传统解决方案&#xff0c;基于盒状模型&#xff0c;依赖 display属性 position属性 float属性 Flex布局简介 Flex是Flexible Box的缩写&#xff0c;意为”弹性布局”&#xff0c;用来为盒状模型提供最大的…

centos 7.9 安装sshpass

1.作用 sshpass是一个用于非交互式SSH密码验证的实用程序。它可以用于自动输入密码以进行SSH登录&#xff0c;从而简化了自动化脚本和批处理作业中的SSH连接过程。 sshpass命令可以与ssh命令一起使用&#xff0c;通过在命令行中提供密码参数来执行远程命令。以下是一个示例命…

客观来说这两年确实是香港优才计划申请的红利期!

客观来说这两年确实是香港优才计划申请的红利期&#xff01; 最明显的网上关于香港优才计划申请的帖子都比之前多了不少&#xff0c;首页经常随便一刷就是分享香港优才计划申请攻略的。 今年以来香港优才计划的政策也发生了很多变化&#xff1a; 1、取消年度配额限制&#xff0…

常见面试题-Redis专栏(一)

typora-copy-images-to: imgs了解 redis 中的大key吗&#xff1f;多大算是大key呢&#xff1f;如何解决&#xff1f; 答&#xff1a; redis 的大 key 指的是 key 对应的 value 所占用的内存比较大。 对于 string 类型来说&#xff0c;一般情况下超过 10KB 则认为是大 key&…

周记之学习总结

你在人群中看到的每一个耀眼的女孩&#xff0c;都是踩着刀尖过来的。你如履平地般地舒适坦然&#xff0c;当然不配拥有任何光芒&#xff1b; 10.11-10.12 思来想去还是不舍得&#xff0c;搞了一下这个jwt&#xff0c;看了很多视频和博客&#xff0c;一直没看懂&#xff0c;两…