Redis底层详解（二） 字符串

Mike

一、sds字符串概述
　　sds 字符串即 Simple Dynamic String（即简单动态字符串），其中动态的含义是内存的分配是动态的，sds的定义如下：

　　它采用一段连续的内存来存储 sds 结构。和普通字符串 char* 不同，sds 是二进制安全的，并不以 '\0' 来标识字符串结尾，于是必须要有一个 len 字段来标记这个字符串的长度。那么，我们可以简单地认为这个字符串是由“字符串长度”和“字符数组”组成的。结构如图所示（实际结构还会稍微复杂一些）：

二、Redis 数据结构定义
　　1、sds 存储结构
       Redis 中的 sds 字符串的具体的存储结构如下图所示：

　　其中 sdshdr 含义为“sds header”（sds 头部），len 字段就存储在这个 header 中；buf 则用来存储字节数组，即原始字符串。
　　2、sds 头部
       为了适应不同长度的字符串，sds 头部一共设计了5种结构，分别适应长度在各自范围内的字符串。这五种结构分别为 sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64（末尾数字对应的是2的次幂）。例如 sdshdr5 用于存储长度在2的5次幂以内的，sdshdr16 用于存储长度在2的16次幂以内的，等等。 

　　
        从上面的代码可以看出，除了 sdshdr5，其它四个 sds 头部的结构设定是完全一致的。
       先来介绍其它四种头部，最后介绍 sdshdr5。其中 __attribute__ ((__packed__)) 的作用是告诉编译器不采用字节对齐。拿 sdshdr32 来举例，由于不采用字节对齐，所以结构体中的每个字段都是紧凑排列的，len 和 alloc 占用4个字节，flags占用1个字节，buf 作为字符串起始地址，本身不占用字节数，所以 sizeof(sdshdr32) 的值就是 4+4+1 = 9。
       len 字段就存下了这个 sds 字符串的长度；sds字符串采用空间预分配机制，alloc 字段就代表当前这个字符串预先分配了多少字节的可用空间，所以 alloc 一定是大于等于 len 的；flags 的低三位代表 sds 的类型，分别用以下五个宏表示：

　　sds 字符串详细的内存结构如下图所示(sdshdr5除外)：

　　为了兼容传统C字符串，需要在 buf 末尾多申请一个字节用于存放 '\0' 。所以一个 sds 字符串占用的内存字节总数为：sizeof(sdshdr) + alloc + 1。
       sdshdr5 的 flags 的低三位存储 SDS_TYPE，高五位存储字符串的长度 len，详见下文的 SDS_TYPE_5_LEN 的宏定义，这个宏就是计算 sdshdr5 表示的字符串的长度。 
       另外两个宏分别代表 SDS_TYPE 占用的比特位数以及它的掩码，掩码 SDS_TYPE_MASK 主要用于和 flags进行 "位与" 运算获取这个字符串的 SDS_TYPE：

三、字符串信息
　　1、长度
      字符串长度就是这个字符串已经使用的空间，即 len 字段的值。当我们得到一个 sds 结构时，它的真正地址是指向 buf 字段的（即字符串首地址）。有了字符串首地址，只要知道这个字符串的长度，就能获取这整个字符串信息了。字符串长度获取是利用 sds.h/sdslen 函数实现的：

#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))      
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
static inline size_t sdslen(const sds s) {
  unsigned char flags = s[-1];          // 1) 偏移获取flags
  switch(flags&SDS_TYPE_MASK) {         // 2) 掩码运算得到SDS_TYPE
    case SDS_TYPE_5:
      return SDS_TYPE_5_LEN(flags);     // 3) 获取SDS_TYPE_5类型的字符串的len
    case SDS_TYPE_8:
      return SDS_HDR(8,s)->len;       // 4) 获取非SDS_TYPE_5类型的字符串的len
    case SDS_TYPE_16:
      return SDS_HDR(16,s)->len;
    case SDS_TYPE_32:
      return SDS_HDR(32,s)->len;
    case SDS_TYPE_64:
      return SDS_HDR(64,s)->len;
  }
  return 0;
}

　　1) 由于 s 的地址指向 buf，所以只要向前偏移1个字节，就能得到 flags 字段了，即 flags = s[-1]；
        2) flags 正好一个字节（总共8个比特位），低3位用来存储 SDS_TYPE，除了 sdshdr5 高5位用来表示字符串长度，其它类型的 flags 的高五位是留空的。SDS_TYPE_MASK 的值为7，二进制表示为(111)，和 flags 作“位与”运算就可以获得 flags 的低3位。
        3) SDS_TYPE_5_LEN是一个宏定义，含义是取 flags 的高5位。再回到之前 sdshdr5 的结构体定义，发现和其它的不同，它没有 len 字段，因为它的长度比较短，所以可以把 len 和 SDS_TYPE 统一存储在 flags 字段上。即用低3位代表 SDS_TYPE，高5位代表字符串长度。这就是为什么获取 SDS_TYPE 时要进行掩码运算的原因。
        4) SDS_HDR(T, s) 也是一个宏，宏定义中用到了字符串连接（'##'）用于获取给定类型T的 "sds header" 结构体，用 s 减去 sizeof(sdshdr) 就能得到 "sds header" 结构体的首地址，进而获得这个字符串 buf 的 len 字段。
　　2、预留空间
        预留空间大小由 alloc 参数指定，用和 sdslen 同样的方法，获取字符串申请了多少可用空间的函数，是在 sds.h/sdsalloc 函数实现的：

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

　　3、剩余空间
        sdslen 和 sdsalloc 的区别仅在于字段的获取上，前者取的是 len 字段，后者取的是 alloc 字段。两者相减，可以得到当前字符串还有多少剩余空间，在 sds.h/sdsavail 函数中实现：

#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
static inline size_t sdsavail(const sds s) {
  unsigned char flags = s[-1];
  switch(flags&SDS_TYPE_MASK) {
    case SDS_TYPE_5: {
      return 0;             // 1) alloc == len
    }
    case SDS_TYPE_8: {
      SDS_HDR_VAR(8,s);         // 2) 似 SDS_HDR 的宏定义
      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;
}

　　1) SDS_TYPE_5 的 alloc == len，所以剩余空间为零；
       2) SDS_HDR_VAR 是和 SDS_HDR 类似的宏定义，只不过它多了一步赋值，将指针的值赋值给了 sh；
四、字符串操作
　　1、字符串创建
       创建一个给定长度的字符串，实现在 sds.c/sdsnewlen 函数中：

sds sdsnewlen(const void *init, size_t initlen) {
  void *sh;
  sds s;
  char type = sdsReqType(initlen);               // 1) 根据长度获取对应的SDS_TYPE
  if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;   // 2) 空字符串采用SDS_TYPE_8
  int hdrlen = sdsHdrSize(type);                 // 3) 根据 SDS_TYPE 获取 header 占据的字节数
  unsigned char *fp;
  sh = s_malloc(hdrlen+initlen+1);               // 4) 分配内存空间
  if (!init)
    memset(sh, 0, hdrlen+initlen+1);             
  if (sh == NULL) return NULL;
  s = (char*)sh+hdrlen;                    // 5) s指针定位到 buf 首地址
  fp = ((unsigned char*)s)-1;                  
  switch(type) {
    case SDS_TYPE_5: {
      *fp = type | (initlen << SDS_TYPE_BITS);       // 6) SDS_TYPE_5 处理
      break;
    }
    case SDS_TYPE_8: {
      SDS_HDR_VAR(8,s);
      sh->len = initlen;
      sh->alloc = initlen;
      *fp = type;
      break;
    }
    case SDS_TYPE_16: ...                   // 7) sdshdr16、sdshdr32、sdshdr64 和 sdshdr8 的处理一致
    case SDS_TYPE_32: ...
    case SDS_TYPE_64: ...
  }
  if (initlen && init)
    memcpy(s, init, initlen);                // 8) 拷贝内存
  s[initlen] = '\0';
  return s;
}

　　1) sdsReqType 函数根据申请的 initlen 大小，分配相应的 SDS_TYPE。例如，长度在2的5次以内的用SDS_TYPE_5，长度在2的8次以内的用SDS_TYPE_8，以此类推；
　　2) 空字符串的 SDS_TYPE 规定为 SDS_TYPE_8，用 SDS_TYPE_5 难以向上兼容；
       3) sdsHdrSize 函数是根据 SDS_TYPE 得到相应的字节数。例如类型为 SDS_TYPE_5，返回值就是 sizeof( struct sdshdr5 )，以此类推；
       4) s_malloc 用来申请内存空间，为了兼容C字符串，需要额外多分配一个字节给'\0'；
       5) s 指针定位到 buf 的首地址，fp 指针定位到 flags 的地址；
       6) SDS_TYPE_5 用一个字节 flags 存 SDS_TYPE 和 长度，之前已经讲过；
       7) 非 SDS_TYPE_5 用同样规则填充 len、alloc、flags 字段；
       8) 调用系统API memcpy 拷贝内存，最后加上一个 '\0' 兼容传统C字符串；
　　由 sdsnewlen 可以引申出一系列字符串的构建函数：空串函数sdsempty、创建函数sdsnew、拷贝函数sdsdup：

sds sdsempty(void) {
  return sdsnewlen("",0);
}
sds sdsnew(const char *init) {
  size_t initlen = (init == NULL) ? 0 : strlen(init);
  return sdsnewlen(init, initlen);
}
sds sdsdup(const sds s) {
  return sdsnewlen(s, sdslen(s));
}

　　2、字符串销毁
        销毁一个字符串，实现在 sds.c/sdsfree 函数中：

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

　　字符串销毁就是释放内存，利用 s_free 接口完成。 s_free 是和 s_malloc 相对应的，所以只要指定内存首地址，就能进行相应的释放工作。利用 s[-1] 得到对应的 sdsheader 大小，然后偏移到 sdsheader 的首地址就能正确释放内存了。
　　3、字符串拼接
       C 字符串的字符串拼接函数是 strcat，存在缓冲区溢出的风险。如图所示，现在要将 src 字符串拼接到 dest 字符串后面，但是 dest 原先分配的最大空间是8个字节，直接调用 strcat 就会造成缓冲区溢出。

　　而 sds 字符串就不会出现这个问题，它的字符串拼接函数 sds.c/sdscatlen 实现是这样的：

sds sdscatlen(sds s, const void *t, size_t len) {     // 1) 字符串拼接
  size_t curlen = sdslen(s);
  s = sdsMakeRoomFor(s,len);              // 2) 扩展空间
  if (s == NULL) return NULL;
  memcpy(s+curlen, t, len);               // 3) 拷贝内存
  sdssetlen(s, curlen+len);               // 4) 设置长度
  s[curlen+len] = '\0';
  return s;
}

　　1) 将一个二进制安全的字符串 t 的前 len 个字符拷贝到 sds 字符串 s 的末尾，由于这样一步操作可能导致整个字符串的内存首地址的改变，所以这个函数需要有一个返回值，指向新的 sds 字符串的首地址；
       2) 如果剩余空间不够，就为 s 再申请 len 个字节的空间，sdsMakeRoomFor 的实现见下文；
       3) 从 t 开始的 len 个字节拷贝到 s 字符串末尾，注意不能使用 strcpy；
       4) 设置新字符串的长度，并且在末尾加上一个 '\0' 用于兼容 C 字符串；
　　由 sdscatlen 引出两个字符串拼接函数：sdscat 用于连接 sds字符串 和 传统C字符串；sdscatsds 用于连接两个 sds 字符串。拼接过程中可能会涉及到空间预分配（下一节具体介绍），所以被拼接的字符串的首地址可能会发生改变，所以需要有返回值返回拼接后字符串的首地址。

sds sdscat(sds s, const char *t) {
  return sdscatlen(s, t, strlen(t));
}
sds sdscatsds(sds s, const sds t) {
  return sdscatlen(s, t, sdslen(t));
}

　　4、字符串空间预分配
       在字符串拼接前，sds 字符串会首先检测缓冲区大小，看是否能够承载待拼接的字符串，如果空间不够，则进行扩容。这就是 sds 字符串的空间预分配。
       分配规则是：如果拼接后的字符串长度 newlen 小于1M（即 1024*1024 个字节，定义在 SDS_MAX_PREALLOC），则需要分配和 newlen 同样大小的未使用空间；反之，则分配 1M 的 未使用的内存空间。换言之，就是需要分配 min {newlen, 1M} 个字节的内存空间。
　　这么做的目的是为了减少连续执行字符串增长操作时所需的内存重分配次数，提高效率。空间预分配的实现如下：

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;
  int hdrlen;
  if (avail >= addlen) return s;             // 1) 空间足够则直接返回
  len = sdslen(s);
  sh = (char*)s-sdsHdrSize(oldtype);
  newlen = (len+addlen);                 // 2) 空间预分配的长度计算
  if (newlen < SDS_MAX_PREALLOC)
    newlen *= 2;
  else
    newlen += SDS_MAX_PREALLOC;
  type = sdsReqType(newlen);
  if (type == SDS_TYPE_5) type = SDS_TYPE_8;       // 3) 不使用 SDS_TYPE_5
  hdrlen = sdsHdrSize(type);
  if (oldtype==type) {
    newsh = s_realloc(sh, hdrlen+newlen+1);      // 4) 扩大内存分配
    if (newsh == NULL) return NULL;
    s = (char*)newsh+hdrlen;
  } else {
    newsh = s_malloc(hdrlen+newlen+1);         // 5) 分配新的内存
    if (newsh == NULL) return NULL;
    memcpy((char*)newsh+hdrlen, s, len+1);
    s_free(sh);                    // 6) 释放之前的内存
    s = (char*)newsh+hdrlen;
    s[-1] = type;
    sdssetlen(s, len);
  }
  sdssetalloc(s, newlen);
  return s;
}

　　1) avail 代表剩余未被使用的空间，如果需要扩充的空间小于等于它，则不需要进行额外空间分配，直接返回即可；
       2) newlen 最后会被用于给新的 sds 字符串的 alloc 字段赋值；
       3) SDS_TYPE_5 和其它结构不同，无法进行向上兼容，所以扩容需要采用 SDS_TYPE_8；
      4) 这里出现一个分支，即扩容后的空间和扩容前，总的内存占用对应的 SDS_TYPE 是否相同，如果相同，则在原 sds header 的首地址处调用 s_realloc 重新进行内存分配，记得加上一个字节的空字符；
       5) 如果 SDS_TYPE 不同，len 和 alloc 字段占用的字节数都会变大，sds header 结构体占用内存会变大，导致实际字符串首地址 buf 向后偏移，所以需要调用 s_malloc 重新申请新的空间来存储字符串字节数组。
       6) 最后，利用 s_free 释放原地址的空间，否则将引起内存泄露。
　　5、字符串比较
       sds 字符串比较类似传统C字符串的比较。利用 sdslen 获取两个字符串的长度，然后利用系统API memcmp 进行字节比较，实现在 sds.c/sdscmp 中：

int sdscmp(const sds s1, const sds s2) {
  size_t l1, l2, minlen;
  int cmp;
  l1 = sdslen(s1);
  l2 = sdslen(s2);
  minlen = (l1 < l2) ? l1 : l2;
  cmp = memcmp(s1,s2,minlen);
  if (cmp == 0) return l1>l2? 1: (l1<l2? -1: 0);
  return cmp;
}