Redis 设计与实现,看 SDS(Simple Dynamic String) 感悟
今天在看 Redis 设计与实现这本书的时候,发现了里面系统定义的数据结构 SDS,中文名为 简单动态字符串。对其设计的思想挺有收获的。
SDS 的定义,位于 sds.h/sdshdr 中:结构如下:
struct sdshdr{
// len 为 buf 数组中已使用字节的数量,等于 SDS 所保存的字符串的长度
int len;
// buf 中未使用字节的数量
int free;
// 字节数组,用于保存字符串
char buf[];
}
SDS 与 C 字符串的区别:
- C 语言使用长度为 N+1 的 字符数组来表示长度为 N 的字符串, 并且字符串最后一个元素总为
- C 字符串并不记录自身的长度信息,所以 取长度的操作为 O(N),SDS 的取长度操作为 O(1)
- C 语言容易 缓冲区 溢出,由于其不记录自身长度所带来的。
接下来是关键: **空间预分配 和 惰性空间释放 **这两种优化策略。
空间预分配
主要用于优化 SDS 的字符串增长操作:当 SDS 的API 对一个 SDS 进行修改,并且需要对 SDS 进行空间扩展时,程序不仅会为 SDS 分配修改所需要必须要的空间,还会为 SDS 分配额外未使用的空间。
额外分配的算法如下:
if len < 1MB
free = len;
else
free = 1MB
假设进行修改之后, SDS 的长度 小于 1MB,假设修改之后 SDS 的 len 为 13, 那么 free 也为 13。 SDS 的 buf 长度将为 13 + 13 + 1 。 其中 1 字节 为 "