深入理解Redis SDS原理

SDS

在 Redis 并没有直接使用 C 中的字符串，而是用一种称为 SDS（Simple Dynamic String）的结构体来保存字符串。

例如：执行命令 set key value，key 和 value 都是一个 SDS 类型的结构存储在内存中。

除了用作默认的字符串表示外，SDS 还被用作缓冲区（buffer），比如 AOF 缓冲区和客户端中的输入缓冲区。

sds

struct sdshdr {
    // buf数组中已使用字节数
    // 等于SDS中保存字符串的长度
    int len;
    // buf数组中未使用字节数
    int free;
    // 字节数组，用于保存字符串
    char buf[];
};

SDS 遵循 C 字符串以"\0" 结尾的惯例，最后一个保存空字符串的 1 字节空间不计算在 len 中。

常数时间复杂度 O(1) 内获得字符串长度：C 字符串本身不记录长度信息，每次获取长度信息都需要遍历整个字符串，复杂度为 O(n)。SDS 中的 len 字段保存着字符串的长度，所以能直接获取字符串的长度。
避免缓冲区溢出：假如内存中存在紧挨着的两个 C 字符串，在对前一个字符串进行修改后没有进行内存重新分配，此时前者可能就会覆盖后面的字符串。但在 SDS 中，如果要对 SDS 进行修改，Redis 会首先检查空间是否足够，若不充足则会分配新空间，避免了缓冲区溢出问题。
减少字符串修改时带来的内存重新分配次数：在 C 中，当频繁的对一个字符串进行修改（append 或 trim）操作的时候，需要频繁的进行内存重新分配的操作，十分影响性能。SDS 通过未使用空间解除了字符串长度和底层数据之间的关联。
二进制安全：C 字符串中的字符必须必须符合某种编码，且除了末尾之外，不能包含空字符串。而 SDS 的 API 都是二进制安全的，所有 SDS API 都会以处理二进制的方式来处理 buf 数组中的后数据，数据在写入时是什么样的，读出来时也是什么样。
兼容部分 C 字符串函数：由于 SDS 遵循 C 字符串以"\0" 结尾的惯例，使得 SDS 可以重用一部分库中的函数。

为了减少字符串修改时带来的内存重新分配次数，SDS 实现了空间预分配和惰性空间释放两种优化策略：

空间预分配：用于优化 SDS 的字符串增长操作。当 SDS 的 API 对一个 SDS 修改后，并且对 SDS 空间扩充时，程序不仅会为 SDS 分配所需要的必须空间，还会分配额外的未使用空间。通过空间预分配策略，Redis 可以减少连续执行字符串增长所需的内存重分配次数。
惰性空间释放：用于优化 SDS 的字符串缩短操作。当对 SDS 进行缩短操作时，程序并不会回收多余的内存空间，而是使用 free 字段将这些字节数量记录下来不释放，后面如果需要 append 操作，则直接使用 free 中未使用的空间，减少了内存的分配。

sds