《Redis设计与实现》Part1:简单动态字符串

Redis 没有直接使用 C 语言的字符串表示，而是定义了一种称为 SDS(simple dynamic string)的类型，并作为 Redis 默认字符串的表示。那么 Redis 为什么要这么做呢？有什么好处呢？接下来咱们就探讨一下。

SDS 定义

src/sds.h/sdshdr

struct sdshdr {

    // 所保存的字符串长度
    unsigned int len;
    // buf数组中未使用的字节数
    unsigned int free;
    // 字节数组，用于保存字符串
    char buf[];
};

图 2.1 展示了一个字符串“Redis”的例子：

len为 5，是字符串“Redis”的长度，表示SDS保存了一个长度为 5 字节的字符串。
free为 0，表示SDS无分配未使用的空间。
buf是一个char类型的数组，数组前五个字节依次为R、e、d、i、s，最后一个字节为空字符\0。

可以看到SDS遵循了C字符以空字符结尾的惯例，这么做的好处是可以重用一部分C字符串中的函数（比如printf）。

SDS 优点

传统C字符串使用长度为 N+1 的字符数组来表示 N 个字符，并以空字符\0结尾，这种简单的字符串表达方式并不能满足Redis对字符串的要求。

获取字符串长度

C 字符串需要遍历整个字符串，直到遇到空字符串\0，所以复杂度为O(n)
SDS 直接访问属性len，复杂度为O(1)

缓冲区溢出

char *strcat(char *dest, const char *src)

C 字符串执行拼接操作时，如未分配足够空间，则可能越界溢出到其它已经被使用的空间
SDS 执行sdscat函数用于字符串拼接，执行sdscat操作之前会自动检查 SDS 是否有足够空间，不够则会先对 SDS 空间进行扩展

减少内存分配次数

内存调用是一个比较耗时的操作，涉及到复杂的算法以及可能执行系统调用，所以一半程序中，如果字符修改情况比较少，那么每次修改字符串则执行一次内存分配是可以接受的，但是在 redis 这种高性能数据库场景，必须要速度快同时数据会被频繁修改，如此一来，频繁执行内存调用进行内存的重分配则会对性能造成极大影响。

strcat 场景

假定字符串s值为“Redis”，现需要将s修改为“Redis Cluster”，如果是 C 字符串，则需要先分配增加至少 8 个字节的空间，再将字符串的实际值写入对应地址。那么 SDS 是如何应对这一场景的呢？

SDS 通过空间预分配，也即当 SDS 通过 api 操作需要对 SDS 空间进行扩展的时候，SDS 不仅会分配所必须的空间，还会额外预先分配未使用的空间，从而达到减少内存分配次数的目的。

分配公式：

修改后如果 SDS 的长度（len 属性）小于 1M，那么则分配与 len 一样大小的未使用空间
修改后如果 SDS 的长度大于大于等于 1M，那么固定分配 1M 的未使用空间

缩短字符串

如果要将字符串“Redis Cluster”缩短为“Redis”，SDS 会通过惰性空间释放的策略，保留字符串缩短后多余的空间，不会立即将其释放，只是更改 free 属性的值，记录当前 SDS 剩余可用空间的字节数。通过惰性空间释放策略，SDS 避免了字符串缩短时的重新空间分配操作，同时优化了后续字符串的增产操作。