Redis 底层数据结构 —— SDS（简单动态字符串）

文章目录

前言
一、SDS是什么？
二、为什么要采用SDS?
三、SDS结构详解
- 3.1 SDS 类型定义
- 3.2 SDS结构组成
四、SDS的预分配内存
五、再谈为什么要采用SDS?
六、总结

前言

我们都知道redis是用c语言实现的，但是c语言并没有字符串结构，而是通过字符数组来间接的表示字符串，如下形式：

char *name = "Jasmine"

而对于c语言来说，对应的存储结果，如下：
在这里插入图片描述

一、SDS是什么？

SDS（Simple Dynamic String） 是 Redis 自研的字符串类型，它是 Redis 为了解决 C 语言原生字符串（以 \0 结尾的字符数组）的一些局限性而设计的。SDS 是动态字符串，可以高效地进行字符串操作并避免了 C 字符串的常见问题（如缓冲区溢出等问题）。

在 Redis 中，所有与字符串相关的数据（如键、值、集合成员等）都使用 SDS 作为底层存储结构。

举一个栗子，客户端set一个值时：

redis> SET msg "hello world"
OK

那么Redis将在数据库中创建了一个新的键值对，其中：

键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串 “msg” 的 SDS 。
键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串 “hello world” 的 SDS 。

也就是key-value都是一个SDS结构

二、为什么要采用SDS?

C语言的字符数组存在的问题：

1.获取字符串长度需要通过运算，时间复杂度O(N)。
2. 非二进制安全。某二进制字符串里面可能也存在’\0’，会导致读取提前结束。

什么是二进制安全？通俗讲，C语言中，用’\0’表示字符串的结束，如果字符串中本身就有’\0’字符，字符串就会被截断，即非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则为二进制安全。

3.不可修改。C语言存储的字符数组在内存中是保存在常量池中，如果要更改就需要重新开辟空间，而且这个过程是相当耗时的

三、SDS结构详解

Redis 根据字符串长度，使用不同的结构体优化内存（以 Redis 5.0 为例）：

3.1 SDS 类型定义

// sdshdr5 结构（长度 ≤ 31）
struct __attribute__((packed)) sdshdr5 {unsigned char flags;  // 低3位存储类型，高5位存储长度char buf[];
};// sdshdr8 结构（长度 ≤ 255）
struct __attribute__((packed)) sdshdr8 {uint8_t len;        // 已使用长度uint8_t alloc;      // 总分配空间（不含头和空字符）unsigned char flags;// 低3位存储类型，高5位未使用char buf[];
};// 类似还有 sdshdr16、sdshdr32、sdshdr64，使用更大位宽的 len 和 alloc。

3.2 SDS结构组成

redis根据所存储的数据类型，将sds划分为五种，分别为sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。虽然64位类型下最大字符串长度为2^63-1，但redis依然限制了字符串最大长度为512MB。在每一种sdshdr里，都包含len、alloc、flags和buf，其中len + alloc + flags被称为header。

len：buf数组中已使用的字节数量，不包括结束符（字符串实际长度）。
alloc：分配的总空间（不含头和空字符），包括 '\0' 结束符。该值通常大于或等于 len，以避免频繁的内存分配和扩展。
flags：低3位标识 SDS 类型（如 SDS_TYPE_5、SDS_TYPE_8），高5位在 sdshdr5 中存储长度。
buf：柔性数组，存储实际数据，末尾保留 '\0'。

从上面插图可以看到sds由两部分构成，分别为sdshdr和alloced_buf，下面会分别说明

sdshdr：SDS 的头部结构，包含了关于字符串的元数据。这个结构存储了字符串的长度、已分配的空间以及与字符数组 buf 相关的信息。

为了尽可能的节省空间Redis将sdshdr的种类做了细分，根据字符串的长度不同，分配不同类型的sdshdr，不同sdshdr的大小也不一样

结构体类型	适用长度范围	len 和 alloc 位宽	内存占用（头+元数据）
sdshdr5	0 ≤ len ≤ 31	高5位存储长度	1字节（仅 flags）
sdshdr8	32 ≤ len ≤ 255	8位（1字节）	3字节（flags+len+alloc）
sdshdr16	256 ≤ len ≤ 65535	16位（2字节）	5字节
sdshdr32	65536 ≤ len ≤ 2^32-1	32位（4字节）	9字节
sdshdr64	极大字符串（罕见）	64位（8字节）	17字节

SDS本质上就是一个char类型的指针，指向上图中sdshdr和alloced buf之间的位置，指针指向位置之后的内容和C字符串完全兼容，而SDS获取字符串长度，以及当前分配空间的大小是先通过解析SDS指向位置前一个字节的Flags字段内容，获取到当前sdshdr的类型，再通过不同sdshdr类型向前移动若干个字节获取Len和Alloc字段内容实现的。
在这里插入图片描述

不管是什么类型的sdshdr，flags字段只占用一个字节，flags字段的低三位用来存储该sdshdr的type，而高五位大多数场景下是无效的，除非当前是sdshdr5类型，就把当前字符串的长度存放到高五位当中(sdshd5类型的SDS，alloced buf的长度就是字符串的长度，没有空间预分配)，从而节省了Len和Alloc字段占用的空间

四、SDS的预分配内存

在 Redis 中，SDS（Simple Dynamic String）采用了空间预分配和惰性空间释放的策略，以优化 C 字符串操作时频繁内存分配的问题。传统的 C 字符串，每次增加或缩短时，操作系统会进行内存重新分配，这会导致性能下降，尤其是在频繁进行字符串拼接或修改的情况下。为了解决这个问题，Redis 对存储字符串的缓冲区（Alloced buf）进行了优化，采取了“空间换时间”的策略，尽量避免内存重新分配的影响。

空间预分配：

若修改后长度 newlen < 1MB，则分配 newlen * 2。
若 newlen ≥ 1MB，则额外分配 1MB。

惰性空间释放：缩短字符串时不立即释放内存，保留空闲空间供后续操作复用。

五、再谈为什么要采用SDS?

采用SDS有以下几个优点：
1.有单独的统计变量len和free(称为头部)。可以很方便地得到字符串长度。
2.内容存放在柔性数组buf中，SDS对上层暴露的指针不是指向结构体SDS的指针，而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。
3.由于长度统计变量len的存在，读写字符串时不依赖'\0'终止符，保证了二进制安全。

buf[]是一个柔性数组。柔性数组成员，也叫伸缩性数组成员，只能被放在结构体的末尾，包含柔性数组成员的结构体，通过malloc函数为柔性数组动态分配内存。用柔性数组存放字符串，是因为柔性数组的地址和结构体是连续的，这样查找内存更快(因为不需要额外通过指针找到字符串的位置)；可以很方便地通过柔性数组的首地址偏移得到结构体首地址，进而能很方便地获取其余变量。