Redis 中字符串的实现并没有完全使用 C 字符串,而是重新定义了简单动态字符串 SDS(Simple Dynamic String)用来表示字符串(Redis 3.2前)。
sds.h/sdshdr
1struct sdshdr {
2 unsigned int len; // 记录 buf 数组中已使字节的数量
3 unsigned int free; // 记录 buf 数组中未使用字节的数量
4 char buf[]; // 字节数组,用于保存字符串
5};
buf 数组长度不一定就是字符串长度 + 1("\0"),还有 free 空间,数组内未使用的字节通过 free 属性记录。
相比于 C 字符串,SDS 有以下优势:
兼容部分 C 字符串函数
sds.c/sdsnew
1 * mystring = sdsnewlen("abc",3);
2 *
3 * You can print the string with printf() as there is an implicit \0 at the
4 * end of the string. However the string is binary safe and can contain
5 * \0 characters in the middle, as the length is stored in the sds header. */
6sds sdsnewlen(const void *init, size_t initlen) {
7 struct sdshdr *sh;
8
9 if (init) {
10 sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
11 } else {
12 sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
13 }
14 if (sh == NULL) return NULL;
15 sh->len = initlen;
16 sh->free = 0;
17 if (initlen && init)
18 memcpy(sh->buf, init, initlen);
19 sh->buf[initlen] = '\0';
20 return (char*)sh->buf;
21}
22
23/* Create a new sds string starting from a null termined C string. */
24sds sdsnew(const char *init) {
25 size_t initlen = (init == NULL) ? 0 : strlen(init);
26 return sdsnewlen(init, initlen);
从 SDS 的创建逻辑中可以看出
- SDS 遵循 C 字符串以空字符("\0")结尾。
- SDS 中的 len 属性(sds.h/sdslen)同 C 字符串函数 strlen 返回结果相同,即不计算尾部空字符。
这样 SDS 就可以直接重用一部分 C 字符串函数库里面的函数(如打印,显示类函数,<stdio.h>/printf),而字符串的修改操作,则使用 SDS 自定义优化后的函数。
常数复杂度获取字符串长度
C 获取一个 C 字符串的长度,程序必须遍历整个字符串,直到遇到代表字符串结尾的空字符串位置,这个操作的复杂度为 O(N)。
但是对于 SDS 来说,获取字符串长度只需要访问 SDS 中的 len 属性。复杂度仅为 O(1),确保了获取字符串长度这样的高频操作不会成为 Redis 性能瓶颈。
对于 SDS 的修改操作,SDS 会实时维护 len 属性,如 sds.c/sdscat(追加 C 字符串到 SDS 字符串)
1/* Append the specified binary-safe string pointed by 't' of 'len' bytes to the
2 * end of the specified sds string 's'.
3 *
4 * After the call, the passed sds string is no longer valid and all the
5 * references must be substituted with the new pointer returned by the call. */
6sds sdscatlen(sds s, const void *t, size_t len) {
7 struct sdshdr *sh;
8 size_t curlen = sdslen(s);
9
10 s = sdsMakeRoomFor(s,len);
11 if (s == NULL) return NULL;
12 sh = (void*) (s-(sizeof(struct sdshdr)));
13 memcpy(s+curlen, t, len);
14 sh->len = curlen+len;
15 sh->free = sh->free-len;
16 s[curlen+len] = '\0';
17 return s;
18}
19
20/* Append the specified sds 't' to the existing sds 's'.
21 *
22 * After the call, the modified sds string is no longer valid and all the
23 * references must be substituted with the new pointer returned by the call. */
24sds sdscatsds(sds s, const sds t) {
25 return sdscatlen(s, t, sdslen(t));
26}
杜绝缓冲区溢出
C 字符串由于不记录自身长度,对其进行修改操作容易造成缓冲区溢出(buffer overflow)。如 C 字符串拼接函数 <stdio.h>/strcat,内存中相邻的字符串 s1 和 s2,对 s1 字符串做拼接操作时,如果没有提前为 s1 分配足够的空间,则 s2 保存的内容会被意外修改。
SDS 内部维护了一个 free 字段,当 SDS API 需要对其进行修改时,API 会调用 sdsMakeRoomForDS
函数检测当前 SDS 的 free 空间是否满足要求,满足直接进行修改;不满足 sdsMakeRoomForDS
则会将 SDS 的空间扩展至执行修改所需的大小,避免缓冲区溢出的情况(如上方 sds.c/sdscat)。
减少修改字符串长度时所需内存重分配次数
Redis 作为数据库,经常被用于速度要求严苛,数据被频繁修改的场景。SDS 实现了 空间预分配 和 惰性空间释放 两种优化策略。
sds.c/sdsMakeRoomFor
1/* Enlarge the free space at the end of the sds string so that the caller
2 * is sure that after calling this function can overwrite up to addlen
3 * bytes after the end of the string, plus one more byte for nul term.
4 *
5 * Note: this does not change the *length* of the sds string as returned
6 * by sdslen(), but only the free buffer space we have. */
7sds sdsMakeRoomFor(sds s, size_t addlen) {
8 struct sdshdr *sh, *newsh;
9 size_t free = sdsavail(s);
10 size_t len, newlen;
11
12 if (free>= addlen) return s;
13 len = sdslen(s);
14 sh = (void*) (s-(sizeof(struct sdshdr)));
15 newlen = (len+addlen);
16 if (newlen < SDS_MAX_PREALLOC)
17 newlen *= 2;
18 else
19 newlen += SDS_MAX_PREALLOC;
20 newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
21 if (newsh == NULL) return NULL;
22
23 newsh->free = newlen - len;
24 return newsh->buf;
25}
空间预分配
可以发现,在 SDS API 进行字符串新增逻辑中会给 SDS 重新分配 free 空间。
- 如果 SDS 的长度(len 属性)小于
SDS_MAX_PREALLOC(1024KB=1M)
,则会分配和 len 属性同样大小的未使用空间给 buf,这时 SDS 的 len 属性和 free 属性值相同。 - 如果 SDS 长度大于或者等于
SDS_MAX_PREALLOC(1024KB=1M)
,则会直接给 free 属性分配SDS_MAX_PREALLOC(1024KB=1M)
的大小。
通过空间预分配策略,Redis 可以减少连续执行字符串增长操作所需的内存重分配次数.
惰性空间释放
sds.c/sdstrim
1/* Remove the part of the string from left and from right composed just of
2 * contiguous characters found in 'cset', that is a null terminted C string.
3 *
4 * After the call, the modified sds string is no longer valid and all the
5 * references must be substituted with the new pointer returned by the call.
6 *
7 * Example:
8 *
9 * s = sdsnew("AA...AA.a.aa.aHelloWorld :::");
10 * s = sdstrim(s,"A. :");
11 * printf("%s\n", s);
12 *
13 * Output will be just "Hello World".
14 */
15sds sdstrim(sds s, const char *cset) {
16 struct sdshdr *sh = (void*) (s-(sizeof(struct sdshdr)));
17 char *start, *end, *sp, *ep;
18 size_t len;
19
20 sp = start = s;
21 ep = end = s+sdslen(s)-1;
22 while(sp <= end && strchr(cset, *sp)) sp++;
23 while(ep> start && strchr(cset, *ep)) ep--;
24 len = (sp> ep) ? 0 : ((ep-sp)+1);
25 if (sh->buf != sp) memmove(sh->buf, sp, len);
26 sh->buf[len] = '\0';
27 sh->free = sh->free+(sh->len-len);
28 sh->len = len;
29 return s;
30}
可以发现,在进行字符串剪切操作时,多出的 buf 空间并不会直接释放,而是存储在 free 字段中。
同时为了避免内存泄露,SDS 也提供了 sds.c/sdsRemoveFreeSpace 释放 free 空间操作,在 redis.c/clientsCronResizeQueryBuffer 中可以看到,当 querybuf 大于 1024 字节,会进行释放操作。
1/* Reallocate the sds string so that it has no free space at the end. The
2 * contained string remains not altered, but next concatenation operations
3 * will require a reallocation.
4 *
5 * After the call, the passed sds string is no longer valid and all the
6 * references must be substituted with the new pointer returned by the call. */
7sds sdsRemoveFreeSpace(sds s) {
8 struct sdshdr *sh;
9
10 sh = (void*) (s-(sizeof(struct sdshdr)));
11 sh = zrealloc(sh, sizeof(struct sdshdr)+sh->len+1);
12 sh->free = 0;
13 return sh->buf;
14}
15
16/* The client query buffer is an sds.c string that can end with a lot of
17 * free space not used, this function reclaims space if needed.
18 *
19 * The function always returns 0 as it never terminates the client. */
20int clientsCronResizeQueryBuffer(redisClient *c) {
21 size_t querybuf_size = sdsAllocSize(c->querybuf);
22 time_t idletime = server.unixtime - c->lastinteraction;
23
24 /* There are two conditions to resize the query buffer:
25 * 1) Query buffer is > BIG_ARG and too big for latest peak.
26 * 2) Client is inactive and the buffer is bigger than 1k. */
27 if (((querybuf_size> REDIS_MBULK_BIG_ARG) &&
28 (querybuf_size/(c->querybuf_peak+1)) > 2) ||
29 (querybuf_size> 1024 && idletime > 2))
30 {
31 /* Only resize the query buffer if it is actually wasting space. */
32 if (sdsavail(c->querybuf) > 1024) {
33 c->querybuf = sdsRemoveFreeSpace(c->querybuf);
34 }
35 }
36 /* Reset the peak again to capture the peak memory usage in the next
37 * cycle. */
38 c->querybuf_peak = 0;
39 return 0;
40}
二进制安全
SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据(如不以 “\0” 当作字符串结尾),程序不会对其中的数据做任何限制、过滤、或者假设,数据在写入时是什么样的,他被读取时就是什么样子。因此 Redis 可以不仅可以保存文本数据,还可以保存图片、音频、视频、压缩文件这样的二进制数据。