Redis源码学习-SDS动态字符串

在Redis中字符串是常用的类型，在本片文章中我们将学习Redis中字符串的源码实现。

Redis中使用的字符串不是C语言字符串，而是自己实现的SDS（Simple Dynamic String），为什么Redis要自己实现呢？这是不是重复造轮子呢？

Redis自己实现SDS的原因主要是C语言字符串存在这下列的问题：

• 获取字符串长度的时间复杂度为O(n)：因为C语言字符串不保存字符串长度，而每次获取字符串长度都需要遍历字符串来计算。
• 容易发生缓冲区溢出：C语言字符串不会对其操作进行边界校验，因此当进行拼接等操作时，容易发送缓冲区溢出。
• 每次修改字符串时都需要进行内存重分配：由于C语言字符串在创建时内存长度是确定的，因此每次扩充或缩小字符串长度都涉及到内存重分配以及内存拷贝。
• 不保证二进制安全：由于C语言字符串使用空字符（"\0"）标识字符串结尾，因此无法存储类似"hello\0world"的字符串，而二进制内容通常会包含该字符。

那么Redis自己实现的SDS是如何解决这些问题的呢？接下来我们将带着这些问题，深入理解Redis SDS的源码实现。

1. SDS 定义

// 用于指向sdshdr结构体对象的buf字段
typedef char *sds;

// sdshdr结构体声明
struct sdshdr {
    // buf已使用长度
    int len;
    // buf未使用长度
    int free;
    // 数据空间，同样已\0结尾
    char buf[];
};

在Redis源码实现中，SDS类型由sdshdr结构体表示，其中buf属性表示数据空间，用于存放字符串字符，与C语言相同，buf[len]处的字符为\0，这样做的好处是可以复用C语言字符串相关处理函数。len表示buf数组已使用的长度，但是不包括\0。free属性表示buf数组未使用的长度。因此buf数组的总长度为len + free + 1。

Char类型指针sds用于表示指向buf属性的指针的别名，即人为规定所有指向buf数组的指针的类型为sds。

sizeof(struct sdshdr)

buf属性属于VLA(variable-length array)中的未指定大小的VLA，也称为Flexible array member。Flexible array member必须放在结构体声明的最后，sizeof(struct struct_name)时不计算其大小，也无法计算其大小。

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

由于SDS中记录了字符串的长度，因此获取字符串长度的时间复杂度为O(1)。

在源码层面，获取SDS长度的函数为sdslen。

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

代码非常简单，入参sds为指向sdshdr的buf属性的指针，s - (sizeof(struct sdshdr))用于计算指向sdshdr对象的指针。然后返回sh->len。

3. SDS不会出现缓冲区溢出

在进行相关操作时，首先会判断SDS剩余的空间是否满足操作的需要，如果不满足，需要申请新的空间。

if (free >= addlen) return s;
// 获取 s 目前已占用空间的长度
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
// s 最少需要的长度
newlen = (len+addlen);
...
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

4. SDS不需要每次修改字符串都需要进行内存重分配

SDS通过空间预分配和懒惰空间释放两种优化策略减少了修改字符串时带来的内存重分配。

空间预分配策略：

• if new_len =< 1M: free = new_len
• if new_len > 1M: free = 1M

// 最大预分配长度
#define SDS_MAX_PREALLOC (1024*1024)

 if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
else
    newlen += SDS_MAX_PREALLOC;

懒惰空间释放：

在字符串长度缩小后，多余空间不会被释放，而是会一直保留直到显式释放。sdsclear方法用于清空字符串，在sdsclear的源码实现中，将多余的空间长度加到free属性中，设置len属性为0并且设置buf[0]为\0。

void sdsclear(sds s) {

    // 取出 sdshdr
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));

    // 重新计算属性
    sh->free += sh->len;
    sh->len = 0;

    // 将结束符放到最前面（相当于惰性地删除 buf 中的内容）
    sh->buf[0] = '\0';
}

5. 保证二进制安全

由于SDS在计算字符串长度时不依赖\0，因此SDS保证了二进制安全。

6. API实现

6.1 sdsnew

新建SDS

sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnewlen(const void *init, size_t initlen) {

    struct sdshdr *sh;

    // 根据是否有初始化内容，选择适当的内存分配方式
    // T = O(N)
    if (init) {
        // zmalloc 不初始化所分配的内存
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        // zcalloc 将分配的内存全部初始化为 0
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }

    // 内存分配失败，返回
    if (sh == NULL) return NULL;

    // 设置初始化长度
    sh->len = initlen;
    // 新 sds 不预留任何空间
    sh->free = 0;
    // 如果有指定初始化内容，将它们复制到 sdshdr 的 buf 中
    // T = O(N)
    if (initlen && init)
        memcpy(sh->buf, init, initlen);
    // 以 \0 结尾
    sh->buf[initlen] = '\0';

    // 返回 buf 部分，而不是整个 sdshdr
    return (char*)sh->buf;
}

6.2 sdsempty

创建一个不包含任何内容的SDS。

sds sdsempty(void) {
    return sdsnewlen("",0);
}

6.3 sdsfree

计算SDS长度

static inline size_t sdslen(const sds s) {
    // 获取sdshdr对象的指针
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    // 返回len属性
    return sh->len;
}

6.4 sdsavail

计算SDS可用的长度。

static inline size_t sdsavail(const sds s) {
    // 获取sdshdr对象的指针
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    // 返回free属性
    return sh->free;
}

6.5 sdsdup

创建sds副本

sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

6.6 sdsclear

清空sds的内容

void sdsclear(sds s) {

    // 取出 sdshdr
    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));

    // 重新计算属性
    sh->free += sh->len;
    sh->len = 0;

    // 将结束符放到最前面（相当于惰性地删除 buf 中的内容）
    sh->buf[0] = '\0';
}

6.7 sdscat

sds拼接c语言字符串

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;
}

sds sdsMakeRoomFor(sds s, size_t addlen) {

    struct sdshdr *sh, *newsh;

    // 获取 s 目前的空余空间长度
    size_t free = sdsavail(s);

    size_t len, newlen;

    // s 目前的空余空间已经足够，无须再进行扩展，直接返回
    if (free >= addlen) return s;

    // 获取 s 目前已占用空间的长度
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));

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

    // 根据新长度，为 s 分配新空间所需的大小 #define SDS_MAX_PREALLOC (1024*1024)
    if (newlen < SDS_MAX_PREALLOC)
        // 如果新长度小于 SDS_MAX_PREALLOC 
        // 那么为它分配两倍于所需长度的空间
        newlen *= 2;
    else
        // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC
        newlen += SDS_MAX_PREALLOC;
    // T = O(N)
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

    // 内存不足，分配失败，返回
    if (newsh == NULL) return NULL;

    // 更新 sds 的空余长度
    newsh->free = newlen - len;

    // 返回 sds
    return newsh->buf;
}

6.8 sdscatsds

与sdscat相比，只是入参不同

csds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

6.9 sdscpy

将字符串中的内容拷贝到sds中。

sds sdscpy(sds s, const char *t) {
    return sdscpylen(s, t, strlen(t));
}

sds sdscpylen(sds s, const char *t, size_t len) {

    struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));

    // sds 现有 buf 的长度
    size_t totlen = sh->free+sh->len;

    // 如果 s 的 buf 长度不满足 len ，那么扩展它
    if (totlen < len) {
        // T = O(N)
        s = sdsMakeRoomFor(s,len-sh->len);
        if (s == NULL) return NULL;
        sh = (void*) (s-(sizeof(struct sdshdr)));
        totlen = sh->free+sh->len;
    }

    // 复制内容
    // T = O(N)
    memcpy(s, t, len);

    // 添加终结符号
    s[len] = '\0';

    // 更新属性
    sh->len = len;
    sh->free = totlen-len;

    // 返回新的 sds
    return s;
}

6.10 sdsgrowzero

用空字符将SDS扩展至给定的长度

sds sdsgrowzero(sds s, size_t len) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    size_t totlen, curlen = sh->len;

    // 如果 len 比字符串的现有长度小，
    // 那么直接返回，不做动作
    if (len <= curlen) return s;

    // 扩展 sds
    // T = O(N)
    s = sdsMakeRoomFor(s,len-curlen);
    // 如果内存不足，直接返回
    if (s == NULL) return NULL;

    /* Make sure added region doesn't contain garbage */
    // 将新分配的空间用 0 填充，防止出现垃圾内容
    // T = O(N)
    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;

    // 返回新的 sds
    return s;
}

6.11 sdsrange

保留range内的内容。

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;
    }

    // 如果有需要，对字符串进行移动
    // T = O(N)
    if (start && newlen) memmove(sh->buf, sh->buf+start, newlen);

    // 添加终结符
    sh->buf[newlen] = 0;

    // 更新属性
    sh->free = sh->free+(sh->len-newlen);
    sh->len = newlen;
}

6.12 sdstrim

修剪SDS字符串开头和结尾出现在cset中的字符，这个函数在《Redis设计与实现》中的解释存在问题

如：sds: "xyzhxyzhzyx", cset: "yxz"

修剪后的结果为： "hxyzh"

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;

    // 修剪, T = O(N^2) strchr函数功能为在一个串中查找给定字符的第一个匹配之处
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep > start && strchr(cset, *ep)) ep--;

    // 计算 trim 完毕之后剩余的字符串长度
    len = (sp > ep) ? 0 : ((ep-sp)+1);
    
    // 如果有需要，前移字符串内容
    // T = O(N)
    if (sh->buf != sp) memmove(sh->buf, sp, len);

    // 添加终结符
    sh->buf[len] = '\0';

    // 更新属性
    sh->free = sh->free+(sh->len-len);
    sh->len = len;

    // 返回修剪后的 sds
    return s;
}

6.13 sdscmp

用于比较两个sds，按照字节序进行比较，其次按照长度进行比较

int sdscmp(const sds s1, const 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;
}

#include <stdio.h>

struct sdshdr {
    int len;
    int free;
    char buf[];
};

int main() {
    printf("struct sdshdr size is %lu\n", sizeof(struct sdshdr));
    return 0;
}

参考文档

why redis use "sizeof" to calculate start address of sdshdr

Flexible_array_member

The usage of sizeof in C