redis设计与实现之动态字符串(SDS)

SDS(Simple Dynamic String)定义

源码中定义 :

1
typedef char *sds;

总结

sds类型实际为 char * 的别名,这样做的好处是，可以复用很多C的原生函数库。

SDS的结构体定义sdshdr

sdshdr有好五个类别，它们分别是：sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64，其中sdshdr5是不使用的

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
/* 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; /* 已使用的长度(字符串真实长度) */
    uint8_t alloc; /* 字符串最大容量,不包含字符串的结尾 \0 */
    unsigned char flags; /* 总是占用一个字节。其中的最低3个bit用来表示header的类型,剩余5位未使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* 已使用的长度(字符串真实长度) */
    uint16_t alloc; /* 字符串最大容量,不包含字符串的结尾 \0 */
    unsigned char flags; /* 总是占用一个字节。其中的最低3个bit用来表示header的类型,剩余5位未使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* 已使用的长度(字符串真实长度) */
    uint32_t alloc; /* 字符串最大容量,不包含字符串的结尾 \0 */
    unsigned char flags; /* 总是占用一个字节。其中的最低3个bit用来表示header的类型,剩余5位未使用 */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* 已使用的长度(字符串真实长度) */
    uint64_t alloc; /* 字符串最大容量,不包含字符串的结尾 \0 */
    unsigned char flags; /* 总是占用一个字节。其中的最低3个bit用来表示header的类型,剩余5位未使用 */
    char buf[];
};

结构体说明

len : 字符串的长度 alloc : 字符串的容量 flags : 用低三位表示header类型,高五位未使用,为何是低三位表示,见下方 buf[] : 实际存储的字符串

细节说明

attribute ((packed)) 说明

__attribute__ ((packed)) 说明

attribute ((packed))实际作用是 取消编译阶段的内存优化对齐功能。 例如：struct aa {char a; int b;}; sizeof(aa) == 8;但是struct attribute ((packed)) aa {char a; int b;}; sizeof(aa) == 5; 这个很重要，redis源码中不是直接对sdshdr某一个类型操作，往往参数都是sds，而sds就是结构体中的buf，在后面的源码分析中，你可能会经常看见s[-1]这种魔法一般的操作，而按照sdshdr内存分布s[-1]就是sdshdr中flags变量，由此可以获取到该sds指向的字符串的类型。

常量定义

1
2
3
4
5
6
7
#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
#define SDS_TYPE_MASK 7
#define SDS_TYPE_BITS 3

为何是低三位表示类型

SDS_TYPE只占用了0,1,2,3,4五个数字，正好占用三位，我们就可以使用flags&SDS_TYPE_MASK来获取动态字符串对应的字符串类型

SDS中的宏定义函数

根据指向buf的sds变量s,得到sdshdr对应的指针变量

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

根据指向buf的sds变量s,得到sdshdr对应的指针地址

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

获取sdshdr5字符串类型的长度

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

c中的##语法

## 是c语言中的连接符, 前加 ## 或者后加 ## 将标记作为一个合法的标识符的一部分，不是字符串．多用于多行的宏定义中。+ 本宏声明中,SDS_HDR_VAR(8,s) 相当于 struct sdshdr8 *sh = (void*)((s)-(sizeof(struct sdshdr8)));

SDS相关内联函数

获取字符串长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static inline size_t sdslen(const sds s) {
    //获取字符串类型flag
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_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;
}

知识点

该处就使用到了 取消编译阶段的内存优化对齐功能 ，直接使用s[-1]获取到flags成员的值，然后根据flags&&SDS_TYPE_MASK来获取到动态字符串对应的类型进而 获取动态字符串的长度,至于 灵性的 s[-1]操作，没研究明白，后续补充

获取字符串可用空间

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
static inline size_t sdsavail(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5: {
            return 0;
        }
        case SDS_TYPE_8: {
            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;
}

知识点

获取动态字符串可使用的空间，从这里可以看出来，SDS和我平常所用到的C语言的原生字符串有差别，因为从获取可用空间的计算方法来看，并未考虑到字符串需要以\0结尾，因为 结构体本身带有长度的成员len，不需要\0来做字符串结尾的判定，而且不使用\0作为结尾有很多好处，可以存储的类型多样性就提高了

设置sds的长度

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

增加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
static inline void sdsinclen(sds s, size_t inc) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            {
                unsigned char *fp = ((unsigned char*)s)-1;
                unsigned char newlen = SDS_TYPE_5_LEN(flags)+inc;
                *fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
            }
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->len += inc;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->len += inc;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->len += inc;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->len += inc;
            break;
    }
}

获取sds已分配空间(容量)的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static inline size_t sdsalloc(const sds s) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            return SDS_TYPE_5_LEN(flags);
        case SDS_TYPE_8:
            return SDS_HDR(8,s)->alloc;
        case SDS_TYPE_16:
            return SDS_HDR(16,s)->alloc;
        case SDS_TYPE_32:
            return SDS_HDR(32,s)->alloc;
        case SDS_TYPE_64:
            return SDS_HDR(64,s)->alloc;
    }
    return 0;
}

设置sds已分配空间(容量)的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static inline void sdssetalloc(sds s, size_t newlen) {
    unsigned char flags = s[-1];
    switch(flags&SDS_TYPE_MASK) {
        case SDS_TYPE_5:
            /* Nothing to do, this type has no total allocation info. */
            break;
        case SDS_TYPE_8:
            SDS_HDR(8,s)->alloc = newlen;
            break;
        case SDS_TYPE_16:
            SDS_HDR(16,s)->alloc = newlen;
            break;
        case SDS_TYPE_32:
            SDS_HDR(32,s)->alloc = newlen;
            break;
        case SDS_TYPE_64:
            SDS_HDR(64,s)->alloc = newlen;
            break;
    }
}

C字符串与SDS对比

C字符串 SDS
获取字符串长度时间复杂度 O(N) 获取字符串长度时间复杂度 O(1)
API不安全，可能造成缓冲区溢出 API是安全的，不会造成缓冲区溢出
修改字符串长度N次，必然要执行 N 次内存分配 修改字符串长度N次，至多执行 N 次内存分配
只能保存文本数据 可以保存文本或二进制数据
可使用所有 <string.h>库中的函数 可使用部分 <string.h>库中的函数

参考资料

  1. 《Redis设计与实现》 ↩
redis > design
#redis设计与实现
redis设计与实现之动态字符串(SDS)
http://www.zhangdeman.cn/archives/616b813e.html
作者
白茶清欢
发布于
2020年9月25日
许可协议