【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）这两种操作：

• 每次计算字符串长度（strlen(s)）的复杂度为 θ(N)。
• 对字符串进行 N 次追加，必定需要对字符串进行 N 次内存重分配（realloc）。

在 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字符串的优点☆☆☆：

四、SDS对内存的优化策略

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

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

• 如果 len 属性值小于 1M，那么分配的未使用空间 free 的大小与 len 属性值相同。
• 如果 len 属性值大于等于 1M ，那么分配的未使用空间 free 的大小固定是 1M。

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

五、SDS模块的API

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

本文仅供学习参考！