Redis SDS相关的源码是什么

Redis中sds相关的源码都在src/sds.c 和src/sds.h中,其中sds.h中定义了所有SDS的api,当然也实现了部分几个api,比如sds长度、sds剩余可用空间……,不急着看代码,我们先看下sds的数据结构,看完后为什么代码那么写你就一目了然。

sdshdr数据结构

redis提供了sdshdr5 sdshdr8 sdshdr16 sdshdr32 sdshdr64这几种sds的实现,其中除了sdshdr5比较特殊外,其他几种sdshdr差不只在于两个字段的类型差别。以下是我举例说明的两个结构体 sdshdr8 和 sdshdr16 的定义。

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中SDS的源码实现原理

下一个问题,为什么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;

} SDS的使用

上面代码中我特意标注了一个注意,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的扩容

在做字符串拼接的时候,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;

} 常用API

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空间

Redis作为一款非常流行的键值数据库,在处理字符串类型的数据时,采用了一种叫做SDS的数据结构。那么,这个SDS的源码是什么呢?下面,我们一起来深入探讨。
一、SDS的数据结构介绍
SDS(Simple Dynamic String)是Redis中一种动态字符串类型的数据结构,这种结构类似于C语言中的char*类型。SDS结构中,既包含字符串长度,又包含字符数组,从而实现了高效的字符串操作。SDS的源码实现位于src/sds.c中。
二、SDS的源码实现原理
SDS的源码实现原理和C语言中的char*类型非常相似。源码中,将SDS看作一个结构体,其中包含字符串长度(len)和字符数组(buf)。在字符串增长时,可以调用sdsMakeRoomFor函数,来扩展buf可用空间,进而增加字符串可存储的长度。SDS还支持在字符串中间插入、删除、修改数据,这些操作都依赖于源码中对字符串长度、buf空间进行灵活管理的算法。
三、SDS的源码应用场景
因为SDS支持高效的字符串操作,Redis中大部分数据都采用了SDS结构存储,例如字符串键值类型字符串型(string)和哈希键值类型哈希型(hash)就都采用了SDS结构存储。
四、总结
SDS是Redis中一种高效的动态字符串存储结构,其源码实现原理非常灵活。通过深入理解SDS的源码实现,可以更好地掌握Redis中字符串的存储和操作技术,为自己的Redis应用场景提供更优秀的解决方案。