Redis 并没有直接使用 C 语言传统的字符串表示,而是自己构建了简单动态字符串(SDS),并作为 Redis 的默认字符串表示。
当 Redis 需要的不仅仅是一个字面量,而是一个可以被修改的字符串值时,就会使用 SDS 来表示字符串值。
2.1 SDS 的定义
在sds.h
中有结构体sdshdr
,表示一个 SDS 值:
struct sdshdr{
//记录buf数组中已使用字节的数量,等于SDS保存的字符串长度
int len;
//记录buf数组中未使用字节的数量
int free;
//字节数组,用于保存字符串
char buf[];
};
最后一个字节保存的**'\0'**
不计算在 SDS 的 len 属性中。
2.2 SDS 与 C 字符串的区别
2.2.1 常数复杂度获取字符串长度
C 字符串本身并不记录自身的长度信息,所以获取 C 字符串的长度需要遍历整个字符串——O(N);SDS 在 len 属性中记录了 SDS 本身的长度——O(1)。
设置和更新 SDS 长度的工作是由 SDS 的 API 在执行时自动完成的。
2.2.2 杜绝缓冲区溢出
C 字符串不记录自身长度的另一个问题就是容易造成缓冲区溢出,strcat()
实现拼接功能,它假定用户在执行该函数时分配了足够多的内存,可以容纳拼接过来的所有内容。而一旦这个假定不成立,就会造成缓冲区溢出。
SDS 的空间分配策略杜绝了缓冲区溢出的可能:当 SDS API 需要对 SDS 进行修改时,API 会先检查 SDS 空间是否满足修改所需的要求,如果不满足,API 会自动扩展空间至所需大小,然后才执行实际修改操作。
2.2.3 减少修改字符串时带来的内存重分配次数
Redis 作为数据库,速度要求严苛,如果每次修改字符串的长度都要执行一次内存重分配的话,那么性能会损失。SDS 通过未使用空间(free
属性)解除了字符串长度和底层数组长度之间的关联:buf 数组的长度不一定就是字符数量加一,数组中可以包含未使用的字节,这些字节的数量就是free
属性。
SDS 通过未使用空间实现了两种优化策略:空间预分配和惰性空间。
空间预分配:用于优化 SDS 的字符串增长操作,不仅会分配修改所必须要的空间,还会分配额外的未使用空间。额外分配的未使用空间数量有两种策略:
- 若对 SDS 修改后,SDS 长度将小于 1MB,那么分配和 len 属性同样大小的未使用空间;
- 若对 SDS 修改后,SDS 长度将大于 1MB,那么分配 1MB 大小的未使用空间。
惰性空间释放:用于优化 SDS 字符串缩短操作,当 API 需要缩短字符串时,程序并不立刻回收,而是使用
free
属性记录起来,等待将来使用。不过也有对应的 API 用于真正释放并回收未使用空间。
2.2.4 二进制安全
所有 API 都会以处理二进制的方式处理 SDS 存放在 buf 数组中的数据。因为 SDS 使用len
属性值而不是'\0'
来判断字符串是否结束。