简单动态字符串(simple dynamic string, SDS)

  Seves

Redis只会使用C字符串作为字面量,大多数情况下,Redis使用SDS(simple dynamic string,简单动态字符串)作为字符串表示

1. SDS定义

struct sdshdr {

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

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

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

};

2. 常数复杂度获取字符串长度

  • C字符串:遍历整个字符串获取字符串长度,复杂度O(N)
  • SDS:直接访问len属性获取SDS字符串长度

3. 杜绝缓冲区溢出

SDS API对SDS字符串进行修改时,API会先检查SDS空间是否满足修改需求,会及时扩容。

4. 减少修改字符串长度时所需的内存重分配次数

  • 空间预分配
    a. 如果对 SDS 进行修改之后, SDS 的长度(也即是 len 属性的值)将小于 1 MB , 那么程序分配和 len 属性同样大小的未使用空间, 这时 SDS len 属性的值将和 free 属性的值相同。 举个例子, 如果进行修改之后, SDS 的 len 将变成 13 字节, 那么程序也会分配 13 字节的未使用空间, SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节(额外的一字节用于保存空字符)。

b. 如果对 SDS 进行修改之后, SDS 的长度将大于等于 1 MB , 那么程序会分配 1 MB 的未使用空间。 举个例子, 如果进行修改之后, SDS 的 len 将变成 30 MB , 那么程序会分配 1 MB 的未使用空间, SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。

  • 惰性空间释放
    当 SDS 的 API 需要缩短 SDS 保存的字符串时, 程序并不立即使用内存重分配来回收缩短后多出来的字节, 而是使用 free 属性将这些字节的数量记录起来, 并等待将来使用

5. 二进制安全

  • C 字符串中的字符必须符合某种编码(比如 ASCII), 并且除了字符串的末尾之外, 字符串里面不能包含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据, 而不能保存像图片、音频、视频、压缩文件这样的二进制数据

  • SDS 的 API 都是二进制安全的(binary-safe): 所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据, 程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的, 它被读取时就是什么样。


上图如果用C字符串只能识别其中“Redis”, 而忽略之后的“Cluster”. 因为SDS是以处理二进制方式来处理Buf数组里的数据,数据写入时是什么样,读取时就是什么样。SDS不是根据’\0’来判断字符串结束, 而是根据len属性判断是否结束。

6. 兼容部分C字符串函数

遵循C字符串以空字符’\0’结尾的惯例,所以SDS可以重用一部分<String.h>库定义的函数。

C字符串和SDS之间的区别总结

7. SDS API

SDS主要操作API

作者 @没有故事的老大爷
中国一点都不能少

31