Redis 设计与实现 3：字符串 SDS

在 Redis 中，字符串都用自定义的结构简单动态字符串(Simple Dynamic Strings，SDS)。
Redis 中使用到的字符串都是用 SDS，例如 key、string 类型的值、sorted set 的 member、hash 的 field 等等等等。。。

数据结构

旧版本的结构

在 3.2 版本之前，sds 的定义是这样的：

struct sdshdr {
    // buf 数组中已使用的字节数量，也就是 sds 本身的字符串长度
    unsigned int len;
    // buf 数组中未使用的字节数量
    unsigned int free;
    // 字节数组，用于保存字符串
    char buf[];
};

旧版本 SDS 结构示例

这样的结构有几个好处：

单独记录长度len，获取字符串长度的时间复杂度是 $O(1)$ 。传统的 C 字符串获取长度需要遍历字符串，直到遇到\0，时间复杂度是 $O(N)$ 。
buf 数组末尾遵循 C 字符串以 \0 结尾的惯例，可以兼容 C 处理字符串的函数。
减少修改字符串带来的内存重分配次数，Redis 使用了 空间预分配(预先申请大一点点的空间) 和 空间惰性释放(字符串变短修改len字段即可)来减少字符串修改引起的内存重新分配。
不以\0为结尾的判断，二进制安全。因为图片等二进制数据中，可能包含\0，传统 C 字符串一遇到 \0 就认为字符串结束了，会导致不能完整保存。

缺点：

len 和 free 的定义用了 4 个字节，可以表示 2^32 的长度。但是我们实际使用的字符串，往往没有那么长。4 个字节造成了浪费。

新版本的结构

旧版本中我们说到，len 和 free 的缺点是用了太长的变量，新版本解决了这个问题。
我们来看一下新版本的 SDS 结构。

在 Redis 3.2 版本之后，Redis 将 SDS 划分为 5 种类型：

类型	字节	位
sdshdr5	< 1	<8
sdshdr8	1	8
sdshdr16	2	16
sdshdr32	4	32
sdshdr64	8	64

新版本新增加了一个 flags 字段来标识类型，长度 1 字节(8 位)。
类型只占用了前 3 位。在 sdshdr5 中，后 5 位用来保存字符串的长度。其他类型后 5 位没有用。

struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 前 3 位保存类型，后 5 位保存字符串长度 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 字符串长度，1 字节 8 位 */
    uint8_t alloc; /* 申请的总长度，1 字节 8 位 */
    unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* 字符串长度，2 字节 16 位 */
    uint16_t alloc; /* 申请的总长度，2 字节 16 位 */
    unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* 字符串长度，4 字节 32 位 */
    uint32_t alloc; /* 申请的总长度，4 字节 32 位 */
    unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* 字符串长度，8 字节 64 位 */
    uint64_t alloc; /* 申请的总长度，8 字节 64 位 */
    unsigned char flags; /* 前 3 位保存类型，后 5 位未使用 */
    char buf[];
};

新版本 SDS 结构示例

优点：

旧版本相对于传统 C 字符串的优点，新版本都有
相对于旧版本，新版本可以通过字符串的长度，选择不同的结构，可以节约内存
使用 __attribute__ ((__packed__)) ，让编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐，可以节约内存

SDS 的初始化

sds 的定义，跟传统的C语言字符串保持类型兼容 char *。但是 sds 是二进制安全的，中间可能包含\0。

sds.h

typedef char *sds;

sds.c

// 初始化 sds
sds sdsnewlen(const void *init, size_t initlen) {
    // 指向 sdshdr 开始地方的指针
    void *sh;
    // sds 实际是一个指针，指向 buf 开始的位置
    sds s;
    // 根据初始化的长度，返回 sds 的类型
    char type = sdsReqType(initlen);
    // initlen == 0，是空字符串，空字符串往往就是用来往后添加字节的，使用 SDS_TYPE_8 比 SDS_TYPE_5 更好
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    // 根据类型获取 struct sdshdr 的长度
    int hdrlen = sdsHdrSize(type);
    // flags 字段的指针
    unsigned char *fp;
    
    // 开始分配空间，+1 是为了最后一个的结束符号 \0
    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    // const char *SDS_NOINIT = "SDS_NOINIT";
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        // 不是 init 则清空 sh 的内存
        memset(sh, 0, hdrlen+initlen+1);
    // s 指向了 buf 开始的地址
    // 从上面结构可以看出，内存地址的顺序： len, alloc, flag, buf
    // 因为 buf 本身不占用空间，hdrlen 实际上就是结构的头(len、alloc、flags)
    s = (char*)sh+hdrlen;
    // flags 占用 1 个字节，所以 s 退一位就是 flags 的开始位置了
    fp = ((unsigned char*)s)-1;
    switch(type) {
        case SDS_TYPE_5: {
            // #define SDS_TYPE_BITS 3
            // 前 3 位保存类型，后 5 位保存长度
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            // define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
            // sh 变量赋值了 struct sdshdr
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        // 下面是对 SDS_TYPE_16、SDS_TYPE_32、SDS_TYPE_64 的初始化，跟 SDS_TYPE_8 的类似，篇幅有限，省略...
    }
    // 如果 init 非空，则把 init 字符串赋值给 s，实际上也是 buf 的初始化
    if (initlen && init)
        memcpy(s, init, initlen);
    // 最后加一个结束标志 \0
    s[initlen] = '\0';
    return s;
}

SDS 的扩/缩容

扩容

扩容就不跟初始化一样写注释写得那么详细了，直接拉最重要的几句代码就行。

sds sdsMakeRoomFor(sds s, size_t addlen) {
    // #define SDS_MAX_PREALLOC (1024*1024)
    // 当新的长度小于 1M 的时候，长度会增长一倍
    // 当新的长度达到 1M 之后，最多就增长 1M 了
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;
    // ...
}

缩容

sds 缩短不会真正缩小 buf，而是只改长度而已，类型也不变。