走进Redis-深入理解SDS

写在前

本系列文章已被收录到专栏中，如果各位看官有兴趣，可以移步深入理解Redis专栏

前言

Redis最常用的字符串类型的底层是自己实现了一个数据结构**（Simple Dynamic Strings）简单动态字符串**，用于存储字符串和整型数据。而这个面试中也会被经常问到：

面试官：知道Redis中的字符底层吗？

小张：知道，就是SDS嘛~😎😎

面试官：行，那你说说他的细节吧，为啥不用C语言中的字符，还要去单独设计一套SDS呢？

小张：(°ー°〃) 愣住

面试官：hh，回去等通知吧。( ﹁ ﹁ ) ~→

数据结构

在C语言中，如果要设计一个SDS，那么必然会有一个字符串指针。除此之外，还可以添加一些基本的统计信息：当前字符串长度、剩余容量等等。

Redis 3.2之前就是采用这种结构的：

struct sds {
    int len;// buf 中已占用字节数
    int free;// buf 中剩余可用字节数
    char buf[];// 真正的数据空间
};
复制代码

相对于c字符串，这样子做有以下几点优势：

• 能够很快的获取到buf[]的长度、剩余可以空间等等，相对于c字符串来说，时间复杂度为O(1)

• 对上层暴露的是指向buf[]的指针，sds封装了一些方法供外部使用，同时sds也兼容对c字符串的各种操作

• 解决了二进制安全问题

  什么是二进制安全？通俗地讲，C语言中，用“\0”表示字 符串的结束，如果字符串中本身就有“\0”字符，字符串就会被截断，即 非二进制安全；若通过某种机制，保证读写字符串时不损害其内容，则 是二进制安全。

图片选自Redis 5设计与源码分析

在x64的操作系统中，len和free各占4个字节，buf[]是一个动态数组，通过malloc给他动态分配内存。

能否再次对SDS进行优化呢？我们考虑到每个字符串真正使用的字节不一样，但是短字符串的头部却跟长字符串的一样长，属实有点浪费。

于是乎，在Redis 5.0以后对SDS能存储的长度进行了分类：长度：小于1字节、1字节、2字节、4字节、8字节，共5种，用位运算保存最少使用3位（000），那么他的高位就可以用来保存buf[]的长度。

比如说对于长度小于32位(2^5)的短字符串，flags只需要占1个字节就可以了，相对于我们前边的4+4这种情况大大的优化了存储。

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__))sdshdr5 {
    unsigned char flags; /* 低3位存储类型, 高5位存储长度 */
    char buf[];/*柔性数组，存放实际内容*/
};
复制代码

sdshdr5的示意图：

这里要说一个细节：

sdshdr5的注释说他不再使用，但其实如果存放一个数据（他的结构是 小于32位的键和小于32位的值），那么他的键会采用sdshdr5存储，而值则会使用sdshdr8。

我们看Redis源码可以发现，还定义了一些其他的类型，我们通常使用的就是这些

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 无符号8位int，记录长度 */
    uint8_t alloc; /* 不包括头部和终止符 */
    unsigned char flags; /* 低三位用来保存类型，高五位没有使用，是个预留空间 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
复制代码

len存储的是buf已占用的字节数

alloc存储给buf分配的字节数，但是不包括头部和终止符

flags用来保存大小类型，高五位预留

buf[]柔性数组

基本操作

那么说完了SDS的数据结构，我们还应该关注最基本的增删改查

提前给大家提供一些方法，大家可以自行查看相关内容

...

这里简单的说几个重要的

字符串创建

typedef char *sds;
/* 使用'init'指针指定的内容创建一个新的sds字符串
  * 和 'initlen'。
  * 如果 NULL 用于 'init'，则字符串用零字节初始化。
  * 如果使用 SDS_NOINIT，则缓冲区未初始化；
  *
  * 字符串总是以空字符结尾（所有 sds 字符串都是，总是）所以
  * 即使您使用以下内容创建 sds 字符串：
  *
  * mystring = sdsnewlen("abc",3);
  *
  * 您可以使用 printf() 打印字符串，因为在
  * 字符串的结尾。 然而，该字符串是二进制安全的，可以包含 \0 字符在中间，因为长度存储在 sds 标头中。 */
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this.  */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;  // 空字符串满足条件后就会在这里强转类型
    int hdrlen = sdsHdrSize(type); // 头部的长度
    unsigned char *fp; // flags 指针
    size_t usable;

    assert(initlen + hdrlen + 1 > initlen); // 初始字符串长度+头部长度+1(这里的1表示 \0结束符)
    sh = trymalloc?
        s_trymalloc_usable(hdrlen+initlen+1, &usable) :
        s_malloc_usable(hdrlen+initlen+1, &usable);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    switch(type) {  //根据不同的SDS类型获取不同的flag
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}
复制代码

大致的一个流程是：

总结：

• 创建空字符串时，SDS_TYPE_5被强制转换为SDS_TYPE_8
• 长度计算时有“+1”操作，是加入了\0结束符

释放

SDS提供了相关的方法sdsfree、sdsclear，前者是直接将内存释放，后者则是将长度清空，降低了内存的开销，这样新的数据进来后直接覆盖就可以了。

void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));//此处直接释放内存
}

void sdsclear(sds s) {
    sdssetlen(s, 0); //统计值len归零
    s[0] = '\0';//清空buf
}
复制代码

拼接

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

/* 将t和s进行拼接*/
sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);
    s = sdsMakeRoomFor(s,len); // 这里做了一个扩容操作
    if (s == NULL) return NULL;
    memcpy(s+curlen, t, len);//直接拼接，保证了二进制安全
    sdssetlen(s, curlen+len);
    s[curlen+len] = '\0';//加上结束符
    return s;
}

复制代码

相关的扩容操作

#define SDS_MAX_PREALLOC (1024*1024) //1MB
/* 扩大 sds 字符串末尾的空闲空间，以便调用者
  * 确定调用此函数后可以覆盖到addlen
  * 字符串结尾后的字节，再加上一个字节作为空项。
  * 如果已经有足够的可用空间，则此函数不带任何返回
  * action，如果没有足够的可用空间，它会分配缺少的，
  * 可能还有更多：
  * 当 greedy 为 1 时，放大超过需要，以避免将来需要重新分配
  * 关于增量增长。
  * 当 greedy 为 0 时，放大到足以让 'addlen' 有可用空间。
  *
  * 注意：这不会改变返回的 sds 字符串的 *length*
  * 通过 sdslen()，但只有我们拥有的可用缓冲区空间。 */
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;
    size_t usable;

    /*如果有足够的空间，请尽快返回。 */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);// 原本长度+拼接的长度
    assert(newlen > len);   /* Catch size_t overflow */
    if (greedy == 1) {   // 空间分配策略
        if (newlen < SDS_MAX_PREALLOC)  // 新长度小于1M
            newlen *= 2;
        else
            newlen += SDS_MAX_PREALLOC; // 新长度大于等于1M
    }
	......
}
复制代码

我们可以看到，Redis在面对不同大小的串时候，分配有不同的策略：

• 如果sds剩余长度足够分配，直接去使用就行了
• 如果sds剩余空间不够了
  • 新长度newlen小于1MB，newlen*2分配
  • newlen大于等于1MB，在newlen的基础上+1MB

这样做的目的是：尽量减少对内存的使用，降低开销

最后呢，扩容中会再次判断一次存储类型是否正确，如果正确就直接分配空间，如果不正确就重新开辟内存并把原字符串移植过去，如下代码

sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
	...
    type = sdsReqType(newlen);

    /* Don't use type 5: the user is appending to the string and type 5 is
     * not able to remember empty space, so sdsMakeRoomFor() must be called
     * at every appending operation. */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    assert(hdrlen + newlen + 1 > len);  /* Catch size_t overflow */
    if (oldtype==type) {
        newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* 由于头部大小发生变化，需要将字符串向前移动，
          * 并且不能使用 realloc */
        newsh = s_malloc_usable(hdrlen+newlen+1, &usable);
        if (newsh == NULL) return NULL;
        memcpy((char*)newsh+hdrlen, s, len+1);
        s_free(sh);
        s = (char*)newsh+hdrlen;
        s[-1] = type;
        sdssetlen(s, len);
    }
    usable = usable-hdrlen-1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);
    sdssetalloc(s, usable);
    return s;
}
复制代码

总的流程：

总结一下

sds相较于strings的优点：

• 能够很快的获取到字符串的统计信息，O(1)的时间复杂度
• 杜绝缓冲区溢出，通过len和free等字段控制
• 保证二进制安全，通过len代替\0结束符
• 减少内存消耗
  • 预分配
  • 惰性释放

写在最后

本章对简单动态字符串的探索到这里就结束了

我是路人小张，一名卷在躺平路上的后端工程师

如果你对我的文章感兴趣，还请多多支持，关注我防走丢~

参考资料

《Redis 5设计与源码分析》--陈雷著