Redis源码阅读笔记(1)-简单动态字符串SDS

字符串是Redis中一个重要的组成部分，Redis没有直接使用C语言自带的字符串，而是自身构建了一个简单动态字符串（Simple dynamic string, SDS）的抽象类型，该抽象类型不仅有额外的特性，还能兼容部分C语言内建的字符串操作函数。

涉及的主要源代码文件

1. sds.h
2. sds.c

SDS的定义

typedef char *sds;      //声明一个字符串指针类型的别名

//动态字符串结构
//总长度 = len + free + 1  (1是末尾字符串\0所占的字节)
struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];        //flexible array member，在计算struct长度是不算在内
};

SDS示例

SDS字符串与C字符串相比，在结构体中定义len和free属性，len用来记录当前buf数组中已使用的字节空间，free记录了buf数组中未使用的字符串空间。SDS字符串与C字符串一样，使用了\0作为字符串结尾，但给\0字符不算入len中，因此buf数组的总大小应为total = len + free + 1。如图中Redis的SDS字符串buf分配的空间为10字节。\0字节的添加完全有SDS底层函数负责，使用者无需关心，也由于这个\0字符的存在，使得SDS可以重用一部分C字符串函数。

备注：sizeof(sdshdr) = 2 * sizeof(int64)，buf所占的空间为0，可参考flexible array member

SDS的关键实现细节

//得到动态字符串锁保存字符串的长度（不含\0）
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;
}

由于SDS中记录了自身的长度len，因此获取字符串长度的时间复杂度为O(1)，而不是C字符串的O(N)，因此提高了获取字符串长度的性能。从上面可以看到，len和free的获取需要通过指针计算来获取sdshdr的实际地址来获得的。

//指定长度初始化sds，init表示初始化填写的内容，init为空表示初始化字符串长度为0
sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;

    //sdshdr的长度: strlen(sdshdr) + initlen + 1(1表示末尾0所占的资费)
    if (init) {
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);      
    } else {
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);      //初始化为0
    }
    if (sh == NULL) return NULL;
    sh->len = initlen;
    sh->free = 0;
    if (initlen && init)
        memcpy(sh->buf, init, initlen);                     //复制init指向地址的字符串
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;                                  //sds的指针为实际字符串的指针
}

从sdsnewlen的返回可以看到，实际返回给上层的是buf数组的地址，对上层屏蔽了sdshdr，sdshdr的地址可以通过sdshder.buf的地址来算出。

//增加sds的额外可存储空间至addlen字节，free = addlen
sds sdsMakeRoomFor(sds s, size_t addlen) {
    struct sdshdr *sh, *newsh;
    size_t free = sdsavail(s);
    size_t len, newlen;

    if (free >= addlen) return s;    //当free空间足够时，直接返回，无需重分配
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen);
    if (newlen < SDS_MAX_PREALLOC)      //预分配策略，若新字符长度小于1M，则为字符串分配2倍所需空间的大小
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;     //否则，只额外添加1M未使用空间
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) return NULL;

    newsh->free = newlen - len;
    return newsh->buf;
}

//字符串左右修剪函数
sds sdstrim(sds s, const char *cset) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    char *start, *end, *sp, *ep;
    size_t len;

    sp = start = s;
    ep = end = s+sdslen(s)-1;
    while(sp <= end && strchr(cset, *sp)) sp++;     //修建左边
    while(ep > start && strchr(cset, *ep)) ep--;    //修建右边
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    if (sh->buf != sp) memmove(sh->buf, sp, len); //移动内存存储内容
    //更新末尾、len、free
    sh->buf[len] = '\0';
    sh->free = sh->free+(sh->len-len);
    sh->len = len;
    return s;
}

//获取子字符串，start/end 允许传负数
void sdsrange(sds s, int start, int end) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    size_t newlen, len = sdslen(s);

    if (len == 0) return;
    if (start < 0) {
        start = len+start;
        if (start < 0) start = 0;
    }
    if (end < 0) {
        end = len+end;
        if (end < 0) end = 0;
    }
    newlen = (start > end) ? 0 : (end-start)+1;
    if (newlen != 0) {
        if (start >= (signed)len) {
            newlen = 0;
        } else if (end >= (signed)len) {
            end = len-1;
            newlen = (start > end) ? 0 : (end-start)+1;
        }
    } else {
        start = 0;
    }
    if (start && newlen) memmove(sh->buf, sh->buf+start, newlen);
    sh->buf[newlen] = 0;
    sh->free = sh->free+(sh->len-newlen);
    sh->len = newlen;
}

由于SDS字符串存在未使用空间，因此修改字符串长度不像C字符串，无需频繁的通过内存重分配来扩展或缩小字符串所占大小。这对于需要频繁修改数据的Redis是一个极大的性能提升。sdsMakeRoomFor函数用来对SDS字符串进行扩展，sdstrim和sdsrange用来对字符串进行缩减。

通过控制未使用空间，SDS实现了空间预分配和惰性释放两种空间优化策略。

1. 空间预分配
   若对字符串进行扩展后的大小(newlen)小于1M (1024*1024字节)，那么给SDS字符串额外分配所需大小一倍(扩展后大小为2*newlen)的空间。若对字符串进行扩展后的大小大于1M，则给SDS字符串额外分配1M空间。通过这种方式，减少了执行字符串增长操作所需的内存分配次数。

2. 惰性释放
   当SDS字符串进行缩减时，并不释放多出来的空间，而是通过修改free属性和len属性来表示字符串的缩减，宠儿频繁的内存操作。

//连接指定长度字符串到sds末尾
sds sdscatlen(sds s, const void *t, size_t len) {
    struct sdshdr *sh;
    size_t curlen = sdslen(s);

    s = sdsMakeRoomFor(s,len);          //扩展空间
    if (s == NULL) return NULL;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);
    sh->len = curlen+len;
    sh->free = sh->free-len;
    s[curlen+len] = '\0';           //末尾添加0
    return s;
}

SDS不使用C字符串函数的strcat函数，而是自己封装了一个，当free空间不足时，会扩展SDS字符串的未使用空间，然后在进行拼接，从而避免了缓冲区溢出。

总结

SDS字符串相比C字符串的优势：

1. O(1)获取字符串长度；
2. 通过空间预分配和惰性空间释放减少内存的操作次数；
3. 杜绝缓冲区溢出
4. 因为是通过len来控制字符串的长度，不依赖于\0，因此字符串是二进制安全的，不仅可以保存文本数据，还可以用来保存任意格式的二进制数据。
5. 因为SDS字符串末尾带有\0，因此作为存储普通字符串，可以使用部分C语言字符串函数。

SDS主要API

Reference