Redis 源码分析-内部数据结构 SDS

Redis 源码分析-内部数据结构 SDS

我们都知道，Redis 是一个高性能的键值数据库，key 是 string，Value 有多种类型，Redis 是 C 语言编写的，C 语言里的字符串其实就是 char *，那 Redis 也是这样实现的吗？如果不是的话，Redis 为什么要单独设计数据结构来存储字符串呢？

传统字符串

在 C 语言的传统字符串里，判断字符串结束是通过末尾的 ‘\0’ 标记，这也意味着字符串里不能有该字符，否则会导致字符串提前结束，即二进制不安全。

#include <stdio.h>
#include <string.h>

int main () {
    char *stra = "red\0is";			
    char *strb = "redis\0";			
    printf("%lu\n", strlen(stra));	// 3
    printf("%lu\n", strlen(strb));	// 5
    return 0;
}

另外我们知道，Redis 如此盛行的一个原因就是，每秒10万级别的读写速率和丰富的数据结构类型，我们在存取字符串时，经常要获取长度（len）和进行拼接操作（append），在 C 语言里，这个操作需要遍历一边操作的字符串，即需要 O(N) 的复杂度，如果空间不足还需要分配新的空间，而 Redis 作为高性能的数据库中间件，肯定要对这种慢操作进行优化。操作时间复杂度高。

SDS

为了解决这样的问题，Redis 中的字符串采用了 SDS （simple dynamic string）简单动态字符串结构，其定义如下：

typedef char *sds;

// SDS 5 比较特殊
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};

// 除 SDS8、SDS16外，还有SDS32、SDS64
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; 			// 已经使用的空间
    uint8_t alloc; 			// 字符串数组可分配的最大空间，不包括最后的'\0'字符
    unsigned char flags; 	// 1字节,低3bit用来区分是哪一种SDS,高5bit暂未使用
    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[];
};

为什么会有这样的设计？

首先，字符串肯定也是有大小的，有的可能很短，有的可能很长，如果设置为统一的长度，对于短字符串来说太浪费了，所以 Redis 针对不同长度的字符串设置了不同的数据结构。

怎么解决传统字符串中的问题呢

1. 使用 len 字段直接标识当前字符串用了多少空间，那么用的时候直接读取这么多字节的数据就行了，自然不用关心中间出现的字符

2. 使用 len 字段和 alloc 字段，取消了获取字符串长度时的遍历操作，在追加时也可以根据 alloc 是否可以容纳 len + 新字符串的长度 来判断

有一些细节需要注意：

• 在 struct 结构体后，有 __attribute__ ((__packed__))的代码，它的意思是告诉编译器把结构体里的成员紧凑排列，原因是，sds *s 的这个指针，执行的其实是 char[] 的内容，如果紧凑排列，s-1 就是 flags 字段的内容，再取低 3bit 就知道当前 SDS 的类型了。
• 在各个header的定义中最后有一个char buf[]。我们注意到这是一个没有指明长度的字符数组，这是 C 语言中定义字符数组的一种特殊写法，称为柔性数组，只能定义在一个结构体的最后一个字段上。它在这里只是起到一个标记的作用，表示在 flags 字段后面就是一个字符数组，或者说，它指明了紧跟在 flags 字段后面的这个字符数组在结构体中的偏移位置。而程序在为header分配的内存的时候，它并不占用内存空间。如果计算 sizeof(struct sdshdr16) 的值，那么结果是 5个字节，其中没有 buf 字段。

看一下获取 SDS 长度的函数

#define SDS_TYPE_MASK 7

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

#define SDS_TYPE_BITS 3		// 给SDS5使用
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)	// SDS5的flags字段右移3位

static inline size_t sdslen(const sds s) {
    unsigned char flags = s[-1];
    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;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

flags & 7其实就是取 flags 低 3bit 的值，进而知道 SDS 的类型，接着传入该类型对应的标识，获取结构体里的 len 字段，SDS5则比较特殊，flags 字段既标识类型也标识长度。

那 SDS 的创建函数就很清晰了

/*
 * 创建新的字符串
 * mystring = sdsnewlen("abc",3);
 */
sds sdsnewlen(const void *init, size_t initlen) {
    void *sh;
    sds s;
    char type = sdsReqType(initlen);

    // 当前传的是空字符串,不要用 SDS5 类型,原因是 SDS5 没法标识出剩余容量等,而空字符串接下来大概率要进行拼接操作,直接使用 SDS8
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;

    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    // 新建 SDS 结构,并分配内存空间
    sh = s_malloc(hdrlen + initlen + 1);
    if (sh == NULL) return NULL;
    if (!init)
        memset(sh, 0, hdrlen + initlen + 1);

    s = (char *) sh + hdrlen;   // s 指向内部的 buf 字符串数组

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

    // 给字符串最后一位设置为 '\0',兼容 C 语言原生字符串
    s[initlen] = '\0';
    return s;
}

/* Create an empty (zero length) sds string. Even in this case the string
 * always has an implicit null term. */
sds sdsempty(void) {
    return sdsnewlen("", 0);
}

/* Create a new sds string starting from a null terminated C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

/* Duplicate an sds string. */
sds sdsdup(const sds s) {
    return sdsnewlen(s, sdslen(s));
}

/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char *) s - sdsHdrSize(s[-1]));
}

// 根据字符串长度大小,返回合适的字符串类型
static inline char sdsReqType(size_t string_size) {
    if (string_size < 1 << 5)		// string_size < (1 << 5) 即长度 < 2^5
        return SDS_TYPE_5;
    if (string_size < 1 << 8)
        return SDS_TYPE_8;
    if (string_size < 1 << 16)
        return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
    if (string_size < 1ll << 32)
        return SDS_TYPE_32;
    return SDS_TYPE_64;
#else
    return SDS_TYPE_32;
#endif
}

以上代码需要注意的点：

• 新建 SDS 时候，如果字符串长度为0，则选择 SDS8，而不是 SDS5，原因是空字符串接下来很可能进行追加操作，而 SDS5 类型不适合追加数据（会引发内存的重新分配）
• 新建 SDS 时候，存放数据的字符数组最后一位设置为了’\0’，这样可以兼容原生的 C 语言字符串
• alloc 初始化成了 initlen，alloc 不是最开始至今被分配为当前 SDS 类型的最大值（2⁸，2¹⁶），而是慢慢增加的

alloc 的变动具体可以参考字符串拼接，sdscatlen函数

// 字符串拼接函数,拼接中可能由于原类型长度不够导致重新分配空间,因此所有引用必须用调用返回的新指针来替换
// 参数为 要拼接的字符串 t,原字符串 s,t 字符串的长度 len
sds sdscatlen(sds s, const void *t, size_t len) {
    // 获取字符串现在的长度
    size_t curlen = sdslen(s);

    // 根据要追加的长度 len,和现有字符串 s 判断是否需要扩大
    s = sdsMakeRoomFor(s, len);
    if (s == NULL) return NULL;

    // 将要追加的字符串 t 追加到 s 后面
    memcpy(s + curlen, t, len);

    // 给 sds 设置最新的长度
    sdssetlen(s, curlen + len);

    // 末尾设置为 '\0'
    s[curlen + len] = '\0';
    return s;
}

关键步骤就是在 sdsMakeRoomFor 函数

sds sdsMakeRoomFor(sds s, size_t addlen) {
    void *sh, *newsh;

    // 获取该 SDS 的剩余容量  alloc - len
    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);

    // 新的长度少于 1024 * 1024,扩大为该值的2倍，否则新增 1M
    if (newlen < SDS_MAX_PREALLOC)
        newlen *= 2;
    else
        newlen += SDS_MAX_PREALLOC;

    // 获取新长度对应的 SDS 类型
    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. */
    // 不要使用 SDS5，追加会重新内存分配，不友好
    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);
    }

    // 给新的 SDS 设置新的 alloc
    sdssetalloc(s, newlen);
    return s;
}

Redis 通过 SDS 这样的数据结构设计，达到了二进制安全（‘\0结尾问题’）、操作高效（保存长度、容量等信息，获取时无需再次遍历）、节省内存（使用紧凑的内存分配方式）的效果。

注意，即使 Redis 的 Value 是字符串，也不是直接用 SDS 存储的，Redis 中有一个数据类型 RedisObject ，所有的 Value 都是这个类型，其中有一个指针，执行具体的实现，即 SDS、Dict、ZipList 等。Redis 的 key 是 SDS 类型。