redis 5.0.7 源码阅读——动态字符串sds

redis中动态字符串sds相关的文件为:sds.h与sds.c

一、数据结构

redis中定义了自己的数据类型"sds",用于描述 char*,与一些数据结构

1 typedef char *sds; 2  3 /* Note: sdshdr5 is never used, we just access the flags byte directly. 4  * However is here to document the layout of type 5 SDS strings. */ 5 struct __attribute__ ((__packed__)) sdshdr5 { 6     unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ 7     char buf[]; 8 }; 9 struct __attribute__ ((__packed__)) sdshdr8 {10     uint8_t len; /* used */11     uint8_t alloc; /* excluding the header and null terminator */12     unsigned char flags; /* 3 lsb of type, 5 unused bits */13     char buf[];14 };15 struct __attribute__ ((__packed__)) sdshdr16 {16     uint16_t len; /* used */17     uint16_t alloc; /* excluding the header and null terminator */18     unsigned char flags; /* 3 lsb of type, 5 unused bits */19     char buf[];20 };21 struct __attribute__ ((__packed__)) sdshdr32 {22     uint32_t len; /* used */23     uint32_t alloc; /* excluding the header and null terminator */24     unsigned char flags; /* 3 lsb of type, 5 unused bits */25     char buf[];26 };27 struct __attribute__ ((__packed__)) sdshdr64 {28     uint64_t len; /* used */29     uint64_t alloc; /* excluding the header and null terminator */30     unsigned char flags; /* 3 lsb of type, 5 unused bits */31     char buf[];32 };

定义结构体时,加上了 __attribute__ ((__packed__)) 关键字,用于取消字节对齐,使其按照紧凑排列的方式,占用内存。这样做的目的并不仅仅只是为了节约内存的使用。结构体最后有一个 char buf[],查了资料之后了解到,其只是定义一个数组符号,并没有任何成员,不占用结构体的内存空间,其真实地址紧随结构体之后,可实现变长结构体。由此可以只根据sds字符串的真实地址,取到sds结构体的任意成员变量数据。如flags:

1 void func(const sds s)2 {3     unsigned char flags = s[-1];      4 }

这个flags,从源码的注释上看,其低三位用于表示sds类型,高五位是当sds类型为sdshdr5时,表明字符串长度的。对于非sdshdr5的类型,有专门的成员变量描述当前已使用的长度,及总buffer长度。

sds类型:

1 #define SDS_TYPE_5  02 #define SDS_TYPE_8  13 #define SDS_TYPE_16 24 #define SDS_TYPE_32 35 #define SDS_TYPE_64 4

sds定义了两个宏,用于获取sds结构体首地址:

1 #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));2 #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

由此可见sds结构体的大致结构为:

1 /* 2 sdshdr5 3 +--------+----...---+ 4 |00011000|abc\0     | 5 +--------+----...---+ 6 |flags   |buf 7  8 sdshdr8 9 +--------+--------+--------+----...---+10 |00000011|00000011|00000001|abc\0     |11 +--------+--------+--------+----...---+12 |len     |alloc   |flags   |buf13 */

sds的一些常规操作,如获取字符串长度、获取剩余buf长度等,都是其于以上操作,首先根据sds字符串地址获取其flags的值,根据flags低三位判断sds类型,接着使用宏SDS_HDR_VAR或SDS_HDR进行操作。如:

1 #define SDS_TYPE_MASK 7   //0000,0111 2  3 static inline size_t sdslen(const sds s) { 4 //获取flags 5     unsigned char flags = s[-1]; 6 //根据flags低三位取类型,根据类型做不同处理 7     switch(flags&SDS_TYPE_MASK) { 8         case SDS_TYPE_5: 9             return SDS_TYPE_5_LEN(flags);10         case SDS_TYPE_8:11             return SDS_HDR(8,s)->len;12         case SDS_TYPE_16:13             return SDS_HDR(16,s)->len;14         case SDS_TYPE_32:15             return SDS_HDR(32,s)->len;16         case SDS_TYPE_64:17             return SDS_HDR(64,s)->len;18     }19     return 0;20 }

关于sds结构体中的len与alloc,len表示的是sds字符串的当前长度,alloc表示的是buf的总长度。

二、一些操作。

首先是一个根据字符串长度来决定sds类型的方法

1 static inline char sdsReqType(size_t string_size) { 2     if (string_size < 1<<5)    //flags高五位最大数字为 1<<5 - 1 3         return SDS_TYPE_5; 4     if (string_size < 1<<8)    //uint8_t 最大数字为 1<<8 - 1 5         return SDS_TYPE_8; 6     if (string_size < 1<<16)  //uint16_t 最大数字为 1<<16 - 1 7         return SDS_TYPE_16; 8 #if (LONG_MAX == LLONG_MAX)  //区分32位/64位系统 9     if (string_size < 1ll<<32)10         return SDS_TYPE_32;11     return SDS_TYPE_64;12 #else13     return SDS_TYPE_32;14 #endif15 }

创建一个新的sds结构体:

1 sds sdsnewlen(const void *init, size_t initlen) { 2     void *sh; 3     sds s; 4     char type = sdsReqType(initlen); 5     if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8; 6     int hdrlen = sdsHdrSize(type); 7     unsigned char *fp; /* flags pointer. */ 8  9     sh = s_malloc(hdrlen+initlen+1);10     if (init==SDS_NOINIT)11         init = NULL;12     else if (!init)13         memset(sh, 0, hdrlen+initlen+1);14     if (sh == NULL) return NULL;15     s = (char*)sh+hdrlen;16     fp = ((unsigned char*)s)-1;17     switch(type) {18         case SDS_TYPE_5: {19             *fp = type | (initlen << SDS_TYPE_BITS);20             break;21         }22         case SDS_TYPE_8: {23             SDS_HDR_VAR(8,s);24             sh->len = initlen;25             sh->alloc = initlen;26             *fp = type;27             break;28         }29         case SDS_TYPE_16: {30             //同SDS_TYPE_8,略31         }32         case SDS_TYPE_32: {33             //同SDS_TYPE_8,略34         }35         case SDS_TYPE_64: {36             //同SDS_TYPE_8,略37         }38     }39     if (initlen && init)40         memcpy(s, init, initlen);41     s[initlen] = '\0';42     return s;43 }

由外部指定初始字符串与初始长度。先根据长度获取sds类型,然后根据不同类型,可以获得实际需要的总内存空间大小(包括sds结构体长度)。值得注意的是,如果初始长度为0的情况下,若为SDS_TYPE_5,则会被强制转为SDS_TYPE_8。根据源码的注释,空串的定义,通常是为了向后追加内容。SDS_TYPE_5并不适合这种场景。分配完内存空间之后,设置好sds结构体的值,再把初始字符串拷至sds字符串的实际初始位置上(如果有),就可以了。

本方法做为最底层的sds字符串初始化接口,被其它接口所调用,如:

1 //空string 2 sds sdsempty(void) { 3     return sdsnewlen("",0); 4 } 5  6 //指定string 7 sds sdsnew(const char *init) { 8     size_t initlen = (init == NULL) ? 0 : strlen(init); 9     return sdsnewlen(init, initlen);10 }11 12 //从现有sds string拷贝13 sds sdsdup(const sds s) {14     return sdsnewlen(s, sdslen(s));15 }

sds的释放也不是简单地free sds字符串,同样,它要先找到sds结构体的首地址,再进行free:

1 void sdsfree(sds s) {2     if (s == NULL) return;3     s_free((char*)s-sdsHdrSize(s[-1]));4 }

做为一个变长字符串,与传统c字符串,最大的区别,是可以动态扩展,就像c++ stl里的变长数组 vector一样。sds的扩容有自己的机制:

1 sds sdsMakeRoomFor(sds s, size_t addlen) { 2     void *sh, *newsh; 3     size_t avail = sdsavail(s); 4     size_t len, newlen; 5     char type, oldtype = s[-1] & SDS_TYPE_MASK; 6     int hdrlen; 7  8     /* Return ASAP if there is enough space left. */ 9     if (avail >= addlen) return s;10 11     len = sdslen(s);12     sh = (char*)s-sdsHdrSize(oldtype);13     newlen = (len+addlen);14     if (newlen < SDS_MAX_PREALLOC)15         newlen *= 2;16     else17         newlen += SDS_MAX_PREALLOC;18 19     type = sdsReqType(newlen);20 21     /* Don't use type 5: the user is appending to the string and type 5 is22      * not able to remember empty space, so sdsMakeRoomFor() must be called23      * at every appending operation. */24     if (type == SDS_TYPE_5) type = SDS_TYPE_8;25 26     hdrlen = sdsHdrSize(type);27     if (oldtype==type) {28         newsh = s_realloc(sh, hdrlen+newlen+1);29         if (newsh == NULL) return NULL;30         s = (char*)newsh+hdrlen;31     } else {32         /* Since the header size changes, need to move the string forward,33          * and can't use realloc */34         newsh = s_malloc(hdrlen+newlen+1);35         if (newsh == NULL) return NULL;36         memcpy((char*)newsh+hdrlen, s, len+1);37         s_free(sh);38         s = (char*)newsh+hdrlen;39         s[-1] = type;40         sdssetlen(s, len);41     }42     sdssetalloc(s, newlen);43     return s;44 }

本方法用于扩容sds,并可以指定长度。首先其先取出了当前还空闲的buf长度,方法如下:

1 static inline size_t sdsavail(const sds s) { 2     unsigned char flags = s[-1]; 3     switch(flags&SDS_TYPE_MASK) { 4         case SDS_TYPE_5: { 5             return 0; 6         } 7         case SDS_TYPE_8: { 8             SDS_HDR_VAR(8,s); 9             return sh->alloc - sh->len;10         }11         case SDS_TYPE_16: {12             SDS_HDR_VAR(16,s);13             return sh->alloc - sh->len;14         }15         case SDS_TYPE_32: {16             SDS_HDR_VAR(32,s);17             return sh->alloc - sh->len;18         }19         case SDS_TYPE_64: {20             SDS_HDR_VAR(64,s);21             return sh->alloc - sh->len;22         }23     }24     return 0;25 }

若当前空闲的长度,比需要的长度大,则认为不用再额外分配空间,直接return。否则就启用扩容操作。

扩容时,先根据当前已使用的长度len与需要增加的长度addlen,算出一个初始新长度newlen,然后对其进行判断,若newlen大于1M,则在newlen的基础上,继续增加1M,否则直接翻倍。然后再根据newlen的最终大小,获取sds的新类型。此时,若类型依然为SDS_TYPE_5,也要强行修正为SDS_TYPE_8。因为SDS_TYPE_5类型并不知道当前空闲空间的大小。此时,若sds的新类型与原来相同,则只需要调用realloc重新分配一下空间即可。此方法会分配出一块新空间的同时,把原来空间的内容拷过去,并释放原有空间。而sds类型发生改变的时候,就需要手动新造一个新的sds了。扩容完成之后,需要修正一下当前已使用的空间len,与总buf大小 alloc。

扩容完成之后,或者是其它什么操作,如人工修改了sds字符串,并更新的len的情况下,会存在空闲空间太大的情况。此时如果想释放这部分空间,sds也提供了相应的操作:

1 sds sdsRemoveFreeSpace(sds s) { 2     void *sh, *newsh; 3     char type, oldtype = s[-1] & SDS_TYPE_MASK; 4     int hdrlen, oldhdrlen = sdsHdrSize(oldtype); 5     size_t len = sdslen(s); 6     size_t avail = sdsavail(s); 7     sh = (char*)s-oldhdrlen; 8  9     /* Return ASAP if there is no space left. */10     if (avail == 0) return s;11 12     /* Check what would be the minimum SDS header that is just good enough to13      * fit this string. */14     type = sdsReqType(len);15     hdrlen = sdsHdrSize(type);16 17     /* If the type is the same, or at least a large enough type is still18      * required, we just realloc(), letting the allocator to do the copy19      * only if really needed. Otherwise if the change is huge, we manually20      * reallocate the string to use the different header type. */21     if (oldtype==type || type > SDS_TYPE_8) {22         newsh = s_realloc(sh, oldhdrlen+len+1);23         if (newsh == NULL) return NULL;24         s = (char*)newsh+oldhdrlen;25     } else {26         newsh = s_malloc(hdrlen+len+1);27         if (newsh == NULL) return NULL;28         memcpy((char*)newsh+hdrlen, s, len+1);29         s_free(sh);30         s = (char*)newsh+hdrlen;31         s[-1] = type;32         sdssetlen(s, len);33     }34     sdssetalloc(s, len);35     return s;36 }

操作与扩容类似,同样是会根据sds类型是否发生变化 ,来决定是使用realloc还是重新造一个sds。

除此之外,sds还实现了一些转义、数据类型转换、一些类似c风格的字符串操作等。如:strcpy、strcat、strlen、strcmp等。只是其更加多样化,如sds的strcat实现,就可以支持类似printf的方式。如:

1 /* Like sdscatprintf() but gets va_list instead of being variadic. */ 2 sds sdscatvprintf(sds s, const char *fmt, va_list ap) { 3     va_list cpy; 4     char staticbuf[1024], *buf = staticbuf, *t; 5     size_t buflen = strlen(fmt)*2; 6  7     /* We try to start using a static buffer for speed. 8      * If not possible we revert to heap allocation. */ 9     if (buflen > sizeof(staticbuf)) {10         buf = s_malloc(buflen);11         if (buf == NULL) return NULL;12     } else {13         buflen = sizeof(staticbuf);14     }15 16     /* Try with buffers two times bigger every time we fail to17      * fit the string in the current buffer size. */18     while(1) {19         buf[buflen-2] = '\0';20         va_copy(cpy,ap);21         vsnprintf(buf, buflen, fmt, cpy);22         va_end(cpy);23         if (buf[buflen-2] != '\0') {24             if (buf != staticbuf) s_free(buf);25             buflen *= 2;26             buf = s_malloc(buflen);27             if (buf == NULL) return NULL;28             continue;29         }30         break;31     }32 33     /* Finally concat the obtained string to the SDS string and return it. */34     t = sdscat(s, buf);35     if (buf != staticbuf) s_free(buf);36     return t;37 }38 39 /* Append to the sds string 's' a string obtained using printf-alike format40  * specifier.41  *42  * After the call, the modified sds string is no longer valid and all the43  * references must be substituted with the new pointer returned by the call.44  *45  * Example:46  *47  * s = sdsnew("Sum is: ");48  * s = sdscatprintf(s,"%d+%d = %d",a,b,a+b).49  *50  * Often you need to create a string from scratch with the printf-alike51  * format. When this is the need, just use sdsempty() as the target string:52  *53  * s = sdscatprintf(sdsempty(), "... your format ...", args);54  */55 sds sdscatprintf(sds s, const char *fmt, ...) {56     va_list ap;57     char *t;58     va_start(ap, fmt);59     t = sdscatvprintf(s,fmt,ap);60     va_end(ap);61     return t;62 }

其它方法在此不再过多描述

三、sds相比c的标准库优势:

1、相比于c标准库,获取字符串的len复杂读从O(N)降低到O(1),sds结构中存储了字符串的长度,所以类似strlen(str)的操作不会成为redis的性能瓶颈。
2、在内存分配策略上,redis总是会尝试多分配一些空间,比如小于1MB的字符串,总是分配2倍内存空间,对于大于1MB的空间追加1MB冗余空间,这对于字符串操作(如strcat等)能减少重新内存分配的几率,提升运行性能。
3、SDS总是安全的,sds总是会自动追加字符串结尾符号’\0’,有效防止溢出发生。
4、惰性释放内存,改变原字符串时,标准库需要重新分配内存的复杂度为O(N),SDS最大为O(N),最优情况下无需重新分配内存空间。

redis 5.0.7 下载链接

http://download.redis.io/releases/redis-5.0.7.tar.gz

源码阅读顺序参考:

https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst

其它参考资料:

https://blog.csdn.net/zzuchengming/article/details/51840067

https://blog.csdn.net/junlon2006/article/details/101369299

(0)

相关推荐

  • (7条消息) C字符串 与 uint32类型互相转换

    字符串转换为 unsigned int 类型 /*将传入的字符串转换为无符号的的32位整形 *@param: str : 传入的字符串 *retval: The converted value.*/s ...

  • redis系列之------简单的动态字符串(SDS)

    前言 Redis 没有直接使用 C 语言传统的字符串表示(以空字符结尾的字符数组,以下简称 C 字符串), 而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的 ...

  • redis 5.0.7 源码阅读——双向链表

    redis中双向链表相关的文件为:adlist.h与adlist.c 一.数据结构 redis里定义的双向链表,与普通双向链表大致相同 单个节点: 1 typedef struct listNode ...

  • TelloPy-develop-0.7.0源码阅读.1

    最近我在反思,为什么我看了那么多书,为什么还是写不出大型的程序?我也很苦恼,我想了下.应该还是看的源码少的过,古人曾经说过熟读唐诗三百首,不会吟诗也会吟 .在读源码的选择上,我没有选择太复杂的开源库, ...

  • 一个超级实用的源码阅读小技巧

    在学习编程的路途漫漫,优秀的源码是非常珍贵的学习资源,阅读源码也是有效提高自己的一个好方法. 工欲善其事必先利其器: 我发现函数调用图可以让我们更加直观地了解到源码函数直接的调用和层次关系,提高阅读源 ...

  • MySQL 8.0.22 源码编译安装全过程

    墨墨导读: Mysql的8.0版本出来已经有一段时间了,近期研究下源码调试.整个编译过程越来越复杂了. 近期研究下源码调试,MySQL5.7版本源码安装还是比较简单的,有很多例子参考.所以这次选择My ...

  • spark源码阅读--shuffle过程分析 ShuffleManager(一)

    ShuffleManager(一) 本篇,我们来看一下spark内核中另一个重要的模块,Shuffle管理器ShuffleManager.shuffle可以说是分布式计算中最重要的一个概念了,数据的j ...

  • dubbo源码阅读之服务目录

    服务目录 服务目录对应的接口是Directory,这个接口里主要的方法是 List<Invoker<T>> list(Invocation invocation) throws ...

  • 手把手教学APK反编译实现源码阅读

    手把手教学APK反编译实现源码阅读

  • Vue2 源码阅读(三) 双向绑定原理

    Vue2 源码阅读(三) 双向绑定原理

  • Vue2.x 响应式部分源码阅读记录

    之前也用了一段时间Vue,对其用法也较为熟练了,但是对各种用法和各种api使用都是只知其然而不知其所以然.最近利用空闲时间尝试的去看看Vue的源码,以便更了解其具体原理实现,跟着学习学习. Proxy ...