面试题：Redis String 类型的底层实现是什么？（SDS）

在面试中，如果被问到 Redis String 类型的底层实现，可以围绕 SDS（Simple Dynamic String，简单动态字符串） 进行回答。以下是详细的回答思路：

---

1. Redis String 的底层实现：SDS

Redis 的 String 类型并不是直接使用 C 语言的原生字符串（以 \0 结尾的字符数组），而是使用了一种自定义的数据结构，称为 SDS（Simple Dynamic String）。SDS 是 Redis 为了高效处理字符串而设计的一种数据结构。

---

2. SDS 的结构

SDS 的结构定义如下（以 Redis 3.x 为例）：

struct sdshdr {
    int len;        // 记录字符串的实际长度
    int free;       // 记录剩余可用空间的长度
    char buf[];     // 存储字符串内容的柔性数组
};

• len：表示字符串的实际长度（不包含结尾的 \0）。
• free：表示缓冲区中未使用的字节数。
• buf：是一个柔性数组，用于存储字符串内容，末尾会自动添加一个 \0，以兼容 C 语言的字符串函数。

---

3. SDS 的优势

相比于 C 语言的原生字符串，SDS 有以下优势：

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

• C 语言的原生字符串需要遍历整个字符串才能获取长度，时间复杂度是 O(N)。
• SDS 直接通过 len 字段获取长度，时间复杂度是 O(1)。

（2）避免缓冲区溢出

• C 语言的原生字符串操作（如 strcat）容易导致缓冲区溢出。
• SDS 在修改字符串时会检查剩余空间（free 字段），如果空间不足，会自动扩容，避免了缓冲区溢出。

（3）减少内存重分配次数

• SDS 采用了 空间预分配 和 惰性空间释放 的策略：
  • 空间预分配：当 SDS 需要扩容时，不仅会分配所需的空间，还会额外分配一定的空闲空间（free 字段），以减少后续扩容的次数。
  • 惰性空间释放：当 SDS 缩短时，不会立即释放多余的空间，而是将其记录在 free 字段中，以便后续使用。

（4）二进制安全

• C 语言的原生字符串以 \0 作为结束符，不能存储包含 \0 的二进制数据。
• SDS 通过 len 字段记录字符串长度，可以存储任意二进制数据，包括 \0。

（5）兼容 C 字符串函数

• SDS 的 buf 字段末尾会自动添加一个 \0，因此可以直接使用 C 语言的字符串函数（如 printf）。

---

4. SDS 的扩容策略

当 SDS 需要扩容时，Redis 会根据以下规则分配空间：

• 如果修改后的字符串长度小于 1MB，则分配 2 倍 的所需空间。
• 如果修改后的字符串长度大于等于 1MB，则分配 额外 1MB 的空间。

例如：

• 如果字符串长度从 5 字节增加到 10 字节，SDS 会分配 20 字节的空间（10 字节用于数据，10 字节空闲）。
• 如果字符串长度从 2MB 增加到 3MB，SDS 会分配 4MB 的空间（3MB 用于数据，1MB 空闲）。

---

5. SDS 在 Redis 中的应用

• Redis 的 String 类型（包括普通字符串、整数、浮点数）都是基于 SDS 实现的。
• SDS 的二进制安全性使得 Redis 可以存储任意类型的数据，而不仅仅是文本数据。

---

6. 示例

以下是一个 SDS 的示例：

struct sdshdr {
    int len = 5;        // 字符串长度为 5
    int free = 5;       // 空闲空间为 5
    char buf[] = "hello\0xxxxx";  // 实际存储的内容
};

---

7. 总结

• Redis 的 String 类型底层使用 SDS（Simple Dynamic String）实现。
• SDS 通过 len 和 free 字段实现了 O(1) 时间复杂度的长度获取、自动扩容、二进制安全等特性。
• SDS 的设计使得 Redis 能够高效地处理字符串操作，同时避免了 C 语言原生字符串的缺陷。

通过理解 SDS 的设计和优势，可以更好地掌握 Redis 的底层实现原理。