1 Redis 字符串

1.1 介绍

redis 中以一种叫 sds(simple dynamic string) 的结构来存储字符串。相比传统的C字符串，sds 有以下优点：

• 以o(1)获取字符串长度
• 是二进制安全的
• 修改字符串可以有效减少内存重新分配的次数

1.2 原理

1.2.1 sds 结构

​ sds 在 redis 中由一个结构体 sdshdr来表示，具体结构如下：

typedef char *sds;

struct sdshdr {
    int len;	// buf 中已占用空间的长度
    int free;	// buf 中剩余可用空间的长度
    char buf[];	// 实际数据空间
};

以下图为例说明上述结构体中的具体内容：

• free 属性的值为0，代表没有可用空间了；
• len 的值为5，代表字符串的长度为5；
• buf 是一个 char 类型的数组，数组中的数据为 "hello"。

需要注意的是，redis 在为 sds 字符串申请空间时，会额外申请一个字节的空间，用于在字符串的结尾放一个'\0'。'\0'字符长度不计入结构体属性 len 中。这样做的好处在于 sds 可以直接使用一部分 C 字符串函数库里的一些函数。

1.2.2 以o(1)获取字符串长度

当我们创建一个 sds 字符串时，实际上是创建了一个sdshdr对象，但是实际使用的指针部分却指向属性 buf。假设有一个 sds 字符串对象 ，字符串内容为 "hello"，则 sds 对象的指针指向为：

所以，可以通过 sds 对象减去sdshdr结构体的长度得到该对象的首地址，然后再取属性 len 来获得字符串的长度。

static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));	// 由 sds 得到 sdshdr 的首地址
    return sh->len;	// 返回 sds 字符串的长度
}

1.2.2 sds 内存分配策略

在 redis 中，当要对 sds 进行扩展或者缩短时，会按照一定的策略来进行扩容和释放空间，以减少内存频繁的分配和释放，提升运行效率。

• 空间预分配策略

​ 当需要为 sds 扩展更多的空间时，redis 不仅会为 sds 分配扩展所需的空间，而且会为 sds 额外分配未使用空间（该部分空间的大小记录在 sdshdr的属性 free中）。当 sds 要增长时，比如拼接操作，会先调用sdsMakeRoomFor函数对 sds 进行扩容操作。在具体的扩容操作中，如果要扩容的大小 addlen小于等于 sds 的未使用空间（也就是 sdshdr的属性 free 的大小），则说明当前 sds 已经申请的内存空间足够扩展addlen个字节，sdsMakeRoomFor会直接返回。否则，sds 会根据当前字符串长度（sdshdr中的属性len的值）加上要扩容的空间addlen的值的和newlen来判断最终要分配空间的大小。如果newlen小于 1M，则 sds 会申请 2*newlen 的空间；否则 sds 申请 newlen+1M 的空间大小。扩容函数sdsMakeRoomFor具体代码如下。

#define SDS_MAX_PREALLOC (1024*1024)	// 最大预分配长度

sds sdsMakeRoomFor(sds s, size_t addlen) {

    struct sdshdr *sh, *newsh;

    size_t free = sdsavail(s);	// 获取 s 目前的未分配空间的长度（sdshdr中的属性 free的值）
    size_t len, newlen;

    if (free >= addlen) return s;	// 目前 s 的空余空间已经足够，无须再进行扩展，直接返回

    len = sdslen(s);	// 获取 s 目前已占用空间的长度
    sh = (void*) (s-(sizeof(struct sdshdr)));

    newlen = (len+addlen);	// s 最少需要的长度

    // 根据新长度，为 s 分配新空间所需的大小
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新长度小于 SDS_MAX_PREALLOC 
        // 那么为它分配两倍于所需长度的空间
        newlen *= 2;
    else
        // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
	
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);	// 重新分配内存

    if (newsh == NULL) return NULL;	// 内存不足，分配失败，返回

    newsh->free = newlen - len;	// 更新 sds 的空余长度

    return newsh->buf;	// 返回 sds
}

• 惰性释放策略

​ redis 中对 sds 进行缩短操作时，并不会立即执行内存重分配来回收字符串缩短后多出来的字节，而是会修改未分配使用空间 free 的值将这些空间记录下来，以供将来使用。