String数据结构

在 Redis 中，String 类型的数据结构是最基本的类型，它实际上是一个字节数组（byte array）。但在底层实现中，Redis 并不是直接使用 C 语言的传统字符串（即以 \0 结尾的字符数组），而是使用了一种名为 SDS（Simple Dynamic String）的抽象数据结构。

1. SDS（Simple Dynamic String）的特点

SDS 是 Redis 中用来表示字符串的基础数据结构，它相比传统的 C 字符串有以下几个特点：

  • 动态扩容：SDS 支持动态扩展，当字符串长度需要增加时，SDS 可以自动调整空间大小，无需手动管理内存。
  • 二进制安全：SDS 不会对字符串内容做任何假设，它可以存储任意二进制数据，而不仅仅是以 \0 结尾的字符数组。
  • 常数时间获取长度：SDS 会在内部记录字符串的长度，所以获取字符串长度的操作是 O(1) 的，而 C 字符串需要遍历整个字符数组来计算长度（O(n)）。
  • 预分配空间和惰性空间释放：SDS 在扩展时会预分配一些额外的空间，以减少频繁的内存分配和复制操作。此外，当 SDS 缩短字符串时，它并不会立即释放多余的内存空间，而是保留起来以备后用。

2. SDS 的结构

SDS 的数据结构大致如下（简化版）：

struct sdshdr {
    int len;        // 当前字符串的长度
    int free;       // 剩余可用空间
    char buf[];     // 字符串数据
};
  • len：表示当前 SDS 所保存字符串的长度。
  • free：表示当前 SDS 预分配的、尚未使用的空间大小。
  • buf：实际保存字符串数据的地方。

例如，一个长度为 5 的字符串 "hello"，对应的 SDS 结构可能是这样的：

  • len = 5
  • free = 3 （预分配了一些额外的空间）
  • buf = “hello\0”（注意 buf 并不是传统意义上的以 \0 结尾的字符串，只是恰好有 \0 用来方便处理）

3. SDS 的扩容机制

当 SDS 需要扩容时，会采用一种“渐进式扩容”的策略：

  • 空间预分配：当 SDS 需要扩展时，它不仅仅只分配所需的内存，还会预分配额外的空间。具体的策略是：

    • 如果 SDS 当前长度小于 1MB，那么扩容时会分配与当前长度相同的额外空间，即如果扩展后的长度是 N，那么实际分配的总空间是 2N。
    • 如果 SDS 当前长度大于等于 1MB，那么每次扩展只额外分配 1MB 的空间。

    这种策略能够有效减少频繁的内存分配操作，提升字符串操作的效率。

  • 惰性空间释放：当字符串缩短时，SDS 并不会立即释放多余的内存空间，而是将这些空间保留起来，以便下次扩展时直接使用。这种策略避免了频繁的内存分配和释放操作，提高了内存使用的效率。

4. SDS 的应用场景

SDS 被广泛应用于 Redis 的各种模块中，尤其是在 Redis 的 String 类型中，SDS 是核心的数据结构。无论是简单的字符串值还是复杂的数据序列化，Redis 都依赖于 SDS 的灵活性和高效性。

通过 SDS，Redis 实现了对字符串操作的高效处理，并且避免了传统 C 字符串在安全性和效率上的不足。