# 概述

《redis 设计与实现》是基于 2.9 版本写作的，现在（2023.06.27）redis 已经更新到 7.0.11 版本了，虽然书中有些介绍已经过时，但是还是可以对 redis 建立起大致的认知的。

# 一、数据结构与对象

redis 有五种基本类型：String、List、Hash、Set、ZSet，目前 7 版本还有五种特殊类型：HyperLogLog、Geospatial、Stream、Bitmaps、Bitfields。

# 数据结构

五种常用的基本类型，底层使用的数据结构有：SDS（Simple Dynamic String）、list、hashtable、zipList、intset、skiplist。

	graph TB;
	String ==> SDS
	List ==> list
	List ==> ziplist
	Hash ==> ziplist
	Hash ==> hashtable
	Set ==> hashtable
	Set ==> intset
	Zset ==> ziplist
	Zset ==> skiplist

在 redis3.2 版本之后 List 底层数据采用快表（quicklist）实现。

# SDS

简单动态字符串，其（3.2 版本之前）结构是：

	struct sdshdr {
	unsigned int len; //buf 中已经使用的长度
	unsigned int free; //buf 中未使用的长度
	char buf[]; // 柔性数组 buf
	};

SDS 与 C 字符串区别：

与 C 字符串不同，使用额外两个变量记录长度，可以使得我们可以 O (1) 时间复杂度级别获取字符串长度。
二进制安全：C 字符串只能使用 ASCII 编码，可能因为二进制文件中可能包含空字符 '\0'，导致 C 字符串误以为终止符，而 sds 使用 len 属性判定终止，不会与文件内容冲突。
杜绝缓存区溢出：C 字符串中，如果出现两个字符串在内存中相邻，修改前字符串 1（长度变长）而不分配空间，就会导致字符串 2 内容被修改。SDS 在修改字符串会先判断给定空间是否足够，足够就直接修改，不够就会先分配空间再去修改。
减少字符串修改带来的内存重分配次数：C 字符串并不记录自身长度，每次修改都需要进行内存重分配：增长字符串不进行内存重分配 — 缓冲区溢出，缩小字符串长度不进行内存重分配 — 内存泄露。Redis 作为数据库，如果每次修改都去做内存中分配，就会对性能造成影响，所以 redis 采用空间预分配以及惰性空间释放策略。

# 空间预分配

在 SDS 增长字符串长度时，如果发现原本的空间不足以修改，需要内存重分配，除了为 SDS 分配修改所必需的空间，还会分配额外的空间：

如果 SDS 修改之后长度小于 1MB，程序会分配和 len 属性同样大小的未使用空间，此时 SDS 的值等于 free 的值
如果 SDS 修改之后长度大于等于 1MB，会分配 1MB 的未使用空间

执行过 APPEND 命令的字符串会带有额外的预分配空间，这些预分配空间不会被释放，除非该字符串所对应的键被删除，或者等到关闭 Redis 之后，再次启动时重新载入的字符串对象将不会有预分配空间。

# 链表 list

作为 List 类型的底层实现，3.2 之后就废用了，使用快表代替。

typedef struct listNode{
    struct listNode *prev;
    struct listNode *next;
    void *value;
}

双端链表

typedef struct list{
	struct listNode *head;
    struct listNode *tail;
    unsigned long len;

}

# 压缩列表 ziplist

压缩列表是列表（3.2 版本之前）和 Hash 表底层实现。

大致结构：

zlbytes	ztail	zllen	entry1	...	entryX	zlend

zlbytes：压缩列表总字节数
ztail：尾部偏移量
zllen：节点数量
entryX：节点

entry 结构：

previous_entry_length	encoding	content

previous_entry_length：前一个节点的长度
encoding：值的编码
content：存储内容（指针指向）

	/* ziplist header 的大小：两个 32 位整数，用于总字节计数 (bytes) 和最后一项偏移量 (ZIPLIST_TAIL_OFFSET)。一个 16 位整数，节点数 (ZIPLIST_LENGTH (zl))。*/
	#define ZIPLIST_HEADER_SIZE (sizeof(uint32_t)*2+sizeof(uint16_t))
	/* ziplist 结尾标识，1 字节. */
	#define ZIPLIST_END_SIZE (sizeof(uint8_t))
	/* 创建一个新的压缩列表 . */
	unsigned char *ziplistNew(void) {
	unsigned int bytes = ZIPLIST_HEADER_SIZE + ZIPLIST_END_SIZE;
	unsigned char *zl = zmalloc(bytes);
	// 压缩列表总字节长度
	ZIPLIST_BYTES(zl) = intrev32ifbe(bytes);
	// 尾节点的偏移量
	ZIPLIST_TAIL_OFFSET(zl) = intrev32ifbe(ZIPLIST_HEADER_SIZE);
	// 节点个数
	ZIPLIST_LENGTH(zl) = 0;
	// 特殊结尾值
	zl[bytes-1] = ZIP_END;
	return zl;
	}

	// 压缩列表节点
	typedef struct zlentry {
	unsigned int prevrawlensize //prevrawlen 的大小，有 1 字节和 5 字节两种
	unsigned int prevrawlen; //prevrawlen 是前一个节点的长度
	unsigned int lensize; // lensize 为编码 len 所需的字节大小
	unsigned int len //len 为当前节点长度
	unsigned int headersize; // 当前节点的 header 大小
	unsigned char encoding; // 节点的编码方式
	unsigned char *p; // 指向节点的指针
	} zlentry;

# 快表 quicklist

3.2 版本之后作为 List 类型的底层实现，是双端链表和压缩列表的结合，使用压缩列表作为双端链表的节点

	typedef struct quicklistNode {
	struct quicklistNode *prev;
	struct quicklistNode *next;
	unsigned char entry; / 指向压缩列表 */
	size_t sz; /* ziplist 字节数 */
	unsigned int count : 16; /* ziplist 节点数量 */
	unsigned int encoding : 2; /* 编码 RAW=1，LZF=2 */
	unsigned int container : 2; /* 容器，NONE=1，ziplist=2 */
	unsigned int recompress : 1; /* 节点是否已被压缩 */
	unsigned int attempted_compress : 1; /* 测试使用，在压缩时，设为 1，解压时设为 0 */
	unsigned int dont_compress : 1; /* 防止压缩稍后将使用的节点 */
	unsigned int extra : 9; /* 留用字段 */
	} quicklistNode;

	// 存储 LZF 压缩后的数据，对于 quicklistNode 来说：
	// 如果数据未被压缩，数据直接存储在 node->zl 中
	// 如果数据被压缩，则 node->zl 存储一个 quicklistLZF，压缩后的数据存在 quicklistLZF 中
	typedef struct quicklistLZF {
	unsigned int sz; //compressed 的大小
	char compressed[]; // LZF 压缩后的数据
	} quicklistLZF;

	// 书签
	typedef struct quicklistBookmark {
	quicklistNode *node; // 书签标记的节点
	char *name; // 书签名
	} quicklistBookmark;

	// 快表定义，size: 40 bytes
	typedef struct quicklist {
	quicklistNode *head; // 头节点
	quicklistNode *tail; // 尾节点
	unsigned long count; // 元素的数量
	unsigned long len; //quicklistNode 的数量
	int fill : QL_FILL_BITS; /* QL_FILL_BITS=16 单个节点的填充系数
	如果为负数则使用的为默认值，参考 optimization_level*/
	unsigned int compress : QL_COMP_BITS; /* QL_COMP_BITS=16，
	压缩深度，对整个列表压缩时，只压缩头尾往中各 compress 个节点，如果为 0 则表示不压缩 */
	unsigned int bookmark_count : QL_BM_BITS; /* QL_BM_BITS=4，
	书签的数量；默认只给了 4 位，空了 4 位没有使用，使用过多的书签会导致性能下降 */
	quicklistBookmark bookmarks[]; // 当前使用的书签
	} quicklist;

	// 快表条目
	typedef struct quicklistEntry {
	const quicklist *quicklist; // 条目所属快表
	quicklistNode *node; // 条目所属节点
	unsigned char *zi; //ziplist item 指针
	unsigned char *value; // 条目的字符串值起始指针
	long long longval; // 条目的整数值
	unsigned int sz; // 条目的大小
	int offset; // 条目在节点中的偏移量（位置）
	} quicklistEntry;
	快表源码解释原文链接：https://blog.csdn.net/weixin_44016271/article/details/110286635

# 字典 / 哈希表 dict

字典是 Set 和 Hash 的底层数据结构。以下是 7 版本的源码。

	struct dict {
	dictType *type;
	// 哈希表数组，有两个用于 rehash
	dictEntry **ht_table[2];
	// 两张哈希表中，分别使用了多少
	unsigned long ht_used[2];

	long rehashidx; /* 记录 rehash 进度的标志，-1 表示 rehash 未进行 */

	/* Keep small vars at end for optimal (minimal) struct padding */
	//pauserehash 为 6 后新加入的特性，为保证效率新增 rehash 的 paused 的操作。
	int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
	signed char ht_size_exp[2]; /* hash 表的长度，2 的 n 次方 */

	void metadata[]; / An arbitrary number of bytes (starting at a
	* pointer-aligned address) of size as defined
	* by dictType's dictEntryBytes. */
	};

	/*
	* dictType 中是一个存放函数的结构体，定义了一些函数指针。
	*/
	typedef struct dictType {
	uint64_t (hashFunction)(const void key);// 哈希函数
	void (keyDup)(dict d, const void key);// 复制 key
	void (valDup)(dict d, const void obj);// 复制 val
	int (keyCompare)(dict d, const void key1, const void key2);// 比较 key
	void (keyDestructor)(dict d, void *key);// 删除 key
	void (valDestructor)(dict d, void *obj);// 删除 val
	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. */
	size_t (dictEntryMetadataBytes)(dict d);
	} dictType;

	typedef 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. */
	void metadata[]; / An arbitrary number of bytes (starting at a
	* pointer-aligned address) of size as returned
	* by dictType's dictEntryMetadataBytes(). */
	} dictEntry;

在书中有提到 dict 是这样的：

	typedef struct dict {
	dictType *type;
	void *privdata;
	dictht ht[2];
	int trehashidx;
	} dict;

	typedef struct dictht {
	dictEntry **table;
	dictType *type;
	unsigned long size;
	unsigned long sizemask;
	unsigned long used;
	};

但是在 7 版本并未使用，而是直接使用 dictEntry **ht_table[2]; 等属性来构造字典

# rehash

当负载因子小于 0.1 时，进行收缩操作。
当未执行 BGSAVE/BGREWRITEAOF 命令时，负载因子大于等于 1 时，进行扩展操作。
当在执行 BGSAVE/BGREWRITEAOF 命令时，负载因子大于等于 5 时，进行扩展操作。

当执行 BGSAVE/BGREWRITEAOF 时提高扩展所需负载因子，主要是因为执行这两个命令时都需要 redis 创建子进程，而此时进行 rehash 操作可能会触发子进程的 "写时复制" 机制。所以此时减少 rehash 操作即可避免不必要的内存写入操作，最大限度的节约内存。

rehash 步骤：

为字典两个哈希表中下标为 1 的未使用的哈希表分配空间：
- 扩展操作：ht [1] 大小 = 大于等于 ht [0].used*2 的 2 的 n 次方。（15 扩展后 32）
- 收缩操作：ht [1] 大小 = 大于等于 ht [0].used 的 2 的 n 次方。（12 收缩后 16）
- 注意是按照已使用也就是元素个数来 rehash，并不是按照 ht [0] 的空间大小来分。
将保存在 ht [0] 的所有键值对 rehash 到 ht [1] 中；
迁移完成后 ht [0] 变为空表，释放 ht [0] 空间，将 ht [1] 设置成 ht [0]，并为 ht [1] 创建空白哈希表，为下一次 rehash 做准备。

# 渐进式 rehash

为了防止在进行扩展 / 收缩的 rehash 时，由于数据过多造成服务器停止服务，采用了渐进式 rehash 思路。

为 ht [1] 分配空间，此时字典同时持有两个哈希表；
将 rehashidx 设置为 0，表示 rehash 开始；
在 rehash 期间，每次对字典执行增删改查都会额外将 ht [0] 中 rehashidex 索引上的的键值对 rehash 到 ht [1] 中，然后对于 rehashidx++；
所有键值对都被 rehash 到 ht [1] 上之后，rehashidx 置为 - 1，rehash 完成。

# 跳跃表 skiplist

跳跃表是 ZSet 的底层数据结构，跳跃表的缺点就是需要的存储空间比较大，属于利用空间来换取时间的数据结构。redis 跳跃表并没有在单独的类（比如 skplist.c) 中定义，而是其定义在 server.h 中：

	/* ZSETs use a specialized version of Skiplists */
	typedef struct zskiplistNode {
	// 持有数据，是 sds 类型
	sds ele;
	// 结点之间凭借得分来判断先后顺序，跳跃表中的结点按结点的得分升序排列.
	double score;
	// 原版跳跃表中所没有的。该指针指向结点的前一个紧邻结点.
	struct zskiplistNode *backward;
	//level 数组用以记录所有结点 (除过头节点外)，每个结点中最多持有 32 个 zskiplistLevel 结构
	struct zskiplistLevel {
	// 指向比自己得分高的某个结点 (不一定是紧邻的)
	struct zskiplistNode *forward;
	// 表 forward 字段指向的结点，距离当前结点的距离.
	unsigned long span;
	} level[];
	} zskiplistNode;

	typedef struct zskiplist {
	struct zskiplistNode header, tail;
	unsigned long length;
	int level;
	} zskiplist;

	typedef struct zset {
	dict *dict;
	zskiplist *zsl;
	} zset;

为什么不使用其他数据结构？

skiplist 和各种平衡树（如 AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个 key 的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

后端