youyichannel

志于道，据于德，依于仁，游于艺！

0%

Simple-Dynamic-String (SDS)

发表于 更新于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

字符串在 Redis 中是非常常见的数据类型，KV 键值对中的键是字符串类型，值有时也是字符串类型。

Redis 没有直接使用 C 语言传统的字符串 (char*) 表示，而是自主封装了 SDS 的数据结构来表示字符串，也就是说 Redis 的 String 数据类型的底层数据结构是 SDS。

为什么 Redis 选择自主设计 SDS 呢？很显然是 C 原生字符串存在一些缺陷无法接受。

C 语言字符串的缺陷

C 语言的字符串是一个字符数组，即数组中每个元素是字符串中的一个字符。

字符数组的结尾位置以 \0 表示，意味着字符串的结束。

1）C 语言获取字符串长度的时间复杂度是 O(N)

C 语言获取字符串长度的函数 strlen，是通过遍历字符数组中的每一个字符，并进行计数，等遇到字符为 \0 后，就会停止遍历，然后返回已经统计到的字符个数，即为字符串长度。

2）C 语言字符串不能保存二进制数据

C 语言字符串用 \0 字符作为结尾标记有个缺陷。假设字符串中间某个位置有个 \0 字符，这时在操作这个字符串时就会提早结束。因此除了字符串的末尾之外，字符串里面不能含有 \0 字符，否则最先被程序读入的 \0 字符将被误认为是字符串结尾，这个限制导致 C 语言的字符串只能保存文本数据，不能保存像图片、音频、视频文化这样的二进制数据。

3）C 语言字符串容易发生缓冲区溢出

C 语言标准库中字符串的操作函数是很不安全的，稍不注意就会导致缓冲区溢出。

比如，strcat 函数是拼接两个字符串：

//将 src 字符串拼接到 dest 字符串后面
char *strcat(char *dest, const char* src);

C 语言字符串不会记录自身缓冲区大小，所以在执行 strcat 函数时，C 默认已经为 dest 分配了足够容纳 src 的内存，而一旦这个假设不存在，就会发生缓冲区移除，就有可能导致程序运行终止。

4）C 语言对字符串的操作效率不高

C 语言中，strcat 函数和 strlen 函数类似，时间复杂度也很高，也都需要先通过遍历字符串才能得到目标字符串的末尾。然后对于 strcat 函数来说，还要再遍历源字符串才能完成追加，对字符串的操作效率都不高。

Redis SDS 的设计

Redis 5.0+ SDS 设计：

1）len: 记录字符串长度。这样获取字符串长度时，只需要返回这个成员变量值即可，时间复杂度为 O(1)；

2）alloc: 记录分配给字符数组的空间长度。这样在修改字符串时，可以通过 alloc - len 计算出剩余空间大小，用于判断是否满足需求，如果不满足，就会自动将 SDS 的空间扩展至修改所需的大小，然后才执行实际的修改操作；这也就解决了缓冲区溢出的问题；

3）flags: 用来表示不同类型的 SDS。

4）buf[]: 字符数组，用来保存实际数据。不仅可以保存文本数据，也可以保存二进制数据。

O(1) 时间复杂度获取字符串长度

C 语言原生字符串长度获取 strlen 函数，需要通过遍历的方式来统计字符串长度，时间复杂度是 O(N)；Redis 的 SDS 结构加入了 len 成员变量，获取字符串长度的时候，直接返回这个成员变量的值即可，时间复杂度为 O(1)。

二进制安全

SDS 不需要使用 \0 字符来标识字符串结尾了，而是有个专门的 len 成员变量来记录长度，所以可存储包含 \0 的数据。但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 \0 字符。

SDS 的 API 都是以处理二进制的方式来处理 SDS 存放在 buf[] 里的数据，程序不会对其中的数据做任何限制，数据写入的时候时什么样的，它被读取时就是什么样的。通过使用二进制安全的 SDS，而不是 C 字符串，使得 Redis 不仅可以保存文本数据，也可以保存任意格式的二进制数据。

不会发生缓冲区溢出

Redis 的 SDS 结构里引入了 alloc 和 len 成员变量，这样 SDS API 通过 alloc - len 计算，可以算出剩余可用的空间大小，这样在对字符串做修改操作的时候，就可以由程序内部判断缓冲区大小是否足够用。当判断出缓冲区大小不够使用时，Redis 会自动扩大 SDS 的空间大小以满足修改的需要。

#define SDS_MAX_PREALLOC (1024*1024)

if (greedy == 1) {
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
}
  • 如果所需的 SDS 长度小于 1 MB，翻倍扩容；
  • 如果所需的 SDS 长度超过 1MB，每次多分配 1MB。

在扩容 SDS 空间之前，SDS API 会优先检查未使用空间是否足够，如果不够的话，API 不仅会为 SDS 分配修改所必须要的空间，还会给 SDS 分配额外的「未使用空间」。这样的好处是，下次在操作 SDS 时，如果 SDS 空间够的话，API 就会直接使用「未使用空间」，而无须执行内存分配，有效的减少内存分配次数。

节约内存空间

SDS 结构中存在 flags 成员变量，表示的是 SDS 类型。Redis 一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64，这 5 种类型的主要区别就在于，它们数据结构中的 len 和 alloc 成员变量的数据类型不同。

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

之所以 SDS 设计不同类型的结构体，是为了能灵活保存不同大小的字符串，从而有效节省内存空间。

除此之外，Redis 在编程上使用了专门的编译优化来节省内存空间，即在 struct 声明了 __attribute__ ((packed)) ，即告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。

相关文章