Redis源码解析-基础数据-sds(simple dynamic string)

太长不看版

• redis内部使用sds(其实就是在字符串前边加了额外的信息(sdshdr))作为默认字符串类型
• sdshdr中len字段记录了字符串长度，可以常数复杂度获取长度
• sds使用sdshdr中的len字段来判断字符串是否结束，实现了二进制安全
• 修改sds时会按需分配内存大小，杜绝缓冲区溢出
• sds空间扩展时会进行预申请，减少内存分配次数 预申请策略: 1M以内, 每次为len * 2，超过1M每次为 len + 1M
• sds支持部分c语言标准库的里的字符串操作函数(因为末尾特意加了'\0')

本篇解析基于redis 5.0.0版本，涉及源码文件为sds.c与sds.h。

redis内部实现中没有直接使用c语言中原始的字符串(字符数组)，而是对原始字符串进行了封装，使用名为sds(simple dynamic string)的抽象类型作为默认字符串类型。

sds定义:

// sds定义
typedef char *sds;

// sds的创建函数
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);
    // ...
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */
    // 申请内存为 头部信息长度 + 字符串长度 + 1
    // sh 指向整体数据开头
    sh = s_malloc(hdrlen+initlen+1);
    // ...
    // s实际类型为char* 指向原始字符串开头
    s = (char*)sh+hdrlen;
    fp = ((unsigned char*)s)-1;
    switch(type) {
        // ...
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        // ...
    if (initlen && init)
        memcpy(s, init, initlen);
    // 此处末尾加上'\0'是为了能够使用标准库里的一些操作函数
    s[initlen] = '\0';
    // 注意，此处返回的是指向原始字符串开始的指针
    return s;
}

从上述定义可以看到，sds实际上是对char*的重定义。而从创建函数的操作可以看到，sds实际上就是在原始字符串的前边加上了一些头部信息。 举个例子:

sds 字符串 hello的数据结构(使用sdshdr8):

头部信息(sdshdr)	字符串	\0
len(4) alloc(8) flags(1)	h e l l o	\0

而初始化函数返回的以及代码中使用的是指向原始字符串的指针，所以经常会在代码里看到s[-1](*(s - 1的语法糖))这种操作来取头部类型flags字段。

而获取字符串头部信息则是用s指针前移至头部信息开始来获取，定义如下:

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

看完了sds的定义，我们再来看看提了半天的头部信息结构到底是怎样的。

sds头部信息(sdshdr)定义

/* 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 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    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[];
};

sds的头部信息一共有5个，根据长度选取对应的类型。 其中sdshdr5因为没有空间存储alloc字段(长度信息和字符串信息存在一起)，所以只用于不存在变更需求的短字符(小于32字节)中，比如小于32字节的键值。具体详情戳这里， 而attribute ((packed))则是为了告诉gcc取消优化对齐。 例如：

struct sdshdr {char flag; int  len;};
//sizeof(sdshdr_test) == 8;
struct attribute ((packed)) sdshdr {char flag; int  len;}; 
//sizeof(sdshdr_test) == 5;

以上的操作归根结底都是为了减少head的实际长度。戳这里了解详情 概括一下sds头部信息定义(实际上初版的sds头部信息定义就是这样的)：

struct sdshdr {
    unsigned int len; /* 字符串长度 */
    unsigned int alloc; /* 实际分配内存长度 */
    unsigned char flags; /* sds类型 */
    char buf[]; /* 实际的数据 */
};

开始我们说了, sds和原始的字符串信息区别就是加了上述的这些头部信息。那么接下来我们再来看看费了这么多劲加这些额外的信息有什么用？

sdshdr的引入解决了什么问题

1. 二进制安全

维基百科: Binary-safe is a computer programming term mainly used in connection with string manipulating functions.A binary-safe function is essentially one that treats its input as a raw stream of data without any specific format. It should thus work with all 256 possible values that a character can take (assuming 8-bit characters).   二进制安全是一种主要用于字符串操作函数相关的计算机编程术语。一个二进制安全功能（函数），其本质上将操作输入作为原始的、无任何特殊格式意义的数据流。其在操作上应包含一个字符所能有的256种可能的值（假设为8为字符）

众所周知，c语言中使用字符数组作为字符串实现，使用'\0'表示结尾，因为'\0'这个‘魔数’的存在，使得c语言原始的字符串是不符合二进制安全的。

sds使用sdshdr中的len字段来判断字符串是否结束，实现二进制安全(二进制中包含\0,原生字符串会截断)。

2. 缓冲区溢出

缓冲区溢出指当某个数据超过了处理程序限制的范围时，程序出现的异常操作。

c语言中字符串处理，字符串指针对应的内存都是由编码者自己控制，保证已经分配了足够多的内存。 然而一旦当分配的内存不足，就出现缓存区溢出。 sds的修改函数在执行修改前会进行判断内存，动态的分配内存，杜绝缓冲区溢出的可能。 例如sds拷贝函数：

/* Destructively modify the sds string 's' to hold the specified binary
 * safe string pointed by 't' of length 'len' bytes. */
sds sdscpylen(sds s, const char *t, size_t len) {
    //如果目标sds已分配的内存长度小于需要拷贝的长度
    if (sdsalloc(s) < len) {
        //则进行内存重新分配
        s = sdsMakeRoomFor(s,len-sdslen(s));
        if (s == NULL) return NULL;
    }
    memcpy(s, t, len);
    //字符串尾部加上'\0',是为了可以使用部分标准库函数，减少工作量
    s[len] = '\0';
    sdssetlen(s, len);
    return s;
}

3. 频繁的内存分配

C字符串如果一直使用与长度匹配的内存，会导致每次字符串长度变化时，就必须进行内存的重新分配。内存重分配设计复杂算法，同时可能执行系统调用，会很耗时。对于redis作为一个内存数据库，势必会面对数据频繁改变的场景，所以如果使用原生的字符串数据，会引发频繁的内存重分配，这个显然是不可接受的。 所以sds每次内存分配时，会通过内存的预申请减少因为修改字符串而引发的内存重分配次数。具体策略是1M(1024 * 1024)以内，每次len * 2, 超过1M每次 len + 1M 。

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;
    //当前sds可用的内存长度,申请的 - 已用的
    size_t avail = sdsavail(s);
    size_t len, newlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;
    int hdrlen;

    /* Return ASAP if there is enough space left. */
    if (avail >= addlen) return s;

    len = sdslen(s);
    sh = (char*)s-sdsHdrSize(oldtype);
    newlen = (len+addlen);
    // #define SDS_MAX_PREALLOC (1024*1024)
    if (newlen < SDS_MAX_PREALLOC)
        // 小于1m, 实际申请内存长度为当前申请的2倍
        newlen *= 2;
    else
        // 大于1m, 实际申请内存长度为当前申请 + 1m
        newlen += SDS_MAX_PREALLOC;

    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);
    if (oldtype==type) {
        newsh = s_realloc(sh, hdrlen+newlen+1);
        if (newsh == NULL) return NULL;
        s = (char*)newsh+hdrlen;
    } else {
        /* Since the header size changes, need to move the string forward,
         * and can't use realloc */
        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;
}

4. O(n)复杂度的长度获取

原生的c语言字符串，获取长度需要遍历字符串直到遇到'\0',需要O(n)复杂度的操作。 sds头部信息中len字段记录了字符串长度，可以常数复杂度获取长度。

static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                // sdshdr5 没有len字段，所以长度信息和头部信息类型放在一起
                unsigned char *fp = ((unsigned char*)s)-1;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
 * end of the specified sds string 's'.
 *
 * After the call, the passed sds string is no longer valid and all the
 * references must be substituted with the new pointer returned by the call. */
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;
}