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

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