Reids 源码阅读 - SDS

Apr 9, 2016


Redis 没有使用传统的 C 字符串,而是自己构建了名为SDS (Simple Dynamic String)的字符串。

SDS的定义

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

free表示未使用字节的数量,len表示字符串长度。 SDS 保存字符串末尾的0不算在len之内。

SDS和 C 字符串的区别

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

显然获取长度的复杂度是$O(1)$。

杜绝缓冲区溢出

当 SDS 需要进行修改时,会检查空间是否满足,如果不满足的话,先扩展再操作。

减少修改字符串带来的内存重分配次数

预分配空间

分配策略是:

  • 如果分配之后,len < 1MB,那么将分配和 len 属性相同大小的未使用空间。
  • 否则分配 1MB 的未使用空间。

惰性空间释放

当截断字符串时,不会缩小空间,而是维护一下 free 的值。

二进制安全

SDS 因为使用 len 来标记长度,所以字符串中出现 0 也没关系,是二进制安全的。