知识点

1.数据结构

• 什么是SDS

2.为什么不直接使用C字符串

• 记录字符串属性避免性能消耗
• 预分配空间
• 二进制安全

Redis的字符串不是C字符串

Redis没有直接使用C语言传统的字符串表示，而是自己构建了一种名为简单动态字符串（SDS）的抽象类型，并将SDS用作Redis的默认字符串表示。
比如在Redis中包含字符串值的键值对在底层都是用SDS实现对。

举个例子

redis> SET msg "hello world"
OK

那么Redis将在数据库中创建一个新对键值对，其中：

• 键值对对键是一个字符串对象，对象对底层实现是一个保存着字符串“msg”对的SDS
• 键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串的"hellow world"的SDS

每个sdshdr结构表示一个SDS值：

struct sdshdr {
    // 记录buf数组中已使用字符的数量
    // 等于 SDS 所保存字符串的长度
    int len;
    // 记录buf数组中未使用的字节数量
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

为什么不直接使用C字符串:

1.为C字符串并不记录自身的长度信息，所以为了获取一个C字符串的长度，程序必须遍历整个字符串，对遇到对每个字符串进行计数，直到遇到代表字符串结尾对空字符串为止，这个操作的复杂度为O(N)。
和C字符串不同，因为SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度仅为O(1)

2.实现了自己的一套字符串空间分配方法性能更优于直接使用C字符串:

• 如果对SDS修改增加长度且超过free+len，若修改后的SDS所保存的字符串长度小于1MB，那么将会分配和字符串长度相等的free，即总长度为字符串长度的两倍。
• 如果对SDS修改增加长度且超过free+len，若修改后的SDS所保存的字符串长度大于1MB，那么将会分配1MB的free,即总长度为字符串长度+1MB。
• 如果对SDS修改增加长度且未超过free+len, 则直接使用未使用的空间，不再重新分配空间。
• 如果对SDS修改减少长度，并不会立即回收这些减少的空间，而是使用free属性将其记录起来，并等待再次使用。
• 通过这套机制可以有效的减少内存分配次数提高字符串的性能

3.二进制安全

源码

//创建一个包含字符串以及len属性为字符串长度free为0的SDS
sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;
    
    sh = malloc(sizeof(struct sdshdr)+initlen+1);
#ifdef SDS_ABORT_ON_OOM
    if (sh == NULL) sdsOomAbort();
#else
    if (sh == NULL) return NULL;
#endif
    sh->len = initlen;
    sh->free = 0;
    if (initlen) {
        if (init) memcpy(sh->buf, init, initlen);
        else memset(sh->buf,0,initlen);
    }
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}
//创建一个不包含任何内容的空SDS
sds sdsempty(void) {
    return sdsnewlen("",0);
}

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}
//创建SDS副本（copy）
sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

//释放SDS
void sdsfree(sds s) {
    if (s == NULL) return;
    free(s-sizeof(struct sdshdr));
}
//更新len属性
void sdsupdatelen(sds s) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    int reallen = strlen(s);
    sh->free += (sh->len-reallen);
    sh->len = reallen;
}
static 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;
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen)*2;
    newsh = realloc(sh, sizeof(struct sdshdr)+newlen+1);
#ifdef SDS_ABORT_ON_OOM
    if (newsh == NULL) sdsOomAbort();
#else
    if (newsh == NULL) return NULL;
#endif

    newsh->free = newlen - len;
    return newsh->buf;
}
//将SDS扩展至给定长度
/* Grow the sds to have the specified length. Bytes that were not part of
 * the original length of the sds will be set to zero. */
sds sdsgrowzero(sds s, size_t len) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    size_t totlen, curlen = sh->len;

    if (len <= curlen) return s;
    s = sdsMakeRoomFor(s,len-curlen);
    if (s == NULL) return NULL;

    /* Make sure added region doesn't contain garbage */
    sh = (void*)(s-(sizeof(struct sdshdr)));
    memset(s+curlen,0,(len-curlen+1)); /* also set trailing \0 byte */
    totlen = sh->len+sh->free;
    sh->len = len;
    sh->free = totlen-sh->len;
    return s;
}
//将C字符串拼接到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';
    return s;
}
//将C字符串拼接到SDS字符串的末尾
sds sdscat(sds s, const char *t) {
    return sdscatlen(s, t, strlen(t));
}
//将C字符串复制到SDS里面并覆盖SDS原有的字符串
sds sdscpylen(sds s, char *t, size_t len) {
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
    size_t totlen = sh->free+sh->len;

    if (totlen < len) {
        s = sdsMakeRoomFor(s,len-sh->len);
        if (s == NULL) return NULL;
        sh = (void*) (s-(sizeof(struct sdshdr)));
        totlen = sh->free+sh->len;
    }
    memcpy(s, t, len);
    s[len] = '\0';
    sh->len = len;
    sh->free = totlen-len;
    return s;
}
//将C字符串复制到SDS里面并覆盖SDS原有的字符串
sds sdscpy(sds s, char *t) {
    return sdscpylen(s, t, strlen(t));
}

sds sdscatvprintf(sds s, const char *fmt, va_list ap) {
    va_list cpy;
    char *buf, *t;
    size_t buflen = 16;

    while(1) {
        buf = malloc(buflen);
#ifdef SDS_ABORT_ON_OOM
        if (buf == NULL) sdsOomAbort();
#else
        if (buf == NULL) return NULL;
#endif
        buf[buflen-2] = '\0';
        va_copy(cpy,ap);
        vsnprintf(buf, buflen, fmt, cpy);
        if (buf[buflen-2] != '\0') {
            free(buf);
            buflen *= 2;
            continue;
        }
        break;
    }
    t = sdscat(s, buf);
    free(buf);
    return t;
}

sds sdscatprintf(sds s, const char *fmt, ...) {
    va_list ap;
    char *t;
    va_start(ap, fmt);
    t = sdscatvprintf(s,fmt,ap);
    va_end(ap);
    return t;
}
//从左右两端分别移除字符串
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);
    sh->buf[len] = '\0';
    sh->free = sh->free+(sh->len-len);
    sh->len = len;
    return s;
}
//保留SDS start到end区间内的数据，不在区间内的数据会被覆盖或清楚
sds 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 s;
    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;
    return s;
}

void sdstolower(sds s) {
    int len = sdslen(s), j;

    for (j = 0; j < len; j++) s[j] = tolower(s[j]);
}

void sdstoupper(sds s) {
    int len = sdslen(s), j;

    for (j = 0; j < len; j++) s[j] = toupper(s[j]);
}
//对比两个SDS字符串是否相同
int sdscmp(sds s1, sds s2) {
    size_t l1, l2, minlen;
    int cmp;

    l1 = sdslen(s1);
    l2 = sdslen(s2);
    minlen = (l1 < l2) ? l1 : l2;
    cmp = memcmp(s1,s2,minlen);
    if (cmp == 0) return l1-l2;
    return cmp;
}

总结

C 字符串                                             SDS
获取字符串长度的复杂度为 O(N) 。                        获取字符串长度的复杂度为 O(1) 。
API 是不安全的，可能会造成缓冲区溢出。                    API 是安全的，不会造成缓冲区溢出。
修改字符串长度 N 次必然需要执行 N 次内存重分配。           修改字符串长度 N 次最多需要执行 N 次内存重分配。
只能保存文本数据。                                     可以保存文本或者二进制数据。
可以使用所有 <string.h> 库中的函数。                    可以使用一部分 <string.h> 库中的函数。