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

Redis 中的 String 类型是其最基本的数据结构之一，而它的底层实现依赖于一种名为 简单动态字符串（Simple Dynamic String, SDS） 的数据结构。

SDS 是 Redis 自行设计并广泛应用于其内部的一种抽象数据类型，用于高效地管理字符串。

SDS 的结构

SDS 在 Redis 中不仅仅是一个简单的字符数组，它还包含了一些额外的信息，使得对字符串的操作更加安全和高效。一个典型的 SDS 结构体定义如下：

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 保存字符串的长度
    int len;

    // 记录 buf 数组中未使用字节的数量
    int free;

    // 字节数组，用于保存字符串
    char buf[];
};

len：记录了 SDS 保存的字符串的实际长度。
free：表示 buf 数组中未使用的字节数量，即可以不重新分配内存就能容纳的额外字符数。
buf[]：一个柔性数组（C99 特性），用于实际存储字符串内容。

SDS 的特点与优势

常数时间获取字符串长度
- 由于 len 属性的存在，获取字符串长度的时间复杂度为 O(1)，避免了 C 字符串需要遍历整个字符串来计算长度的问题。
杜绝缓冲区溢出
- 在执行拼接操作前，SDS 会检查剩余空间是否足够。如果不够，则会自动扩展空间，防止因为空间不足而导致的缓冲区溢出问题。
减少修改字符串时带来的内存重分配次数
- 通过预分配策略，在适当时候分配更多空间（free），以减少后续连续增长操作所需的内存重分配次数。
- 同样地，当缩短字符串时，并不会立即释放多余的空间，而是保持一定的冗余，以便未来可能的增长操作能够快速完成。
二进制安全
- SDS 不是以空字符 \0 来标识字符串的结束，它可以保存任意类型的二进制数据，包括但不限于文本文件、图片等多媒体信息。
兼容部分 C 字符串函数
- 尽管 SDS 提供了更强大的功能，但它仍然兼容一部分标准 C 字符串处理函数，这得益于其遵循以 \0 结尾的传统习惯（尽管这不是必须的）。

SDS 的版本演进

随着 Redis 的发展，SDS 数据结构也经历了几次重要的改进，主要是为了更好地支持不同的字符串大小需求以及优化内存使用效率。

最新的 Redis 版本中，SDS 被划分为多个不同尺寸的结构体，每个都针对特定范围内的字符串长度进行了优化，从而进一步提升了性能和内存利用率。

总之，SDS 作为 Redis 中 String 类型的基础，不仅提供了高效的字符串操作能力，同时也保证了内存使用的灵活性和安全性，是 Redis 实现高性能的关键因素之一。

THE END

Redis 面试题