时间轴 分类 标签 关于

Contents

Redis 源码之简单动态字符串

 included in 源码阅读
   2329 words   5 minutes 

Redis 中字符串的实现并没有完全使用 C 字符串，而是重新定义了简单动态字符串 SDS（Simple Dynamic String）用来表示字符串（Redis 3.2前）。

sds.h/sdshdr

1
2
3
4
5

struct sdshdr {
    unsigned int len; // 记录 buf 数组中已使字节的数量
    unsigned int free; // 记录 buf 数组中未使用字节的数量
    char buf[]; // 字节数组，用于保存字符串
};

buf 数组长度不一定就是字符串长度 + 1（"\0"），还有 free 空间，数组内未使用的字节通过 free 属性记录。

相比于 C 字符串，SDS 有以下优势：

兼容部分 C 字符串函数

sds.c/sdsnew

 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

 * mystring = sdsnewlen("abc",3);
 *
 * You can print the string with printf() as there is an implicit \0 at the
 * end of the string. However the string is binary safe and can contain
 * \0 characters in the middle, as the length is stored in the sds header. */
sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;

    if (init) {
        sh = zmalloc(sizeof(struct sdshdr)+initlen+1);
    } else {
        sh = zcalloc(sizeof(struct sdshdr)+initlen+1);
    }
    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;
}

/* Create a new sds string starting from a null termined C string. */
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    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
 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

/* 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);

    s = sdsMakeRoomFor(s,len);
    if (s == NULL) return NULL;
    sh = (void*) (s-(sizeof(struct sdshdr)));
    memcpy(s+curlen, t, len);
    sh->len = curlen+len;
    sh->free = sh->free-len;
    s[curlen+len] = '\0';
    return s;
}

/* Append the specified sds 't' to the existing sds 's'.
 *
 * 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. */
sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

杜绝缓冲区溢出

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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/* Enlarge the free space at the end of the sds string so that the caller
 * is sure that after calling this function can overwrite up to addlen
 * bytes after the end of the string, plus one more byte for nul term.
 *
 * Note: this does not change the *length* of the sds string as returned
 * by sdslen(), but only the free buffer space we have. */
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;
    else
        newlen += SDS_MAX_PREALLOC;
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);
    if (newsh == NULL) return NULL;

    newsh->free = newlen - len;
    return newsh->buf;
}

空间预分配

可以发现，在 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
 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

/* 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;
    while(sp <= end && strchr(cset, *sp)) sp++;
    while(ep> start && strchr(cset, *ep)) ep--;
    len = (sp> ep) ? 0 : ((ep-sp)+1);
    if (sh->buf != sp) memmove(sh->buf, sp, len);
    sh->buf[len] = '\0';
    sh->free = sh->free+(sh->len-len);
    sh->len = len;
    return s;
}

可以发现，在进行字符串剪切操作时，多出的 buf 空间并不会直接释放，而是存储在 free 字段中。

同时为了避免内存泄露，SDS 也提供了 sds.c/sdsRemoveFreeSpace 释放 free 空间操作，在 redis.c/clientsCronResizeQueryBuffer 中可以看到，当 querybuf 大于 1024 字节，会进行释放操作。

 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

/* Reallocate the sds string so that it has no free space at the end. The
 * contained string remains not altered, but next concatenation operations
 * will require a reallocation.
 *
 * 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 sdsRemoveFreeSpace(sds s) {
    struct sdshdr *sh;

    sh = (void*) (s-(sizeof(struct sdshdr)));
    sh = zrealloc(sh, sizeof(struct sdshdr)+sh->len+1);
    sh->free = 0;
    return sh->buf;
}

/* The client query buffer is an sds.c string that can end with a lot of
 * free space not used, this function reclaims space if needed.
 *
 * The function always returns 0 as it never terminates the client. */
int clientsCronResizeQueryBuffer(redisClient *c) {
    size_t querybuf_size = sdsAllocSize(c->querybuf);
    time_t idletime = server.unixtime - c->lastinteraction;

    /* There are two conditions to resize the query buffer:
     * 1) Query buffer is > BIG_ARG and too big for latest peak.
     * 2) Client is inactive and the buffer is bigger than 1k. */
    if (((querybuf_size> REDIS_MBULK_BIG_ARG) &&
         (querybuf_size/(c->querybuf_peak+1)) > 2) ||
         (querybuf_size> 1024 && idletime > 2))
    {
        /* Only resize the query buffer if it is actually wasting space. */
        if (sdsavail(c->querybuf) > 1024) {
            c->querybuf = sdsRemoveFreeSpace(c->querybuf);
        }
    }
    /* Reset the peak again to capture the peak memory usage in the next
     * cycle. */
    c->querybuf_peak = 0;
    return 0;
}

二进制安全

SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据（如不以 “\0” 当作字符串结尾），程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，他被读取时就是什么样子。因此 Redis 可以不仅可以保存文本数据，还可以保存图片、音频、视频、压缩文件这样的二进制数据。

SDS API

https://img.aladdinding.cn/sdsapi.png
SDS API
Updated on 2021-11-05
 Redis
Back | Home