⭐ 题目日期：

阿里 - 2024/8/21

📝 题解：

在 Redis 中，字符串（String） 的底层实现并不是传统的 C 语言字符串（以 \0 结尾的字符数组），而是一种称为 SDS（Simple Dynamic String，简单动态字符串） 的自定义数据结构。SDS 的设计优化了字符串操作的性能、安全性和内存效率。

---

1. SDS 的结构定义

SDS 的结构会根据字符串长度的不同，选择不同的类型（如 sdshdr5、sdshdr8、sdshdr16 等），以节省内存。以下是 Redis 5.0 后的一种典型实现：

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;        // 字符串当前长度（已用字节数）
    uint8_t alloc;      // 分配的总容量（不包括头部和末尾的\0）
    unsigned char flags;// 标志位（低 3 位表示类型，如 SDS_TYPE_8）
    char buf[];         // 实际存储的字符数组（柔性数组）
};

• len：字符串的实际长度（字节数），允许存储二进制数据（如 \0）。
• alloc：分配的缓冲区总大小（不包括头部和末尾的 \0）。
• flags：标识 SDS 类型（如 sdshdr8、sdshdr16 等），根据字符串长度选择。
• buf：存储字符数据的柔性数组，末尾自动添加 \0 以保证部分兼容 C 字符串函数。

---

2. SDS 的核心优势

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

• C 字符串：需遍历字符数组直到 \0，时间复杂度为 O(n)。
• SDS：直接读取 len 属性，时间复杂度为 O(1)。

(2) 杜绝缓冲区溢出

• C 字符串：拼接操作可能因未检查目标缓冲区大小导致溢出。
• SDS：修改前自动检查 alloc，若空间不足则扩展缓冲区。

(3) 减少内存重分配次数

• 空间预分配：
  当 SDS 扩容时，会额外分配未使用的空间（alloc），策略为：

  • 若新长度 < 1MB，则分配 2 * len 的空间（加倍）。
  • 若新长度 >= 1MB，则分配 len + 1MB 的空间。
    例如：原长度 10KB，扩容到 12KB 时，分配 24KB 的缓冲区。

• 惰性空间释放：
  缩短字符串时，不立即释放多余空间，而是保留给后续可能的扩展操作。

(4) 二进制安全

• C 字符串：以 \0 结尾，无法存储包含 \0 的二进制数据（如 JPEG 图片）。
• SDS：依赖 len 属性记录长度，可安全存储任意二进制数据。

(5) 兼容部分 C 字符串函数

• SDS 的 buf 数组末尾会添加 \0，因此可直接使用 <string.h> 中的部分函数（如 strcmp）。

---

3. SDS 内存布局示例

假设存储字符串 "Redis"（长度 5），其内存布局如下：

+---------+---------+-------+---------------+------+
|  len=5  | alloc=5 | flags |   buf[]="Redis\0"    |
+---------+---------+-------+---------------+------+

• len=5：字符串实际长度为 5。
• alloc=5：当前分配的缓冲区容量为 5（未预留额外空间）。
• flags：标识 SDS 类型（如 sdshdr8）。
• buf：存储数据，末尾自动添加 \0。

---

4. SDS 的类型选择

Redis 根据字符串长度选择不同的 SDS 类型以节省内存：

SDS 类型	长度范围	len 和 alloc 的位宽
sdshdr5	0~31 字节	5 位（通过 flags 存储）
sdshdr8	0~255 字节	8 位（1 字节）
sdshdr16	0~65535 字节	16 位（2 字节）
sdshdr32	0~4294967295 字节	32 位（4 字节）
sdshdr64	更大的字符串	64 位（8 字节）

例如，存储一个 100 字节的字符串会选择 sdshdr8，其 len 和 alloc 各占 1 字节，而存储 10KB 的字符串会选择 sdshdr32。

---

5. 操作示例

(1) 拼接字符串（追加操作）

sds s = sdsnew("Hello");
s = sdscat(s, " World!");  // 自动检查并扩展缓冲区

(2) 缩短字符串

s = sdsrange(s, 0, 4);     // 缩短为 "Hello"，不释放多余内存

(3) 二进制安全存储

sds s = sdsnewlen("\0abc\0", 5);  // 可安全存储包含 \0 的数据

---

6. 总结

• 性能优化：通过 len 和 alloc 实现快速长度获取和缓冲区管理。
• 内存效率：根据字符串长度选择不同 SDS 类型，减少内存浪费。
• 安全设计：避免缓冲区溢出，支持二进制安全。
• 兼容性：保留 \0 结尾以兼容部分 C 函数。

SDS 是 Redis 高效处理字符串的核心基础，其设计思想（如空间预分配、惰性释放）也常见于其他高性能系统的内存管理中。