Redis 源码学习 -- sds

发表于 更新于 阅读次数：

redis学习笔记

基于 Redis 6.0.4

1
2
redis / src / sds.h
redis / src / sds.c

介绍

简单动态字符串 (simple dynamic string, SDS) 是 Redis 基本的底层抽象数据结构之一，用来替代 c 字符串作为默认的字符串使用。

结构

struct sdshdr

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
// 新版本
struct sdshdr {
    uintx_t len;            // 实际被使用长度,x为8,16,32,64
    uintx_t alloc;          // 被分配的最大长度,x为8,16,32,64
    unsigned char flags;    // sdshdr类型,x为8,16,32,64
    char buf[];             // 实际字符串的开始,x为8,16,32,64
}

// 旧版本 2.x
struct sdshdr {
    int len;    // 实际被使用长度
    int free;   // 剩余可用空间
    char buf[]; // 实际字符串的开始
}

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
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[];
};

__attribute__ ((__packed__)) 作用是告诉编译器取消结构在编译过程中的优化对齐，按照实际占用字节数进行对齐——即取消 4k 对齐而是以 1byte 来对齐。这是 GCC 特有的语法，保证 header 和 sds 的数据部分紧紧前后相邻，可以按照固定向低地址方向偏移 1 个字节的方式来获取 flags 字段。

在各个 header 的定义中最后有一个 char buf[]。注意到这是一个没有指明长度的字符数组，这是 C 语言中定义字符数组的一种特殊写法，它在这里只是起到一个标记的作用，表示在 flags 字段后面就是一个字符数组，而程序在为 header 分配的内存的时候，它并不占用内存空间。如果计算 sizeof(struct sdshdr16) 的值,那么结果是 5 个字节，其中没有 buf 字段。

sdshdr5 与其它几个 header 结构不同，它不包含 alloc 字段，而长度使用 flags 的高 5 位来存储。因此，它不能为字符串分配空余空间，如果字符串需要动态增长，那么它就必然要重新分配内存才行。所以这种类型的 sds 字符串更适合存储静态的短字符串 (长度小于 32)。主要目的是减小内存使用开销。

sds

sds 就是 char*，指向字符串数据的开始。

1
typedef char *sds;

部分函数实现

SDS_HDR_VAR()

创建一个 struct sdshdrX* sh 变量，并指向 sds s 的 sdshdrX

1
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));

SDS_HDR()

返回一个指向 sds s 的 sdshdrX 的指针

1
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

SDS_TYPE_5_LEN()

flags 右移 3 位得到数据部分长度大小

1
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)

sdslen()

获取 sds 对应的数据部分的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static inline size_t sdslen(const sds s) {
    // 因为 s 指向的是字符串数据的开始 所以 s 的前一个字节就是 sdshdr 中 flags 的位置
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            // SDS_TYPE_5 通过 flags 的高 5 位代表数据部分的长度
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->len;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->len;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->len;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->len;
    }
    return 0;
}

sdsavail()

获取 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
static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        // SDS_TYPE_5 类型是静态的 没有动态的剩余空间 因此剩余 0
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            // SDS_HDR_VAR() 会自己创建变量 sh 指向 s 的 sdshdr
            SDS_HDR_VAR(8,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            return sh->alloc - sh->len;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            return sh->alloc - sh->len;
        }
    }
    return 0;
}

sdssetlen()

设置 sdshdr 的 len。

注意这个函数并不安全，因为它没有检测 s 的大小，如果不同步和 s 相关内容一起设置可能会导致溢出问题。sdsinclen()、sdssetalloc()也一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static inline void sdssetlen(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                // SDS_TYPE_5 的低 3 位为类型，高 5 位为大小，SDS_TYPE_BITS = 3
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len = newlen;
            break;
    }
}

sdsnewlen()

创建新的 sds。

这个函数不会检测输入的 init 的有效性，因为 init 可以为 NULL，此时会创建一个长度为 initlen 的被初始化的空 sds。init 还可以是 SDS_NOINIT，此时 init 也代表为 NULL，不过这时 sdsnewlen() 不会对申请出来的内存进行初始化。

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
84
/* Create a new sds string with the content specified by the 'init' pointer
 * and 'initlen'.
 * If NULL is used for 'init' the string is initialized with zero bytes.
 * If SDS_NOINIT is used, the buffer is left uninitialized;
 *
 * The string is always null-termined (all the sds strings are, always) so
 * even if you create an sds string with:
 *
 * 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) {
    void *sh;
    sds s;
    // 判断适合的类型
    char type = sdsReqType(initlen);
    /* Empty strings are usually created in order to append. Use type 8
     * since type 5 is not good at this. */
    // 当发现类型为 SDS_TYPE_5 时需要判断 输入的 size 大小，如果是 0 说明
    // 创建后通常会对 sds 进行修改，而 SDS_TYPE_5 并不适合进行修改，因此
    // 会把类型修正为 SDS_TYPE_8
    if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
    // 根据类型获取相应类型结构体头长度
    int hdrlen = sdsHdrSize(type);
    unsigned char *fp; /* flags pointer. */

    // s_malloc 就是 zmalloc，zmalloc 根据编译时选择的内存管理库的有不同的实现效果
    // 最后的 1 用来存放 '\0'
    sh = s_malloc(hdrlen+initlen+1);
    if (sh == NULL) return NULL;
    // SDS_NOINIT 是字符串 "SDS_NOINIT"，代表 init 为 NULL，目的是通过外层对 init 的检查
    if (init==SDS_NOINIT)
        init = NULL;
    else if (!init)
        memset(sh, 0, hdrlen+initlen+1);
    // sds 指向数据的开始位置
    s = (char*)sh+hdrlen;
    // fp 指向 flag 的位置
    fp = ((unsigned char*)s)-1;
    // 填充 sdshdr 结构体
    switch(type) {
        case SDS_TYPE_5: {
            *fp = type | (initlen << SDS_TYPE_BITS);
            break;
        }
        case SDS_TYPE_8: {
            SDS_HDR_VAR(8,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_16: {
            SDS_HDR_VAR(16,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_32: {
            SDS_HDR_VAR(32,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
        case SDS_TYPE_64: {
            SDS_HDR_VAR(64,s);
            sh->len = initlen;
            sh->alloc = initlen;
            *fp = type;
            break;
        }
    }
    // 填充 sds 字符串部分
    if (initlen && init)
        memcpy(s, init, initlen);
    // 结尾置 '\0'
    s[initlen] = '\0';
    // 返回字符串数据的开始位置的指针
    return s;
}

sdsfree()

释放 sds。

1
2
3
4
5
6
/* Free an sds string. No operation is performed if 's' is NULL. */
void sdsfree(sds s) {
    if (s == NULL) return;
    // 会回退到 sdshdr 开始的位置
    s_free((char*)s-sdsHdrSize(s[-1]));
}

辅助函数

sdsReqType()

根据输入的大小计算必要的数据类型，不同的数据类型有不同的最大长度限制，可以做到提高内存使用率的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static inline char sdsReqType(size_t string_size) {
	// 当 size < 2^4 = 16
    if (string_size < 1<<5)
        return SDS_TYPE_5; 
    // 当 16 <= size < 2^8 = 256
    if (string_size < 1<<8)
        return SDS_TYPE_8;
    // 当 256 <= size < 2^16 = 65536
    if (string_size < 1<<16)
        return SDS_TYPE_16;
// 判断系统是否支持 64 位的大小
#if (LONG_MAX == LLONG_MAX)
    // 当 65536 <= size < 2^32
    if (string_size < 1ll<<32)
        return SDS_TYPE_32;
    // 当 size 是 32 位也无法满足的长度
    return SDS_TYPE_64;
#else
    // 不支持 64 位，直接返回最大类型
    return SDS_TYPE_32;
#endif
}

总结

SDS 遵循 C 字符串以空字符结尾的惯例，可以在有需要时重用 <string.h> 函数库，从而避免了不必要的代码重复。

SDS C 字符串
获取长度的时间复杂度 O(1) O(n)
避免溢出机制 有 没有
二进制安全 是 否

注: 二进制安全是指 SDS 会记录信息的长度，因此在除结尾字符外允许有‘\0’的出现，而 C 字符串不行。

SDS 相当于 C 字符串而做的优化:

  • 空间预分配

    通过 sdsMakeRoomFor() 进行扩容时:

    • 若 addlen <= avail(free) 直接返回
    • 若 newlen < SDS_MAX_PREALLOC(1024 * 1024) 则会分配 newlen * 2 + 1 的空间大小
    • 若 newlen >= SDS_MAX_PREALLOC 则会分配 newlen + SDS_MAX_PREALLOC + 1 大小的空间
    • 按分配后的空间大小，可能需要更换header类型。此时整个字符串空间 (包括 header) 都需要重新分配 (s_malloc)，并拷贝原来的数据到新的位置
    • 如果不需要更换 header，那么调用一个比较特殊的 s_realloc 试图在原来的地址上重新分配空间。s_realloc 的具体实现得看 Redis 编译的时候选用了哪个 allocator (在 Linux 上默认使用 jemalloc)

  • 惰性空间释放

    通过 sdsfree() 进行释放空间时并不会真正的回收未利用空间而是仅仅缩短 alloc 的长度。

SDS 中的很多函数会在调用的过程中将原来的对象给释放，并返回一个新的对象地址，原来的旧的变量会失效，需要进行替换。