Marvel-Site
Marvel
2022-07-24
目录

Redis底层数据结构

# Redis底层数据结构

内容参考：《Redis设计与实现》

# 1. 简单动态字符串

Redis没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，一下简称C字符串），而是构建了一种名为简单动态字符串（Simple Dynamic String，SDS）的抽象类型。

# 1.1 SDS定义

struct sdshdr {
	int len;
	int free;
	char buf[];
}
1
2
3
4
5
  • len：记录 buf 数组中已使用字节的数量，等于 SDS 所保存字符串的长度。
  • free：记录 buf 数组中未使用字节的数量。
  • buf[]：字节数组，用于保存字符串。

在这里插入图片描述

  • free 属性值为 5：表示 SDS 分配 5 字节未使用空间。
  • len 属性值为 5：表示 SDS 保存一个 5 字节长的字符串。
  • buf 属性是一个 char 类型的数组，保存了 5 个字符和 1 个空字符\0，后面由 5 字节未使用空间。长度为 5 + 5 + 1 = 11

# 1.2 SDS与C字符串区别

C 语言使用后为 N+1 的字符数组表示长度为 N 的字符串，并且字符数组最后一个元素总是空字符 \0。

🔶 常数复杂度获取字符串长度

C 字符串不记录自身的长度信息，所以获取一个 C 字符串的长度，程序必须遍历整个字符串，时间复杂度为O(N)。

SDS 在 len 属性中记录了 SDS 本身的长度，获取 SDS 长度的的时间复杂度为 O(1).

🔶 杜绝缓冲区溢出

C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（Buffer Overflow）。

举个例子，两个相邻内存中存放C字符串s1和s2，s1保存字符串redis，s2保存字符串mongoDB，如果此时将s1内容修改为Redis Cluster而忘记分配足够的空间，那么s1的数据将溢出到s2所在的空间，导致s2被修改。

SDS 空间分配策略完全杜绝 了发生缓冲区溢出的可能性，当需要对 SDS 进行修改时，首先检查 SDS 空间是否满足修改所需的要求，如果不满足会自动扩展空间到需要的大小后再进行修改。

🔶 减少修改字符串时带来的内存重分配次数

每次增长或缩短一个C字符串，程序都要对保存这个C字符串的数组进行一次内存重新分配：

  • 在操作之前，需要通过内存重分配来扩展底层数组空间大小，否则会产生缓冲区溢出。
  • 缩短字符操作：在操作之后，需要通过内存重分配来释放不再使用的空间，否则会产生内存泄露。

内存重分配设计复杂的算法，可能需要执行系统调用，非常耗时。在Redis中，需要经常修改字符串，并且对速度要求苛刻，如果每次修改字符串都要内存重分配的话，会对整体的性能造成影响。

SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。SDS实现了空间预分配和惰性空间两种优化策略。

▶ 空间预分配：用于优化字符串增长操作

当对SDS进行修改时（修改后的字符串长度变长），首先会检查未分配空间是否足够，如果足够的话，将使用未分配空间，而不需要空间扩展。如果空间不够的话，需要进行空间扩展，程序不仅会分配所需的必须空间，还会分配额外的空间。通过预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

▶ 惰性空间释放：用于优化字符串缩短操作

当SDS缩短时，并不会立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，为将来可能有的增长操作提供了优化。 SDS提供相应的API，在我们有需要时，真正地释放SDS的未使用空间，所以不需要担心惰性空间释放策略会造成内存浪费。

🔶 二进制安全

C字符串中的字符必须符合编码要求，除了字符串的末尾外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存图片、音频、视频、压缩文件这样的二进制数据。

为了确保Redis可以适用于各种不同的使用场景，不仅可以保存文本数据，还可以保存任意格式的二进制数据。SDS的API是二进制安全的，程序不会对数据做任何处理，输入在写入时是什么样，读出来就是什么样。

🔶 兼容部分C字符串函数

SDS 遵循 C 字符串以空字符串结尾的管理，这样可以重用一部分 <string.h> 库定义的函数。

🔷 总结

C字符串 SDS
获取字符串长度的时间复杂度为O(N) 获取字符串长度的时间复杂度为O(1)
API是不安全的，可能找出缓冲区溢出 API是安全的，不会找出缓冲区溢出
修改字符串长度N次必然执行N次内存重分配 修改字符串长度N次最多需要执行N次内存重分配
只能保存文本数据 可以保存文本或二进制数据
可以使用所有<string.h>库中的函数 可以使用部分<string.h>库中的函数

# 2. 链表

链表数据结构由链表和链表节点两部分组成。通过链表结构，使链表、链表节点的操作更加方便。

🔶 链表节点

链表节点使用adlist.h/listNode结构表示

typedef struct listNode {
	// 前置节点
	struct listNode *prev;
	// 后置节点
	struct listNode *next;
	// 节点值
	void *value;
}listNode;
1
2
3
4
5
6
7
8

多个listNode可以通过prev和next指针组成双端链表。

🔶 链表

链表使用adlist.h/list结构表示：

typedef struct list{
	// 表头节点
	listNode *head;
	// 表尾节点
	listNode *tail;
	// 链表所包含的节点数量
	unsigned long len;
	// 节点值复制函数
	void *(*dup) (void *ptr);
	// 节点值释放函数
	void *(*free) (void *ptr);
	// 节点值对比函数
	int (*match) (void *ptr, void *key);
}list;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

提供表头指针 head、表位指针 tail、链表长度计数器 len。

  • dup 函数：复制链表节点所保存的值。
  • free：释放链表节点所保存的值。
  • match：对比链表节点所保存的值和另一个输入值是否相等。

🔶 结构图

在这里插入图片描述

🔶 特性

  • 双端：链表节点带有prev、next指针，获取某个节点的前置节点和后置节点。
  • 无环：头节点prev指针和尾节点next指针指向NULL。
  • 带表头指针和表位指针：通过list结构的head指针和tail指针获取链表的表头节点和表尾节点的时间复杂度为O(1)。
  • 带链表长度计数器：获取链表中节点数量的时间复杂度为O(1)。
  • 多态：链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

# 3. 字典

字典（符号表、关联数组、映射），用于保存键值对的抽象数据结构。

# 3.1 实现

Redis的字典使用哈希表作为底层实现，由哈希表、哈希表节点、字典三个结构组成。一个哈希表里面可以有多个哈希表节点，每一个哈希节点就保存了字典中的一个键值对。

🔶 哈希表

哈希表使用dict.h/dictht结构表示

typedef struct dictht {
	// 哈希表数组
	dictEntry **table;
	// 哈希表大小
	unsigned long size;
	// 哈希表大小掩码，用于计算索引值
	// 总是等于size-1
	unsigned long sizemark;
	//该哈希表已有节点数量
	unsigned long used;
} dictht;
1
2
3
4
5
6
7
8
9
10
11

table属性是一个数组，数组中每个元素都是一个指向dictEntry结构的指针，每一个dictEntry结构保持着一个键值对。

在这里插入图片描述

🔶 哈希表节点

哈希表使用dict.h/dictEntry结构表示，每个dictEntry结构都保存着一个键值对。

typedef struct dictht {
	// 键
	void *key;
	// 值
	union {
		void *val;
		uint64_tu64;
		int64_ts64;
	} v;
	// 指向下个哈希表节点，形成链表
	struct dictEntry *next;
} dictEntry;
1
2
3
4
5
6
7
8
9
10
11
12
  • key 保存键
  • value 保存值，值可以是一个指针，或者是一个uint64_t整数，或者是一个int64_t整数。
  • next 是指向下一个哈希表节点的指针，用于解决哈希冲突。

在这里插入图片描述

🔶 字典

字典由dict.h/dict结构表示

typedef struc dict {
	// 类型特定函数
	dictType *type;
	// 私有数据
	void *privdata;
	// 哈希表
	dictht ht[2];
	// rehash索引（渐进式rehash扩容时使用，后面介绍），当rehash不再进行时，值为-1
	int trehashidx;
} dict;
1
2
3
4
5
6
7
8
9
10
  • type 和 privdata 属性是针对不同类型的键值对，为创建多态字典而设置的。
  • type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。
  • privdata 属性保存需要传给那些特定函数的可选参数。
typedef struc dictType {
	// 计算哈希值的函数
	unsigned int (*hashFunction) (const void *key);
	// 复制键的函数
	void *(*keyDup) (void *privdata, const void *key);
	// 复制值的函数
	void *(*valDup) (void *privdata, const void *obj);
	// 对比键的函数
	int (*keyCompare) (void *privdata, const void *key1, const void *key2);
	// 销毁键的函数
	void *(*keyDestructor) (void *privdata, const void *key);
	// 销毁值的函数
	void *(*valDestructor) (void *privdata, const void *obj);
} dictType;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

▶ ht 属性包含两个哈希表，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。 ▶ rehashidx 记录了 rehash 目前的进度，扩容到了第几个值，如果目前没有进行 rehash，值为 -1。

下图展示一个普通状态下的字典（没有进行rehash）：

image-20240426201202244

# 3.2 哈希算法

当要将一个新的键值添加到字典里面时，就是将其添加到ht[0]哈希表中，程序需要根据键值对的键计算出哈希值的索引值，根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

在这里插入图片描述

通过链表法解决哈希冲突。

在这里插入图片描述

# 3.3 rehash

随着操作的不断进行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load factor）维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行扩展或收缩。步骤如下：

  1. 为字典的 ht[1] 哈希表分配空间，ht[1] 的大小为第一个大于等于 $$ ht[0].used \times2^n $$
  2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面，就是重新计算键的哈希值和索引值，并移动到指定位置。
  3. 当 ht[0] 包含的所有键值对都迁移到 ht[1] 后（ht[0]变为空表），释放 ht[0]，将 ht[1] 设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。

# 3.4 渐进式rehash

如果 redis 的字典中保存大量键值对，要一次性将这些键值对全部 rehash 到 ht[1] 的话，庞大的计算可能会导致服务器在一段时间内停止服务。因此需要分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到 ht[1]。下面是 rehash 的步骤：

  1. 为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
  2. 在字典中维持一个索引计算器变量 rehashidx，并将它设置为 0，表示 rehash 正式开始。
  3. 在 rehash 进行期间，每次对字典执行添加、删除、查找或更新操作时，程序除了执行指定的操作以外，还会顺带将 ht[0] 在哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成之后，程序将 rehashidx 值增一。
  4. 随着字典操作的不断执行，最终在某个时间点上，ht[0] 的所有键值对都会被 rehash 至 ht[1]，这时程序将 rehashidx 属性设置为 -1，表示 rehash 操作已完成。

在渐进式 rehash 过程中，字典会同时使用 ht[0] 和 ht[1]，所以字典的删除、查找、更新等操作会在两个哈希表上进。

例如，要在字典里面查找一个键的话，程序会现在ht[0]里面查找，如果没找到的话，就会继续到ht[1]里面查找。

在渐进式 rehash 过程中，添加到字典的键值对一律会被保存到 ht[1] 里面，保证 ht[0] 的键值对数量只减不增。

# 四、跳跃表

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表支持平均 O(logN)、最坏 O(N) 复杂度的节点查找。

Redis 使用跳跃表作为有序集合键的底层实现之一。

跳跃表由 zskiiplistNode 跳跃表节点和 zskiplist 跳跃表两个结构定义：

# 4.1 跳跃表节点

跳跃表节点由 redis.h/zskiplistNode 结构定义：

typedef struct zskiplistNode {
	// 层
	struct zskiplistLevel {
		// 前进指针
		struct zskiplistNode *forward;
		// 跨度
		unsigned int span;
	} level[];
	// 后退指针
	struct zskiplistNode *backward;
	// 分值
	double score;
	// 成员对象
	robj *obj;
} zskiplistNode;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

🔶 层 level[]

跳跃表的level数组可以包含很多元素，每个元素都包含一个指向其他节点的指针，可以通过这些层来加快访问其他节点的速度，层的数量越多访问节点的速度越快。

每次创建一个新跳跃表节点的时候，程序都根据幂次定律随机生成一个介于1和32之间的值作为level数组的大小。

🔶 前进指针 forward

每个层都有一个指向表尾方向的前进指针level[i].forward

🔶 跨度 span

层的跨度level[i].span用于记录两个节点之间的距离。跨度并不是用于遍历操作，而是用于计算排位的，在查找某一个节点的过程中，将沿途访问过的所有层的跨度累计起来，得到的结果就是目标节点在跳跃表中的排位。

🔶 后退指针 backward

用于从表尾向表头方向访问节点，每个节点只有一个后退指针，每次只能后退至前一个节点。

🔶 分值 score 和成员 obj

分值：double 类型，跳跃表中的所有节点都按分支从小到大排序。

成员对象：是一个指针，它指向一个SDS字符串对象。各个节点保存的成员对象必须是唯一的，分值相同的节点按成员对象在字典序中的大小来进行排序。

# 4.2 跳跃表

跳跃表由redis.h/zskiplist结构定义：

typedef struct zskiplist {
	// 表头节点和表尾节点
	struct skiplistNode *header, *tail;
	// 表中节点的数量
	unsigned long length;
	// 表中数量最大的节点的层数
	int level;
}
1
2
3
4
5
6
7
8

header和tail指针分别指向跳跃表的表头和表尾节点，通过这两个指针，程序定位表头节点和表尾节点的复杂度尾O(1)。

跳跃表结构如下图：

在这里插入图片描述

编辑 (opens new window)
#Redis
上次更新: 2024/04/26, 20:23:02
Redis常用命令
Redis数据结构

← Redis数据结构→

最近更新
01
位运算
05-21
02
二叉树
05-12
03
Spring三级缓存解决循环依赖
03-25
更多文章>
Theme by Vdoing | Copyright © 2022-2024 Marvel