面试题：Redis中SDS如何存储不同长度的字符串类型数据

Question

请阐述Redis的SDS（简单动态字符串）在存储不同长度字符串时，是如何自适应并优化存储结构的，比如短字符串和长字符串处理方式有何不同。

Answer 1

1. SDS 结构简介

Redis 的 SDS 结构定义如下：

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

2. 短字符串处理方式

• 空间分配：对于短字符串，SDS 在分配空间时，除了保存字符串本身所需的空间外，还会额外分配一些空间。例如，当存储一个较短的字符串 "hello"，其 len 为 5，free 可能会分配一定的额外空间（如 3 个字节），总共 buf 数组大小为 len + free + 1（最后的 1 用于保存字符串结束符 '\0'）。这样设计是为了在字符串进行追加操作时，尽量减少内存重新分配的次数。
• 优化特点：通过 free 字段，在短字符串进行拼接等操作时，如果 free 空间足够，就不需要重新分配内存，直接在 buf 数组剩余空间上追加内容即可，提升了操作效率。并且，由于 SDS 采用 len 字段记录字符串长度，获取长度的操作时间复杂度为 O(1)，而传统 C 字符串获取长度需要遍历到 '\0'，时间复杂度为 O(N)。

3. 长字符串处理方式

• 空间分配：长字符串同样遵循上述 SDS 结构，但由于其本身占用空间较大，在空间分配上会更加谨慎。当存储长字符串时，Redis 会根据字符串长度分配足够的空间，free 字段也会相应调整。不过，与短字符串相比，长字符串可能不会像短字符串那样预留过多的 free 空间，因为长字符串占用空间大，预留过多可能造成内存浪费。
• 优化特点：对于长字符串，虽然 free 空间相对预留较少，但 SDS 结构依然保证了获取长度的 O(1) 时间复杂度。同时，在进行修改操作时，如果需要重新分配内存，Redis 会采用类似于“加倍”的策略来减少内存重新分配次数。例如，当发现 free 空间不足时，可能会一次性分配比当前所需更多的空间，以应对后续可能的操作，避免频繁的内存重新分配带来的性能开销。