前言

Redis 3.0 内部的基础数据结构有 6 种:SDS, List, Dict, Intset, SkipList, ZipList,Redis 系列笔记将从结构定义、操作 API 和优缺点三个角度去分析,同时画图示意、简述逻辑,力求分析到位。本节从 SDS 开始


SDS 定义

全称 Simple Dynamic String(简单动态字符串),是 Redis 对 C 原生字符串的封装,结构如下:

1
2
3
4
5
6
typedef char *sds; // sds 是 char* 类型别名
struct sdshdr { // sds 元信息 header
int len; // 已用字节数,即 buf 中有效字符串的长度,是读写操作的安全边界
int free; // 剩余可用字节数
char buf[]; // sds 指向的字符数组
};

buf字段:未指定长度的柔性数组(Flexible Array),C99 引入的不完整类型,为保证内存连续性只能是最后一个字段,且不能是唯一字段;其长度并不计入sdshdr空间,需在运行时指定长度分配内存后才能引用

内存布局:初始化为 “Redis” 的 sds

image-20190919175541169

验证:

1
2
3
4
5
6
sds sds = sdsnew("Redis");
int *f = (void *) (sds - sizeof(int));
int *l = (void *) (sds - sizeof(struct sdshdr));
size_t *prefixSize = (void*)((char *) l - sizeof(size_t));
printf("len:%d, free:%d\n", *l, *f); // 5,0
printf("prefix:%zu, used_memory:%zu\n", *prefixSize, zmalloc_used_memory()); // 14,24

SDS API

1. 初始化

sdsnewlen:拷贝指定长度的字面量字符串,分配内存生成 sds

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
sds sdsnewlen(const void *init, size_t initlen) {
struct sdshdr *sh;

if (init) {
sh = zmalloc(sizeof(struct sdshdr)+initlen+1); // 尾部多分配 1 字节存 \0,对调用方透明
} else {
sh = zcalloc(sizeof(struct sdshdr)+initlen+1); // 创建新 sds 并零初始化
}
if (sh == NULL) return NULL;
sh->len = initlen;
sh->free = 0;
if (initlen && init)
memcpy(sh->buf, init, initlen); // 内存拷贝
sh->buf[initlen] = '\0';
return (char*)sh->buf; // 将分配的堆内存解释为 char* 即 sds
}

2. 扩缩容

sdsclear:更新元信息标记 sds 数据无效,等待覆盖写或内存释放

1
2
3
4
5
6
void sdsclear(sds s) {
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
sh->free += sh->len;
sh->len = 0; // 标记脏数据不可用
sh->buf[0] = '\0'; // 直接截断
}

sdsMakeRoomFor:在现有字符串之上,再分配 addlen 个字节。采用了内存预分配策略,类似操作系统读文件的 pre-read,因为 sds 扩容意味着之后很可能会继续增长,能将分配操作的时间复杂度均摊到多次调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define SDS_MAX_PREALLOC (1024*1024)
sds sdsMakeRoomFor(sds s, size_t addlen) {
struct sdshdr *sh, *newsh;
size_t free = sdsavail(s);
size_t len, newlen;

if (free >= addlen) return s;
len = sdslen(s);
sh = (void*) (s-(sizeof(struct sdshdr)));
newlen = (len+addlen); // 扩容后需使用的字节数
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2; // <1MB 翻倍扩容
else
newlen += SDS_MAX_PREALLOC; // >=1MB 递增 1MB 可控扩容

// 旧 sh->buf 尾部的 \0 也计入了 newlen,需 +1
newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
if (newsh == NULL) return NULL;
newsh->free = newlen - len;
return newsh->buf; // 扩容后地址已变,需更新使用返回值
}

3. 整型转换

sdsll2str:将长整型转为字符串写入 sds;算法:从低位到高位逐个对 10 取余,再对称翻转,处理好负号

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
// 用 s 保存的 long long 最长为 ULONG_LONG_MAX+\0,即 20+1 字节
#define SDS_LLSTR_SIZE 21
int sdsll2str(char *s, long long value) {
char *p, aux;
unsigned long long v;
size_t l;

// 从低到高对 10 取余得位数
v = (value < 0) ? -value : value;
p = s;
do {
*p++ = '0'+(v%10); // 数字转 ASCII 码
v /= 10;
} while(v);
if (value < 0) *p++ = '-';

l = p-s;
*p = '\0'; // 额外的 1 字节手动截断

// 翻转字符串:向内对称 swap
p--;
while(s < p) {
aux = *s;
*s = *p;
*p = aux;
s++;
p--;
}
return l;
}

4. 格式化

sdscatvprintf:复用vsnprintf将格式化的字符串写入 sds;trick:由于绝大多数格式化后字符串都少于 1KB,其先尝试用栈内存上的char staticbuf[1024]来存储格式化后的字符串,若溢出才分配堆内存

sdscatfmt:自定义简化版格式化逻辑的高性能sdscatvprintf;算法:逐个遍历格式化字符串,根据%??指示,对参数进行字符串内存拷贝、整型转 sds 等操作,累积追加到 sds 后返回

5. trim 与截断

sdstrim:从 sds 的前后缀中删掉在字符集中出现的任何字符;算法:左右向内strchr检测并定位终止索引

sdsrange:将 sds 截断为指定左右索引的闭合区间;算法:先处理负数边界,再做越界检测,区间索引都合法后才移动内存并截断

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
void sdsrange(sds s, int start, int end) {
struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
size_t newlen, len = sdslen(s);

if (len == 0) return;
// 1. 负边界处理及索引重置
if (start < 0) {
// 细节:负索引 ni 从 -1 开始,len 长度比正索引多 1,相加正好抵消使 ni 正好是从 1 开始倒数的序号
start = len+start;
if (start < 0) start = 0;
}
if (end < 0) {
end = len+end;
if (end < 0) end = 0;
}
// 2. 越界检测
// 截断操作仅需两个参数:start 定位区间起始索引,newlen 决定区间长度
newlen = (start > end) ? 0 : (end-start)+1;
if (newlen != 0) {
if (start >= (signed)len) {
newlen = 0; // start 越界则清空 sds
} else if (end >= (signed)len) {
end = len-1; // end 越界则重置为最后一个字符
newlen = (end-start)+1;
}
} else {
start = 0;
}
if (start && newlen) memmove(sh->buf, sh->buf+start, newlen); // 内存移动
sh->buf[newlen] = 0; // 手动截断
sh->free = sh->free+(sh->len-newlen);
sh->len = newlen;
}

6. 子串分割

sdssplitlen:将 sds 按子串分割,返回 sds 数组

  • 算法:逐个遍历字符,试探性做内存比较,若匹配则拷贝前一区间右边界到当前字符的子串
  • trick:由于子串数组长度不可知,故从 5 开始翻倍增长,避免频繁地重分配内存
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
sds *sdssplitlen(const char *s, int len, const char *sep, int seplen, int *count) {
int elements = 0, slots = 5, start = 0, j;
sds *tokens;
if (seplen < 1 || len < 0) return NULL;

tokens = zmalloc(sizeof(sds)*slots);
if (tokens == NULL) return NULL;
if (len == 0) {
*count = 0;
return tokens;
}
// 逐个字符遍历
// 注意边界只到倒数第 seplen-1 个字符,还不匹配则无需再向后对比
for (j = 0; j < (len-(seplen-1)); j++) {
// elements 为下一个子串索引,+2 是为下一个子串、最后一个子串预留空间
if (slots < elements+2) {
sds *newtokens;
slots *= 2;
newtokens = zrealloc(tokens,sizeof(sds)*slots);
if (newtokens == NULL) goto cleanup;
tokens = newtokens; // 翻倍扩容
}
// 尝试从 j 处开始完整匹配
if ((seplen == 1 && *(s+j) == sep[0]) || (memcmp(s+j,sep,seplen) == 0)) {
// 上一子串右边界 start 到 j 为一个子串
tokens[elements] = sdsnewlen(s+start,j-start);
if (tokens[elements] == NULL) goto cleanup;
elements++;
// start 跳过此子串,为右边界
start = j+seplen;
// 下次循环会 j++,故此处 -1
j = j+seplen-1;
}
}
// 追加最后一个子串,内存已预分配
tokens[elements] = sdsnewlen(s+start,len-start);
if (tokens[elements] == NULL) goto cleanup;
elements++;
*count = elements;
return tokens;
cleanup: // ...
}

SDS 优点

1. O(1) 获取字符串长度

  • 原生字符串:strlen操作需遍历,复杂度为O(N)

  • sds:字段sds->len动态维护了 sds 的有效字符串长度,直接读取复杂度O(1)

    1
    2
    3
    4
    static inline size_t sdslen(const sds s) {
    struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr)));
    return sh->len;
    }

2. 避免缓冲区溢出

  • 原生:多个操作依赖用户保证内存有效性,比如strcpydst未分配足够内存,则会造成内存溢出

  • sds:操作前都会检查其大小是否足够,不够则对调用方透明地扩容,避免溢出

3. 二进制安全

  • 原生:以'\0'作为字符串尾部分隔符,无法直接保存内部包含字符 0 的数据

  • sds:由sds->len指示安全边界;但 sds 的部分 API 依旧会在尾部插入'\0'以复用 string.h 标准库函数

4. 内存预分配与惰性释放

  • 原生:每次增长都要 realloc
  • sds:扩容时的内存预分配均摊了操作复杂度,清空时并不释放内存而是等待重用写覆盖

总结

Redis 封装 C 原生字符串为 SDS,动态维护free, len等元信息,以此实现了一套高效操作 API;在设计上用空间换时间的思想,降低了大量高频操作的复杂度,均摊了内存分配的复杂度;在实现上也有性能优化的 trick,如格式化时尽量先使用栈内存、子串分割时堆内存的翻倍预分配等,都值得学习