关于redis:Redis设计与实现之简单动态字符串

简略动静字符串

什么是 SDS

SDS，即 Simple Dynamic String，简略动静字符串。

Redis 没有间接应用 C 语言传统的字符串示意（以空字符结尾的字符数组），而是本人构建了一种名为简略动静字符串（simple dynamic string，SDS）的形象类型，并将 SDS 用作 Redis 的默认字符串示意。

在 Redis 外面，C 字符串只会作为字符串字面量（string literal）用在一些 毋庸对字符串值进行批改的中央，比方打印日志。

当 Redis 须要的不仅仅是一个字符串字面量，而是一个能够被批改的字符串值时，Redis 就会应用 SDS 来示意字符串值，比方在 Redis 的数据库外面，蕴含字符串值的 键值 对在底层都是由 SDS 实现的。

SDS 的定义

在 SDS 构造中蕴含：

• buf：字节数组，用于保留字符串
• len：记录 buf 数组中已应用的字节数，等于 SDS 保留的字符串长度
• free：记录 buf 数组中未应用字节的数量

举例：

• len 属性的值等于 5，示意在 SDS 中保留了一个五字节长度的字符串
• free 属性的值等于 0，示意在 SDS 中没有调配任何未应用的空间
• buf 属性是一个 char 数组，前五位保留了五个字符，在最初一个字节保留了一个空字符 ’\0′

须要留神的是：SDS 遵循 C 字符串以空字符结尾的常规，保留空字符的 1 字节空间并不计算在 SDS 的 len 属性中，并且调配这额定的 1 字节空间，以及增加空字符到字符串开端等操作，都是由 SDS 函数主动实现的。

方才展现了 free 为 0 的状况，而存在未应用空间的时候则如下图，咱们还是应用“Redis”字符串。

SDS 与 C 字符串的区别

方才咱们说过 C 语言应用长度为 N+1 的字符数组来示意长度为 N 的字符串，并且字符数组的最初一个元素总是空字符 ’\0’。

这种简略的字符串示意形式，并不能满足 Redis 对字符串的安全性、效率以及性能上的要求。咱们接下来比照一下 SDS 和 C 字符串之间的区别。

常数复杂度获取字符串长度

首先 C 字符串并不记录本身的长度信息，要是想获取 C 字符串长度，则必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到结尾标识符 ’\0’ 为止。复杂度为 O(N)。

而 SDS 不同，SDS 中的 len 属性记录了 SDS 自身的长度，所以获取 SDS 字符串长度的复杂度仅仅为 O(1)。

须要留神的是，设置和更新 SDS 长度的工作是由 SDS 的 API 在执行的时候主动实现的。

应用 SDS 将获取字符串长度从复杂度 O(N)升高到了 O(1)，确保了在 Redis 中获取字符串长度不会成为性能瓶颈。

杜绝缓冲区溢出

除了获取字符串长度的复杂度高之外，C 字符串不记录本身长度带来的另一个问题就是容易造成缓冲区溢出。

举个例子，在 string.h 中 strcat 函数能够将 src 字符串中的内容拼接到 dest 字符串的开端。

char *strcat(char *dest, const char *src);

因为 C 字符串不记录本身长度，如果没有为 dest 调配足够多的内存来容下 src 字符串的所有内容的话，则会产生缓冲区溢出。

📢 须要留神，如果内存中相邻 s1，s2 两个字符串，如果在批改 s1 字符串的时候没有调配足够的空间，可能会导致溢出到 s2 字符串所在的内存空间，导致 s2 字符串被篡改。

而 SDS 不同，SDS 的 空间调配策略 齐全杜绝了产生缓冲区溢出的可能。在对 SDS 进行批改的时候，API 首先会查看是否满足所需的要求，如果不满足则会主动进行扩容，而后再进行批改。

举例：

如上图，这时候咱们执行

sdscat(s,"Cluster");

首先在拼接之前会进行检测以后 s 的长度是否足够，发现不足以拼接 ” Cluster” 后，进行扩容，随后进行拼接，如下图所示。

📢 须要留神：SDS 不仅仅进行了拼接操作，还另外调配了 13 字节的未应用空间，上面咱们会理解 SDS 的空间调配策略。

缩小批改字符串时带来的内存重调配次数

咱们方才说过，C 字符串是不记录字符串长度的，所以在减少或缩短一个字符串时，都要进行内存重调配操作。

• 如果执行的是增长字符串操作，比方 append，那么在操作前须要通过内存重调配策略来扩大底层数组的大小，如果遗记这一步，则会产生缓冲区溢出
• 如果执行的是缩短字符串操作，比方 trim，那么在执行这个操作后须要进行内存重调配来开释不再应用的空间，如果遗记这一步，则会产生内存透露

为了防止 C 字符串的这种缺点，SDS 通过未应用空间 free 解除了字符串长度与底层数组长度之间的关联，在 SDS 中，buf 数组的长度并不一定是字符数量加一，还可能蕴含未应用字节。

通过未应用空间 free，SDS 实现了空间预调配和惰性空间开释两种优化策略。

1. 空间预调配

顾名思义，SDS 在进行扩大的时候，不仅仅会为 SDS 调配批改所必要的空间，还会为 SDS 调配额定的未应用空间。

闲暇空间调配策略：

• 在批改之后，如果 SDS 的长度 len 小于 1MB，那么就会给 free 调配和 len 一样大小的未应用空间。即len = free
• 在批改之后，如果 SDS 的长度 len 大于等于 1MB，那么就会给 free 调配 1MB 的闲暇空间，比方 SDS len 为 30MB，那么就会调配 1MB 未应用空间给 free，此时 buf 数组长度为 30MB+1MB+1byte

通过这种预调配策略，SDS 将间断增长 N 次的字符串所需内存操作次数从必然 N 次缩小到了最多 N 次。

2. 惰性空间开释

在进行缩短字符串操作时，SDS 并不会立刻应用内存重调配来进行回收多余的空间，而是应用 free 进行记录，在后续如果进行增长操作的时候，就可能不须要再进行扩容。SDS 也提供了 API，来进行开释 SDS 未应用的空间。

二进制平安

咱们晓得 C 字符串开端是空字符示意，在两头是不能蕴含空字符，否则会被认为是字符结尾。并且须要合乎某种编码（比方 ASCII），导致 C 字符串只能保留文本数据，无奈保留图片、视频等二进制数据。

SDS 的 API 都是二进制平安的，程序并不会对数据进行任何解决，写入时是什么样子，读取时候就是什么样子，而且在 SDS 中是能够蕴含空字符，因为 SDS 中是应用 len 来判断字符串是否完结。

然而为什么 SDS 开端还是会有一个空字符？这是为了能够重用 <string.h> 中的局部函数，防止不必要的代码反复。

总结