简单动态字符串
#Redis#源码剖析 2025-02-18

结构体

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
typedef char *sds;

/* Note: sdshdr5 从未被使用过 */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

#define SDS_TYPE_5  0
#define SDS_TYPE_8  1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4

示意图：

image20250218122020595.png

alloc - len 就等于还有多少空闲空间，可用来存储数据。

由于已经记录字符串的长度，可以通过 O(1) 时间复杂度获取字符串长度。

__attribute__ ((__packed__)) 避免结构体内存对齐，Redis 选择牺牲一部分性能，节省内存。

image20250218122800584.png

Redis 的字符串经过这样设计，不仅可以存储字符串型的数据，还可以存储二进制数据。原生字符串是通过末尾的\0判断字符串的结束，但是这样就让二进制数据无法存储，因为你不确定字符串哪里是完整的部分。但现在我们通过 len 成员就可以避免这个问题，实现二进制数据存储。

创建字符串

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/* 创建一个新的 sds 字符串，内容由 `init` 指针和 `initlen` 指定。
 * - 如果 `init` 传入 NULL，则字符串初始化为空（填充 0）。
 * - 如果 `init` 传入 SDS_NOINIT，则不初始化 buffer（提高性能）。
 */
sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) {
    void *sh; // 指向 sds 结构头部的指针
    sds s;    // 指向 sds 数据部分（字符串数据）的指针
    char type = sdsReqType(initlen); // 计算所需的 sds 类型
    
    /* 空字符串通常用于后续追加，因此选择 SDS_TYPE_8 而不是 SDS_TYPE_5 */
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    
    int hdrlen = sdsHdrSize(type); // 计算 sds 头部大小
    unsigned char *fp; // 指向 flags（类型标识符）的位置
    size_t usable; // 可用的分配空间大小

    /* 分配内存（带 usable 空间计算），trymalloc 决定是否使用非失败分配 */
    sh = trymalloc ?
        s_trymalloc_usable(hdrlen + initlen + 1, &usable) :
        s_malloc_usable(hdrlen + initlen + 1, &usable);
    if (sh == NULL) return NULL; // 分配失败返回 NULL

    /* 根据 SDS_NOINIT 规则决定是否清空已分配内存 */
    if (init == SDS_NOINIT)
        init = NULL; // 直接使用未初始化的 buffer
    else if (!init)
        memset(sh, 0, hdrlen + initlen + 1); // 清零整个 sds 结构（头部 + 数据）

    /* 计算 sds 数据部分的起始地址 */
    s = (char*)sh + hdrlen;
    fp = ((unsigned char*)s) - 1; // `flags` 字节位于数据起始地址之前
    usable = usable - hdrlen - 1; // 计算可用数据空间

    /* 限制分配的 usable 大小，防止超出 sds 允许的最大容量 */
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);

    /* 根据 sds 类型填充结构体头部 */
    switch (type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS); // 5 位存储 len
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8, s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16, s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32, s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64, s);
            sh->len = initlen;
            sh->alloc = usable;
            *fp = type;
            break;
        }
    }

    /* 如果提供了初始化数据，则拷贝到 sds 数据区域 */
    if (initlen && init)
        memcpy(s, init, initlen);
    
    /* 确保 sds 结尾是 `\0`，保证 printf 可用 */
    s[initlen] = '\0';

    return s; // 返回指向 sds 数据部分的指针
}

核心步骤：

  1. 确定 SDS 类型
  2. 分配内存，内存大小为 头部长度（不同SDS类型对应的结构体大小）+申请长度+1（填充空字符）
  3. 根据 SDS_NOINIT 规则决定是否清空已分配内存
  4. 初始化 SDS 结构体
  5. 如果提供了初始化数据，则拷贝到 sds 数据区域
  6. 最后，返回字符串的起始地址（不是SDS 结构体的起始地址哦）

释放字符串

1
2
3
4
void sdsfree(sds s) {
    if (s == NULL) return;
    s_free((char*)s-sdsHdrSize(s[-1]));
}

sdsfree 会确确实实调用 free 回收内存，但 Redis 还提供 sdsclear 操作来通过重新设置 len 来假装释放掉字符串对应的内存空间。

1
2
3
4
void sdsclear(sds s) {
    sdssetlen(s, 0);
    s[0] = '\0';
}

拼接字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
sds sdscatsds(sds s, const sds t) {
    return sdscatlen(s, t, sdslen(t));
}

/* 该函数会修改原来的 sds 字符串，并返回新的字符串指针。
 * 调用后，传入的原 sds 字符串不再有效，所有对其的引用必须替换为调用返回的新指针。
 */
sds sdscatlen(sds s, const void *t, size_t len) {
    size_t curlen = sdslen(s);

    // 为扩展空间申请足够的内存
    s = sdsMakeRoomFor(s, len);
    if (s == NULL) return NULL;
    memcpy(s + curlen, t, len);
    sdssetlen(s, curlen + len);

    // 确保字符串的结尾是 NULL 终止的
    s[curlen + len] = '\0';
    return s;
}

如果扩容，申请足够的内存之后，就会把原数据拷贝到新空间，并且把要拼接的数据也拼接到后面，返回给用户新指针。

因此，重点看看 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/* 扩展 SDS 字符串末尾的空闲空间，确保调用该函数后，可以在字符串的末尾覆盖最多 addlen 字节，
 * 还会为末尾的 null 终止符保留一个字节。
 * 如果已经有足够的空闲空间，则该函数不会进行任何操作。如果空间不足，将为剩余空间分配内存，可能还会多分配一些：
 * - 当 greedy 为 1 时，将会分配超过需求的空间，避免频繁的重新分配。
 * - 当 greedy 为 0 时，仅分配足够的空间以容纳 'addlen' 字节。
 *
 * 注意：此函数仅修改 SDS 字符串的空闲缓冲区空间，而不改变 `sdslen()` 返回的字符串长度。*/
sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) {
    void *sh, *newsh;
    size_t avail = sdsavail(s);  // 当前字符串末尾的可用空间
    size_t len, newlen, reqlen;
    char type, oldtype = s[-1] & SDS_TYPE_MASK;  // 获取当前字符串的类型
    int hdrlen;  // 存储头部大小
    size_t usable;  // 可用内存

    /* 如果已经有足够的空闲空间，直接返回原始字符串 */
    if (avail >= addlen) return s;

    len = sdslen(s);  // 获取当前字符串的长度
    sh = (char*)s - sdsHdrSize(oldtype);  // 获取字符串实际的内存地址（减去头部大小）
    reqlen = newlen = (len + addlen);  // 计算新的总长度
    assert(newlen > len);  // 检查是否有溢出

    /* 如果 greedy 为 1，表示需要更大程度地扩展内存，以避免频繁的重新分配 */
    if (greedy == 1) {
        if (newlen < SDS_MAX_PREALLOC)
            newlen *= 2;  // 如果新长度小于最大预分配大小，扩展为两倍
        else
            newlen += SDS_MAX_PREALLOC;  // 否则加上预分配的常量
    }

    /* 根据新的长度确定字符串类型 */
    type = sdsReqType(newlen);

    /* 不能使用类型 5，因为类型 5 无法记住空闲空间，每次追加时都必须调用 sdsMakeRoomFor() */
    if (type == SDS_TYPE_5) type = SDS_TYPE_8;

    hdrlen = sdsHdrSize(type);  // 计算新类型的头部大小
    assert(hdrlen + newlen + 1 > reqlen);  // 检查是否有溢出

    /* 如果原始类型与新类型相同，使用 realloc 调整内存 */
    if (oldtype == type) {
        newsh = s_realloc_usable(sh, hdrlen + newlen + 1, &usable);
        if (newsh == NULL) return NULL;  // 如果重新分配失败，返回 NULL
        s = (char*)newsh + hdrlen;  // 将 s 移动到新的内存位置
    } else {
        /* 如果类型不同，无法使用 realloc，只能分配新的内存 */
        newsh = s_malloc_usable(hdrlen + newlen + 1, &usable);
        if (newsh == NULL) return NULL;  // 分配失败，返回 NULL
        memcpy((char*)newsh + hdrlen, s, len + 1);  // 将原字符串内容复制到新内存
        s_free(sh);  // 释放原内存
        s = (char*)newsh + hdrlen;  // 将 s 指向新内存位置
        s[-1] = type;  // 更新新的类型信息
        sdssetlen(s, len);  // 保持原始长度不变
    }

    /* 计算可用空间，并确保不会超过最大类型限制 */
    usable = usable - hdrlen - 1;
    if (usable > sdsTypeMaxSize(type))
        usable = sdsTypeMaxSize(type);

    /* 更新字符串的分配大小 */
    sdssetalloc(s, usable);

    /* 返回新的 sds 字符串 */
    return s;
}

如果剩余空间能够容纳追加的字符串，就不会额外申请空间。否则，就额外申请空间。

如果指定 greedy 为 0，就申请追加字符串长度大小空间；如果指定 greedy 为 1，就申请追加两倍字符串长度大小空间，避免后续再次分配，减少性能损耗。