关于java:Redis源码剖析之SDSSimple-Dynamic-String

SDS(simple dynamic string)是 Redis 提供的字符串的封装，在 redis 中也是存在最宽泛的数据结构，它也是很多其余数据结构的根底，所以才抉择先介绍 SDS。SDS 也兼容局部 C 字符串 API(strcmp,strlen)，它如何兼容 C 字符串我感觉也是有个很 sao 的操作，等看完我这篇博客你就明确了。在开始正式内容前，我先抛几个问题(有些也是面试高频题)，带着问题去学习也是一种十分好的学习办法。

C 语言中也算是反对 String 了，为什么 Redis 还要本人封装一个？
SDS 中的 D(dynamic)到底是什么含意？
SDS 的数据结构是啥样的？为什么要那么设计？
SDS 是如何兼容 C 字符串的?

Redis 中 sds 相干的源码都在 src/sds.c 和 src/sds.h 中（链接能够间接跳转到我中文正文版 redis 源码），其中 sds.h 中定义了所有 SDS 的 api，当然也实现了局部几个 api，比方 sds 长度、sds 残余可用空间……，不急着看代码，咱们先看下 sds 的数据结构，看完后为什么代码那么写你就高深莫测。

redis 提供了 sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64 这几种 sds 的实现，其中除了 sdshdr5 比拟非凡外，其余几种 sdshdr 差不只在于两个字段的类型差异。我就拿 sdshdr8 和 sdshdr16 来举例，其 struct 定义别离如下。

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 已应用空间大小 */
    uint8_t alloc; /* 总共可用的字符空间大小，应该是理论 buf 的大小减 1(因为 c 字符串开端必须是 \0, 不计算在内) */
    unsigned char flags; /* 标记位，次要是辨认这是 sdshdr 几，目前只用了 3 位，还有 5 位空余 */
    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[];};

sdshdr32 sdshdr64 也和下面的构造统一，差异只在于 len 和 alloc 的数据类型不一样而已。相较于 c 原生的字符串，sds 多了 len、alloc、flag 三个字段来存储一些额定的信息，redis 思考到了字符串拼接时带来的微小损耗，所以每次新建 sds 的时候会 预调配 一些空间来应答将来的增长，sds 和 C string 的关系相熟 java 的旁友可能会决定就好比 java 中 String 和 StringBuffer 的关系。正是因为预留空间的机制，所以 redis 须要记录下来已调配和总空间大小，当然可用空间可用间接算进去。

下一个问题，为什么 redis 费神费劲要提供 sdshdr5 到 sdshdr64 这五种 SDS 呢？我觉着这只能阐明 Redis 作者抠内存抠到机制，就义了代码的简洁性换取了每个 sds 省下来的几个字节的内存空间。从 sds 初始化办法 sdsnew 和 sdsnewlen 中咱们就能够看出，redis 在新建 sds 时须要传如初始化长度，而后依据初始化的长度确定用哪种 sdshdr，小于 2^8 长度的用 sdshdr8，这样 len 和 alloc 只占用两个字节，比拟短字符串可能十分多，所以节省下来的内存还是十分可观的，晓得了 sds 的数据结构和设计原理，sdsnewlen 的代码就十分好懂了，如下：

sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    // 依据初始化的长度确定用哪种 sdshdr
    char type = sdsReqType(initlen);
    /* 空字符串大概率之后会 append，但 sdshdr5 不适宜用来 append，所以间接替换成 sdshdr8 */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    /* 留神：返回的 s 并不是间接指向 sds 的指针，而是指向 sds 中字符串的指针，sds 的指针还须要
     * 依据 s 和 hdrlen 计算出来 */
    s = (char*)sh+hdrlen;  
    fp = ((unsigned char*)s)-1;
    switch(type) {
        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 = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    if (initlen && init)
        memcpy(s, init, initlen);
    s[initlen] = '\0';
    return s;
}

下面代码中我特意标注了一个留神，sdsnewlen() 返回的 sds 指针并不是间接指向 sdshdr 的地址，而是间接指向了 sdshdr 中 buf 的地址。这样做有啥益处？益处就是这样能够兼容 c 原生字符串。buf 其实就是 C 原生字符串 + 局部空余空间，两头是特殊符号 ’0’ 隔开，‘0’有是标识 C 字符串开端的符号，这样就实现了和 C 原生字符串的兼容，局部 C 字符串的 API 也就能够间接应用了。当然这也有害处，这样就没法间接拿到 len 和 alloc 的具体值了，然而也不是没有方法。

当咱们拿到一个 sds，假如这个 sds 就叫 s 吧，其实一开始咱们对这个 sds 无所不知，连他是 sdshdr 几都不晓得，这时候能够看下 s 的后面一个字节，咱们曾经晓得 sdshdr 的数据结构了，前一个字节就是flag，依据 flag 具体的值咱们就能够推断出 s 具体是哪个 sdshdr，也能够推断出 sds 的真正地址，相应的就晓得了它的 len 和 alloc，晓得了这点，上面这些有点艰涩的代码就很好了解了。

oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 看下 s 后面一个字节 (flag) 推算出 sdshdr 的类型。// 这个宏定义间接推算出 sdshdr 头部的内存地址
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

// 获取 sds 反对的长度  
static inline size_t sdslen(const sds s) {unsigned char flags = s[-1];  // -1 相当于获取到了 sdshdr 中的 flag 字段  
    switch(flags&SDS_TYPE_MASK) {  
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;  // 宏替换获取到 sdshdr 中的 len
        ...
        // 省略 SDS_TYPE_16 SDS_TYPE_32 的代码…… 
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}
// 获取 sds 残余可用空间大小 
static inline size_t sdsavail(const sds s) {unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {return 0;}
        case SDS_TYPE_8: {SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        ... 
        // 省略 SDS_TYPE_16 SDS_TYPE_32 的代码…… 
        case SDS_TYPE_64: {SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}
/* 返回 sds 理论的起始地位指针 */
void *sdsAllocPtr(sds s) {return (void*) (s-sdsHdrSize(s[-1]));
}

在做字符串拼接的时候，sds 可能残余的可用空间有余，这个时候须要扩容，什么时候该扩容，又该怎么扩? 这是不得不思考的问题。Java 中很多数据结构都有动静扩容的机制，比方和 sds 很相似的 StringBuffer，HashMap，他们都会在应用过程中动静判断是否空间短缺，而且基本上都采纳了先指数扩容，而后到肯定大小限度后才开始线性扩容的形式，Redis 也不例外，Redis 在 10241024 以内都是 2 倍的形式扩容，只有不超出 10241024 都是先额定申请 200% 的空间，但一旦总长度超过 10241024 字节，那每次最多只会扩容 10241024 字节。Redis 中 sds 扩容的代码是在 sdsMakeRoomFor()，能够看到很多字符串变更的 API 结尾都间接或者间接调用这个。和 Java 中 StringBuffer 扩容不同的是，Redis 这里还须要思考不同字符串长度时 sdshdr 类型的变动，具体代码如下：

// 扩充 sds 的理论可用空间，以便后续能拼接更多字符串。// 留神：这里理论不会扭转 sds 的长度，只是减少了更多可用的空间(buf) 
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK; // SDS_TYPE_MASK = 7 
    int hdrlen;

    /* 如果有足够的残余空间，间接返回 */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // 在未超出 SDS_MAX_PREALLOC 前，扩容都是按 2 倍的形式扩容，超出后只能递增 
    if (newlen < SDS_MAX_PREALLOC)  // SDS_MAX_PREALLOC = 1024*1024
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    type = sdsReqType(newlen);

    /*  在真正应用过程中不会用到 type5，如果遇到 type5 间接应用 type8*/
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);
    if (oldtype==type) {newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        // 扩容其实就是申请新的空间，而后把旧数据挪过来  
        newsh = s_malloc(hdrlen+newlen+1);
        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);
    }
    sdssetalloc(s, newlen);
    return s;
}

sds.c 还有很多源码我都没有贴到，其余代码实质上都是围绕 sdshdr 数据结构和各种字符串操作写的(基本上都是各种字符串新建、拼接、拷贝、扩容……)，只有晓得了 sds 的设计原理，置信你也能轻易写进去，这里我就列一下所有 sds 相干的 API，对源码有趣味的旁友能够移步到 src/sds.c，中文正文版的 API 列表见 src/sds.c

sds sdsnewlen(const void *init, size_t initlen);  // 新建一个容量为 initlen 的 sds
sds sdsnew(const char *init); // 新建 sds，字符串为 null，默认长度 0 
sds sdsempty(void);  // 新建空字符“”sds sdsdup(const sds s); // 依据 s 的理论长度创立新的 sds，目标是升高内存的占用
void sdsfree(sds s); // 开释 sds 
sds sdsgrowzero(sds s, size_t len); // 把 sds 增长到指定的长度，增长进去的新的空间用 0 填充 
sds sdscatlen(sds s, const void *t, size_t len); // 在 sds 上拼接字符串 t 的指定长度局部 
sds sdscat(sds s, const char *t);  // 把字符串 t 拼接到 sds 上 
sds sdscatsds(sds s, const sds t); // 把两个 sds 拼接在一起  
sds sdscpylen(sds s, const char *t, size_t len); //  把字符串 t 指定长度的局部拷贝到 sds 上 
sds sdscpy(sds s, const char *t); // 把字符串 t 拷贝到 sds 上 

sds sdscatvprintf(sds s, const char *fmt, va_list ap); // 把用 printf 格式化后的字符拼接到 sds 上 

sds sdscatfmt(sds s, char const *fmt, ...);   // 将多个参数格式化成一个字符串后拼接到 sds 上 
sds sdstrim(sds s, const char *cset);  // 在 sds 中移除结尾或者开端在 cset 中的字符  
void sdsrange(sds s, ssize_t start, ssize_t end);  // 截取 sds 的子串 
void sdsupdatelen(sds s); // 更新 sds 字符串的长度 
void sdsclear(sds s);  // 清空 sds 中的内容，但不开释空间 
int sdscmp(const sds s1, const sds s2);  // sds 字符串比拟大小 
sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count);
void sdsfreesplitres(sds *tokens, int count);
void sdstolower(sds s); // 字符串转小写
void sdstoupper(sds s);  // 字符串转大写
sds sdsfromlonglong(long long value);  // 把一个 long long 型的数转成 sds  
sds sdscatrepr(sds s, const char *p, size_t len); 
sds *sdssplitargs(const char *line, int *argc);
sds sdsmapchars(sds s, const char *from, const char *to, size_t setlen);
sds sdsjoin(char **argv, int argc, char *sep); // 把字符串数组按指定的分隔符拼接起来
sds sdsjoinsds(sds *argv, int argc, const char *sep, size_t seplen); // 把 sds 数组按指定的分隔符拼接起来

/* sds 底层 api */
sds sdsMakeRoomFor(sds s, size_t addlen);  // sds 扩容
void sdsIncrLen(sds s, ssize_t incr); // 扩容指定长度
sds sdsRemoveFreeSpace(sds s); // 开释 sds 占用的多余空间
size_t sdsAllocSize(sds s); // 返回 sds 总共占用的内存大小
void *sdsAllocPtr(sds s); // 返回 sds 理论的起始地位指针

void *sds_malloc(size_t size); // 为 sds 调配空间 
void *sds_realloc(void *ptr, size_t size); // 
void sds_free(void *ptr);  // 开释 sds 空间

回到开篇的几个问题，置信看完下面的内容后你都能答复上来了，如果答复不上来那就再多看两遍，本博客 + 源码搭配服用成果更佳。

为了管制博客篇幅，这里只解说了外围代码，很多 API 的源码我都没有贴上来(毕竟太多)，有趣味的同学能够再看下源码 https://github.com/xindoo/redis/。

本文是 Redis 源码分析系列博文，同时也有与之对应的 Redis 中文正文版，有想深刻学习 Redis 的同学，欢送 star 和关注。
Redis 中文注解版仓库：https://github.com/xindoo/redis
Redis 源码分析专栏：https://zxs.io/s/1h

关于java:Redis源码剖析之SDSSimple-Dynamic-String

sdshdr 数据结构

SDS 的应用

SDS 的扩容

罕用 API

结语