Redis源码剖析之SDS

迈不过友情╰ 2022-05-19 07:40 438阅读 0赞

#

以下涉及到的源码均为redis5.0-rc3版本的代码【点击查看官方源码】

文章目录

    • SDS简介
    • SDS数据结构
    • SDS特点
    • SDS操作函数

SDS简介

简单动态字符串(simple dynamic string)，是redis底层为字符串而设计的一种数据结构，是针对C字符串的一个改良版。凡是涉及到需要修改的字符串均采用sds来存储，而非C字符串。

SDS数据结构

如下是sds数据结构的定义（sds.h头文件中）：

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

从以上源码中可看见，redis针对C中类型长度的不同定义了5中结构：sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，其中sdshdr5已经不再使用了（由源码中注释得知-“sdshdr5 is never used, we just access the flags byte directly”）。下面给出结构示意图：
这里写图片描述
其中：

  • len：已使用的空间；
  • alloc：除了空符号和结构头部之外所有的已分配空间，即真正为字符串分配的空间；
  • flags：结构类型
  • buf[]：存字符串的空间；

以sdshdr16结构的字符串“string”为例，如下所示：
这里写图片描述
总共占用17（4+4+1+6+1+1）个字节，这里的flags为何为2将在后续进行说明。

SDS特点

  1. 能以O(1)的复杂度获取字符串的长度（len）以及剩余的未使用空间情况（alloc-len：此将对空间的分配和释放有重大影响）。
  2. 保留了C字符串的空字符‘\0’，这样就可以是的sds能无影响的使用部分的C字符串操作函数。
  3. 在空间分配方面，采用结构类（java的集合）常用的预分配策略。而sds的分配策略是当前空间小于1M时则变成当前空间的两倍，否则直接再分配1M。
  4. 在空间回收方面，sds不会立即释放，而是先保留，防止后续在空间不足的情况下再次分配带来的代价。
  5. 相比C字符串而言，sds是二进制安全的，因为sds识别整个字符串是通过len来判断，并不是同C而言是通过空字符结尾来判断。

SDS操作函数

这里只列出部分函数。
在列出操作函数之前，首先给出如下的宏定义：

  1. //定义结构类型
  2. #define SDS_TYPE_5  0 
  3. #define SDS_TYPE_8  1
  4. #define SDS_TYPE_16 2
  5. #define SDS_TYPE_32 3
  6. #define SDS_TYPE_64 4
  7. //定义结构类型的掩码
  8. #define SDS_TYPE_MASK 7
  9. #define SDS_TYPE_BITS 3
  10. //获取header指针
  11. #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
  12. #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
  13. //sdshdr5类型的len
  14. #define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

接下来是6个静态内联函数。在看它们之前，需要先说明一下sds结构中的flags，前面说了它是代表结构的类型，那么它又是怎样来表明的呢？首先已知sds字符串s，那么根据内存分布情况就可以得到flags的值为s[-1], 在将其与宏定义的类型掩码进行与运算便得出类型值，如此便可以知道一个sds究竟使用的是哪儿种类型进行存储的了。

获取len的方法：

  1. static inline size_t sdslen(const sds s) {
  2.     unsigned char flags = s[-1];
  3.     switch(flags&SDS_TYPE_MASK) {
  4.         case SDS_TYPE_5:
  5.             return SDS_TYPE_5_LEN(flags);
  6.         case SDS_TYPE_8:
  7.             return SDS_HDR(8,s)->len;
  8.         case SDS_TYPE_16:
  9.             return SDS_HDR(16,s)->len;
  10.         case SDS_TYPE_32:
  11.             return SDS_HDR(32,s)->len;
  12.         case SDS_TYPE_64:
  13.             return SDS_HDR(64,s)->len;
  14.     }
  15.     return 0;
  16. }

获取free空间（即未被使用的空间）的方法：

  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. }

对len的值进行重计算：

  1. //直接进行赋值设置
  2. static inline void sdssetlen(sds s, size_t newlen) {
  3.     unsigned char flags = s[-1];
  4.     switch(flags&SDS_TYPE_MASK) {
  5.         case SDS_TYPE_5:
  6.             {
  7.                 unsigned char *fp = ((unsigned char*)s)-1;
  8.                 *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
  9.             }
  10.             break;
  11.         case SDS_TYPE_8:
  12.             SDS_HDR(8,s)->len = newlen;
  13.             break;
  14.         case SDS_TYPE_16:
  15.             SDS_HDR(16,s)->len = newlen;
  16.             break;
  17.         case SDS_TYPE_32:
  18.             SDS_HDR(32,s)->len = newlen;
  19.             break;
  20.         case SDS_TYPE_64:
  21.             SDS_HDR(64,s)->len = newlen;
  22.             break;
  23.     }
  24. }
  26. //相加改变len值
  27. static inline void sdsinclen(sds s, size_t inc) {
  28.     unsigned char flags = s[-1];
  29.     switch(flags&SDS_TYPE_MASK) {
  30.         case SDS_TYPE_5:
  31.             {
  32.                 unsigned char *fp = ((unsigned char*)s)-1;
  33.                 unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
  34.                 *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
  35.             }
  36.             break;
  37.         case SDS_TYPE_8:
  38.             SDS_HDR(8,s)->len += inc;
  39.             break;
  40.         case SDS_TYPE_16:
  41.             SDS_HDR(16,s)->len += inc;
  42.             break;
  43.         case SDS_TYPE_32:
  44.             SDS_HDR(32,s)->len += inc;
  45.             break;
  46.         case SDS_TYPE_64:
  47.             SDS_HDR(64,s)->len += inc;
  48.             break;
  49.     }
  50. }

获取sds字符串总共分配的空间：

  1. /* sdsalloc() = sdsavail() + sdslen() */
  2. static inline size_t sdsalloc(const sds s) {
  3.     unsigned char flags = s[-1];
  4.     switch(flags&SDS_TYPE_MASK) {
  5.         case SDS_TYPE_5:
  6.             return SDS_TYPE_5_LEN(flags);
  7.         case SDS_TYPE_8:
  8.             return SDS_HDR(8,s)->alloc;
  9.         case SDS_TYPE_16:
  10.             return SDS_HDR(16,s)->alloc;
  11.         case SDS_TYPE_32:
  12.             return SDS_HDR(32,s)->alloc;
  13.         case SDS_TYPE_64:
  14.             return SDS_HDR(64,s)->alloc;
  15.     }
  16.     return 0;
  17. }

重新设置alloc值：

  1. static inline void sdssetalloc(sds s, size_t newlen) {
  2.     unsigned char flags = s[-1];
  3.     switch(flags&SDS_TYPE_MASK) {
  4.         case SDS_TYPE_5:
  5.             /* Nothing to do, this type has no total allocation info. */
  6.             break;
  7.         case SDS_TYPE_8:
  8.             SDS_HDR(8,s)->alloc = newlen;
  9.             break;
  10.         case SDS_TYPE_16:
  11.             SDS_HDR(16,s)->alloc = newlen;
  12.             break;
  13.         case SDS_TYPE_32:
  14.             SDS_HDR(32,s)->alloc = newlen;
  15.             break;
  16.         case SDS_TYPE_64:
  17.             SDS_HDR(64,s)->alloc = newlen;
  18.             break;
  19.     }
  20. }

sds空间分配和释放相关的两个函数如下所示：

  1. //sds最大空间预分配值（在头文件中顶定义）
  2. #define SDS_MAX_PREALLOC (1024*1024)
  5. /* Enlarge the free space at the end of the sds string so that the caller
  6.  * is sure that after calling this function can overwrite up to addlen
  7.  * bytes after the end of the string, plus one more byte for nul term.
  8.  *
  9.  * Note: this does not change the *length* of the sds string as returned
  10.  * by sdslen(), but only the free buffer space we have. */
  11. sds sdsMakeRoomFor(sds s, size_t addlen) {
  12.     void *sh, *newsh;
  13.     size_t avail = sdsavail(s);
  14.     size_t len, newlen;
  15.     char type, oldtype = s[-1] & SDS_TYPE_MASK;
  16.     int hdrlen;
  18.     /* Return ASAP if there is enough space left. */
  19.     if (avail >= addlen) return s;
  21.     //如果可用空间不足的情况下，进行空间增加
  22.     len = sdslen(s);
  23.     sh = (char*)s-sdsHdrSize(oldtype);
  24.     newlen = (len+addlen);
  25.     if (newlen < SDS_MAX_PREALLOC)
  26.         //小于1M直接变为原来的2倍
  27.         newlen *= 2;
  28.     else
  29.         //大于1M的情况，累加1M
  30.         newlen += SDS_MAX_PREALLOC;
  32.     type = sdsReqType(newlen);
  34.     /* Don't use type 5: the user is appending to the string and type 5 is
  35.      * not able to remember empty space, so sdsMakeRoomFor() must be called
  36.      * at every appending operation. */
  37.     if (type == SDS_TYPE_5) type = SDS_TYPE_8;
  39.     hdrlen = sdsHdrSize(type);
  40.     if (oldtype==type) {
  41.         newsh = s_realloc(sh, hdrlen+newlen+1);
  42.         if (newsh == NULL) return NULL;
  43.         s = (char*)newsh+hdrlen;
  44.     } else {
  45.         /* Since the header size changes, need to move the string forward,
  46.          * and can't use realloc */
  47.         newsh = s_malloc(hdrlen+newlen+1);
  48.         if (newsh == NULL) return NULL;
  49.         memcpy((char*)newsh+hdrlen, s, len+1);
  50.         s_free(sh);
  51.         s = (char*)newsh+hdrlen;
  52.         s[-1] = type;
  53.         sdssetlen(s, len);
  54.     }
  55.     sdssetalloc(s, newlen);
  56.     return s;
  57. }
  60. /* Reallocate the sds string so that it has no free space at the end. The
  61.  * contained string remains not altered, but next concatenation operations
  62.  * will require a reallocation.
  63.  *
  64.  * After the call, the passed sds string is no longer valid and all the
  65.  * references must be substituted with the new pointer returned by the call. */
  66. sds sdsRemoveFreeSpace(sds s) {
  67.     void *sh, *newsh;
  68.     char type, oldtype = s[-1] & SDS_TYPE_MASK;
  69.     int hdrlen, oldhdrlen = sdsHdrSize(oldtype);
  70.     size_t len = sdslen(s);
  71.     sh = (char*)s-oldhdrlen;
  73.     /* Check what would be the minimum SDS header that is just good enough to
  74.      * fit this string. */
  75.     type = sdsReqType(len);
  76.     hdrlen = sdsHdrSize(type);
  78.     /* If the type is the same, or at least a large enough type is still
  79.      * required, we just realloc(), letting the allocator to do the copy
  80.      * only if really needed. Otherwise if the change is huge, we manually
  81.      * reallocate the string to use the different header type. */
  82.     if (oldtype==type || type > SDS_TYPE_8) {
  83.         newsh = s_realloc(sh, oldhdrlen+len+1);
  84.         if (newsh == NULL) return NULL;
  85.         s = (char*)newsh+oldhdrlen;
  86.     } else {
  87.         newsh = s_malloc(hdrlen+len+1);
  88.         if (newsh == NULL) return NULL;
  89.         memcpy((char*)newsh+hdrlen, s, len+1);
  90.         s_free(sh);
  91.         s = (char*)newsh+hdrlen;
  92.         s[-1] = type;
  93.         sdssetlen(s, len);
  94.     }
  95.     sdssetalloc(s, len);
  96.     return s;
  97. }

发表评论

表情：
评论列表 （有 0 条评论，438人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Redis源码剖析之RDB

    我们小学三年级的时候就知道，redis是一个纯内存存储的中间件，那它宕机会怎么样？数据会丢失吗？答案是可以不丢。 事实上redis为了保证宕机时数据不丢失，提供了两种数据持久化

    拼搏现实的明天。拼搏现实的明天。/ 0 赞/ 484 阅读