Redis中的动态字符串学习教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

sds 的用途
Sds 在 Redis 中的主要作用有以下两个：

实现字符串对象（StringObject）；
在 Redis 程序内部用作 char* 类型的替代品；
以下两个小节分别对这两种用途进行介绍。

实现字符串对象

Redis 是一个键值对数据库（key-value DB），数据库的值可以是字符串、集合、列表等多种类型的对象，而数据库的键则总是字符串对象。

对于那些包含字符串值的字符串对象来说，每个字符串对象都包含一个 sds 值。

“包含字符串值的字符串对象”，这种说法初听上去可能会有点奇怪，但是在 Redis 中，一个字符串对象除了可以保存字符串值之外，还可以保存 long 类型的值，所以为了严谨起见，这里需要强调一下：当字符串对象保存的是字符串时，它包含的才是 sds 值，否则的话，它就是一个 long 类型的值。
举个例子，以下命令创建了一个新的数据库键值对，这个键值对的键和值都是字符串对象，它们都包含一个 sds 值：

redis> SET book "Mastering C++ in 21 days"
OK

redis> GET book
"Mastering C++ in 21 days"

以下命令创建了另一个键值对，它的键是字符串对象，而值则是一个集合对象：

redis> SADD nosql "Redis" "MongoDB" "Neo4j"
(integer) 3

redis> SMEMBERS nosql
1) "Neo4j"
2) "Redis"
3) "MongoDB"

用 sds 取代 C 默认的 char* 类型

因为 char* 类型的功能单一，抽象层次低，并且不能高效地支持一些 Redis 常用的操作（比如追加操作和长度计算操作），所以在 Redis 程序内部，绝大部分情况下都会使用 sds 而不是 char* 来表示字符串。

性能问题在稍后介绍 sds 定义的时候就会说到，因为我们还没有了解过 Redis 的其他功能模块，所以也没办法详细地举例说那里用到了 sds ，不过在后面的章节中，我们会经常看到其他模块（几乎每一个）都用到了 sds 类型值。

目前来说，只要记住这个事实即可：在 Redis 中，客户端传入服务器的协议内容、 aof 缓存、返回给客户端的回复，等等，这些重要的内容都是由 sds 类型来保存的。

redis 中的字符串
在 C 语言中，字符串可以用一个 \0 结尾的 char 数组来表示。

比如说， hello world 在 C 语言中就可以表示为 "hello world\0" 。

这种简单的字符串表示，在大多数情况下都能满足要求，但是，它并不能高效地支持长度计算和追加（append）这两种操作：

每次计算字符串长度（strlen(s)）的复杂度为 θ(N) 。
对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配（realloc）。
在 Redis 内部，字符串的追加和长度计算很常见，而 APPEND 和 STRLEN 更是这两种操作，在 Redis 命令中的直接映射，这两个简单的操作不应该成为性能的瓶颈。

另外， Redis 除了处理 C 字符串之外，还需要处理单纯的字节数组，以及服务器协议等内容，所以为了方便起见， Redis 的字符串表示还应该是二进制安全的：程序不应对字符串里面保存的数据做任何假设，数据可以是以 \0 结尾的 C 字符串，也可以是单纯的字节数组，或者其他格式的数据。

考虑到这两个原因， Redis 使用 sds 类型替换了 C 语言的默认字符串表示： sds 既可高效地实现追加和长度计算，同时是二进制安全的。

sds 的实现

在前面的内容中，我们一直将 sds 作为一种抽象数据结构来说明，实际上，它的实现由以下两部分组成：

typedef char *sds;


struct sdshdr {

  // buf 已占用长度
  int len;

  // buf 剩余可用长度
  int free;

  // 实际保存字符串数据的地方
  char buf[];
};

其中，类型 sds 是 char * 的别名（alias），而结构 sdshdr 则保存了 len 、 free 和 buf 三个属性。

作为例子，以下是新创建的，同样保存 hello world 字符串的 sdshdr 结构：

struct sdshdr {
  len = 11;
  free = 0;
  buf = "hello world\0"; // buf 的实际长度为 len + 1
};

通过 len 属性， sdshdr 可以实现复杂度为 θ(1) 的长度计算操作。

另一方面，通过对 buf 分配一些额外的空间，并使用 free 记录未使用空间的大小， sdshdr 可以让执行追加操作所需的内存重分配次数大大减少，下一节我们就会来详细讨论这一点。

当然， sds 也对操作的正确实现提出了要求 —— 所有处理 sdshdr 的函数，都必须正确地更新 len 和 free 属性，否则就会造成 bug 。

数据类型定义
与sds实现有关的数据类型有两个，一个是 sds：

  // 字符串类型的别名 
  typedef char *sds;

另一个是 sdshdr：

  // 持有sds的结构 
  struct sdshdr { 
    // buf中已经被使用的字符串空间数量 
    int len; 
    // buf中预留字符串的空间数量 
    int free; 
    // 实际存储字符串的地方 
    char buf[]; 
  };

其中，sds只是字符串数组类型char*的别名，而sdshdr用于持有和保存sds的信息

比如，sdshdr.len可以用于在O（1）的复杂度下获取sdshdr.buf中存储的字符串的实际长度，而sdshdr.free则用于保存sdshdr.buf中还有多少预留空间

（这里sdshdr应该是sds handler的缩写）

将sdshdr用作sds
sds模块对sdshdr结构使用了一点小技巧：通过指针运算，它使得sdshdr结构可以像sds类型一样被传值和处理，并在需要的时候恢复成sdshdr类型

通过下面的函数定义来理解这个技巧

sdsnewlen 函数返回一个新的sds值，实际上，它创建的却是一个sdshdr结构：

  sds sdsnewlen(const void *init, size_t initlen) 
  { 
    struct sdshdr *sh; 
   
    if (init) { 
      // 创建 
      sh = malloc(sizeof(struct sdshdr) + initlen + 1); 
    } else { 
      // 重分配 
      sh = calloc(1, sizeof(struct sdshdr) + initlen + 1); 
    } 
   
    if (sh == NULL) return NULL; 
   
    sh->len = initlen; 
    sh->free = 0;  // 刚开始free为0 
   
    if (initlen && init) { 
      memcpy(sh->buf, init, initlen); 
    } 
    sh->buf[initlen] = '\0'; 
   
    // 只返回sh->buf这个字符串部分 
    return (char *)sh->buf; 
  }

通过使用变量持有一个sds的值，在遇到那些只处理sds值本身的函数时，可以直接将sds传给它们。比如说，sdstoupper 函数就是其中的一个例子：

  static inline size_t sdslen(const sds s) 
  { 
    // 从sds中计算出相应的sdshdr结构 
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    return sh->len; 
  } 
   
   
  void sdstoupper(sds s) 
  { 
    int len = sdslen(s), j; 
   
    for (j = 0; j < len; j ++) 
      s[j] = toupper(s[j]); 
  }

这里有一个技巧，通过指针运算，可以从sds值中计算出相应的sdshdr结构：

sds虽然是指向char *的buf（ps：并且空数组不占用内存空间，数组名即为内存地址），但是分配的时候是分配sizeof(struct sdshdr) + initlen + 1的，通过sds - sizeof(struct sdshdr)可以计算出struct sdshdr的首地址，从而可以得到len和free的信息

sdsavail 函数就是使用这中技巧的一个例子：

  static inline size_t sdsavail(const sds s) 
  { 
    struct sdshdr *sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    return sh->free; 
  }

内存分配函数实现
和Reids 的实现决策相关的函数是 sdsMakeRoomFor ：

  sds sdsMakeRoomFor(sds s, size_t addlen) 
  { 
    struct sdshdr *sh, *newsh; 
    size_t free = sdsavail(s); 
    size_t len, newlen; 
   
    // 预留空间可以满足本地拼接  
    if (free >= addlen) return s; 
   
    len = sdslen(s); 
    sh = (void *)(s - (sizeof(struct sdshdr))); 
   
    // 设置新sds的字符串长度 
    // 这个长度比完成本次拼接实际所需的长度要大 
    // 通过预留空间优化下次拼接操作 
    newlen = (len + addlen); 
    if (newlen < 1024 * 1024) 
      newlen *= 2; 
    else 
      newlen += 1024; 
   
    // 重新分配sdshdr 
    newsh = realloc(sh, sizeof(struct sdshdr) + newlen + 1); 
    if (newsh == NULL) return NULL; 
   
    newsh->free = newlen - len; 
   
    // 只返回字符串部分 
    return newsh->buf; 
  }

这种内存分配策略表明，在对sds 值进行扩展（expand）时，总会预留额外的空间，通过花费更多的内存，减少了对内存进行重分配(reallocate)的次数，并优化下次扩展操作的处理速度

再把redis的如果实现对sds字符串扩展的方法贴一下，很不错的思路：

  /** 
   * 按长度len扩展sds，并将t拼接到sds的末尾 
   */ 
  sds sdscatlen(sds s, const void *t, size_t len) 
  { 
    struct sdshdr *sh; 
   
    size_t curlen = sdslen(s); 
   
    // O(N) 
    s = sdsMakeRoomFor(s, len); 
    if (s == NULL) return NULL; 
   
    // 复制 
    memcpy(s + curlen, t, len); 
   
    // 更新len和free属性 
    sh = (void *)(s - (sizeof(struct sdshdr))); 
    sh->len = curlen + len; 
    sh->free = sh->free - len; 
   
    // 终结符 
    s[curlen + len] = '\0'; 
   
    return s; 
  } 
   
  /** 
   * 将一个char数组拼接到sds 末尾 
   */ 
  sds sdscat(sds s, const char *t) 
  { 
    return sdscatlen(s, t, strlen(t)); 
  }