Chapter 2 - 简单动态字符串

Created by : Mr Dk.

2020 / 06 / 01 14:12

Nanjing, Jiangsu, China

---

Redis 中自行构建了一种字符串表示，称为 简单动态字符串 (Simple Dynamic String, SDS)，而普通的 C 字符串只会被用于一些字面常量。

Definition

SDS 的定义如下。对于这种设计，与传统的 C 字符串相比，有什么优势？

struct sdshdr {
    int len;
    int free;
    char buf[];
}

• len 记录了字符串目前的长度 (不包括 \0)
• free 记录了缓冲区中剩余空闲空间的长度
• buf 指向缓冲区首地址

String Length

在普通的 C 字符串中，并不维护字符串的长度。如果要获得一个字符串的长度，strlen() 需要对整个字符串进行遍历，时间复杂度为 O(N)。Redis 的 SDS 中直接维护了字符串的长度，时间复杂度减小到 O(1) - 对于一个特别长的字符串反复执行 STRLEN 也不会对性能有影响。

Memory Security

C 字符串不记录自身长度带来的一个问题是容易造成缓冲区溢出。比如在进行 strcat(dest, src) 时，如果 dest 的缓冲区长度不够，将会覆盖 dest 缓冲区之后的内存内容。由于 SDS 记录了字符串长度，在字符串发生修改前，会对缓冲区长度进行检查。如果缓冲区长度不够，SDS 的空间将先被扩展，再进行后续操作。

Memory Allocation

扩展 SDS 的内存空间涉及到内存的重新分配。频繁的重分配肯定是相当耗时的。SDS 中实现了两种优化机制。

空间预分配

由于 SDS 中可以记录缓冲区中的空闲空间。为了减少内存重分配的次数，很容易想到的策略就是一次分配较多的空间，记录在 free 中，后续就不需要重复分配了。这种策略带来的问题就是会有一些空间被浪费。Redis 的实现在其中做了折衷：

• 对 SDS 修改后，SDS 的长度 < 1MB，那么修改后 len 属性与 free 属性相同 (相当于空间扩展到实际内容的两倍长度)
• 对 SDS 修改后，SDS 长度 >= 1MB，那么修改后将保证 free 为 1MB (分配 1MB 的额外空间)

通过这种空间预分配技术，可以在一定程度上减少内存重新分配的次数。

惰性内存释放

当 SDS 字符串缩短后，并不立刻回收内存，而是用 free 将空出的空间记录下来，以便下次使用。当然，也有对应的 API 可以真正释放这些未使用空间。

Binary Safety

SDS 从一定意义上来说已经不是字符串了，而是 字节数组。SDS API 会以二进制方式 (而不是字符串方式) 来处理缓冲区中的数据。比如，如果数据的中间有一个 \0，那么普通的 C 字符串 API 将会将字符串的一部分作为结果返回，从而带来错误。SDS API 不会出现这种问题。

同时，由于 SDS 中的 buf 也遵循 C 字符串的 \0 结尾惯例，因此也兼容部分 C 字符串函数。