Redis 源码之简单动态字符串

Redis 中字符串的实现并没有完全使用 C 字符串

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 的创建逻辑中可以看出

  1. SDS 遵循 C 字符串以空字符("\0")结尾。
  2. 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 空间。

  1. 如果 SDS 的长度(len 属性)小于 SDS_MAX_PREALLOC(1024KB=1M),则会分配和 len 属性同样大小的未使用空间给 buf,这时 SDS 的 len 属性和 free 属性值相同。
  2. 如果 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 可以不仅可以保存文本数据,还可以保存图片、音频、视频、压缩文件这样的二进制数据。

SDS API

Licensed under CC BY-NC-SA 4.0