-
Notifications
You must be signed in to change notification settings - Fork 4
Redis源码阅读笔记之字符串
在redis中,字符串(String)是由一个结构体SDS(Simple Dynamic String)组成,不仅字符串使用SDS,它也可以用于缓冲区:AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区都是由SDS组成的。其结构图如下:
其源码如下所示:
/*
* 类型别名,用于指向 sdshdr 的 buf 属性
*/
typedef char *sds;
/*
* 保存字符串对象的结构
*/
struct sdshdr {
// buf 中已占用空间的长度
int len;
// buf 中剩余可用空间的长度
int free;
// 数据空间
char buf[];
};
/*
* 返回 sds 实际保存的字符串的长度
*
* T = O(1)
*/
static inline size_t sdslen(const sds s) {
//sdshdr的大小等于len+free+buf=4+4+buf,而buf=len+free+1('\0'C语言字符串结束符)
//一个SDS结构体的大小等于SDS=buf+size(free)+size(len)=buf+8=len+free+9(刚开始没有创建字符串时len=0,free=0)
//减去结构体本身的大小剩下的为实际保存的字符串的长度
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->len;
}
/*
* 返回 sds 可用空间的长度
*
* T = O(1)
*/
static inline size_t sdsavail(const sds s) {
struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
return sh->free;
}
C语言获取字符串长度的时间复杂度为O(N),SDS获取字符串长度的时间复杂度为O(1)。
C语言在字符串拼接的时候有可能会缓冲区溢出,而SDS API会在拼接字符串时先检查是否有可用空间,如果没有会进行分配然后拼接,因此防止了缓冲区溢出。
C语言如果一个字符串要追加内容就需要扩容,重新分配足够的空间,否则会缓冲区溢出;如果要缩短一个字符串,必须释放空闲的空间,即也要进行空间重新分配,否则就会内存泄漏。
而空间内存的重新分配涉及到复杂的内存处理算法,如果这样频繁的进行操作对于性能的影响十分大,况且redis进行高效的读写,修改频繁,因此,redis防止重新内存频繁分配,使用了空间预分配和惰性分配策略。
空间预分配
对于频繁的字符串追加内容的操作,redis使用空间预分配策略,有以下两种情况:
1.如果修改后的字符串小于SDS_MAX_PREALLOC(1MB),则将分配len(使用空间的大小)大小的空间给free作为未使用的空间进行预分配。最终的SDS的大小为2*len+1(字符串以'\0'结尾)。
// 根据新长度,为 s 分配新空间所需的大小
if (newlen < SDS_MAX_PREALLOC)
// 如果新长度小于 SDS_MAX_PREALLOC
// 那么为它分配两倍于所需长度的空间
newlen *= 2;
2.如果修改后的字符串大小大于SDS_MAX_PREALLOC(1MB),则分配1MB的空间给free进行预分配,即最终返回的SDS大小为len+1MB+1。
else
// 否则,分配长度为目前长度加上 SDS_MAX_PREALLOC
newlen += SDS_MAX_PREALLOC;
惰性分配
对于字符串缩减的操作,为了避免重复的回收空间,redis在对字符串进行缩减操作之后会利用free来保存释放的空间大小,而不是去回收它,为下一次字符串追加操作做空间的预分配。SDS API也提供了相应的API在我们真正需要回收内存时对内存进行释放,因此不必担心会空间浪费。
源码如下所示:
/*
* 对 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;
}
/*
* 将长度为 len 的字符串 t 追加到 sds 的字符串末尾
*
* 返回值
* sds :追加成功返回新 sds ,失败返回 NULL
*
* 复杂度
* T = O(N)
*/
/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
* end of the specified sds string 's'.
*
* After the call, the passed sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call. */
sds sdscatlen(sds s, const void *t, size_t len) {
struct sdshdr *sh;
// 原有字符串长度
size_t curlen = sdslen(s);
// 扩展 sds 空间
// T = O(N)
s = sdsMakeRoomFor(s,len);
// 内存不足?直接返回
if (s == NULL) return NULL;
// 复制 t 中的内容到字符串后部
// T = O(N)
sh = (void*) (s-(sizeof(struct sdshdr)));
memcpy(s+curlen, t, len);
// 更新属性
sh->len = curlen+len;
sh->free = sh->free-len;
// 添加新结尾符号
s[curlen+len] = '\0';
// 返回新 sds
return s;
}
在C语言字符串中,遵循ASCII编码格式,即除了末尾的'\0'外,在其他任何地方出现'\0'都会被误认为是字符串的结束符,因此C语言字符串只能存储一些文件数据,对于一些图片,音频等二进制数据不能存储,为了避免这一缺点,redis使用SDS API来保证二进制数据的安全,不会去改变字符串的内容。
可以使用<string.h>库中的部分函数来对字符串进行比较,拼接等操作。
在这些API中,需要注意:
sdsclear函数清空字符串内容时使用的是惰性删除。源码如下:
void sdsclear(sds s) {
// 取出 sdshdr
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
// 重新计算属性
sh->free += sh->len;
sh->len = 0;
// 将结束符放到最前面(相当于惰性地删除 buf 中的内容)
sh->buf[0] = '\0';
}
sdstrim函数对SDS两端的内容进行修剪
/*
* 对 sds 左右两端进行修剪,清除其中 cset 指定的所有字符
*
* 比如 sdsstrim(xxyyabcyyxy, "xy") 将返回 "abc"
*
* 复杂性:
* T = O(M*N),M 为 SDS 长度, N 为 cset 长度。
*/
/* Remove the part of the string from left and from right composed just of
* contiguous characters found in 'cset', that is a null terminted C string.
*
* After the call, the modified sds string is no longer valid and all the
* references must be substituted with the new pointer returned by the call.
*
* Example:
*
* s = sdsnew("AA...AA.a.aa.aHelloWorld :::");
* s = sdstrim(s,"A. :");
* printf("%s\n", s);
*
* Output will be just "Hello World".
*/
sds sdstrim(sds s, const char *cset) {
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
char *start, *end, *sp, *ep;
size_t len;
// 设置和记录指针
sp = start = s;
ep = end = s+sdslen(s)-1;
// 修剪, T = O(N^2)
//strchr函数用来查找某字符在字符串中首次出现的位置
while(sp <= end && strchr(cset, *sp)) sp++;
while(ep > start && strchr(cset, *ep)) ep--;
// 计算 trim 完毕之后剩余的字符串长度
len = (sp > ep) ? 0 : ((ep-sp)+1);
// 如果有需要,前移字符串内容
// T = O(N)
if (sh->buf != sp) memmove(sh->buf, sp, len);
// 添加终结符
sh->buf[len] = '\0';
// 更新属性
sh->free = sh->free+(sh->len-len);
sh->len = len;
// 返回修剪后的 sds
return s;
}