- 本文对Redis源码的学习是基于5.0.2版本.
前言
Redis并没有直接沿用C字符串,而是自己构建了一种名为简单动态字符串(Simple Dynamic Strings,SDS).
SDS --- (源文件sds.h/sds.c)
SDS的多种结构体 : 根据字符串长度来使用不同的结构体,其中 sdshdr5 比其他结构体少了两个属性,具体下面再分析.
typedef char *sds;
1 << 5 = 32 : 表示低于32长度则使用该结构体
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; 类型,3bit位表示类型,剩下5bit没有其他占用,下面的其他结构体一样表示该作用
char buf[]; 字符数组,以'\0'结尾
};
1 << 8 = 256
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; // 字符串长度
uint8_t alloc; // 分配的总长度
unsigned char flags;
char buf[];
};
1 << 16
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};
1 << 32
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len;
uint32_t alloc;
unsigned char flags;
char buf[];
};
1 << 64
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len;
uint64_t alloc;
unsigned char flags;
char buf[];
};
# flags类型如以下 :
#define SDS_TYPE_5 0 //长度小于 1<<5 即32，类型为SDS_TYPE_5
#define SDS_TYPE_8 1 // ...
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
结构体属性如下图 :
创建 --- sdsnew
了解字符串的创建过程,我们有必要先了解SDS在内存中的总体结构,如下图 :
PS : 上图的alloc、len属性占用的是4字节,复制的时候忘记改了
sdsnew()
# sdsnew()
sds sdsnew(const char *init) {
1. // 计算传进去的字符串长度
size_t initlen = (init == NULL) ? 0 : strlen(init);
2. 最终调用 sdsnewlen()来分配内存
return sdsnewlen(init, initlen);
}
sdsnewlen()
# sdsnewlen()
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
1. // 根据字符串长度获取结构体类型,该函数下面会分析
char type = sdsReqType(initlen);
// SDS_TYPE_5类型的结构体 且 为空字符串的情况下使用 SDS_TYPE_8类型的结构体
// 解析 : 空字符串通常是为了追加而创建的;
// 使用 SDS_TYPE_8 是因为 SDS_TYPE_5 不擅长这个
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
2. // 根据结构体类型申请头部字节占用的大小
int hdrlen = sdsHdrSize(type);
3. // flags指针,即类型
unsigned char *fp;
4. // 申请内存 : header + string + \0
sh = s_malloc(hdrlen+initlen+1);
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
5. // 初始化
memset(sh, 0, hdrlen+initlen+1);
if (sh == NULL) return NULL;
// 向右移动hdrlen偏移,s指针用于字符串内存的内存复制
s = (char*)sh+hdrlen;
// 回退1就是flags , 与之对应的s[-1] 也是flags
fp = ((unsigned char*)s)-1;
6. // 根据type来设置 len、alloc、type
switch(type) {
6.1 // 上面说到 sdshdr5 比较特殊
// sdshdr5 的 flags的 高5bit位存放着len 低3bit位存放着type
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
6.2 // 设置len、alloc、type,下面的都是一样的
case SDS_TYPE_8: {
// 使用相对应的结构体
SDS_HDR_VAR(8,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
}
7. // 设置完len、alloc、type后复制字符串到指定的内存中
if (initlen && init)
7.1. // 将字符串复制到s指针位置
memcpy(s, init, initlen);
8. // 最后设置 \0
s[initlen] = '\0';
return s;
}
SDS_TYPE_5 和其他类型的区别 :
sdsnew()创建字符串的指针 :
sdsReqType()
根据字符串长度获取结构体类型 :
tatic inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5;
if (string_size < 1<<8)
return SDS_TYPE_8;
if (string_size < 1<<16)
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
sdsHdrSize()
根据结构体类型计算Header占用的字节 :
static inline int sdsHdrSize(char type) {
switch(type&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return sizeof(struct sdshdr5);
case SDS_TYPE_8:
return sizeof(struct sdshdr8);
case SDS_TYPE_16:
return sizeof(struct sdshdr16);
case SDS_TYPE_32:
return sizeof(struct sdshdr32);
case SDS_TYPE_64:
return sizeof(struct sdshdr64);
}
return 0;
}
拼接C字符串 --- sdscat
sdscat()
sdscat() : 将C字符串拼接到SDS字符串末尾,注意是 C字符串.
# sdscat()
sds sdscat(sds s, const char *t) {
// 最终调用sdscatlen()
return sdscatlen(s, t, strlen(t));
}
sdscatlen()
# sdscatlen()
sds sdscatlen(sds s, const void *t, size_t len) {
1. // 获取sds的字符串长度
size_t curlen = sdslen(s);
2. // 检查是否需要扩容
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
3. // 把 C字符串拼接(拷贝)到sds中
memcpy(s+curlen, t, len);
4. // 保存len
sdssetlen(s, curlen+len);
5. // 保存 \0
s[curlen+len] = '\0';
return s;
}
sdsMakeRoomFor()
该函数会检查是否需要扩容 :
- ①检查当前sds剩余空间是否够用 :
- 够用 : 直接什么都不做,返回;
- 不够用 : 扩容操作
- ②扩容操作 : 根据拼接后的字符串长度来判断如何扩容
- 如果拼接后的字符串长度小于1M,则在拼接后的字符串长度基础上乘2倍;
- 如果拼接后的字符串长度大于1M,则在拼接后的字符串长度基础上加1M;
- ③扩容完成,需要根据拼接后的字符串长度来计算的结构体是否发生变化来设置len、flags、alloc :
- 如果没有发生变化,则在原有的结构体上重新分配内存就好了【s_realloc()】;
- 如果发生变化,则需要重新申请新的内存【s_malloc()】,重新申请新的内存后,sds的字符串需要重新拷贝到新的内存中【memcpy()】,然后回收原先扩容前的结构体内存【s_free()】;
- 保存最新的len、flags、alloc
# sdsMakeRoomFor()
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
1. // 获取当前sds还有多少剩余可使用的空间
size_t avail = sdsavail(s);
size_t len, newlen;
// s[-1] 与之对应的是flags : flags & SDS_TYPE_MASK 得到的是之前的 结构体类型
char type, oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
2. // 如果sds的剩余可使用空间足够供给拼接的C字符串使用,那么无需扩容了,直接返回
if (avail >= addlen) return s;
# 需要扩容操作
3. // 获取sds字符串长度
len = sdslen(s);
4. // 向右移动sdsHdrSize(oldtype)偏移
sh = (char*)s-sdsHdrSize(oldtype);
5. // 计算拼接完后最新长度
newlen = (len+addlen);
6. // 如果拼接字符串后的长度小于 1M,则扩容为 拼接字符串后的长度的2倍
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
6.1 // 否则 是 拼接字符串后的长度的基础上 加 1M
newlen += SDS_MAX_PREALLOC;
7. // 获取最新的type
type = sdsReqType(newlen);
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
8. // 重新计算Header长度
hdrlen = sdsHdrSize(type);
9. // 如果扩容后结构体保持不变
if (oldtype==type) {
9.1 // 尝试重新调整之前调用 malloc 或 calloc 所分配的 sh 所指向的内存块的大小
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
9.2 // s指向操作字符串的偏移位置
s = (char*)newsh+hdrlen;
} else {
10. // 扩容后结构体发生变化
10.1 // 重新申请内存
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
10.2 // 把sds的字符串(包括 \0)拷贝到最新申请的newsh
memcpy((char*)newsh+hdrlen, s, len+1);
10.3 // 释放之前的结构体的内存
s_free(sh);
10.4 // s指向操作字符串的偏移位置
s = (char*)newsh+hdrlen;
10.5 // 保存最新的flags
s[-1] = type;
10.6 // 保存最新的len
sdssetlen(s, len);
}
11. // 保存最新的alloc
sdssetalloc(s, newlen);
12. // 返回sds
return s;
}
拼接SDS --- sdscatsds()
与之对应类似的是拼接SDS,调用的是相同的sdscatlen()
# sdscatsds()
sds sdscatsds(sds s, const sds t) {
return sdscatlen(s, t, sdslen(t));
}
为了控制博客篇幅,这里只讲解了创建、拼接 两个函数,很多API的源码我都没有贴上来(毕竟太多).
SDS与C字符串的区别
C字符串并不能满足Redis对字符串在安全性、效率以及功能方面的要求,所以Redis没有选择使用C字符串,而是自己构建了SDS,接下来我们来看看两者之间的区别.值得注意的是,C字符串与SDS的最后一个元素总是空字符 '\0' .
常数复杂度获取字符串长度
C字符串并不记录自身的长度信息,所以为了获取一个C字符串的长度,需要遍历整个字符串,对遇到的每个字符进行计数,直到遇到字符串结尾的空字符为止,这个操作的复杂度为O(N).而Redis的SDS获取字符串长度的操作复杂度只需要O(1).
社绝缓冲区溢出
C字符串容易造成缓冲区溢出,而SDS的空间分配策略完全社绝了缓冲区溢出.由上面 sdscat() 知识点可以知道,在执行拼接字符串之前会进行检查SDS剩余空间是否足够,如果不够则进行扩容.
二进制安全
C字符串除了末尾之外,不能包含空字符,否则最先被读入的空字符会被误认为是字符串末尾,这个限制导致C字符串只能保存文本数据,而不能保存图片、视频、音频、压缩文件等这样的二进制数据.而SDS不仅可以保存文本数据,也可以保存二进制数据.
兼容部分C字符串函数
SDS遵循C字符串结尾的惯例,这是为了让那些保存文本数据的SDS可以重用一部分 <string.h> 库定义的函数,从而避免了不必要的代码重复.
SDS常用API
| 函数 | 作用 | 时间复杂度 |
|---|---|---|
| sdsnew | 创建一个包含给定C字符串的SDS | O(N),N为给定C字符串的长度 |
| sdsempty | 创建一个不包含任何内容的空SDS | O(1) |
| sdsfree | 释放给定的SDS | O(N),N为释放SDS的长度 |
| sdslen | 返回SDS的已使用空间的长度 | O(1),这个值可以通过len属性直接获取 |
| sdsavail | 返回SDS的未使用空间的长度 | O(1),这个值可以通过avail属性 减去 len属性 |
| sdsdup | 创建一个给定SDS的副本(copy) | O(N),N为给定SDS的长度 |
| sdsclear | 清空SDS保存的字符串内容 | O(1),懒惰性空间释放策略 |
| sdscat | 将给定C字符串拼接到SDS字符串的末尾 | O(N),N为C字符串的长度 |
| sdscatsds | 将给定SDS字符串拼接到另一个SDS字符串的末尾 | O(N),N为被拼接SDS字符串的长度 |
| sdscpy | 将给定的C字符串复制到SDS,覆盖原有SDS的字符串 | O(N),N为被复制C字符串的长度 |
| sdsgrowzero | 用空字符串将SDS扩展至给定的长度 | O(N),N扩展新增的长度 |
| sdsrange | 保留SDS给定区间内的数据,不在区间内的数据会被覆盖或清除,类似于Java的substring | O(N),N为保留数据的长度 |
| sdstrim | 接受一个SDS和C字符串作为参数,从SDS中移除所有在C字符串中出现过的字符 | O(N^2),N为给定C字符串的长度 |
| sdscmp | 对比两个SDS字符串是否相同 | O(N),N为两个SDS中较短的那个SDS的长度 |
结束语
- 原创不易
- 希望看完这篇文章的你有所收获!
相关参考资料
- Redis设计与实现【书籍】