SDS(simple dynamic string)是redis提供的字符串的封装,在redis中也是存在最广泛的数据结构,它也是很多其他数据结构的基础,所以才选择先介绍SDS。 SDS也兼容部分C字符串API(strcmp,strlen),它如何兼容C字符串我觉得也是有个很sao的操作,等看完我这篇博客你就明白了。在开始正式内容前,我先抛几个问题(有些也是面试高频题),带着问题去学习也是一种非常好的学习方法。
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字符串末尾必须是 ,不计算在内) */
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] = '