原文作者:
2018年04月28日 12:03:29 孤独剑0001 

  1.     看过了《redis设计与实现》，了解了redis设计的基本原理。但是三个月之后发现，遗忘了很多，只好重新温习。只是，这次是从redis源码的角度学习的，当然过程中会翻阅《redis设计与实现》这本书，毕竟需要一个框架指导。按照redis源码的阅读顺序，按照从基本到复杂、从redis使用的基本数据结构开始。本文就介绍redis中使用的最常见的数据结构之一---sds（simple dynamic string)，当然是从源码的角度进行解释的。大致的原理，读者可以参考《redis设计与实现》第一章。<br />        redis源码中，关于sds的代码分布在sds.h和sds.c两个文件夹中。本文主要配合源码介绍redis代码中关于sds实现的重要思想。<br />        sds是基于c语言中的char*实现的，存储的字符串都是char*类型的。这从sds的定义可以看得出来（ typedef char* sds;），这可以让redis直接使用c语言的字符串的很多函数，而不必自己实现一些在c语言中已有的函数。<br />        但是，redis中实现的sds与一般的c语言的字符串又不一样。sds除了存放字符串本身的数据之外，sds还分别存放着字符串相关的信息，如字符串的长度、未使用的空间的长度，同时针对不同的字符串的长度采用五种不同的说明字符串信息的头结构，最大化节约内存；sds使用空间预分配和惰性空间释放策略，减少内存中空间分配的次数，提高该数据库的性能。下面针对redis中使用的五种不同的字符串头结构及其空间预分配和惰性空间释放策略进行介绍。

一、字符串的五种头结构

  1. //sdshdr5与其他几个header结构体不同，不包含alloc字段，而是用flags的高5位来存储。因此不能为字符串分配空余空间。如果字符串需要动态增长，那么他>  就必然要分配内存才行。所以说，这种类型的sds字符串更适合存储静态的短字符串（长度小于32）
  2. struct __attribute__ ((__packed__)) sdshdr5 {
  3.   unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
  4.   char buf[];
  5. };
  6. struct __attribute__ ((__packed__)) sdshdr8 {
  7.   uint8_t len; /* used */
  8.   uint8_t alloc; /* excluding the header and null terminator */
  9.   unsigned char flags; /* 3 lsb of type, 5 unused bits */
  10.   char buf[];
  11. };
  12. struct __attribute__ ((__packed__)) sdshdr16 {
  13.   uint16_t len; /* used */
  14.   uint16_t alloc; /* excluding the header and null terminator */
  15.   unsigned char flags; /* 3 lsb of type, 5 unused bits */
  16.   char buf[];
  17. };
  18. struct __attribute__ ((__packed__)) sdshdr32 {
  19.   uint32_t len; /* used */
  20.   uint32_t alloc; /* excluding the header and null terminator */
  21.   unsigned char flags; /* 3 lsb of type, 5 unused bits */
  22.   char buf[];
  23. };
  24. struct __attribute__ ((__packed__)) sdshdr64 {
  25.   uint64_t len; /* used */
  26.   uint64_t alloc; /* excluding the header and null terminator */
  27.   unsigned char flags; /* 3 lsb of type, 5 unused bits */
  28.   char buf[];
  29. };
  1.     上面列出的五种struct就是redis中的sds使用的五种管理字符串的结构头，现在分别对其中的成员变量做解释。<br />        uint(8,16,32,64)_t：是已经占用的字节数，就是buf中存放的字符串的长度，不包括结尾的'\0'。<br />        uint(8,16,32,64)_t：是一共分配的空间的大小，包括使用的和未使用的大小，不包括结尾的'\0'。<br />        unsigned char flag：是用于表示该结构体类型的标志位，在sdshdr8，sdshdr16，sdshdr32和sdshdr64中主要用于表示该结构体的类型，在sdshdr5中还用于表示长度。这五种结构体中flags的低三位都是用于表示结构体的类型，因为有五种，所以需要使用三位进行表示；高五位在hdrsds5中用于表示长度；在其他的四种struct中是未被使用的位。<br />        char buf[]：在这里只是一个占位符而已，表示在flag之后是buf的位置，并不占用空间。如果对struct __attribute__ ((packed)) sdshdr64取长度，就是sizeof(struct __attribute__ ((packed)) sdshdr64)，那么值应该是17，既不是24，也不是其他的值。这是因为，其一使用了__attribute__ ((packed))，其二char buf[]不占用实际的空间。关于__attribute__ ((packed))的详细解释，可以自行google。<br />        __attribute__ ((packed))这个命令的作用是取消编译阶段的内存优化对齐功能，按照结构体重各个元素实际占用的字节数进行对齐。使用__attribute__ ((packed))之后，sdshdr（8，16，32，64)中各个元素是紧紧相邻的，其内存中的布局如图1所示。<br />![](https://cdn.nlark.com/yuque/0/2019/png/383291/1563675367308-d18651e1-ee42-4847-beda-8d2aa2a5e584.png#align=left&display=inline&height=100&originHeight=100&originWidth=418&size=0&status=done&width=418)<br />图 1 sds内存空间布局<br />        <br />        因此，使用了__attribute__ ((packed))属性之后，有以下两点好处：<br />        1.redis一般作为内存数据库使用，因此__attribute__ ((packed))属性能够尽最大的可能节约内存空间，从而增加内存中可以存放的键值对的数量，提高系统的性能；<br />        2.__attribute__ ((packed))属性使得所有的元素在内存中的位置可以按照简单的加减进行计算，因此可以根据指定的sds的位置，确定flag的位置；例如给定sds为s，那么flag的位置就是s[-1]，结构体内部寻址变得简单；<br />        如果没有__attribute__ ((packed))属性，那么struct中的成员建按照内存进行对齐，那么就不能根据sds的变量s，直接用s[-1]获取flag的位置了。<br />        sds.h文件中存在几个比较重要的宏定义，如下。
  1. #define SDS_TYPE_5  0
  2. #define SDS_TYPE_8  1
  3. #define SDS_TYPE_16 2
  4. #define SDS_TYPE_32 3
  5. #define SDS_TYPE_64 4
  1.     五种类型，因此需要每个struct中flag中的三位进行表示，因此，还存在一下两种宏定义，用于确定当前struct的类型。
  1. //flags中最低的三位用于表示类型，因此取SDS_TYPE_MASK为7,这三位都是1,用"位与"操作获取header的类型;
  2. #define SDS_TYPE_MASK 7
  3. //标志位占据的长度
  4. #define SDS_TYPE_BITS 3
  1.     由于sdshdr5中用flag的低三位表示结构体的类型，高五位表示结构体中字符串的的长度，因此sdshdr5中最多表示32个字符的字符串，将flag右移三位的数值就是字符串的长度大小，所以sdshdr5的长度的宏定义如下：
  1. #define SDS_TYPE_5_LEN ((f)>>SDS_TYPE_BITS)
  1.     在redis的源码中，我们一般直接使用的是sds类型的对象，至于该sds对象应该使用哪种类型的sdshdr，则应该由实际保存的字符串的长度决定，这对于使用者而言是透明的，无需关心。既然我们直接使用sds对象，那么在修改对象的时候应该能够修改该对象对应的len和alloc属性，甚至要修改flag属性；为了修改这两个属性，则必须能够取到这几个属性所对应的地址。为此，redis在sds.h文件中实现了两个宏定义，用于相关的操作。

  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))))
  1.     上**述的两个宏定义是有区别的。SDS_HDR(T, s)是为了根据s和T获取s的头指针，SDS_HDR(8, s1)表示获取指向s1的header的指针，SDS_HDR(16, s2)表示s2的header的指针，都是指向sdshdr##T的开始位置的指针。而SDS_HDR_VAR是定义一个指向sdshdt##T指针，相当于在使用该宏定义的作用于内定义了一个新的指向sdshdr##T的指针，例如sdsnewlen中使用该宏定义就是在case中重定义了指向sdshdr##T的指针---sh，外层作用域中定义的sh在case定义中失效，以减少不必要的代码重复。下面我们详细介绍sdsnewlen（const void* init, size_t initlen)，是怎样根据sds中字符串的长度选择不同的sdshdr的。**
  1. //返回指向实际分配的字符串开始位置的char*
  2. sds sdsnewlen(const void *init, size_t initlen) {
  3.   //只是为了指向新分配的一段空间，与case语句中使用的sh无关，可以替换成任意的别的名字的变量;
  4.   void *sh;
  5.   sds s;
  6.   //为了节省内存而是用不同的类型,根据请求的长度确定应该使用的类型;
  7.   char type = sdsReqType(initlen);
  8.   /* Empty strings are usually created in order to append. Use type 8
  9.        * since type 5 is not good at this. */
  10.   if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
  11.   int hdrlen = sdsHdrSize(type);
  12.   unsigned char *fp; /* flags pointer. */
  13.   //分配的内存块的大小包括头的大小和实际字符串的大小以及结尾的"\0"的总长度;
  14.   sh = s_malloc(hdrlen+initlen+1);
  15.   //如果init为NULL，则将所有的数据都清0;
  16.   if (!init)
  17.     memset(sh, 0, hdrlen+initlen+1);
  18.   //为什么不先检查内存的分配是否成功呢？？？是不是应该和上一句调换顺序???
  19.   if (sh == NULL) return NULL;
  20.   //确定实际字符串的位置;
  21.   s = (char*)sh+hdrlen;
  22.   //确定类型的地址;
  23.   fp = ((unsigned char*)s)-1;
  24.   //到此为止，只是将sh指向了一个新分配的固定大小的空间，用于存放sds，但是并没有关联任何类型的sdshdr；
  25.   switch(type) {
  26.     case SDS_TYPE_5: {
  27.       //设置分配的长度以及类型;
  28.       *fp = type | (initlen << SDS_TYPE_BITS);
  29.       break;
  30.     }
  31.     case SDS_TYPE_8: {
  32.       //#define SDS_HDR_VAR struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdsfdr##T)));
  33.       //由该宏定义可以知道，该宏定义在相应的作用范围内重新定义了一个指向struct sdshdr##T的指针sh，该定义要屏蔽掉外层空间中定义的void* s  h的定义；case语句的作用就是将包含s地址的一段连续空间初始化为与具体的sdshdr##T相关联的数据结构，而不仅仅是一段已经分配好的连续地址空间而已。当
  34.       //然这里，下面的写法和case SDS_TYPE_16效果是一样的;
  35.       //SDS_HDR_VAR(8, s);
  36.       //sh->len = initlen;
  37.       //sh->alloc = initlen;
  38.       //*fp = type;
  39.       //break;
  40.       struct sdshdr8* test;
  41.       test = SDS_HDR(8,s);
  42.       test->len = initlen;
  43.       test->alloc = initlen;
  44.       *fp = type;
  45.       break;
  46.     }
  47.     case SDS_TYPE_16: {
  48.       /** 定义一个sh指针，并且用16和s进行初始化 **/
  49.       SDS_HDR_VAR(16,s);
  50.       sh->len = initlen;
  51.       sh->alloc = initlen;
  52.       *fp = type;
  53.       break;
  54.     }
  55.     case SDS_TYPE_32: {
  56.       SDS_HDR_VAR(32,s);
  57.       sh->len = initlen;
  58.       sh->alloc = initlen;
  59.       *fp = type;
  60.       break;
  61.     }
  62.     case SDS_TYPE_64: {
  63.       SDS_HDR_VAR(64,s);
  64.       sh->len = initlen;
  65.       sh->alloc = initlen;
  66.       *fp = type;
  67.       break;
  68.     }
  69.   }
  70. }
  71. if (initlen && init)
  72.   memcpy(s, init, initlen);
  73. s[initlen] = '\0';
  74. return s;
  75. }
  1.     从sdsnewlen的定义可以看出来，根据传入的字符串的长度的不同，得到的sdshdr的类型不同，具体的sdsReqType和sdsHdrSize，可以参考redis源码的相关实现。sdsnewlen的实现中，首先根据需要的initlen+hdrlen+1确定需要分配的空间的大小，然后确定sds的位置。**这里需要注意的一点是，几乎所有的参数传递都是直接传递sds，而不包括描述该sds的头部信息的结构体。但是根据，sdshdr和s的位置的相关信息，能够在常量时间内确定描述sds的头部的初始位置。**当然，也可以常量时间内确定该sds的长度，只需要返回sdshdr中的len成员变量的值即可，这是使用sdshdr描述字符串的原因之一；另一个使用sdshdr描述字符串的重要原因就是这样做是二进制安全的。因为char* 是以'\0'确定字符串的结束位置的，因此字符串中间不能出现'\0'，否则就被认为是字符串的结束；但是sds使用len记录使用的字节的长度，不必以'\0'表示结束，所以字符串的中间可以出现'\0'。这也就造成了sds和char*类型存放数据的不同，sds是二进制安全的，存放的数据内容中间可以出现'\0'，char* 只能存放普通的文本字符串。

二、空间预分配和惰性空间释放策略

  1.     正如前所述，sds使用了sdshdr记录相关的sds的长度和总的分配的长度，因此sds在其后追加字符串的时候能够防止缓冲区溢出。在追加字符串到已有字符串末尾的时候（sdscat，sdscatsds)，首先检查剩余的字符串的空间大小（alloc-len)是否能够容纳将要添加的字符串，如果可以的话，则直接将字符串添加进去。如果剩余的空闲空间不够，那么需要重新分配空间，再将原来的字符串复制进去（这是sdshdr类型发生变化的做法），然后将要添加的字符串再复制进去；或者直接使用realloc函数分配空间（这是sdshdr的类型没有发生变化的情况），然后将要添加的字符串复制进去。鉴于可能存在空间重新分配，因此参数中传入的sds的变量（假设为s），可能并不再有效，因此需要使用函数返回的sds。<br />        我们说在已有字符串末尾添加新的字符串的时候，可能需要重新分配空间，那么需要分配的空间的大小怎么确定？？？是不是只需要重新分配和需要添加的字符串长度大小一致的空间呢？当然不是，要是这样的话，每次添加字符串都需要重新分配内存，这是一件极为耗时的事情。Redis在重新分配空间的时候使用空间预分配策略。下面是Redis执行空间分配的函数sdsMakeRoomFor(sds s, size_t addlen)，我们将详细解释该函数。
  1. //空间分配策略的执行过程:
  2. //1.首先检查新要分配的空间的大小与现存的空间的大小，如果新要增加的空间的大小小于已存在的空闲空间的大小，那么直接返回，无需再分配内存空间；否>  则的话需要重新分配空间；
  3. //2.新分配的被占用的空间的大小等于已经占用的空间的大小加上传入函数中addlen参数的大小；
  4. //3.执行空间预分配策略，如果新要分配的已经占用的空间的大小小于SDS_MAX_PREALLOC，那么新分配的总大小为已经占用的空间大小的2倍;如果要分配的占用>  空间的大小大于SDS_MAX_REALLOC的大小，则需要分配的总的长度为 newlen + 1MB 的大小;
  5. //4.如果执行分配之后的newlen的大小没有导致header类型发生变化，则直接执行realloc，不必更改s相对于header的偏移；如果newlen导致header的type发生>  变化，需要执行malloc重新分配空间并将原来的内容复制到新分配的内存中间中，释放原来的空间（包括s和header的空间）,更改type和新分配的空间的len，同
  6. 时更改s相对于header指针的偏移量;
  7. sds sdsMakeRoomFor(sds s, size_t addlen) {
  8. void *sh, *newsh;
  9. //可用的剩余空间的大小;
  10. size_t avail = sdsavail(s);
  11. size_t len, newlen;
  12. //通过s[-1] & SDS_TYPE_MASK可以确定旧的sdshdr的类型;
  13. char type, oldtype = s[-1] & SDS_TYPE_MASK;
  14. int hdrlen;
  15. /* Return ASAP if there is enough space left. */
  16. if (avail >= addlen) return s;
  17. len = sdslen(s);
  18. sh = (char*)s-sdsHdrSize(oldtype);
  19. newlen = (len+addlen);
  20. /* 执行空间预分配策略的方式，如果当前需要占用的空间的数量<SDS_MAX_PREALLOC,直接按照当前需要使用的空间的2倍的大小进行分配；如果当前需要占>  用的空间的数量>=SDS_MAX_PREALLOC,那么直接预分配SDS_MAX_PREALLOC执行空间预分配 */
  21. if (newlen < SDS_MAX_PREALLOC)
  22. newlen *= 2;
  23. else
  24. newlen += SDS_MAX_PREALLOC;
  25. type = sdsReqType(newlen);
  26. /* Don't use type 5: the user is appending to the string and type 5 is
  27.        * not able to remember empty space, so sdsMakeRoomFor() must be called
  28.        * at every appending operation. */
  29. /* SDS_TYPE_5之所以不被使用，使用为该类型无法记住空闲的空间大小，如果使用这种类型的sdshdr，那么每次使用sdscat的时候必须要重新分配空间 */
  30. if (type == SDS_TYPE_5) type = SDS_TYPE_8;
  31. hdrlen = sdsHdrSize(type);
  32. if (oldtype==type) {
  33. newsh = s_realloc(sh, hdrlen+newlen+1);
  34. if (newsh == NULL) return NULL;
  35. //复制新的数据之后，将s指向数据复制之后的地址;
  36. s = (char*)newsh+hdrlen;
  37. } else {
  38. /* Since the header size changes, need to move the string forward,
  39.            * and can't use realloc */
  40. newsh = s_malloc(hdrlen+newlen+1);
  41. if (newsh == NULL) return NULL;
  42. memcpy((char*)newsh+hdrlen, s, len+1);
  43. s_free(sh);
  44. s = (char*)newsh+hdrlen;
  45. s[-1] = type;
  46. sdssetlen(s, len);
  47. }
  48. sdssetalloc(s, newlen);
  49. return s;
  50. }
  1.     空间分配策略的执行过程:<br />        1.首先检查新要分配的空间的大小与现存的空间的大小，如果新要增加的空间的大小小于已存在的空闲空间的大小，那么直接返回，无需再分配内存空间；否>  则的话需要重新分配空间；<br />        2.新分配的被占用的空间的大小等于已经占用的空间的大小加上传入函数中addlen参数的大小；<br />        3.执行空间预分配策略，如果新要分配的已经占用的空间的大小小于SDS_MAX_PREALLOC，那么新分配的总大小为已经占用的空间大小的2倍;如果要分配的占用>  空间的大小大于SDS_MAX_REALLOC的大小，则需要分配的总的长度为 newlen + 1MB 的大小;<br />        4.如果执行分配之后的newlen的大小没有导致header类型发生变化，则直接执行realloc，不必更改s相对于header的偏移；如果newlen导致header的type发生>  变化，需要执行malloc重新分配空间并将原来的内容复制到新分配的内存中间中，释放原来的空间（包括s和header的空间）,更改type和新分配的空间的len，同时更改s相对于header指针的偏移量;<br />        5.最终返回新的sds；<br />        通过空间预分配策略，redis将执行n次sdscat（）函数需要重新分配n次内存空间变为之多需要分配n次空间，提高了代码的执行效率。<br />        所谓的惰性空间释放是当sds的字符串缩短的时候，只是改变存储的字符串和len的大小，并不改变释放多余的空间和改变alloc的大小。如果将来有新的字符串需要添加到已有字符串的末尾，那么可以减少空间分配的次数。当然sds也提供了函数sdsRomoveFreeSpace(sds s)用于真正的释放未使用的空间。