【死磕 Redis】—— Redis 数据结构：sds

字符串使我们在编程过程中使用最为广泛的对象了，在 Redis 中同样如此。我们知道 Redis 是 C 语言实现的，但是 Redis 放弃了 C 语言传统的字符串而是自己创建了一种名为简单动态字符串 SDS（Simple Dynamic String）的抽象类型，并将 SDS 用作 Redis 的默认字符串表示，其主要原因就是传统的字符串表示方式并不能满足 Redis 对字符串在安全性、效率、以及功能方面的要求。所以这篇文章就来说说 SDS。

在 Redis 里面，只会将 C 语言字符串当做字符串字面量，用于一些无须对字符串进行修改的地方，比如打印日志。在大多数场景下，Redis 都是使用 SDS 来作为字符串的表示。

对比 C 语言字符串，SDS 具有如下优点：

1. 常数复杂度获取字符串长度。
2. 杜绝缓冲区溢出。
3. 减少修改字符串长度时所需的内存重分配次数。
4. 二进制安全。
5. 兼容部分 C 字符串函数。

SDS 的定义

SDS 的源码主要实现在 sds.c 和 sds.h 两个文件中。其定义为：

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

从上述代码可以看出，每一个 sdshdr 都是由以下几个部分组成（sdshdr5除外）：

• len：SDS 字符串已使用的空间
• alloc：申请的空间，减去len就是未使用的空间，初始时和len一致。
• flag：只使用了低三位表示类型，细化了SDS的分类，根据字符串的长度的不同选择不同的 SDS 结构体，而结构体的主要区别是 len 和 alloc 的类型，这样做可以节省一部分空间大小，毕竟在 Redis 字符串非常多，进一步的可以节省空间。
• buf：char 类型数组，表示不定长字符串。

SDS 采用一段连续的内存空间来存储字符串，下图是字符串 “Redis” 在内存中的示例图：

SDS 与 C 字符串的区别

SDS相比C字符串，在安全性、性能、功能性具有优势：

1. 安全性：防止缓冲区溢出、二进制安全
2. 性能：获取字符串长度、空间预分配、惰性释放
3. 功能性：二进制安全、兼容部分C字符串函数

缓冲区溢出

缓冲区溢出（buffer overflow）：是这样的一种异常，当程序将数据写入缓冲区时，会超过缓冲区的边界，并覆盖相邻的内存位置。

C 字符串不记录自身长度，不会自动进行边界检查，所以会增加溢出的风险。如下面函数

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

该函数是将 src 字符串内容拼接到 dest 字符串的末尾。假如有 s1 = “Redis”，s2 = "MongoDB"，如下：

当执行 strcat(s1,'Cluster') 时，未给 s1 分配足够的内存空间，s1 的数据将会溢出到 s2 所在的内存空间，导致 s2 保存的内容被修改，如下：

与 C 字符串不同，SDS 杜绝了发生缓存溢出的可能性，他会按照如下步骤进行：

1. 先检查 SDS 的空间是否满足修改所需的要求
2. 如果不满足要求的话，API 会自动将 SDS 的空间扩展到执行修改所需的大小
3. 最后才是执行实际的修改操作

例子可见：sds.c/sdscat：

sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';
    return s;
}

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

我们知道 C 字符串是不会记录自身的长度信息，因此我们要获取一个 C 字符串的长度，需要变脸整个字符串，直到遇到第一个 '\0'，复杂度为 O(n)。但是 SDS 记录了自身长度 len，因此其复杂度降为 O(1) 就能获取字符串的长度。

空间预分配

当 SDS 的 API 要对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用的空间，具体策略见 sds.c/sdsMakeRoomFor，如下：

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        newsh = s_malloc(hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    sdssetalloc(s, newlen);
    return s;
}

• 如果对 SDS 进行修改后，SDS 的长度小于 1MB，那么则扩大两倍，若 SDS 的长度大于等于 1MB，那么则会增加 1MB。

通过空间预分配策略，Redis 可以减少联系执行字符串增长操作所需的内存分配次数。

惰性释放

预分配空间用于优化 SDS 字符串增长操作，惰性释放则用于优化字符串缩短的操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是回归到 alloc 属性中，并等待将来使用。

通过惰性释放策略，SDS 避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。

二进制安全

二进制安全（binary-safe）：指能处理任意的二进制数据，包括非ASCII和null字节。

我们知道 C 字符串是以空字符（\0）结尾，所以除了字符串的末尾之外，字符串里面不能包含任何的空字符，否则最先被程序读入的空字符会被误认为是字符串的结尾。这些限制使得 C 字符串只能保存文本数据，不能保存图像、视频、音频等二进制数据。

而 SDS 不会对数据做任何限制、过滤、假设，数据在写入时是什么样子的，它被读取时就是什么样的。因此 Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据。

参考

• 《Redis 设计与实现》
• Redis源码分析之sds
• redis源码分析（二）、redis源码分析之sds字符串