Redis- 简单动态字符串

Redis 没有直接使用 C 语言传统的字符串，而自己构建了一种简单动态字符串（Simple Dynamic String）的抽象类型，简称为 SDS。并将 SDS 作为 Redis 的默认字符串表示。

例如：当我们在 redis-client 执行如下的命令时;

> redis 127.0.0.1:6379>set message 'Hello World'
> 
> OK

那么 Redis 将会在数据库中创建一个新的键值对，其中：

• 键值对的键是一个字符串对象，对象底层的实现是一个保存着字符串“msg”的 SDS。
• 键值对的值也是一个字符串对象，对象底层的实现是一个保存着字符串“Hello World”的 SDS。

SDS 的定义

每个 sds.h/sdshdr 结构表示一个 SDS 值：

struct sdshdr{

 int len; //记录buf中已使用字节的数量等于SDS所保存的字符串的长度

 int free; //记录buf中未使用字节的长度

 char []buf; //字节数据，保存字符串

}

获取字符串的长度

Redis 获取字符串长度可以通过 SDS 中的 len 属性来获得，时间复杂度为 O(1)。而 C 语言获取字符串需要去遍历 char 数据来叠加获得，时间复杂度为 O(n)。这就保证了在获取字符串长度时不会成为 Redis 的性能瓶颈。

杜绝缓存区溢出

除了获取字符串长度复杂度高之外，C 语言不记录自身字符串长度带来的另一个问题是容易造成缓存区溢出（Buffer Overflow）。SDS 属性 len 可以记录自身字符串的长度，因此当对 SDS 字符串进行拼接时，SDS API 会先去检测 buf 的空间，如果空间不足，SDS 先会扩容 buf 的空间，之后进行拼接。反之，直接去拼接。

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

• 空间预分配

空间预分配用于优化 SDS 字符串增长操作，当 SDS 的 API 对 SDS 的字符串进行修改，并且要对 SDS 进行空间扩展的时候，程序不仅会为 SDS 分配修改所必须要的空间，还会为 SDS 分配额外未使用的空间。分配公式主要有 SDS 中的 len 属性的大小决定。当 len 属性值小于 1MB 时，buf 数组的实际长度为 len(修改后的 len 值)*2+1byte，这时 len 和 free 相等，一个字节用于保存空字符。当 len 属性值大于 1MB 时，buf 数组的实际长度为 len(修改后的 len 值)+1MB+1byte，这时 free 的值为 1MB。通过内存预分配策略，Redis 可以减少连续执行字符串增长操作所需要的内存重分配次数。

• 惰性空间释放

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

二进制安全

由于 SDS 是通过 len 属性来判断字符串是否结束的，而不是使用空字符串来判断字符串是否结束的，并且 SDS 的 API 都是二进制安全的，所有的 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组中的数据，程序不会对数组中的数据进行任何的过滤，限制，假设，数据在写入和读出的时候是一致的。

兼容部分 C 字符串函数

虽然 SDS API 是二进制安全的，但它依然遵循 C 字符串以空字符结尾的惯例。

总结

SDS API