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));	// 3printf("%lu\n", strlen(strb));	// 5return 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 没法标识出剩余容量等,而空字符串接下来大概率要进行拼接操作,直接使用 SDS8if (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^5return 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;
#elsereturn 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 - lensize_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倍，否则新增 1Mif (newlen < SDS_MAX_PREALLOC)newlen *= 2;elsenewlen += 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 设置新的 allocsdssetalloc(s, newlen);return s;
}

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

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