redis底层数据结构

底层数据结构

一、SDS简单动态字符串

​ Redis是用C语言写的，因为 C的字符串表示（C是字符串是以\0空字符结尾的字符数组）char* 类型的功能单一， 抽象层次低， 并且不能高效地支持一些 Redis 常用的操作（比如追加操作和长度计算操作）,因此自己构建了一种简单动态字符串（simple dynamic string，SDS）的抽象类型，并作为Redis的默认字符串表示。

I、SDS定义

SDS的结构定义在sds.h文件中，SDS的定义在Redis 3.2版本之后有一些改变，由一种数据结构变成了5种数据结构，会根据SDS存储的内容长度来选择不同的结构，以达到节省内存的效果，具体的结构定义：

• len：记录当前已使用的字节数（不包括'\0'），获取SDS长度的复杂度为O(1)
• alloc：记录当前字节数组总共分配的字节数量（不包括'\0'）
• flags：标记当前字节数组的属性，是sdshdr8还是sdshdr16等，flags值的定义可以看下面代码
• buf：字节数组，用于保存字符串，包括结尾空白字符'\0'

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[];
};

在redis3.2版本之后会根据字符串来选择对应的数据结构：

static inline char sdsReqType(size_t string_size) {
    if (string_size < 1<<5)
        return SDS_TYPE_5;
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    if (string_size < 1<<16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

flags当前使用的数据结构定义：

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3

II、SDS与C字符串的区别

C语言使用长度为N+1的字符数组来表示长度为N的字符串，字符数组的最后一个元素为空字符'\0'，但是这种简单的字符串表示方法并不能满足Redis对于字符串在安全性、效率以及功能方面的要求。有以下两点考虑：

1. 它并不能高效地支持长度计算和追加（append）这两种操作:
   • C字符串不记录字符串长度，获取长度必须遍历整个字符串，复杂度为O(N)；
   • 对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配（realloc）。
2. Redis 除了处理 C 字符串之外， 还需要处理单纯的字节数组， 以及服务器协议等内容， 所以为了方便起见， Redis 的字符串表示还应该是二进制安全的： 程序不应对字符串里面保存的数据做任何假设， 数据可以是以 \0 结尾的 C 字符串， 也可以是单纯的字节数组， 或者其他格式的数据。

参考于《Redis设计与实现》

1. 常数复杂度获取字符串长度

​ SDS结构中本身就有记录字符串长度的len属性，所有复杂度为O(1)。Redis将获取字符串长度所需的复杂度从O(N)降到了O(1)，确保获取字符串长度的工作不会成为Redis的性能瓶颈

2. 杜绝缓冲区溢出，减少修改字符串时带来的内存重分配次数

​ C字符串不记录自身的长度，每次增长或缩短一个字符串，都要对底层的字符数组进行一次内存重分配操作。如果是拼接append操作之前没有通过内存重分配来扩展底层数据的空间大小，就会产生缓存区溢出；如果是截断trim操作之后没有通过内存重分配来释放不再使用的空间，就会产生内存泄漏

​ 而SDS通过未使用空间解除了字符串长度和底层数据长度的关联，3.0版本是用free属性记录未使用空间，3.2版本则是alloc属性记录总的分配字节数量。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化的空间分配策略，解决了字符串拼接和截取的空间问题

redis> SET msg "hello world"
OK

redis> APPEND msg " again!"
(integer) 18

redis> GET msg
"hello world again!"

执行以上命令是redis内部的运行情况：

struct sdshdr  {
 len = 11;
 alloc = 16;
 flags = 2;
 buf = "hello world\0";
}

当执行 APPEND 命令时，相应的 sdshdr 被更新，字符串 " again!" 会被追加到原来的 "hello world" 之后：

struct sdshdr  {
 len = 18
 alloc = 32;
 flags = 3;
 buf = "hello world again!\0";
}

注意， 当调用 SET 命令创建 msg时， sdshdr 的 free 属性为 0 ， Redis 也没有为 buf 创建额外的空间 —— 而在执行 APPEND 之后， Redis 为 buf 创建了多于所需空间一倍的大小。

sds的动态扩容机制：

1. 如果newlen小于1024（byte） * 1024（byte）=1（MB）则新的长度为二倍的newlen。
2. 如果newlen的长度大于等于1MB，则新的newlen的长度为newlen的长度加上1MB。

sds通过预分配一些内存区域来减少内存申请，拷贝的次数，虽然预分配规则很简单，但是是很有效的。

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

因为执行 APPEND 命令的字符串键数量通常并不多， 占用内存的体积通常也不大， 所以这一般并不算什么问题。

另一方面， 如果执行 APPEND 操作的键很多， 而字符串的体积又很大的话， 那可能就需要修改 Redis 服务器， 让它定时释放一些字符串键的预分配空间， 从而更有效地使用内存。

3. 二进制安全

​ C字符串中的字符必须符合某种编码，除了字符串的末尾，字符串里面是不能包含空字符的，否则会被认为是字符串结尾，这些限制了C字符串只能保存文本数据，而不能保存像图片这样的二进制数据

​ 而SDS的API都会以处理二进制的方式来处理存放在buf数组里的数据，不会对里面的数据做任何的限制。SDS使用len属性的值来判断字符串是否结束，而不是空字符

兼容部分C字符串函数

虽然SDS的API是二进制安全的，但还是像C字符串一样以空字符结尾，目的是为了让保存文本数据的SDS可以重用一部分C字符串的函数

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

二.链表

​ 链表是一种比较常见的数据结构了，特点是易于插入和删除、内存利用率高、且可以灵活调整链表长度，但随机访问困难。许多高级编程语言都内置了链表的实现，但是C语言并没有实现链表，所以Redis实现了自己的链表数据结构

链表在Redis中应用的非常广，列表（List）的底层实现就是链表。此外，Redis的发布与订阅、慢查询、监视器等功能也用到了链表

I、链表节点和链表的定义

链表上的节点定义如下，adlist.h/listNode

typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点值
    void *value;
} listNode;
复制代码

链表的定义如下，adlist.h/list

typedef struct list {
    // 链表头节点
    listNode *head;
    // 链表尾节点
    listNode *tail;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
    // 链表所包含的节点数量
    unsigned long len;
} list;
复制代码

每个节点listNode可以通过prev和next指针分布指向前一个节点和后一个节点组成双端链表，同时每个链表还会有一个list结构为链表提供表头指针head、表尾指针tail、以及链表长度计数器len，还有三个用于实现多态链表的类型特定函数

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

II、链表结构图

III、链表特性

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

​ 双向链表因为使用两个额外的空间存储前驱和后继指针，因此在数据量较小的情况下会造成空间上的浪费(因为数据量小的时候速度上的差别不大，但空间上的差别很大)。这是一个时间换空间还是空间换时间的思想问题，Redis在列表对象中小数据量的时候使用压缩列表作为底层实现，而大数据量的时候才会使用双向无环链表。

参考以下文章

• 掘金 CoderZS https://juejin.cn/post/6844903951502934030
• 掘金 TurboSnail https://juejin.cn/post/6844903936520880135
• https://www.laoyu.site/2018/%E6%8A%80%E6%9C%AF%E5%AE%9E%E8%B7%B5/redis/Redis%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E2%80%94%E2%80%94%E9%93%BE%E8%A1%A8/