Redis_SDS_简单动态字符串

数据结构

Redis中用简单动态字符串SDS来表示字符串内容，而不是使用传统C字符串（以空字符结尾的字符数组）

比如:set msg "hello world"，其中msg和hello world分别是两个SDS

sds.h/sdshdr中定义了sds结构，如下：

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

举个例子：字符串’hello’内部中的 len=5,buf='hello\0',free=0.free根据预分配的长度来确定。

对比之下，nginx_str的实现方式中，只有两个成员，有效数据data,数据长度len,其中data中没有结束符\0

typedef struct {
    size_t      len;  //字符串的有效长度
    u_char     *data; //字符串的内容，指向字符串的起始位置
} ngx_str_t;

特性分析

1.获取字符串长度的时间复杂度

由上可见，len成员保存长度，则获取字符串长度的时间复杂度为O(1)

static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
}

2.缓冲区溢出

传统的C字符串不记录字符串长度，导致执行strcat等函数由缓冲区溢出的风险，而redis需要对sds字符串进行修改时，则会检查长度是否满足需求，不满足则会拓展空间。

sds sdscat(sds s, const char *t) {
    //执行长度检查
    return sdscatlen(s, t, strlen(t));
}

sds sdscatlen(sds s, const void *t, size_t len) {    
    struct sdshdr *sh;
    // 原有字符串长度
    size_t curlen = sdslen(s);
    // 扩展 sds 空间
    // T = O(N)
    s = sdsMakeRoomFor(s,len);
    // 内存不足？直接返回
    if (s == NULL) return NULL;
    // 复制 t 中的内容到字符串后部
    // T = O(N)
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);
    // 更新属性
    sh->len = curlen+len;
    sh->free = sh->free-len;
    // 添加新结尾符号
    s[curlen+len] = '\0';
    // 返回新 sds
    return s;
}

3.内存重分配的次数

Redis中需要频繁修改字符串，如果每次字符串的修改都需要重新分配内存，则会降低程序性能。

Redis的解决方法是，预分配内存，通过free成员来记录剩余空间大小。

空间预分配大小

采用的策略是，sds的新长度小于SDS_MAX_PREALLOC时，分配free=new_len,新长度大于SDS_MAX_PREALLOC时，分配free=SDS_MAX_PREALLOC。

其中#define SDS_MAX_PREALLOC (1024*1024),即判断标准为是否大于1M。

代码可见于sdsMakeRoomFor中，如下：

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

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

当我们的增长字符串时，就根据free的长度来做判断，根据实际情况，是否需要拓展空间；缩短字符串时，只需要更新free信息即可。

回收空闲空间

函数sdsRemoveFreeSpace的作用就是回收sds中的空闲空间，避免造成内存浪费，其中调用了zrealloc。

sds sdsRemoveFreeSpace(sds s) {
    struct sdshdr *sh;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    // 进行内存重分配，让 buf 的长度仅仅足够保存字符串内容
    // T = O(N)
    sh = zrealloc(sh, sizeof(struct sdshdr)+sh->len+1);
    // 空余空间为 0
    sh->free = 0;
    return sh->buf;
}

4.兼容 cstring api

sds中buf也是以\0结尾，所以也可以重用部分cstring api，比如：

strcasecmp(sds->buf,"hello world");

strcat(c_string,sds->buf);

与C字符串的区别

下表总结了C字符串和sds之间的区别：

–	C字符串	SDS
字符串长度时间复杂度	O(N)	O(1)
缓冲区安全	不安全	安全
修改字符串重分配空间	是	否
保存内容	文本	二进制
是否兼容`<string.h>`	是	部分

SDS API

sdsempty创建一个空的sds
sdsnew创建给定内容的sds
sdscat字符串拼接
sdscpy复制cstring内容到sds中
sdscmp比较是否相同

Rerference

黄健宏. Redis设计与实现[M]. 机械工业出版社, 2014.