redis 学习之字符串

来自于《 Rdis 设计与实现》一书
Redis 没有使用 C 语言传统的字符串表示，而是构建了一种名为简单动态字符串（simple dynamic string, SDS）的抽象类型。我将其理解为一个 struct 结构体。

struct sdshdr {
    int len;    # 记录 buf 数组中已使用字节的数量
    int free;    #记录 buf 数组中未使用字节的数量
    char buf[];    # 字节数组，用于保存字符串
}

顺便说一点，这与 Python 很像，因为 Python 的 len 就是直接在结构体中去取这么一个变量。
为什么要使用这种结构？

• C 语言的字符串在执行拼接操作时，有可能出现缓冲区溢出危险行为。
• 如果需要进行缩短字符串，那么有可能出现内存泄漏，即忘记释放字符串不需要的那部分空间。
  通过未使用空间，SDS 实现了空间预分配和惰性空间释放两种优化策略。

1. 空间预分配

• 当进行字符串扩容时，有一个公式
  如果修改之后 SDS 长度（即 len）小于 1 MB，那么程序间分配和 len 属性同样大小的未使用空间，即 len 属性值和 free 属性值相等。例如，进行修改之后，SDS len 变为 10 字节后，那么 free 也会为 10 字节。buff 总长度为 10+10+1 字节。1字节用来保存空字符。
  如果 SDS 长度大于等于 1 MB，那么程序会分配 1MB 的未使用空间。例如，如果修改之后 len 变为 10 MB，那么 free 会变为 1MB，buf 数组的实际长度为 10MB + 1MB + 1byte。

通过这种预分配策略，SDS 将连续增长N次字符串所需的内存重分配次数从必定N次 降低为最多 N 次。

2. 惰性空间释放
   惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的 字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性 将这些字节的数量记录起来，并等待将来使用。
   通过惰性空间释放策略，SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化。
   但是它也有 API 在有需要时直接释放这些未使用空间。

二进制安全

我们知道 C 字符串以 \0 结尾，这就使得字符串里面不能包含空字符。而 Redis 的 SDS 的 API 都是二进制安全的。它不会对数据做任何限制，过滤，换句话说，读取的就是写入的东西。所以 buf 称为字节数组，用它来保存一系列二进制数据。
这样使得 Redis 不仅可以保存文本数据，而且可以保存任意格式的二进制数据。

兼容部分 C 字符串函数。SDS 的 API 遵循 C 字符串以空字符结尾的惯例。这是为了让 SDS 用来保存文本数据时可以重用 <string.h> 库定义的函数。比如对比两个文本字符串 strcasecmp 和 strcat 等

C 字符串和 SDS 之间的区别.

C 字符串	SDS
获取字符串长度复杂度 O(N)	O(1)
API 是不安全的，可能会造成缓冲区溢出	安全，不会造成溢出
修改字符串长度N次必然需要执行 N 次内存重分配	修改N次最多需要执行 N 次内存重分配
只能保存文本数据	可以保存文本或者二进制数据
可以使用所有<string.h>库中的函数	可以使用一部分<string.h>库中的函数