Redis内部数据结构详解之简单动态字符串(sds)

预备知识 下面介绍有关sizeof计算参数所占字节数的部分实例，方便下面对sds数据结构地址的计算理解 typedef struct Node{ int len; char str[5];}Node;typedef struct Node2{ int len; char str[];}Node2;sizeof(char*) = 4sizeof(Node*) = 4sizeof(Node) =

预备知识

下面介绍有关sizeof计算参数所占字节数的部分实例，方便下面对sds数据结构地址的计算理解

typedef struct Node{
    int len;
    char str[5];
}Node;
typedef struct Node2{
    int len;
    char str[];
}Node2;
sizeof(char*) = 4
sizeof(Node*) = 4
sizeof(Node) = 12
sizeof(Node2) = 4

简单解释下上述sizeof的结果值，前两个等于4是因为指针；第三个值等于12是因为len占4个字节，char str[5]实际应该占5个字节，但是由于计算机内存对齐的原因其实际占8个字节；最后一个等于4，因为char str[]没有实际长度，不被分配内存。

了解sizeof之后还需要了解stdarg.h中的va_list, va_start,va_end,va_copy的知识，这个在网上有很多就不多解释了。

简单动态字符串sds与char*对比

sds在Redis中是实现字符串对象的工具，并且完全取代char*.

char*的功能比较单一，不能实现Redis对字符串高效处理的需求，char*的性能瓶颈主要在：计算字符串长度需要使用strlen函数，该函数的时间复杂度是O(N)，而在Redis中计算字符串长度的操作十分频繁，O(N)的时间复杂度完全不能接受，sds实现能在O(1)时间内得到字符串的长度值；同时，在处理字符串追加append操作时，如果使用char*则需要多次重新分配内存操作。

简单动态字符串sds数据结构

typedef char *sds;

struct sdshdr {
    int len;     //buf已占用的长度，即当前字符串长度值
    int free;    //buf空余可用的长度，append时使用
    char buf[];  //实际保存字符串数据
};

通过增加len字段，就可以实现在O(1)时间复杂度内得到字符串的长度，增加free字段，在需要append字符串时，如果free的值大于等于需要append的字符串长度，那么直接追加即可，不需要重新分配内存。sizeof(sdshdr) = 8.

简单动态字符串sds中函数API

Redis中sds实现的细节解析

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

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

上述两个函数sdslen, sdsavail分别用来计算给定的sds的字符串长度和给定的sds空余的字节数。仔细观察会发现函数的参数是sds即char *，接着通过一行代码就能得到给定sds所对应的sdshdr数据结构，貌似很神奇的样子啊！

看Redis中初始化一个sds的代码

/*init: C字符串，initlen：C字符串的长度*/
sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;

    if (init) {
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }
    if (sh == NULL) return NULL;
    sh->len = initlen;
    sh->free = 0;
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}

/* Create a new sds string starting from a null termined C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

核心函数是sdsnewlen，sh = zmalloc(sizeof(struct sdshdr)+initlen+1)为sdshdr数据结构分配内存，该段内存分为两个部分：sdshdr数据结构所占的内存数sizeof(sdshdr)，我们知道其值为8；initlen+1为sdshdr数据结构中buf的内存。而sdsnewlen函数的返回值是buf的首地址，这样在看sdslen函数，通过给定的sds首地址减去sizeof(sdshdr)，那么就应该是该sds所对应的sdshdr数据结构首地址，自然就能得到sh->len与sh->free。这种操作真的很神奇，这就是C语言指针的妙用，而且使用这种方式，很好的隐藏了sdshdr数据结构，对外接口全部同C字符串类似，却达到了求取sds字符串长度时间复杂度O(1)与降低append操作频繁申请内存的效果。

简单动态字符串sds空间扩展操作解析

sds模块的函数都比较简单，不一一介绍，主要讲解sds如何对空间进行扩展的，扩展操作主要在append操作的时候使用。

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
//对sdshdr的buf进行扩展
sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s); //查看当前sds空余的长度
    size_t len, newlen;

    if (free >= addlen) return s; //不需要扩展
    len = sdslen(s); //得到当前sds字符串的长度
    sh = (void*) (s-(sizeof(struct sdshdr))); //得到sdshdr首地址
    newlen = (len+addlen); //追加之后sds新的长度
    if (newlen < SDS_MAX_PREALLOC) //SDS_MAX_PREALLOC (1024*1024)，扩展的具体方法
        newlen *= 2;
    else
        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;
}

小结

Redis的简单动态字符串sds对比C语言的字符串char*，有以下特性：

1) 可以在O(1)的时间复杂度得到字符串的长度

2) 可以高效的执行append追加字符串操作

3) 二进制安全

sds通过判断当前字符串空余的长度与需要追加的字符串长度，如果空余长度大于等于需要追加的字符串长度，那么直接追加即可，这样就减少了重新分配内存操作；否则，先用sdsMakeRoomFor函数先对sds进行扩展，按照一定的机制来决定扩展的内存大小，然后再执行追加操作，扩展后多余的空间不释放，方便下次再次追加字符串，这样做的代价就是浪费了一些内存，但是在Redis字符串追加操作很频繁的情况下，这种机制能很高效的完成追加字符串的操作。

由于sds其他的函数比较简单，如果有问题的可以在回复中提出。

指出一点2.8源码中sds作者作出的注释有一处是错误的，具体就不列出了。

最后感谢黄健宏（huangz1990）的Redis设计与实现及其他对Redis2.6源码的相关注释对我在研究Redis2.8源码方面的帮助。