redis实现动态字符串SDS_数据库_开发者_运维开发者技术经验分享

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”在内存中的结构如下：

redis实现动态字符串SDS

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

redis实现动态字符串SDS

该结构与前面不同的是，这里有 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的大致流程：首先计算好不同类型的头部和初始长度，然后php动态分配内存。需要注意以下3点：

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

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

typedef char ＊sds;

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

4.2、释放字符串

SDS提供了直接释放内存的方法——sdsfree，该方法通过对s的偏移，可定位到SDS结构体的首部，然后调http://www.devze.com用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

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;
    }