redis实现动态字符串SDS_Redis

1、sds简介

无论是 redis 的 key 还是 value，其基础数据类型都是字符串。例如，hash 型 value 的 field 与 value 的类型、list 型、set 型、zset 型 value 的元素的类型等都是字符串。虽然 redis 是使用标准 c 语言开发的，但并没有直接使用 c 语言中传统的字符串表示，而是自定义了一种字符串。这种字符串本身的结构比较简单，但功能却非常强大，称为简单动态字符串， simple dynamic string，简称 sds。

注意，redis 中的所有字符串并不都是 sds，也会出现 c 字符串。c 字符串只会出现在字符串“字面常量”中，并且该字符串不可能发生变更。 redislog(redis_warnning, “sdfsfsafsafds”);

2、sds结构

sds 不同于 c 字符串。c 字符串本身是一个以双引号括起来，以空字符’\0’结尾的字符序列。但sds是一个结构体，定义在redis安装目录下的src/sds.h中。

struct sdshdr {
// 字节数组，用于保存字符串
char buf[];
// buf[]中已使用字节数量，称为 sds 的长度
int len;
// buf[]中尚未使用的字节数量
int free;
}

例如执行 set country “china”命令时，键 country 与值”china”都是 sds 类型的，只不过一个是 sds 的变量，一个是 sds 的字面常量。”china”在内存中的结构如下：

通过以上结构可以看出，sds 的 buf 值实际是一个 c 字符串，包含空字符’\0’共占 6 个字节。但 sds 的 len 是不包含空字符’\0’的。

该结构与前面不同的是，这里有 3 字节未使用空间。

3、sds的优点

c 字符串使用 len+1 长度的字符数组来表示实际长度为 len 的字符串，字符数组最后以空字符’\0’结尾，表示字符串结束。这种结构简单，但不能满足 redis 对字符串功能性、安全性及高效性等的要求。

（1）、防止“字符串长度获取”性能瓶颈

对于c字符串，若要获取其长度，则必须要通过遍历整个字符串才可以获取到的。对于超常字符串的遍历，会成为系统的性能瓶颈。

但是，由于sds结构体中直接就存放着字符串的长度数据，所以对于获取字符串长度需要消耗的系统性能，与字符串本身长度是无关的，不会成为redis的性能瓶颈。

（2）保障二进制安全

c 字符串中只能包含符合某种编码格式的字符，例如 ascii、utf-8 等，并且除了字符串末尾外，其它位置是不能包含空字符’\0’的，否则该字符串就会被程序误解为提前结束。而在图片、音频、视频、压缩文件、office 文件等二进制数据中以空字符’\0’作为分隔符的情况是很常见的。故而在 c 字符串中是不能保存像图片、音频、视频、压缩文件、office 文件等二进制数据的。但 sds 不是以空字符’\0’作为字符串结束标志的，其是通过 len 属性来判断字符串是否结束的。所以，对于程序处理 sds 中的字符串数据，无需对数据做任何限制、过滤、假设，只需读取即可。数据写入的是什么，读到的就是什么。

（3）、减少内存再分配次数

sds采用了空间预分配策略与惰性空间释放策略来避免内存再分配问题。

空间预分配策略是指，每次sds进行空间扩展时，程序不但为其分配所需的空间，还会为其分配额外的未使用的空间，以减少内存再分配次数。而额外分配的未使用空间大小取决于空间扩展后sds的len属性值。

如果 len 属性值小于 1m，那么分配的未使用空间 free 的大小与 len 属性值相同。

如果 len 属性值大于等于 1m ，那么分配的未使用空间 free 的大小固定是 1m。

sds对于空间释放采用的是惰性空间释放策略。该策略是指，sds字符串长度如果缩短，那么多出的未使用空间将暂时不释放，而是增加到free中。以使后期扩展sds时减少内存再分配次数。

如果要释放 sds 的未使用空间，则可通过 sdsremovefreespace()函数来释放。

（4）兼容c函数

redis 中提供了很多的 sds 的 api，以方便用户对 redis 进行二次开发。为了能够兼容 c 函数，sds 的底层数组 buf[]中的字符串仍以空字符’\0’结尾。现在要比较的双方，一个是 sds，一个是 c 字符串，此时可以通过 c 语言函数 strcmp(sds_str->buf，c_str）

4、基本操作

数据结构的基本操作不外乎增、删、改、查，sds也不例外。由于redis 3.2后的sds涉及多种类型，修改字符串内容带来的长度变化可能会影响sds的类型而引发扩容。

4.1、创建字符串

redis通过sdsnewlen函数创建sds。在函数中会根据字符串长度选择合适的类型，初始化完相应的统计值后，返回指向字符串内容的指针，根据字符串长度选择不同的类型：

    sds sdsnewlen(const void ＊init, size_t initlen) {
        void ＊sh;
        sds s;
        char type = sdsreqtype(initlen); //根据字符串长度选择不同的类型
        if (type == sds_type_5 && initlen == 0) type = sds_type_8; //sds_type_5强制转化
            为sds_type_8
        int hdrlen = sdshdrsize(type); //计算不同头部所需的长度
        unsigned char ＊fp; /＊ 指向flags的指针 ＊/
        sh = s_malloc(hdrlen+initlen+1); //"+1"是为了结束符'\0'
        ...
        s = (char＊)sh+hdrlen; //s是指向buf的指针
        fp = ((unsigned char＊)s)-1; //s是柔性数组buf的指针，-1即指向flags
        ...
        s[initlen] = '\0'; //添加末尾的结束符
        return s;
    }

注意： redis 3.2后的sds结构由1种增至5种，且对于sdshdr5类型，在创建空字符串时会强制转换为sdshdr8。原因可能是创建空字符串后，其内容可能会频繁更新而引发扩容，故创建时直接创建为sdshdr8。

创建sds的大致流程：首先计算好不同类型的头部和初始长度，然后动态分配内存。需要注意以下3点：

创建空字符串时，sds_type_5被强制转换为sds_type_8。
长度计算时有“+1”操作，是为了算上结束符“\0”。
返回值是指向sds结构buf字段的指针。

返回值sds的类型定义如下：

typedef char ＊sds;

从源码中我们可以看到，其实s就是一个字符数组的指针，即结构中的buf。这样设计的好处在于直接对上层提供了字符串内容指针，兼容了部分c函数，且通过偏移能迅速定位到sds结构体的各处成员变量。

4.2、释放字符串

sds提供了直接释放内存的方法——sdsfree，该方法通过对s的偏移，可定位到sds结构体的首部，然后调用s_free释放内存：

    void sdsfree(sds s) {
        if (s == null) return;
        s_free((char＊)s-sdshdrsize(s[-1])); //此处直接释放内存
    }

为了优化性能（减少申请内存的开销）, sds提供了不直接释放内存，而是通过重置统计值达到清空目的的方法——sdsclear。该方法仅将sds的len归零，此处已存在的buf并没有真正被清除，新的数据可以覆盖写，而不用重新申请内存：

    void sdsclear(sds s) {
        sdssetlen(s, 0); //统计值len归零
        s[0] = '\0'; //清空buf
    }

4.3、拼接字符串

拼接字符串操作本身不复杂，可用sdscatsds来实现，代码如下：

    sds sdscatsds(sds s, const sds t) {
        return sdscatlen(s, t, sdslen(t));
    }

sdscatsds是暴露给上层的方法，其最终调用的是sdscatlen。由于其中可能涉及sds的扩容，sdscatlen中调用sdsmakeroomfor对带拼接的字符串s容量做检查，若无须扩容则直接返回s；若需要扩容，则返回扩容好的新字符串s。函数中的len、curlen等长度值是不含结束符的，而拼接时用memcpy将两个字符串拼接在一起，指定了相关长度，故该过程保证了二进制安全。最后需要加上结束符。

    /＊ 将指针t的内容和指针s的内容拼接在一起，该操作是二进制安全的＊/
    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;
    }

下图描述了sdsmakeroomfor的实现过程。

redis的sds中有如下扩容策略：

1）若sds中剩余空闲长度avail大于新增内容的长度addlen，直接在柔性数组buf末尾追加即可，无须扩容。代码如下：

    sds sdsmakeroomfor(sds s, size_t addlen)
    {
        void ＊sh, ＊newsh;
        size_t avail = sdsavail(s);
        size_t len, newlen;
        char type, oldtype = s[-1] &amp; sds_type_mask; //s[-1]即flags
        int hdrlen;
        if (avail &gt;= addlen) return s; //无须扩容，直接返回
        ...
    }

2）若sds中剩余空闲长度avail小于或等于新增内容的长度addlen，则分情况讨论：新增后总长度len+addlen<1mb的，按新长度的2倍扩容；新增后总长度len+addlen>1mb的，按新长度加上1mb扩容。代码如下：

    sds sdsmakeroomfor(sds s, size_t addlen)
    {
        ...
        newlen = (len+addlen);
        if (newlen &lt; sds_max_prealloc)// sds_max_prealloc这个宏的值是1mb
            newlen ＊= 2;
        else
            newlen += sds_max_prealloc;
        ...
    }

3）最后根据新长度重新选取存储类型，并分配空间。此处若无须更改类型，通过realloc扩大柔性数组即可；否则需要重新开辟内存，并将原字符串的buf内容移动到新位置。具体代码如下：

    sds sdsmakeroomfor(sds s, size_t addlen)
    {
        ...
        type = sdsreqtype(newlen);
        /＊ type5的结构不支持扩容，所以这里需要强制转成type8＊/
        if (type == sds_type_5) type = sds_type_8;
        hdrlen = sdshdrsize(type);
        if (oldtype==type) {
        /＊无须更改类型，通过realloc扩大柔性数组即可，注意这里指向buf的指针s被更新了＊/
                    newsh = s_realloc(sh, hdrlen+newlen+1);
            if (newsh == null) return null;
            s = (char＊)newsh+hdrlen;
        } else {
            /＊ 扩容后数据类型和头部长度发生了变化，此时不再进行realloc操作，而是直接重新开辟内存，
              拼接完内容后，释放旧指针＊/
            newsh = s_malloc(hdrlen+newlen+1); //按新长度重新开辟内存
            if (newsh == null) return null;
            memcpy((char＊)newsh+hdrlen, s, len+1); //将原buf内容移动到新位置
            s_free(sh); //释放旧指针
            s = (char＊)newsh+hdrlen; //偏移sds结构的起始地址，得到字符串起始地址
            s[-1] = type; //为falgs赋值
            sdssetlen(s, len); //为len属性赋值
        }
        sdssetalloc(s, newlen); //为alloc属性赋值
        return s;
    }