Redis SDS 的介绍

前言

SDS（简单动态字符串）是 Redis 最基础的数据类型，那 SDS 字符串又是什么呢，为什么 Redis 没有直接使用 C 语言的字符串表示呢，使用 SDS 为什么要比使用 C 语言的字符串效率要高呢

下面就直接来谈一谈这些问题

什么是SDS呢

SDS（simple dynamic string），意为简单动态字符串，是 Redis 的默认字符串表示

C 语言的字符串是使用长度为 N+1 的字符数组来表示长度为 N 的字符串，且最后一个元素总是空字符'\0'（SDS 遵循了 C 字符串以空字符结尾的惯例，也就是说 SDS 最后一个字节保存了空字符'\0'），而 C 语言使用的这种字符串并不能满足 Redis 对字符串在安全性、效率以及功能方面的要求，从而自己构建了 SDS

SDS 有两个版本，这是之前版本的 SDS：

typedef char *sds;

struct sdshdr {
    // 记录buf数组中已使用字节数量，也即是SDS所保存字符串的长度
    unsigned int len;
    // 记录buf数组中未使用字节的数量
    unsigned int free;
    // 字节数组，用于保存字符串
    char buf[];
};
复制代码

当然，这里的 len 属性并没有包含 SDS 结尾的空字符（比如一个带有未使用空间的 SDS）：

SDS 之后的版本是针对不同的长度范围定义了不同的结构，不过大体上结构是相同的：有一个 表示已用长度的 len，一个表示 buf 数组分配长度的 alloc，一个表示 SDS 类型的 flag 以及 字节数组 buf

SDS 与 C 字符串的区别

1.获取字符串长度的时间复杂度

C 字符串并没有记录自身的长度信息，所以为了获取一个 C 字符串的长度，就得遍历整个字符串，所以这样时间复杂度为 O(n)

而对于 SDS 来说，直接访问 len 属性就行，所以 Redis 将获取字符串长度的复杂度从 O(n) 降到了 O(1)

2.杜绝缓冲区溢出

C 字符串没有记录自身长度容易造成缓冲区溢出，比如将一个 C 字符串 src 直接拼接到 另一个字符串 dest 的末尾，如果 dest 没有预先分配足够多的内存，那么就会造成缓冲区溢出

而对于 SDS 来说，因为有 free 这个属性，那么在 执行拼接操作之前就检查长度是否足够，如果可以，就直接拼接，不行的话，就先扩展 SDS 的空间，再拼接

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

使用 C 字符串的话，每次对其进行增长或缩短操作，都需要对这个 C 字符串的数组进行以此内存重分配，比如 C 字符串的拼接，需要先通过内存重分配来扩展底层数组的空间大小以避免缓冲区溢出，又比如 C 字符串的截断，需要通过内存重分配来释放字符串中不在使用的那部分空间以避免内存泄漏

而使用 SDS 就可以通过 len 属性和 free 属性来实现 空间预分配 和 惰性空间释放 两种优化策略

• 空间预分配

空间预分配用于优化 SDS 的字符串增长操作：需要对 SDS 进行空间扩展的时候，不仅会对 SDS 分配修改所必须要的空间，还会为 SDS 分配额外的未使用空间

如果 修改后的 SDS 长度小于 1MB，那么 free 属性的值和 len 属性的值相同

如果 修改后的 SDS 长度大于等于 1MB，那么就会分配 1MB 的未使用空间

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

• 惰性空间释放

惰性空间释放用于优化 SDS 的字符串缩短操作：需要对 SDS 进行缩短操作时，用 free 属性来记录，而不是使用内存重分配来回收多出来的字节

当然，如果有需要，可以借助相应的 API 来真正释放 SDS 的未使用空间

4.二进制安全

C 语言中的字符必须符合某种编码（比如 ASCII），并且字符串里面不能包含空字符，所以使得 C 字符串只能保存文本数据

而 SDS 的 API 都是二进制安全的，都会以处理二进制的方式来处理 SDS 里 buf 数组的数据，所以 SDS 不仅可以保存文本数据，还可以保存任意格式的二进制数据

SDS 的编码方式

字符串对象的编码可以是 int，raw 或者 embstr

如果一个字符串对象保存的是整数值，并且这个整数值可以用 long 类型表示，那么字符串对象会将整数值保存在字符串对象结构的 ptr 属性里（将 void* 转换为 long）：

redis> SET number 666
OK
redis> OBJECT ENCODING number
"int"
复制代码

这里说说 redisObject 结构体

所有的 Redis 对象都有一个 Redis 对象头结构体

不同的对象具有不同的类型 type，同一个类型的 type 会有不同的编码 encoding

每个对象都有个引用计数 refcount，当引用计数为零时，对象就会被销毁，内存被回收。ptr 指针将指向对象内容 (body) 的具体存储位置

struct RedisObject { // 一共占用16字节
    int4 type; // 4bits 类型
    int4 encoding; // 4bits 编码
    int24 lru; // 24bits 记录LRU信息
    int32 refcount; // 4bytes 引用计数
    void *ptr; // 8bytes，64-bit system 
} robj;
复制代码

如果字符串对象保存的是一个字符串值，并且这个字符串值的长度大于39字节，那么字符串对象将使用 SDS 来保存这个字符串值，并将对象的编码设置为 raw：

redis> SET sentence "I was forced to 996 and I just felt tired after work"
OK
redis> STRLEN sentence
(integer) 52
redis> OBJECT ENCODING sentence
"raw"
复制代码

如果字符串对象保存的是一个字符串值，并且这个字符串值得长度小于等于39字节，那么字符串对象将使用 embstr 编码的方式来保存这个字符串值

embstr 是专门用于保存短字符串的一种优化编码方式，相比于 raw 编码会调用两次内存分配函数来分别创建 redisObject 结构和 sdshdr 结构，embstr 编码则通过调用一次内存分配函数来分配一块连续的空间并包含了 redisObject 和 sdshdr 结构

而且 embstr 编码的字符串对象的所有数据都保存在一块连续的内存里，所以能够更好的利用缓存带来的优势

redis> SET msg "hello"
OK
redis> OBJECT ENCODING msg
"embstr"
复制代码

如果要保存一个浮点数到字符串对象里，那么会先将这个浮点数转换为字符串值，然后再保存转换所得的字符串值，如果需要对这个浮点数计算的话，会先将保存在字符串对象里的字符串值转换为浮点数值，执行操作后再将所得的浮点数转换回字符串值并保存在里面

另外， embstr 编码的字符串对象实际上是只读的（因为没有为 embstr 编码的字符串对象写相应的修改程序）如果需要对 embstr 编码的字符串对象执行任何修改命令时，程序会将编码从 embstr 转换为 raw，然后再执行修改命令