redis sds

ddatsh

dev #redis 【redis】 2024/06/20

为什么 redis 不用 char *

使用 C 语言字符串时，经常需要手动检查和分配字符串空间，增加代码开发的工作量。图片等数据还无法用字符串保存，限制了应用范围

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
    char *str = malloc(14 * sizeof(char));
    if (str != NULL) {
        strcpy(str, "Hello, World!"); 
        printf("%s\n", str); 
        free(str); 
    }
    return 0;
}

\0 结束字符对字符串长度的影响

1
2
3
4
5
6
7
8
9


  #include <stdio.h>
  #include <string.h>
  int main()  {
     char *a = "red\0is";
     char *b = "redis\0";
     printf("%lu\n", strlen(a));
     printf("%lu\n", strlen(b));
     return 0;
  }

字符串操作函数复杂度

strlen

需要遍历字符数组中的每一个字符，才能得到字符串长度，复杂度 O(N)
strcat

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


char *strcat(char *dest, const char *src) {
 //将目标字符串复制给tmp变量
 char *tmp = dest;
 //用一个while循环遍历目标字符串，直到遇到“\0”跳出循环，指向目标字符串的末尾
 while(*dest)
    dest++;
 //将源字符串中的每个字符逐一赋值到目标字符串中，直到遇到结束字符
 while((*dest++ = *src++) != '\0' )
 return tmp;
}

遍历字符串才能得到目标字符串的末尾

还要再遍历源字符串才能完成追加

调用 strcat 时还需要确认目标字符串具有足够的可用空间，不然就需要手动分配空间，从而增加了编程的复杂度。复杂度增加，影响字符串操作效率

SDS

SDS 本质还是字符数组，此基础上增加了额外的元数据。在 Redis 中需要用到字符数组时，就直接使用 sds 这个别名

sdsnewlen 重点

创建新字符串时，调用 SDS 创建函数 sdsnewlen

sdsnewlen 会新建 sds 类型变量 s （也就是 char* 类型变量）

根据长度选择 shshdr结构(sdsReqType)

新建 SDS 结构体(SDS_HDR_VAR宏)

sds 类型变量 s 指向 SDS 结构体中的数组 buf[] (s = (char*)sh+hdrlen)

把要创建的字符串拷贝给 sds 变量(memcpy)

s[initlen] = ‘\0’;

SDS 操作效率

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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);
    s[curlen+len] = '\0';
    return s;
}

获取目标字符串的当前长度，并调用 sdsMakeRoomFor 保证其有足够的空间接收追加的字符串
在保证了目标字符串的空间足够后，将源字符串中指定长度 len 的数据追加到目标字符串
最后，设置目标字符串的最新长度

SDS 已存字符数组的使用长度和分配空间大小，避免了对字符串的遍历操作，降低了操作开销，(创建、追加、复制、比较等)更高效

把目标字符串的空间检查和扩容封装在了 sdsMakeRoomFor 函数中，涉及字符串空间变化的操作中，如追加、复制等，会直接调用该函数,避免开发人员因忘记给目标字符串扩容，而导致操作失败(如内存溢出)的情况

紧凑型字符串结构的编程技巧

sdshdr

SDS 结构中元数据 flags字段表示SDS 类型(sdshdr8/16/32/64)。主要区别在 len 和 alloc两个元数据的数据类型不同

1
2
3
4
5
6


struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* 字符数组现有长度*/
    uint8_t alloc; /* 字符数组的已分配空间，不包括结构体和\0结束字符*/
    unsigned char flags; /* SDS类型*/
    char buf[]; /*字符数组*/
};

8 位无符号整型uint8_t 占 1 字节内存空间。当字符串类型是 sdshdr8 时，能表示字符数组长度（包括最后一位\0）不超过 2^8=256字节

sdshdr8/16/32/64 元数据占内存1/2/4/8字节，保存小字符串时，结构头占用空间也比较少

SDS 是一个经典的空间换时间实现

编译优化

64 位系统编译器默认按 8 字节对齐方式分配内存

1
2
3
4
5
6


struct  s1 {
    char a;
    int b;
} ts1;

printf("%lu\n", sizeof(ts1));

char 占 1 字节，int 占 4 字节，但打印结果是 8。编译器给 s1 结构体对齐后，分配的是 8 个字节的空间

Redis 用了 attribute ((packed)) 属性定义结构体，结构体实际占用多少内存空间，编译器就分配多少空间

1
2
3
4
5


struct __attribute__((packed)) s2{
    char a;
    int b;
} ts2;
printf("%lu\n", sizeof(ts2));

兼容 c string

SDS 同样遵循 C 字符串以 \0 结尾， \0 的 1 字节不计算在len 属性里

遵循 \0 结尾的好处是， SDS 可以直接重用一部分 C 字符串函数库函数

SDS 指针 s ，可以直接使用 stdio.h/printf 函数

1

printf("%s", s->buf);

C 字符串作为字符串字面量（string literal），用在一些无须对字符串值进行修改的地方，比如打印日志

sdshdr 数据结构(sds.h)

几种不同长度的sdshdr结构体 sdshdr5,sdshdr8,sdshdr16,sdshdr32,sdshdr64

 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


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[];
};

MSB (Most Significant Bit)：最高有效位 / LSB (Least Significant Bit)：最低有效位。例，8位二进制数11001010中，最左边的1就是MSB，最右边的0就是LSB

能通过 buf 数组向低地址偏移一个字节来获取 flags 字段的值

buf是一个柔性数组成员，不占用结构体自身的空间

牺牲代码简洁性换取每个 sds 省下来的几个字节内存空间

新建 sds 时需要传初始化长度，然后根据初始化的长度确定用哪种 sdshdr

成员变量 len/alloc/flags

len：已使用的长度，用来记录字符串当前实际使用的字节数
alloc：分配的总长度，即为了存储该字符串所分配的内存大小
flags：类型信息，其中前3位用于存储特定标志，后5位预留(sdshdr5特殊)

attribute((packed))

让编译器以 紧凑模式 分配内存, 结构体成员不做内存对齐优化

以sdshdr32为例：

len、alloc 为 uint32_t 类型，占4字节
flags 为 unsigned char类型，占1字节
buf是一个柔性数组成员，不占用结构体自身的空间

未使用__attribute__((__packed__))属性时，编译器对结构体进行字节对齐，通常按成员中占用空间最大的基本数据类型进行对齐

可能会在flags成员后填充3个字节，以保证下一个成员buf从合适的位置开始，总大小12字节（4 + 4 + 1 + 3字节填充）

使用__attribute__((__packed__))属性后，结构体取消字节对齐，不自动添加填充字节。sdshdr32结构体大小只需计算成员变量本身的大小，即4（len）+ 4（alloc）+ 1（flags），共9字节，相比未使用packed属性节省3字节内存空间

大规模使用动态字符串时，可以显著减少内存的使用量，提升Redis的性能和效率

结构体大小和成员地址

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <stdio.h>
#include"sds.h"

int main(){

    printf("%zu\n", sizeof(struct sdshdr5));
    printf("%zu\n", sizeof(struct sdshdr8));
    printf("%zu\n", sizeof(struct sdshdr16));
    printf("%zu\n", sizeof(struct sdshdr32));
    printf("%zu\n", sizeof(struct sdshdr64));

    printf("Offset of len: %zu\n", (size_t)&(((struct sdshdr32*)0)->len));
    printf("Offset of alloc: %zu\n", (size_t)&(((struct sdshdr32*)0)->alloc));
    printf("Offset of flags: %zu\n", (size_t)&(((struct sdshdr32*)0)->flags));
    printf("Offset of buf: %zu\n", (size_t)&(((struct sdshdr32*)0)->buf));

    return 0;
}

(size_t)&(((struct sdshdr32 *)0)->len) 用来获取结构体成员在内存中的偏移量（即成员的地址）

(struct sdshdr32 \*)0：
- (struct sdshdr32 *) 是一个类型转换操作，将整数 0 转换为指向 sdshdr32 结构体的指针类型
- 0 通常被用作一个特殊值，表示空指针。在这里，我们不关心实际的对象，只是想得到一个合法的结构体指针
((struct sdshdr32 \*)0)->len：
- ((struct sdshdr32 *)0) 返回一个指向结构体 sdshdr32 的指针，即使它是一个无效的地址（因为0地址通常不是合法地址，但在这里我们只是想要获取结构体的成员偏移量）
- ->len 表示对指针指向的结构体成员 len 进行访问
&(((struct sdshdr32 \*)0)->len)：
- & 运算符获取其后表达式的地址，这里是获取 ((struct sdshdr32 *)0)->len 的地址，即 len 成员的地址
(size_t)：
- 强制类型转换为 size_t 类型，确保输出是地址的整数值

`sdshdr5` 的特例

每种 sdshdr 结构都包含一个 flags 字段，标识该 sds 属于哪种 sdshdr 类型

flags 字段低 3 位用于存储类型信息，而 sdshdr5 是个特殊的例子，它的高 5 位可能包含有效数据

为了解析和判断 sds 的类型，Redis 使用 SDS_TYPE_MASK 和位操作来屏蔽掉 flags 字段的高 5 位，仅保留低 3 位用于比较

 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


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include"sds.h"

static int sdsType(sds s) {
    unsigned char flags = s[-1];
    return flags & SDS_TYPE_MASK;
}
static inline int sdsHdr5Len(sds s) {
    unsigned char flags = s[-1];
    return (flags >> 3) & 0x1F;
}

int main(){

    printf("%d\n", sdsType(sdsnew("1234567890123456789012345678901")));
    printf("%d\n", sdsType(sdsnew("12345678901234567890123456789012")));

    // Allocate memory for sdshdr5 (including space for the string and null terminator)
    size_t len = 5; // Example length
    struct sdshdr5 *sh = malloc(sizeof(struct sdshdr5) + len + 1);
    sh->flags = (len << 3) | SDS_TYPE_5;
    strcpy(sh->buf, "Hello");

    // Convert to sds
    sds my_sds = sh->buf;

    // Get type and length
    int type = sdsType(my_sds);
    int length = sdsHdr5Len(my_sds);

    printf("Type: %d\n", type); // Should print 0 (SDS_TYPE_5)
    printf("Length: %d\n", length); // Should print 5
    printf("String: %s\n", my_sds); // Should print "Hello"

    // Free allocated memory
    free(sh);

    return 0;
}

-1 相当于获取到了sdshdr中的flag字段
sdsHdr5Len 提取 sdshdr5 的 flags 字段的高 5 位，得到字符串的长度
sdsType 提取 flags 字段的低 3 位，得到 sds 的类型

SDS 扩容 sdsMakeRoomFor

C 语言字符串不记录自身的长度，如strcat 去 append要重分配,忘了会缓冲区溢出;trim要重分配，忘了会内存泄露

SDS 的空间分配策略杜绝了发生缓冲区溢出的可能性： SDS API先检查空间，不够，自动扩展，使用 SDS 不需要手动修改 SDS 空间大小，也不会缓冲区溢出

SDS 实现了空间预分配和惰性空间释放优化策略

若 SDS 中剩余空闲空间 avail 大于新增内容的长度 addlen，无需扩容
若 SDS 中剩余空闲空间 avail 小于或等于新增内容 addlen：
- 新增后总长度 len + addlen < 1M, 按新长度的两倍扩容
- 新增后总长度 len + addlen >=1M, 按新长度加上 1M 扩容

预分配

如SDS修改后,len=13, 那会分配 13 字节未使用空间， buf 长度=13 + 13 + 1 = 27 字节（额外的一字节 \0）

SDS len =30 MB ，分配 1 MB 未使用空间， buf 数组的实际长度将为 30 MB + 1 MB + 1 byte

将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次

惰性释放

SDS API 需要缩短字符串时，不立即内存重分配回收，用 free 属性将这些字节的数量记录起来，并等待将来使用

SDS 也提供了真正地释放未使用空间的API