Redis学习笔记（１）——数据结构与对象

简单动态字符串 SDS(simple dynamic string)

简介

Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串），而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型，并将 SDS 用作 Redis 的默认字符串表示。

/*
 * 保存字符串对象的结构
 */
struct sdshdr {

    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

空间预分配

空间预分配用于优化 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 。

通过空间预分配策略， Redis 可以减少连续执行字符串增长操作所需的内存重分配次数。

惰性空间释放

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

二进制安全

SDS 的 API 都是二进制安全的（binary-safe）：所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设 —— 数据在写入时是什么样的，它被读取时就是什么样。（为了确保 Redis 可以适用于各种不同的使用场景）通过使用二进制安全的 SDS ，而不是 C 字符串，使得 Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据。

SDS API

函数	作用	时间复杂度
sdsnew	创建一个包含给定 C 字符串的 SDS 。	O(N) ， N 为给定 C 字符串的长度。
sdsempty	创建一个不包含任何内容的空 SDS 。	O(1)
sdsfree	释放给定的 SDS 。	O(1)
sdslen	返回 SDS 的已使用空间字节数。	这个值可以通过读取 SDS 的 len 属性来直接获得，复杂度为 O(1) 。
sdsavail	返回 SDS 的未使用空间字节数。	这个值可以通过读取 SDS 的 free 属性来直接获得，复杂度为 O(1) 。
sdsdup	创建一个给定 SDS 的副本（copy）。	O(N) ， N 为给定 SDS 的长度。
sdsclear	清空 SDS 保存的字符串内容。	因为惰性空间释放策略，复杂度为 O(1) 。
sdscat	将给定 C 字符串拼接到 SDS 字符串的末尾。	O(N) ， N 为被拼接 C 字符串的长度。
sdscatsds	将给定 SDS 字符串拼接到另一个 SDS 字符串的末尾。	O(N) ， N 为被拼接 SDS 字符串的长度。
sdscpy	将给定的 C 字符串复制到 SDS 里面，覆盖 SDS 原有的字符串。	O(N) ， N 为被复制 C 字符串的长度。
sdsgrowzero	用空字符将 SDS 扩展至给定长度。	O(N) ， N 为扩展新增的字节数。
sdsrange	保留 SDS 给定区间内的数据，不在区间内的数据会被覆盖或清除。	O(N) ， N 为被保留数据的字节数。
sdstrim	接受一个 SDS 和一个 C 字符串作为参数，从 SDS 左右两端分别移除所有在 C 字符串中出现过的字符。	O(M*N) ， M 为 SDS 的长度， N 为给定 C 字符串的长度。
sdscmp	对比两个 SDS 字符串是否相同。	O(N) ， N 为两个 SDS 中较短的那个 SDS 的长度。

重点

Redis 只会使用 C 字符串作为字面量，在大多数情况下， Redis 使用 SDS （Simple Dynamic String，简单动态字符串）作为字符串表示。

比起 C 字符串， SDS 具有以下优点：

常数复杂度获取字符串长度。
杜绝缓冲区溢出。
减少修改字符串长度时所需的内存重分配次数。
二进制安全。
兼容部分 C 字符串函数。

参考

《Redis 设计与实现》
http://redisbook.com/index.html