# 概述

《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 的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。

后端