redis核心数据结构源码分析

devtools/2024/12/21 20:35:33/

dictEntry和redisObject

在 Redis 的实现中，当一个键值对被创建并存储时，键通常是一个字符串，而值则是一个 redisObject。因此，在 dictEntry 结构中，key 成员指向的是一个字符串，而 v.val 成员则指向一个 redisObject。这意味着，当你在 Redis 中存储一个值时，你实际上是在字典中插入一个 dictEntry，其中 dictEntry 的值部分指向一个包含实际数据和元数据的 redisObject。

dictEntry

struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;     /* Next entry in the same hash bucket. */
};
/*位置：dict.c*/

一个dictEntry就是哈希表中的一个结点。

1.void *val：这是指向键的指针。在 Redis 中，键通常是字符串，但这里使用void * 是为了增加灵活性，允许键的类型在底层实现中变化。

2.union { ... } v;

这是一个联合体（union），就是哈希表结点中的value。

void *val;：一个通用指针，通常用于指向更复杂的数据结构，如链表、压缩列表或字符串。

uint64_t u64;：一个无符号 64 位整数，用于存储较小的数值类型。

int64_t s64;：一个带符号 64 位整数，用于存储较小的数值类型。

double d;：一个双精度浮点数，用于存储实数。

在任何给定时刻，联合体中只有一个成员会被使用，具体取决于值的实际类型。这种设计节省了内存，因为不需要为每种类型分配独立的空间。

3.struct dictEntry *next;  

链地址法解决哈希冲突

redisObject

struct redisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or* LFU data (least significant 8 bits frequency* and most significant 16 bits access time). */int refcount;void *ptr;
};
/*位置：server.h*/

1.unsigned type:4;

4位的type表示具体的数据类型。包括OBJ_STRING,OBJ_LIST,OBJ_HASH,OBJ_SET,OBJ_ZSET

可通过type命令查看

2.unsigned encoding:4;

4位的encoding表示该类型的物理编码方式(如下），同一种数据类型可能有不同的编码方式。(比如String就提供了3种:int embstr raw)

#define OBJ_ENCODING_RAW 0     /* Raw representation */
#define OBJ_ENCODING_INT 1     /* Encoded as integer */
#define OBJ_ENCODING_HT 2      /* Encoded as hash table */
#define OBJ_ENCODING_ZIPMAP 3  /* No longer used: old hash encoding. */
#define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. */
#define OBJ_ENCODING_ZIPLIST 5 /* No longer used: old list/hash/zset encoding. */
#define OBJ_ENCODING_INTSET 6  /* Encoded as intset */
#define OBJ_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define OBJ_ENCODING_EMBSTR 8  /* Embedded sds string encoding */
#define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of listpacks */
#define OBJ_ENCODING_STREAM 10 /* Encoded as a radix tree of listpacks */
#define OBJ_ENCODING_LISTPACK 11 /* Encoded as a listpack */
#define OBJ_ENCODING_LISTPACK_EX 12 /* Encoded as listpack, extended with metadata */
/*位置：server.h*/

可通过object encoding命令查看 

3.unsigned lru:LRU_BITS;

对象最后一次被访问的时间戳，与内存回收有关。

4.int refcount

refcount表示对象的引用计数（可类比JVM中的引用计数法）

5.void *ptr

ptr指针指向实际对象

五大基本数据类型和底层数据类型对应关系

redis6

redis7

五大基本数据类型源码分析

 String

三大物理编码方式

1.int

保存long型的64位(8个字节）有符号整数

只有整数才会使用int,如果是浮点数，Redis内部其实先将浮点数转化为字符串值，然后再保存。

2.embstr

embedded string,表示嵌入式的String。代表embstr格式的SDS（simple dynamic string，简单动态字符串），保存长度小于44字节的字符串。

嵌入式怎么理解？

robj *createEmbeddedStringObject(const char *ptr, size_t len) {robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr8)+len+1);struct sdshdr8 *sh = (void*)(o+1);o->type = OBJ_STRING;o->encoding = OBJ_ENCODING_EMBSTR;o->ptr = sh+1;//sh 是 sdshdr8 结构体的指针，它紧跟在 redisObject 结构体之后在内存中分配。o->refcount = 1;o->lru = 0;sh->len = len;sh->alloc = len;sh->flags = SDS_TYPE_8;if (ptr == SDS_NOINIT)sh->buf[len] = '\0';else if (ptr) {memcpy(sh->buf,ptr,len);sh->buf[len] = '\0';} else {memset(sh->buf,0,len+1);}return o;
}
/*位置：object.c*/

字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间，字符串sds嵌入在redisObject对象之中一样。 

3.raw

保存长度大于44字节的字符串

源码证明：

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44
robj *createStringObject(const char *ptr, size_t len) {if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) //长度小于44return createEmbeddedStringObject(ptr,len);//emb编码elsereturn createRawStringObject(ptr,len);//raw编码
}
/*位置：object.c*/

SDS 

typedef char *sds;/* Note: sdshdr5 is never used, we just access the flags byte directly.* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {unsigned char flags; /* 3 lsb of type, and 5 msb of string length */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* used */uint8_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len; /* used */uint16_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* used */uint32_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; /* used */uint64_t alloc; /* excluding the header and null terminator */unsigned char flags; /* 3 lsb of type, 5 unused bits */char buf[];
};
/*位置：sds.h*/
  •  len:字符串的实际长度（不包括末尾的空字符），对sdshdr8的uint8_t 来说，可存储0-255的长度。
  • alloc:为字符串分配的总空间大小（同样不包括结构体头部和空终止符）。
  • flags：标志位。低 3 位被用于表示 SDS 的类型，而剩下的 5 位目前是未使用的。
  • buf:实际存储字符串的字符数组，SDS本质上也是一个字符数组。

为什么要重新设计一个简单动态字符串（SDS），而不直接用c语言的char[]？

  • 字符串长度处理：c的cha[]要遍历得到长度，时间复杂度为O(n)，SDS与len，直接读取即可，时间复杂度为O(1)。
  • 内存分配：预先分配更多的空间，减少频繁的内存重新分配；且SDS缩短时并不会回收多余的空间，而是用free将多余的空间记录下来，如果后序需要再分配，直接使用free标记的字段，而不用重新申请。
  • 因为c的char[]将\0作为字符串结束的标志，如果字符串内容中含有\0，会错把该字符当做结束标志。而SDS根据len判断字符串结束，不会有该问题。

Hash

redis6

redis中Hash结构由zipList和Hashtable构成。当hashkey满足1.哈希对象保存的键值对数量小于512个； 2.所有的键值对的健和值的字符串长度都小于等于64byte(一个英文字母一个字节)时用ziplist,反之用hashtable。ziplist升级到hashtable可以，反过来降级不可以。

ziplist：

ziplist 是一个经过特殊编码的双向链表，它的设计目标是节约内存。它可以存储字符串或者整数。其中整数是按二进制进行编码的，而不是字符串序列。它能以 O(1) 的时间复杂度在列表的两端进行 push 和 pop 操作。但是由于每个操作都需要对 ziplist 所使用的内存进行重新分配，所以实际操作的复杂度与 ziplist 占用内存大小有关。（官方注释）

因为 ziplist 的设计目标是为了 节约内存，而链表的各项之间需要使用指针连接起来，这种方式会带来大量的内存碎片，而且地址指针也会占用额外的内存，（压缩的地方）这与 ziplist 的设计初衷不符。而且后面我们看了 ziplist 的数据结构就会发现，ziplist 实际上是一块连续的内存。

因此我们可以这么理解：ziplist 是一个特殊的双向链表，特殊之处在于：没有维护双向指针，prev、next，而是存储了上一个 entry 的长度和当前 entry 的长度，通过长度推算下一个元素。

也就是：

  • 压缩列表本质上就是一个字节数组
  • 是 Redis 为了节约内存而设计的一种线性结构
  • 可以包含多个元素，每个元素可以是一个字节数组或一个整数

zipList结构：

 

每个entry结构：

 previous_entry_length 字段表示前一个元素的字节长度

encoding 字段表示当前元素的编码，记录了节点的 content 字段所保存数据的类型以及长度

content 字段存储节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性决定。

ziplist的连锁更新问题：

previous_entry_length 属性都记录了前一个节点的长度：

  • 如果前一节点的长度小于 254 字节，那么 previous_entry_length 属性需要用 1 字节长的空间来保存这个长度值。
  • 如果前一节点的长度大于等于 254 字节，那么 previous_entry_length 属性需要用 5 字节长的空间来保存这个长度值。

现在假设一个压缩列表中有多个连续的、长度在 250～253 之间的节点，如下图：

因为这些节点长度值小于 254 字节，所以 prevlen 属性需要用 1 字节的空间来保存这个长度值，一切OK，O(∩_∩)O哈哈~

这时，如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，即新节点将成为entry1的前置节点，如下图：

因为entry1节点的prevlen属性只有1个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作并将entry1节点的prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。

连续更新问题出现

entry1节点原本的长度在250～253之间，因为刚才的扩展空间，此时entry1节点的长度就大于等于254，因此原本entry2节点保存entry1节点的 prevlen属性也必须从1字节扩展至5字节大小。entry1节点影响entry2节点，entry2节点影响entry3节点......一直持续到结尾。这种在特殊情况下产生的连续多次空间扩展操作就叫做「连锁更新」 

为了解决连锁更新，redis7中出现了listpack（紧凑列表）

redis7

listpack（1.哈希对家保存的键值对数量小于512个；2.所有的键值对的健和值的字符串长度都小于等于64byte(一个英文字母一个字节)时用listpack,反之用nashtable listpack升级到hashtable可以，反过来降级不可以）

和ziplist列表项类似，listpack列表项也包含了元数据信息和数据本身。不过，为了避免ziplist引起的连锁更新问题，listpack中的每个列表项不再像ziplist列表项那样保存其前一个列表项的长度。

List

redis6

list用quicklist来存储，quicklist存储了一个双向链表，每个节点都是一个ziplist。

quicklist源码：

quicklistNode：

  

redis7

 Iist用quicklist来存储，quicklist存储了一个双向链表，每个节点都是一个listpack

Set

intset或hashtable

集合元素都是long类型并且元素个数<=set-max-intset-entries，编码就是intset,反之就是hashtable

zset

redis6是ziplist+skiplist。redis7是listpack+skiplist

当ZSet的元素数量比较少时，Redis会采用ZipList(ListPack)来存储ZSet的数据。ZipList(ListPack)是一种紧凑的列表结构，它通过连续存储元素来节约内存空间。当ZSet的元素数量增多时，Redis会自动将ZipList(ListPack)转换为SkipList,以保持元素的有序性和支持范围查询操作。

skiplist

时间复杂度：O(n)。空间复杂度：O(n) 


http://www.ppmy.cn/devtools/102363.html

相关文章

VS2022中打开某设计文件时闪退

VS2022中打开某设计文件时闪退

报错日志如下&#xff1a; 错误应用程序名称: devenv.exe&#xff0c;版本: 17.11.35219.272&#xff0c;时间戳: 0x66c41957 错误模块名称: KERNELBASE.dll&#xff0c;版本: 10.0.22621.3958&#xff0c;时间戳: 0xfbc3a4f6 异常代码: 0xe0434352 错误偏移量: 0x00000000000…
阅读更多...
【设计模式】单例模式、工厂模式、策略模式、观察者模式、装饰器模式

【设计模式】单例模式、工厂模式、策略模式、观察者模式、装饰器模式

1 单例模式 2 工厂模式 3 策略模式 4 观察者模式 5 装饰器模式 1 单例模式 class Singleton:"""单例模式&#xff1a;确保一个类只有一个实例&#xff0c;并提供一个全局访问点。在需要全局状态或者需要频繁创建和销毁实例会导致性能问题时非常有用。"&qu…
阅读更多...
大数据学习路线基础指南‌

大数据学习路线基础指南‌

随着信息技术的迅猛发展&#xff0c;‌大数据已成为当今社会的热门话题。‌无论是企业决策、‌市场分析还是科学研究&#xff0c;‌大数据都扮演着举足轻重的角色。‌对于想要投身这一领域的学习者来说&#xff0c;‌制定一份清晰、‌系统的大数据学习路线是至关重要的。‌提供…
阅读更多...
罗德与施瓦茨RS、UPV 音频分析仪 250KHZ 双通道分析仪UPL

罗德与施瓦茨RS、UPV 音频分析仪 250KHZ 双通道分析仪UPL

罗德与施瓦茨 UPV 音频分析仪的规格包括&#xff1a; 模拟 双通道分析仪&#xff1a;带宽高达 250 kHz 生成正弦波信号&#xff1a;单通道最高 185 kHz&#xff08;需要 B1&#xff09;和双通道最高 80 kHz FFT本底噪声&#xff1a;< -140dB 固有频率响应&#xff08;20 …
阅读更多...
计算机毕业设计选题推荐-高中素质评价档案系统-Java/Python项目实战

计算机毕业设计选题推荐-高中素质评价档案系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…
阅读更多...
【JS】使用MessageChannel实现深度克隆

【JS】使用MessageChannel实现深度克隆

前言 通常使用简便快捷的JSON 序列化与反序列化实现深克隆&#xff0c;也可以递归实现或者直接使用lodash。 但 JSON 序列化与反序列化 无法处理如下的循环引用&#xff1a; 实现 MessageChannel 内部使用了浏览器内置的结构化克隆算法&#xff0c;该算法可以在不同的浏览器上…
阅读更多...
c#入门篇5

c#入门篇5

目录 一、常量 二、枚举 1、枚举类型和int以及string类型之间的转换 2、注意事项 强制转换&#xff08;Explicit Casting&#xff09;&#xff1a; Enum.Parse 和 Enum.TryParse&#xff1a; 三、结构 定义方式&#xff1a;结构体使用 struct 关键字进行定义。结构体通常用…
阅读更多...
科技在教育领域的创新应用与在工作场所的智能化转型

科技在教育领域的创新应用与在工作场所的智能化转型

随着信息技术的迅猛发展&#xff0c;‌科技正以前所未有的速度改变着我们的生活、‌学习和工作方式。‌其中&#xff0c;‌教育领域和工作场所作为社会的重要组成部分&#xff0c;‌也迎来了深刻的变革。‌ 在教育领域&#xff0c;‌科技的创新应用为传统教学模式带来了颠覆性…
阅读更多...
最新文章

Copyright @ 2022~2023