【Redis】关于Redis数据结构简单动态字符串(SDS)的一些杂记

【Redis】关于Redis数据结构“简单动态字符串(SDS)”的一些杂记

推荐几篇关于SDS数据结构讲解较为详细的文章：

一、简单动态字符串 — Redis 设计与实现 (redisbook.readthedocs.io)

二、深入理解Redis之简单动态字符串 - itbsl - 博客园 (cnblogs.com)

三、Redis内部数据结构详解(2)——sds - 铁蕾的个人博客 (zhangtielei.com)

四、简单动态字符串 — Redis 设计与实现 (redisbook.readthedocs.io)

一、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 。

二、字符串对象

Redis 是一个键值对数据库（key-value DB）， 数据库的值可以是字符串、集合、列表等多种类型的对象， 而数据库的键则总是字符串对象。对于那些包含字符串值的字符串对象来说， 每个字符串对象都包含一个 sds 值。

注意：

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

例如，以下命令创建了一个新的键值对，该键值对的键和值都是字符串对象，他们都包含一个sds值：

127.0.0.1:6379> set school "HeFeiUniversity"
OK
127.0.0.1:6379> get school
"HeFeiUniversity"
127.0.0.1:6379>

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

127.0.0.1:6379> sadd nosql "MongoDB" "Redis" "Neo4j"
(integer) 3
127.0.0.1:6379> smembers nosql
1) "Neo4j"
2) "Redis"
3) "MongoDB"
127.0.0.1:6379>

三、Redis字符串与C字符串的区别

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

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

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

在 Redis 内部， 字符串的追加和长度计算很常见， 而 APPEND 和 STRLEN 更是这两种操作，在 Redis 命令中的直接映射， 这两个简单的操作不应该成为性能的瓶颈。

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

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

和C字符串不，因为SDS在len属性中记录了SDS本身的长度，所以获取一个SDS长度的复杂度为O(1)。

通过使用SDS而不是C字符串，Redis将获取字符串长度所需的复杂度从O(N)降低到了O(1)，这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。所以，即使我们对一个非常长的字符串反复执行STRLEN命令，也不会对系统性能造成任何影响，因为STRLEN命令的复杂度仅为O(1)。

SDS相对于传统C字符串的优点☆☆☆：

C字符串 SDS
获取字符串长度的复杂度为 O(N) 获取字符串长度的复杂度为 O(1)
操作字符串函数不安全，可能造成缓冲区溢出 安全的操作字符串API，避免缓冲区溢出
修改字符串长度 N 次必然需要执行 N 次内存重分配 修改字符串长度 N 次最多需要执行 N 次内存重分配
只能保存文本数据 可以保存文本以及图片、音频、视频、压缩文件这样的二进制数据。

四、SDS对内存的优化策略

SDS采用了空间预分配策略与惰性空间释放策略来避免内存分配问题。

空间预分配策略是指，每次 SDS 进行空间扩展时，程序不但为其分配所需的空间，还会为其分配额外的未使用空间，以减少内存再分配次数。而额外分配的未使用空间大小取决于空间扩展后SDS 的 len 属性值。

SDS 对于空间释放采用的是惰性空间释放策略。该策略是指，SDS 字符串长度如果缩短，那么多出的未使用空间将暂时不释放，而是增加到 free 中。以使后期扩展 SDS 时减少内存 再分配次数。如果要释放 SDS 的未使用空间，则可通过 sdsRemoveFreeSpace()函数来释放。

五、SDS模块的API

sds 模块基于 sds 类型和 sdshdr 结构提供了以下 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)

本文仅供学习参考！

标签 , ,

发表回复