简单动态字符串

sds 的用途
- 实现字符串对象
- 用 sds 取代 C 默认的 char* 类型
Redis 中的字符串
- sds 实现
优化追加操作
sds 操作API
小结

Sds Simple Dynamic String 简单动态字符串 是 Redis 底层所使用的字符串表示，几乎所有的 Redis 模块中都用了 sds

本章将对 sds 的实现、性能和功能等方面进行介绍， 并说明 Redis 使用 sds 而不是传统 C 字符串的原因

sds 的用途

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

实现字符串对象 String Object
在 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) 的复杂度为 \(O(N)\)
对字符串进行 \(n\) 次追加，必定需要对字符串进行 \(n\) 次内存重分配 realloc

在 Redis 内部，字符串的追加和长度计算很常见

 APPEND 和 STRLEN  这两种操作，是 Redis 命令中的直接映射

这两个简单的操作不应该成为性能的瓶颈

另外， Redis 除了处理 C 字符串之外，还需要处理单纯的字节数组，以及服务器协议等内容，所以为了方便起见， Redis 的字符串表示还应该是二进制安全的

程序不应对字符串里面保存的数据做任何假设，

数据可以是以 \0 结尾的 C 字符串， 也可以是单纯的字节数组， 或者其他格式的数据

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

sds 实现

在前面的内容中，我们一直将 sds 作为一种抽象数据结构来说明

实际上，它的实现由以下两部分组成：

typedef char *sds;

struct sdshdr {
    int len; // buf 已占用长度
    int free; // buf 剩余可用长度
    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 可以实现复杂度为 \(O(1)\) 的 长度计算 操作
通过对 buf 分配一些额外的空间，并使用 free 记录未使用空间的大小，sdshdr 可以让执行追加操作所需的内存重分配次数大大减少

当然，sds 也对操作的正确实现提出了要求：

所有处理 sdshdr 的函数，都必须正确地更新 len 和 free 属性，否则就会造成 bug

优化追加操作

为了易于理解，用一个 Redis 执行实例作为例子，解释一下，当执行以下代码时， Redis 内部发生了什么：

redis> SET msg "hello world"
OK

redis> APPEND msg " again!"
(integer) 18

redis> GET msg
"hello world again!"

首先， SET 命令创建并保存 hello world 到一个 sdshdr 中，这个 sdshdr 的值如下：

struct sdshdr {
    len = 11;
    free = 0;
    buf = "hello world\0";
}

当执行 APPEND 命令时，相应的 sdshdr 被更新，字符串 " again!" 会被追加到原来的 "hello world" 之后：

struct sdshdr {
    len = 18;
    free = 18;
    buf = "hello world again!\0                  ";     // 空白的地方是预分配空间，共 18 + 18 + 1 个字节
}

注意：当调用 SET 命令创建 sdshdr 时， sdshdr 的 free 属性为 0 ，Redis 也没有为 buf 创建额外的空间。而是在执行 APPEND 之后， Redis 为 buf 创建了多于所需空间一倍的大小

在这个例子中， 保存 "hello world again!" 共需要 18 + 1 个字节，但程序却预先分配了 18 + 18 + 1 = 37 个字节

这样一来，如果将来再次对同一个 sdshdr 进行追加操作，只要追加内容的长度不超过 free 属性的值，那么就不需要对 buf 进行内存重分配

比如说，执行以下命令并不会引起 buf 的内存重分配，因为新追加的字符串长度小于 18 ：

redis> APPEND msg " again!"
(integer) 25

再次执行 APPEND 命令之后， msg 的值所对应的 sdshdr 结构可以表示如下：

struct sdshdr {
    len = 25;
    free = 11;
    buf = "hello world again! again!\0           ";     // 空白的地方为预分配空间，共 18 + 18 + 1 个字节
}

sds.c/sdsMakeRoomFor 函数描述了 sdshdr 的这种内存预分配优化策略，以下是这个函数的伪代码版本：

def sdsMakeRoomFor(sdshdr, required_len):

    # 预分配空间足够，无须再进行空间分配
    if (sdshdr.free >= required_len):
        return sdshdr

    # 计算新字符串的总长度
    newlen = sdshdr.len + required_len

    # 如果新字符串的总长度小于 SDS_MAX_PREALLOC
    # 那么为字符串分配 2 倍于所需长度的空间
    # 否则就分配所需长度加上 SDS_MAX_PREALLOC 数量的空间
    if newlen < SDS_MAX_PREALLOC:
        newlen *= 2
    else:
        newlen += SDS_MAX_PREALLOC

    # 分配内存
    newsh = zrelloc(sdshdr, sizeof(struct sdshdr)+newlen+1)

    # 更新 free 属性
    newsh.free = newlen - sdshdr.len

    # 返回
    return newsh

在目前版本的 Redis 中， SDS_MAX_PREALLOC 的值为 \(1024 * 1024\) ：

当小于 \(1MB\) 的字符串执行追加操作时， sdsMakeRoomFor 就为它们分配多于所需大小一倍的空间
当字符串的大小大于 \(1MB\) ，那么 sdsMakeRoomFor 就为它们额外多分配 \(1MB\) 的空间

执行过 APPEND 命令的字符串会带有额外的预分配空间，这些预分配空间不会被释放，除非该字符串所对应的键被删除，或者等到关闭 Redis 之后， 再次启动时重新载入的字符串对象将不会有预分配空间。这种分配策略会浪费内存吗？

因为执行 APPEND 命令的字符串键数量通常并不多， 占用内存的体积通常也不大， 所以这一般并不算什么问题

另一方面，如果执行 APPEND 操作的键很多， 而字符串的体积又很大的话， 那可能就需要修改 Redis 服务器， 让它定时释放一些字符串键的预分配空间， 从而更有效地使用内存

sds 操作API

sds 模块基于 sds 类型和 sdshdr 结构提供了以下 API ：

Table 1: sds API
函数	作用	算法复杂度
sdsnewlen	创建一个指定长度的 sds ，接受一个 C 字符串作为初始化值	O(N)
sdsempty	创建一个只包含空白字符串 "" 的 sds	O(1)
sdsnew	根据给定 C 字符串，创建一个相应的 sds	O(N)
sdsdup	复制给定 sds	O(N)
sdsfree	释放给定 sds	O(N)
sdsupdatelen	更新给定 sds 所对应 sdshdr 结构的 free 和 len	O(N)
sdsclear	清除给定 sds 的内容，将它初始化为 ""	O(1)
sdsMakeRoomFor	对 sds 所对应 sdshdr 结构的 buf 进行扩展	O(N)
sdsRemoveFreeSpace	在不改动 buf 的情况下，将 buf 内多余的空间释放出去	O(N)
sdsAllocSize	计算给定 sds 的 buf 所占用的内存总数	O(1)
sdsIncrLen	对 sds 的 buf 的右端进行扩展（expand）或修剪（trim）	O(1)
sdsgrowzero	将给定 sds 的 buf 扩展至指定长度，无内容的部分用 \0 来填充	O(N)
sdscatlen	按给定长度对 sds 进行扩展，并将一个 C 字符串追加到 sds 的末尾	O(N)
sdscat	将一个 C 字符串追加到 sds 末尾	O(N)
sdscatsds	将一个 sds 追加到另一个 sds 末尾	O(N)
sdscpylen	将一个 C 字符串的部分内容复制到另一个 sds 中，需要时对 sds 进行扩展	O(N)
sdscpy	将一个 C 字符串复制到 sds	O(N)

sds 还有另一部分功能性函数， 比如 sdstolower 、 sdstrim 、 sdscmp ， 等等

基本都是标准 C 字符串库函数的 sds 版本， 这里不一一列举了

小结

Redis 的字符串表示为 sds ，而不是 C 字符串以 \0 结尾的 char*
对比 C 字符串，sds 有以下特性：
- 可以高效地执行长度计算 strlen
- 可以高效地执行追加操作 append
- 二进制安全
sds 会为追加操作进行优化：加快追加操作的速度，并降低内存分配的次数，代价是多占用了一些内存，而且这些内存不会被主动释放

Next: 双向链表

Home: 内部数据结构