当前位置：首页 > news >正文

6、Redis系统-数据结构-01-String

news 来源：原创 2024/9/21 14:50:35

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 的性能和功能。