6、Redis系统-数据结构-01-String
Redis 数据结构简介
前言
Redis 是一个高性能的内存数据库，其关键在于其数据结构的设计。Redis 数据结构是指底层实现 Redis 键值对中值的数据类型的方式。它包括了以下几种主要对象：
- String（字符串）对象：最基本的数据类型，可以存储任意类型的数据，包括字符串、整数、浮点数等。
- List（列表）对象：一个链表，可以按顺序存储多个字符串，支持从两端进行操作。
- Hash（哈希）对象：用于存储键值对集合，类似于一个小型的键值对数据库。
- Set（集合）对象：一个无序集合，自动去重，支持集合操作如交集、并集等。
- Zset（有序集合）对象：类似于 Set，但每个元素都会关联一个权重（score），元素按权重排序。
随着 Redis 版本的更新，这些数据类型的底层数据结构也有所不同，如双向链表、压缩列表、哈希表、跳表、整数集合、quicklist 和 listpack 等。这些数据结构的选择使得 Redis 在处理数据的增删查改操作时能够高效地运行。
研究 Redis 的底层数据结构有助于我们深入理解 Redis 的工作原理，优化性能，确保数据的安全性，扩展系统的能力，并更好地排查和解决问题。这对于使用和管理 Redis 数据库以及构建高效可靠的应用程序都是非常有价值的。本文将详细介绍 Redis 的底层数据结构。
一、SDS（Simple Dynamic String，简单动态字符串）
1、SDS的必要性
-
C 语言字符串的限制：
- 字符数组表示：在 C 语言中，字符串是以字符数组（char*）的形式表示，以\0字符作为结尾标记。
- 长度计算复杂度高：字符串长度的获取需要遍历整个字符数组，时间复杂度为 O(N)。
- 无法保存二进制数据：由于\0字符标记字符串结束，字符串中不能包含\0字符，因此无法保存二进制数据。
- 安全性问题：C 语言标准库中的字符串操作函数如 strcat 存在缓冲区溢出等安全性问题，因为它们不检查缓冲区大小是否足够。
-
Redis 的需求：
- 高效操作：需要高效获取字符串长度和修改字符串的能力。
- 二进制安全：需要能够存储和操作二进制数据。
- 安全性：需要安全的字符串操作，避免缓冲区溢出等问题。
为了克服 C 语言字符串的不足，Redis 采用了 SDS 作为其字符串数据类型的底层数据结构。
2、SDS的数据结构
SDS 的数据结构如下：
struct sdshdr {
int len; // 记录了字符串的长度
int free; // 分配给字符数组的剩余空间长度
char buf[]; // 字符数组，用来保存实际数据
};
结构中的每个成员变量分别介绍如下：
- len：记录了字符串长度。这样在获取字符串长度时，只需要返回这个成员变量值即可，时间复杂度为 O(1)。
- alloc：分配给字符数组的剩余空间长度。在修改字符串时，可以通过 alloc - len 计算出剩余的空间大小，用于判断是否需要扩展空间。
- buf[]：字符数组，用来保存实际数据。不仅可以保存字符串，也可以保存二进制数据。
总的来说，Redis 的 SDS 结构在原本字符数组之上，增加了三个元数据：len、free、flags，用来解决 C 语言字符串的缺陷。
3、SDS的优势
-
O(1) 复杂度获取字符串长度：
- C 语言的 strlen 函数需要遍历字符串，时间复杂度为 O(N)。
- SDS 通过 len 成员变量直接返回字符串长度，时间复杂度为 O(1)。
-
二进制安全：
- SDS 不需要 \0 字符标识字符串结尾，而是通过 len 成员变量记录长度，可以存储包含 \0 的数据。
- 为了兼容部分 C 语言标准库函数，SDS 字符串结尾仍会加上 \0 字符。
- SDS 的 API 处理数据时以二进制方式处理，程序不会对数据做任何限制，保证数据的原样读取和写入。
-
避免缓冲区溢出：
- C 语言字符串操作函数如 strcat 把缓冲区大小是否满足操作需求的检查交给开发者，存在缓冲区溢出的风险。
- SDS 通过 alloc 和 len 成员变量，在进行字符串修改时由程序内部判断缓冲区大小是否足够。
- 当缓冲区大小不够用时，Redis 会自动扩展 SDS 的空间大小，满足修改所需的空间。
SDS 的扩容规则如下：
- 如果所需的 SDS 长度小于 1 MB，扩容按翻倍进行，即 2 倍的 newlen。
- 如果所需的 SDS 长度超过 1 MB，扩容长度为 newlen + 1MB。
-
节省空间：
- SDS 设计了 5 种类型的结构体（sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64），根据 len 和 alloc 成员变量的数据类型不同来适应不同大小字符串的存储需求。
- 不同的数据类型限制了字符数组长度和分配空间大小的上限，从而有效地节省内存空间。
4、SDS 数据结构的实现
以下是 SDS 的实现示例，包括创建、释放、拼接和复制操作：
-
创建 SDS：
sds sdsnew(const char *init) { size_t initlen = (init == NULL) ? 0 : strlen(init); sds s = sdsnewlen(init, initlen); return s; } -
释放 SDS：
void sdsfree(sds s) { if (s == NULL) return; zfree((char*)s - sizeof(struct sdshdr)); } -
拼接字符串：
sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t)); } -
复制字符串：
sds sdscpy(sds s, const char *t) { return sdscpylen(s, t, strlen(t)); } -
获取 SDS 长度：
size_t sdslen(const sds s) { struct sdshdr *sh = (void*) (s - (sizeof(struct sdshdr))); return sh->len; } -
清空 SDS：
void sdsclear(sds s) { struct sdshdr *sh = (void*) (s - (sizeof(struct sdshdr))); sh->free += sh->len; sh->len = 0; s[0] = '\0'; }
5、整数类型存储优化
在 Redis 中，如果字符串内容可以表示为数字类型，通常可以优化存储为 long 类型或整数集合（intset）。这是因为整数类型的存储和操作通常比字符串更高效。
-
使用整数类型存储数字字符串：
- Redis 的字符串对象可以存储整数类型的值。如果字符串可以被解析为整数，Redis 会将其转换为整数类型进行存储。例如，执行 SET key "12345" 时，Redis 会将其存储为整数编码（INT），而不是字符串编码。
-
整数集合（intset）：
- 整数集合是一种紧凑的有序集合，适用于存储小范围的整数集合。它的内部结构如下：
typedef struct intset { uint32_t encoding; // 编码类型（int16, int32, int64） uint32_t length; // 集合中元素的个数 int8_t contents[]; // 元素数组 } intset;
结论
通过上述解析，我们可以更好地理解 SDS 的设计思想和实现原理，从而在实际开发中更好地利用 SDS 提供的优势。在 Redis 中，字符串可以表示为数字类型时，会自动转换为整数类型进行存储，以提高存储和操作效率。此外，Redis 提供了整数集合（intset）数据结构，用于高效存储一组整数。了解这些优化策略
，可以帮助我们在实际应用中更好地利用 Redis 的性能和功能。
-
