简单动态字符串SDS

作用

1、保存数据库中字符串的值

2、AOF中的缓冲区以及客户端状态中的缓冲区

具体结构代码

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr {
	// 记录buf数组中已经使用字节的数量
    // 等于SDS所保存字符串的长度
    int len;
    
    // 记录buf数组中未使用字节的数量
    int free;
    
    // 字节数组，用于保存字符串
    char buf[];
}

因为C语言的字符串在每次赋值前都需要申请空间，而且获取长度需要遍历整个字符串，所以Redis采用上述设计。

SDS的好处

1、可以在O(1)的时间复杂度之内获取到字符串的长度。

2、杜绝缓冲区的溢出。

​ SDS的API每次操作SDS时，会先检查SDS空间是否满足，如果不满足会将空间扩展至足够的大小，然后才执行实际的修改。

3、减少修改字符串时带来的内存分配的次数。在C语言中，每一次修改字符串都需要重新分配内存空间，而SDS采用空间预分配和惰性删除来减少分配次数

​ 1）空间预分配：如果需要对SDS进行扩容，如果扩容后SDS的长度小于1mb，那么就会额外分配len长度的空间。比如原来10kb，扩容后30kb，小于1mb，就会多分配30kb。如果大于1mb，就会额外分配1mb。

​ 2）惰性删除：当需要缩短字符串时，SDS并不会了立即释放多余的空间，而是使用free字段来记录这些空间，等到下一次分配时使用。同时也提供了API进行真正的释放这些空间。

链表

使用场景

1、发布与订阅

2、慢查询

3、监视器

4、构建客户端输出缓冲区

链表以及链表节点的实现

链表的每一个节点结构体

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
// 链表每个节点
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    
    // 后置节点
    struct listNode *next;
    
    // 节点的值
    void *val;
} listNode;

// 整个链表
typedef struct listNode {
    // 表头节点
    listNode *head;
    
    // 表尾节点
    listNode *tail;
    
    // 链表所包含节点的数量
    unsigned long len;
    
    // 节点复制函数
    void *(*dup) {void *ptr;}
    
    // 节点值释放函数
    void (*free) {void *ptr;}
    
    // 节点值对比函数
    int (*match) {void *ptr, void * key;}
} list;

参考

《Redis设计与实现》