Redis内部数据结构SDS详解

Redis内部数据结构SDS详解

前言

Redis是使用C写的，而C中根本不存在string,list,hash，set和zset这些数据类型，那么C是如何将这些数据类型实现出来的呢?我们从该篇开始，就要开始分析源码啦??。

API使用

我们这篇来学习string的底层实现，首先看下API的简单应用，设置str1变量为helloworld，然后我们使用debug object +变量名的方式看下，注意标红的编码为embstr。

如果我们将str2设置为helloworldhelloworldhelloworldhelloworldhell，字符长度为44，再使用下debug object+变量名的方式看下，注意标红的编码为embstr。

但是当我们设置为helloworldhelloworldhelloworldhelloworldhello，字符长度为45，再使用debug object+变量名的方式看下，注意标红的编码为raw。

最后我们将str3设置为整数100，再使用debug object+变量名的方式看下，注意标红的编码为int。

所以Redis的string类型一共有三种存储方式，当字符串长度小于等于44，底层采用embstr;当字符串长度大于44，底层采用raw;当设置是整数，底层则采用int。

embstr和raw的区别

所有类型的数据结构最外层都是RedisObject，这部分会说，先这样大致了解下，因为这篇的重点不在这。如果字符串小于等于44，实际的数据和RedisObject在内存中地址相邻，如下图。

如果字符串大于44，实际的数据和RedisObject在内存中地址不相邻，如下图。

再次强调，这些不重要，以后会讲，现在提下，只是为了能让Redis的String类型有个大致了解，先从整体把握。我们今天要说的其实是实际的数据，即上图指针指向的位置??。

SDSHdr的定义

其实的数据并不是直接存储，也有封装，看下面的代码就知道分为五种，分别是sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。sdshdr5和另外四种的区别比较明显，sdshrd5其实对内存空间的更加节约。其他四种乍一看都差不多，包括已用长度len，总长度alloc，标记flags(感觉没啥用，要是有知道的小伙伴，欢迎指教)，实际数据buf。

//定义五种不同的结构体，sdshdr5,sdshdr8, sdshdr16,sdshdr32,sdshdr64 struct __attribute__ ((__packed__)) sdshdr5 {     unsigned char flags; // 8位的标记     char buf[];//实际数据的指针 }; struct __attribute__ ((__packed__)) sdshdr8 {     uint8_t len; /* 已使用长度 */     uint8_t alloc; /* 总长度*/     unsigned char flags;     char buf[]; }; struct __attribute__ ((__packed__)) sdshdr16 {     uint16_t len;     uint16_t alloc;     unsigned char flags;     char buf[]; }; struct __attribute__ ((__packed__)) sdshdr32 {     uint32_t len;     uint32_t alloc;     unsigned char flags;     char buf[]; }; struct __attribute__ ((__packed__)) sdshdr64 {     uint64_t len;     uint64_t alloc;     unsigned char flags;     char buf[]; };

SDS具体逻辑图

假设我们设置某个字符串为hello，那么他SDS的可用长度len为8，已用长度len为6，如下图。注意：Redis会根据具体的字符长度，选择相应的sdshdr，但是各个类型都差不多，所以下图加简单画了。

SDS的优势

我们可以看到是对字符数组的再封装，但是为什么呢，直接使用字符数组不是更简单吗?这要从C和Java语言的根本区别说起。

更快速的获取字符串长度

我们都知道Java的字符串有提供length方法，列表有提供size方法，我们可以直接获取大小。但是C却不一样，更偏向底层实现，所以没有直接的方法使用。这样就带来一个问题，如果我们想要获取某个数组的长度，就只能从头开始遍历，当遇到第一个'\0'则表示该数组结束。这样的速度太慢了，不能每次因为要获取长度就变量数组。所以设计了SDS数据结构，在原来的字符数组外面增加总长度，和已用长度，这样每次直接获取已用长度即可。复杂度为O(1)。

数据安全，不会截断

如果传统字符串保存图片，视频等二进制文件，中间可能出现'\0'，如果按照原来的逻辑，会造成数据丢失。所以可以用已用长度来表示是否字符数组已结束。

SDS关键代码分析

获取常见值(抽象出常见方法)

在sds.h中写了一些常见方法，比如计算sds的长度(即sdshdr的len)，计算sds的空闲长度(即sdshdr的可用长度alloc-已用长度len)，计算sds的可用长度(即sdshdr的alloc)等等。但是大家有没有疑问，这不是一行代码搞定的事吗，为啥要抽象出方法呢?那么问题在于在上面，我们有将sdshdr分为五种类型，分别是sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64。那么我们在实际使用的时候，想要区分当前是哪个类型，并取其相应字段或设置相应字段。

//计算sds对应的字符串长度，其实上取得是字符串所对应的哪种sdshdr的len值 static inline size_t sdslen(const sds s) {     // 柔性数组不占空间，所以倒数第二位的是flags     unsigned char flags = s[-1];     //flags与上面定义的宏变量7做位运算     switch(flags&SDS_TYPE_MASK) {         case SDS_TYPE_5://0             return SDS_TYPE_5_LEN(flags);         case SDS_TYPE_8://1             return SDS_HDR(8,s)->len;//取上面结构体sdshdr8的len         case SDS_TYPE_16://2             return SDS_HDR(16,s)->len;         case SDS_TYPE_32://3             return SDS_HDR(32,s)->len;         case SDS_TYPE_64://5             return SDS_HDR(64,s)->len;     }     return 0; } //计算sds对应的空余长度，其实上是alloc-len 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;         }         case SDS_TYPE_16: {             SDS_HDR_VAR(16,s);             return sh->alloc - sh->len;         }         case SDS_TYPE_32: {             SDS_HDR_VAR(32,s);             return sh->alloc - sh->len;         }         case SDS_TYPE_64: {             SDS_HDR_VAR(64,s);             return sh->alloc - sh->len;         }     }     return 0; } //设置sdshdr的len static inline void sdssetlen(sds s, size_t newlen) {     unsigned char flags = s[-1];     switch(flags&SDS_TYPE_MASK) {         case SDS_TYPE_5:             {                 unsigned char *fp = ((unsigned char*)s)-1;                 *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);             }             break;         case SDS_TYPE_8:             SDS_HDR(8,s)->len = newlen;             break;         case SDS_TYPE_16:             SDS_HDR(16,s)->len = newlen;             break;         case SDS_TYPE_32:             SDS_HDR(32,s)->len = newlen;             break;         case SDS_TYPE_64:             SDS_HDR(64,s)->len = newlen;             break;     } } //给sdshdr的len添加多少大小 static inline void sdsinclen(sds s, size_t inc) {     unsigned char flags = s[-1];     switch(flags&SDS_TYPE_MASK) {         case SDS_TYPE_5:             {                 unsigned char *fp = ((unsigned char*)s)-1;                 unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;                 *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);             }             break;         case SDS_TYPE_8:             SDS_HDR(8,s)->len += inc;             break;         case SDS_TYPE_16:             SDS_HDR(16,s)->len += inc;             break;         case SDS_TYPE_32:             SDS_HDR(32,s)->len += inc;             break;         case SDS_TYPE_64:             SDS_HDR(64,s)->len += inc;             break;     } } //获取sdshdr的总长度 static inline size_t sdsalloc(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)->alloc;         case SDS_TYPE_16:             return SDS_HDR(16,s)->alloc;         case SDS_TYPE_32:             return SDS_HDR(32,s)->alloc;         case SDS_TYPE_64:             return SDS_HDR(64,s)->alloc;     }     return 0; } //设置sdshdr的总长度 static inline void sdssetalloc(sds s, size_t newlen) {     unsigned char flags = s[-1];     switch(flags&SDS_TYPE_MASK) {         case SDS_TYPE_5:             /* Nothing to do, this type has no total allocation info. */             break;         case SDS_TYPE_8:             SDS_HDR(8,s)->alloc = newlen;             break;         case SDS_TYPE_16:             SDS_HDR(16,s)->alloc = newlen;             break;         case SDS_TYPE_32:             SDS_HDR(32,s)->alloc = newlen;             break;         case SDS_TYPE_64:             SDS_HDR(64,s)->alloc = newlen;             break;     } }

创建对象

我们通过sdsnew方法来创建对象，显示通过判断init是否为空来确定初始大小，接着调用方法sdsnew(这边方法名一样，但是参数不一样，其为方法的重载)，先根据长度确定类型(上面有提过五种类型，不记得的可以往上翻)，然后根据类型分配相应的内存资源，最后追加C语言的结尾符'\0'。

sds sdsnew(const char *init) {     size_t initlen = (init == NULL) ? 0 : strlen(init);     return sdsnewlen(init, initlen); }  sds sdsnewlen(const void *init, size_t initlen) {     void *sh;     sds s;     char type = sdsReqType(initlen);//根据长度确定类型     /*空字符串，用sdshdr8，这边是经验写法，当想构造空串是为了放入超过32长度的字符串 */     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 (!init)         memset(sh, 0, hdrlen+initlen+1);     if (sh == NULL) return NULL;     s = (char*)sh+hdrlen;     fp = ((unsigned char*)s)-1;     //根据不同的类型，创建不同结构体，调用SDS_HDR_VAR函数     //为不同的结构体赋值,如已用长度len,总长度alloc     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'     s[initlen] = '\0';     return s; }  //根据实际字符长度确定类型 static inline char sdsReqType(size_t string_size) {     if (string_size < 1<<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; #endif     return SDS_TYPE_64; }

删除

String类型的删除并不是直接回收内存，而是修改字符，让其为空字符，这其实是惰性释放，等待将来使用。在调用sdsempty方法时，再次调用上面的sdsnewlen方法。

/*修改sds字符串使其为空（零长度）。  *但是，所有现有缓冲区不会被丢弃，而是设置为可用空间  *这样，下一个append操作将不需要分配到  *当要缩短SDS保存的字符串时，程序并不立即使用内存充分配来回收缩短后多出来的字节，并等待将来使用。*/ void sdsclear(sds s) {     sdssetlen(s, 0);     s[0] = '\0'; }  sds sdsempty(void) {     return sdsnewlen("",0); }

添加字符(扩容)重点!!!

添加字符串，sdscat输入参数为sds和字符串t，首先调用sdsMakeRoomFor扩容方法，再追加新的字符串，最后添加上结尾符'\0'。我们来看下扩容方法里面是如何实现的?第一步先调用常见方法中的sdsavail方法，获取还剩多少空闲空间。如果空闲空间大于要添加的字符串t的长度，则直接返回，不想要扩容。如果空闲空间不够，则想要扩容。第二步判断想要扩容多大，这边有分情况，如果目前的字符串小于1M，则直接扩容双倍，如果目前的字符串大于1M，则直接添加1M。第三个判断添加字符串之后的数据类型还是否和原来的一致，如果一致，则没啥事。如果不一致，则想要新建一个sdshdr，把现有的数据都挪过去。

这样是不是有点抽象，举个例子，现在str的字符串为hello，目前是sdshdr8，总长度50，已用6，空闲44。现在想要添加长度为50的字符t，第一步想要看下是否要扩容，50明显大于44，需要扩容。第二步扩容多少，str的长度小于1M，所以扩容双倍，新的长度为50*2=100。第三步50+50所对应sdshdr类型还是sdshdr8吗?明显还是sdshdr8，所以不要数据迁移，还在原来的基础上添加t即可。

sds sdscat(sds s, const char *t) {     return sdscatlen(s, t, strlen(t)); }  sds sdscatlen(sds s, const void *t, size_t len) {     //调用sds.h里面的sdslen，即取已用长度     size_t curlen = sdslen(s);     //扩容方法     s = sdsMakeRoomFor(s,len);     if (s == NULL) return NULL;     memcpy(s+curlen, t, len);     sdssetlen(s, curlen+len);     s[curlen+len] = '\0';     return s; }  sds sdsMakeRoomFor(sds s, size_t addlen) {     void *sh, *newsh;     //调用sds.h，获取空闲长度alloc     size_t avail = sdsavail(s);     size_t len, newlen;     char type, oldtype = s[-1] & SDS_TYPE_MASK;     int hdrlen;     //空闲长度大于需要增加的，不需要扩容，直接返回     if (avail >= addlen) return s;  //调用sds.h里面的sdslen，即取可用长度     len = sdslen(s);      sh = (char*)s-sdsHdrSize(oldtype);     //len加上要添加的大小     newlen = (len+addlen);      //#define SDS_MAX_PREALLOC (1024*1024)     //当新长度小于 1024*1024，直接扩容两倍     if (newlen < SDS_MAX_PREALLOC)         newlen *= 2;     else //当新长度大于 1024*1024，加2014*1024         newlen += SDS_MAX_PREALLOC;  //根据长度计算新的类型     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. */     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; }  //计算不同类型的结构体的大小 static inline int sdsHdrSize(char type) {     switch(type&SDS_TYPE_MASK) {         case SDS_TYPE_5:             return sizeof(struct sdshdr5);         case SDS_TYPE_8:             return sizeof(struct sdshdr8);         case SDS_TYPE_16:             return sizeof(struct sdshdr16);         case SDS_TYPE_32:             return sizeof(struct sdshdr32);         case SDS_TYPE_64:             return sizeof(struct sdshdr64);     }     return 0; }

总结

该篇主要讲了Redis的底层实现SDS，包括SDS是什么，与传统的C语言相比的优势，具体的逻辑图，常见的方法(包括创建，删除，扩容等)。同时也知道了Redis的embstr和raw的区别。

如果觉得写得还行，麻烦给个赞??，您的认可才是我写作的动力!

如果觉得有说的不对的地方，欢迎评论指出。

好了，拜拜咯。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。