Redis 数据结构（一）字符串

SDS 是在 Redis 中被广泛使用的字符串结构，它的全称是 Simple Dynamic String。

内容来只《Redis设计与实现》和其他网络资料，Redis3.0源码-注释版

SDS的定义

redis-3.0-annotated/src/sds.h

typedef char *sds;
struct sdshdr {
    // buf 中已占用空间的长度
    int len;
    // buf 中剩余可用空间的长度
    int free;
    // 数据空间
    char buf[];
};

SDS与C字符串的区别

C 语言使用长度为 N+1 的字符数组来表示长度为 N 的字符串，并且字符数组的最后一个元素总是空字符 '\0'，C 语言使用的这种简单的字符串表示方式，并不能满足 Redis 对字符串在安全性、效率、以及功能方面的要求

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

C 字符串并不记录自身的长度信息，所以为了获取一个 C 字符串的长度，程序必须遍历整个字符串，对遇到的每个字符进行计数，直到遇到代表字符串结尾的空字符为止。

SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为 O(1)

杜绝缓冲区溢出

C 字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow）。

修改两个相邻的字符串的时候，需要修改前一个没有重新分配内存就有可能覆盖后一个字符串的内容。

SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当 SDS API 需要对 SDS 进行修改时， API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话， API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，所以使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出问题。

减少修改字符串时带来的内存重分配次数

C 字符串底层是一个字符数组，每次增长或者缩短一个 C 字符串，程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作，无论是增加、拼接、截取都得先通过内存重分配来扩展底层数组的空间大小，否则就可能造成溢出的情况

SDS空间预分配

内存重分配涉及复杂的算法，并且可能需要执行系统调用是一个比较耗时的操作。SDS通过空间预分配的方式来减少系统调用从而加快执行的速度。

当 SDS 的 API 对一个 SDS 进行修改，并且需要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间

额外分配的未使用空间数量由以下公式决定

如果对SDS进行修改之后，SDS的长度（也即是 len 属性的值）将小于1 MB，那么程序分配和 len 属性同样大小的未使用空间，这时SDS的len属性的值将和 free 属性的值相同。
举个例子，如果进行修改之后， SDS 的 len 将变成 13 字节，那么程序也会分配 13 字节的未使用空间， SDS 的 buf 数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）
如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ，那么程序会分配 1 MB 的未使用空间。
举个例子，如果进行修改之后， SDS 的 len 将变成 30 MB ，那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。

SDS是二进制安全的

C字符串中的字符必须符合某种编码（比如 ASCII），并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

SDS使用 len 属性的值而不是空字符来判断字符串是否结束，因此SDS的API都是二进制安全的（binary-safe）。