简单动态字符串
初识动态字符串
redis没有直接使用C语言传统的字符串表示(以空字符结尾的字符数组),而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS作为redis的默认字符串表示。
在redis中,c字符串只会作为字符串字面量用在一些无须对字符串值进行修改的地方,比如日志。当Redis需要的不仅仅是一个字符串字面量,而是一个可以被修改的字符串值时,redis就会使用SDS来表示字符串值。
值的注意的是,对于redis中的key都是使用SDS来实现的。此外,SDS除了用来保存Redis数据库中的字符串值之外,SDS还被用作缓冲区(buffer): AOF模块中的AOF缓冲区,以及客户端状态中的输入缓冲区。sds的结构
1
2
3
4
5
6
7
8struct sdshdr{
// 记录buf数组中已使用字节的数量等价于sds所保存字符串的长度
int len;
// 记录buf数组中未使用字节的数量
int free;
// 字节数组,用于保存字符串
char buf[];
}注意:
sds遵循c字符串以空字符结尾的惯例,保存空字符的1字节空间不计算在sds的len属性中,并且为空字符分配额外的1字节空间,以及添加空字符到字符串末尾等操作,都是由sds函数自动完成的。遵循空字符结尾的好处是,sds可以直接使用一部分C字符串函数库里面的函数。
sds与c字符串的区别
c语言使用的简单字符串表示方式,并不能满足redis对字符串在安全性、效率以及功能方面的要求。
3.1 常数复杂度获取字符串长度
因为c字符串并不记录自身的长度信息,所以要获取长度就必须遍历整个字符串,故获取字符串长度的复杂度为O(N)。而redis的sds结构中通过len属性记录了sds的长度,故获取字符串长度的复杂度为O(1)。注意,设置和更新sds长度的工作是由sds的API在执行时自动完成的,使用sds无须进行任何手动修改长度的操作。
3.2 避免缓冲区溢出
c字符串不记录自身长度,很容易造成缓冲区溢出。与c字符串不同,sds的空间分配策略完全杜绝了发生缓冲区溢出的可能性,当sds api需要对sds进行修改时,api会先检查sds的空间是否满足需要,如果不满足的话,api会自动将sds的空间扩展至执行所需的大小,然后才执行实际的修改操作,因此使用sds既不需要手动修改sds的空间大小,也不会出现c字符串中可能出现的缓冲区溢出问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);
//追加时先进行扩容,后面详细说明
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
//拼接字符串
memcpy(s+curlen, t, len);
sdssetlen(s, curlen+len);
s[curlen+len] = '\0';
return s;
}
// s:原数组
//strlen(t) 需拼接的目标数组的长度
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
3.3 内存分配与释放
因为c字符串的长度和底层数组的长度之间存在着关联性,所以
每次增加或者缩短一个c字符串,程序都总要对保存这个c字符串的数字进行一次分配操作
,但是内存分配操作涉及到复杂的算法,并且可能需要执行系统调用,所以通常是一个比较耗时的操作。redis作为数据库,经常被用于速度要求严苛、数据被频繁修改的场合,为了避免c字符串的这种缺陷,sds通过未使用空间解除了字符串长度和底层数组长度之间的关联,通过未使用空间,sds实现了空间预分配和惰性空间释放两种优化策略。空间预分配
空间预分配用于优化sds的字符串增长操作:当sds的api对一个sds进行修改,并且需要对sds进行空间扩展的时候,程序不仅会为sds分配修改所必须要的空间,还会为sds分配额外的未使用空间。通过空间预分配策略,redis可以减少连续执行字符串增长操作所需的内存重新分配次数,在扩展sds空间之前,sds api 会先检查未使用空间是否足够,如果足够就直接使用未使用空间,而不需要执行内存重新分配。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52// redis 扩容源码
/*
* 对 sds 中 buf 的长度进行扩展,确保在函数执行之后,
* buf 至少会有 addlen + 1 长度的空余空间
* (额外的 1 字节是为 \0 准备的)
*
* 返回值
* sds :扩展成功返回扩展后的 sds
* 扩展失败返回 NULL
*
* 复杂度
* T = O(N)
*/
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
// 获取 s 目前的空余空间长度
size_t free = sdsavail(s);
size_t len, newlen;
// s 目前的空余空间已经足够,无须再进行扩展,直接返回
if (free >= addlen) return s;
// 获取 s 目前已占用空间的长度
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
// s 最少需要的长度
newlen = (len+addlen);
// 根据新长度,为 s 分配新空间所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC
// 那么为它分配两倍于所需长度的空间
newlen *= 2;
else
// 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
// T = O(N)
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
// 内存不足,分配失败,返回
if (newsh == NULL) return NULL;
// 更新 sds 的空余长度
newsh->free = newlen - len;
// 返回 sds
return newsh->buf;
}额外分配未使用空间数量的计算策略:
- 对sds修改后,sds的长度(即len属性的值)小于1MB,那么程序分配和len属性同样大小的未使用空间,这时sds的len属性的值将和free属性的值相同。例如:修改后sds的len变成10字节,那么程序也会分配10字节的未使用空间,sds的buf数组的实际长度:10 + 10 + 1 = 21字节
- 对sds修改后,sds的长度大于等于1MB,那么程序会分配1MB的未使用空间。例如:修改后sds的len变成30MB,那么程序会分配1MB的未使用空间,sds的buf数组的时间长度:30MB + 1MB + 1byte
惰性空间释放
惰性空间释放用于优化sds的字符串缩短操作:当sds的api需要缩短sds保存的字符串时,程序并不立即使用内存重分配来回收缩短后多来的字节,而是使用free属性将这些字节的数量纪录起来,用于将来对sds进行增长操作时,这些未使用空间可能就派上用场了。注意,sds也提供了相应的api,可以真正地释放sds的未使用空间,所以不用担心惰性空间释放策略会造成内存浪费。
3.4 二进制安全
c字符串中的字符必须符合某种编码,并且除了字符串的末尾之外,字符串里不能包含空字符,否则在读取的时候会被默认为结束字符,这些限制使得c字符串只能保存文本数据,不能保存图片、音视频、压缩文件这类的二进制数据。sds的api都是二进制安全的,所有的sds api都会以
二进制的方式处理sds存放在buf数组里的数据
,程序不会对其中的数据做任何限制、过滤,数据写入时是什么样,它被读取时就是什么样。这也是将sds的buf属性称为字节数组的原因,redis不是用这个数组来保存字符,而是用它来保存一系列二进制数据
。c字符串和sds之间的区别
1
2
3
4
5
6C字符串 SDS
- 获取字符串长度的复杂度为O(n) 获取字符串长度的复杂度O(1)
- API是不安全的,可能造成缓冲区溢出 API是安全的
- 修改字符串长度N次,必然要执行N次内存重分配 修改字符长度N次,最多执行N次内存重分配
- 只能保存文本数据 可以保存文本或者二进制数据
- 可使用<string.h>库中的函数 可使用一部分<string.h>库中的函数sds更多的api可参考源码