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

function	description	time complexity
sdslen	获取sds字符串长度	O(1)
sdsavail	获取sds可用长度	O(1)
sdsnewlen	创建指定长度的sds，并接受C字符串为初始化内容	O(N)
sdsnew	根据给定的C字符串创建sds	O(N)
sdsempty	创建一个空的sds	O(1)
sdsdup	复制sds	O(N)
sdsfree	释放sds	O(1)
sdsgrowzero	将sds扩展到指定长度，新扩展的内容用\0赋值	O(N)
sdscatlen	将一个给定字符串复制指定长度到sds末尾	O(N)
sdscat	将一个给定字符串添加到sds末尾	O(n)
sdscatsds	将一个sds添加到sds末尾	O(N)
sdscpylen	将一个给定字符串复制一定长度到sds中	O(N)
sdscpy	将一个给定字符串复制到sds中	O(N)
sdstrim	修剪sds	O(M*N),M为sds长度，N为修剪内容长度
sdsrange	保留给定sds一定范围的长度	O(N)
sdsupdatelen	重新计算sds文本字符串的长度	O(N)
sdsclear	清除sds为空字符串	O(1)
sdscmp	比较sds字符串	O(N)
sdstolower	sds字符串转为小写	O(N)
sdstoupper	sds字符串转为大写	O(N)

Reference