Redis中SDS的数据结构

Redis 是用 C 语言写的，但是对于Redis的字符串，却不是 C 语言中的字符串（即以空字符’\0’结尾的字符数组），它是自己构建了一种名为 简单动态字符串（simple dynamic string）简称SDS的抽象类型，并将 SDS 作为 Redis的默认字符串表示。

设置和获取Redis字符串值

redis 127.0.0.1:6379> SET xiaoxu code
OK
redis 127.0.0.1:6379> GET xiaoxu
"code"

SDS的结构

Redis3.2之前的结构

struct sdshdr {
    int len;  // 记录 buf 数组中已使用字节的数量，即字符串长度
    int free; // 记录 buf 数组中未使用字节的数量
    char buf[]; // 用于存储字符串的字节数组
};

Redis 3.2 及之后的 SDS 结构

SDS在Redis源码中的结构代码

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 
    uint8_t alloc; 
    unsigned char flags; 
    char buf[]; 
};

字段说明：

len : 记录buf数组中已使用的字节数量
alloc : 分配的buf数组长度，不包括头和空字符结尾
flags : 标志位，标记当前字节数组是 sdshdr8/16/32/64 中的哪一种，占 1 个字节。
buf[] : 字符数组，用于存放实际字符串

对应在文章开头中我们设置的 key="xiaoxu"、value="code"，存储情况如下图所示：

从图中可以看出SDS 也遵循 C 字符串以空字符“\0”结尾的惯例，而保存空字符的大小不计算在 SDS 的 len 属性中。

不过你也注意到了此时表示SDS类型的flags字段的值是 1，也就是 sdshdr8。

SDS的类型

Redis 3.2 版本之后，SDS 由一种数据结构变成了 5 种数据结构。这5 种类型分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64 五种类型的区别在于数组的 len 长度和分配空间长度 alloc。

sdshdr5：存储大小为 32 byte = 2^ 5 【被弃用】
sdshdr8：存储大小为 256 byte = 2^ 8
sdshdr16：存储大小为 64KB = 2 ^16
sdshdr32：存储大小为 4GB = 2^ 32
sdshdr64：存储大小为 2^ 64

五种数据类型的源码

底层编码选择

字符串是 Redis最基本的数据类型，Redis 中字符串对象的编码可以是下面三种类型：

int 编码：存储8个字节的长整型（long，2^63-1）字符串，长度小于等于20
embstr 编码：长度小于44字节的字符串
raw 编码：长度大于44字节的字符串

示例

SDS的经典问题

1.SDS如何进行高效的字符串长度的计算

我们都知道，在 Redis 内部，字符串的长度计算特别常见，这个操作对应在 C 语言中就是 strlen 命令。
在 C 语言中，字符串并不记录自身的长度信息，所以为了获取一个 C 字符串的长度，程序必须遍历整个字符串，对遇到的每个字符串进行计数，直到遇到代表字符串结尾的空字符串为止，整个时间复杂度为 O(N)。

但是这种简单的操作不应该成为 Redis 性能的瓶颈，于是 Redis 定义了一个 len 属性，专门用于存储字符串的长度，获取字符串的长度操作的时间复杂度为 O(1)，典型的空间换时间。
关于 len 属性问题，我们后续看 Redis SDS 数据结构就会明白。

2.二进制安全问题

在 C 语言中，字符串实际上是使用字符 \0 终止的一维字符数组。比如说，hello world 在 C 语言中就可以表示为 "hello world\0"。所以在 C 语言获取一个字符串长度，会逐个字符遍历，直到遇到代表字符串结尾的空字符为止。这就会导致二进制安全问题。

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

实际上，使用 SDS 会保证二进制安全，因为在 SDS 中，是使用 len 属性而不是空字符串来判断字符串是否结束。

3.缓存区溢出问题

C 语言不记录自身长度带来的另外一个问题就是容易造成缓存区溢出。
简单的来说，缓存区溢出通常指向缓存区写入了超过缓存区所能保存的最大数据量的数据。

比如我们使用

char *strcat(char *dest, const char *src);

strcat函数来将 src 字符串中的内容拼接到 dest 字符串的末尾。

因为 C 字符串不记录自身的长度，所以 strcat 会假定用户在执行这个函数时，已经为 dest 分配足够多的内存了，可以容纳 src 字符串中的所有内容，而一旦这个假设不成立，就会产生缓存区溢出。
我们举例看一下：
比如我们在内存中有紧挨着的两个字符串 s1 和 s2，其中 s1 字符串保存 redis，s2 字符串保存 mysql，他们在内存中应该是这个样子的：

假如，我们把 “Redis” 改为 “Redis Client”，但忘记了重新分配内存，就会导致如下所示的结果。

可以看到，我们修改 “Redis” 字符串时，无意导致把 “Mysql” 字符串的位置给占了，导致数据污染。
所以在使用 strcat 拼接两个字符串时，一定要判断第一个字符串后面是否有足够的内存空间；如果不够了，就得手动扩容，这一系列判断 + 扩容操作需要开发人员自己去完成，步骤有些麻烦。
而 Redis SDS 提供的所有修改字符串的 API 中，都会判断修改之后是否会有内存溢出，SDS 会帮我们处理内存扩容，无需我们开发人员手动判断 + 扩容。

4.频繁的内存分配问题

C 字符串本身不记录字符串的长度，所以对于一个包含了 N 个字符的 C 字符串来说，这个 C 字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符）

因为 C 字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个 C 字符串，程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作：

增长操作：比如拼接操作（append），执行增长操作之前需要先进行内存重分配，以扩展底层数组的空间大小，如果忘了就会导致缓冲区溢出。
缩短操作：比如截断操作（trim），执行缩短操作之后需要进行内存重分配，来释放掉字符串不再使用的那部分空间，如果忘了就会导致内存泄漏。

然而内存重分配其实涉及复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作。
为了避免 C 字符串的这种缺陷， SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联。通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

空间预分配用于优化 SDS 的字符串增长操作：当 SDS 的 API 对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间。

其中，额外分配的未使用空间数量由以下公式决定：

如果对 SDS 进行修改之后，SDS 的长度将小于 1MB，那么程序分配和 len 属性同样大小的未使用空间。
如果对 SDS 进行修改之后，SDS 的长度将大于等于 1MB，那么程序会分配 1MB 的未使用空间。

在扩展 SDS 空间之前，SDS API 会先检查未使用空间是否足够，如果足够的话，API 就会直接使用未使用空间，而无需执行内存重分配。通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。

惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录下来，并等待将来使用。

通过惰性空间释放策略，SDS 避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。
与此同时，SDS 也提供了响应的 API，让我们可以在有需要时，真正的释放 SDS 里面的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费。

3.2 版本之后 Redis 中的free字段被移除，通过used_memory_rss和used_memory等字段来提供更详细的内存信息。

总结：

可以看到的是 SDS 数据结构的设计正好解决了上面我们提到的几个问题：

使用 len 来存储字符数组长度，因此获取字符串长度的时间复杂度为 O(1) （C 语言中获取字符串长度的时间复杂度为 O(N)。），同时读写字符串不依赖 \0，保证了二进制安全。
使用 free 来存储未使用的字节，来避免频繁的内存分配，减少耗时。
使用 buff 来存储字符串内容。字符串仍然以 \0 作为结尾，是为了和 C 语言字符串保持一致，这样就可以复用 C 语言字符串相关函数，避免重新造轮子。
使用柔性数组 来存储 buf。SDS 对上层暴露的指针不是指向结构体 SDS 的指针，而是直接指向柔性数组 buf 的指针。上层可像读取 C 字符串一样读取 SDS 的内容，兼容 C 语言处理字符串的各种函数。