redis基本结构

发表于 | 分类于 | 评论数：

前言

上一篇大概介绍了 redis 属于内存数据库，采用了事件驱动模式并通过 io 复用来实现。除此之外，redis 还可以以 AOF 与 RDB 两种方式进行持久化等。接下来，我们继续从 redis 的早期版本入手，了解 redis 基本结构。

导航

从文件名出发……

files

文件并不多，大体如下：

  • 数据结构
    • adlist:双向链表
    • dict:哈希表
  • 事件驱动
    • ae,ae_epoll,ae_kqueue,aeselect
  • 辅助
    • 压缩：lzf
    • 排序：pqsort
    • 字符串：sds
  • 功能性
    • tcp：anet
    • 开放 api：hiredis
    • 命令行编辑器：linenoise
  • main
    • 命令行(command line interface)：redis-cli
    • 状态：redis-stat
    • redis.c

可以看出主体服务在 redis.c 文件中，而这些文件中有一个字符串辅助库 sds(A C dynamic strings library)比较特别。

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

struct sdshdr {
    long len; // 字符串长度
    long free; //
    char buf[]; // 字符串，'\0'结尾（同c字符串）
};

// sds.c

// new sds
sds sdsnew(const char *init) {
    size_t initlen = (init == NULL) ? 0 : strlen(init);
    return sdsnewlen(init, initlen);
}

sds sdsnewlen(const void *init, size_t initlen) {
    struct sdshdr *sh;

    sh = zmalloc(sizeof(struct sdshdr)+initlen+1); // 分配空间
    // ...
    sh->len = initlen;
    sh->free = 0;
    if (initlen) {
        if (init) memcpy(sh->buf, init, initlen); //
        else memset(sh->buf,0,initlen);
    }
    sh->buf[initlen] = '\0';
    return (char*)sh->buf;
}

可以看到，sds 总是指向 sdshdr 结构中实际存储字符串的地方 buf[]，而 sdsnew()函数返回的是 sds。这样，一方面可以兼容 c 字符串函数，另一方便，通过指针的移动，很容易获取 sdshdr 结构中的其他成员：len，free。len 记录着 sds 的长度，注意这个长度并不是 buf[]的长度，而是 buf[]中实际用于存储字符的长度。至于 buf 中没有用来存储字符的长度，则记录在了 free 里。所以实际上，len(buf)=len+free+1(结尾字符)。

所以使用 sds，可以避免通过遍历来计算字符串的长度，将 O(n)的时间复杂度降为 O(1)；还可以通过预分配来减少重新分配内存空间次数：

1
2
3
4
5
6
7
8
9
10
11
static sds sdsMakeRoomFor(sds s, size_t addlen) {
    // ...

    if (free >= addlen) return s; // free大于所需空间直接返回
    len = sdslen(s);
    sh = (void*) (s-(sizeof(struct sdshdr)));
    newlen = (len+addlen)*2; // 预分配 len+addlen 长度
    newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1);

    // ...
}

而 sdstrim()函数中，也不会释放多余的内存空间，而是通过变更 len 与 free 值来维护 sds。

redis.c

了解了 sds，再看服务入口文件 redis.c。在 redis.c 文件中，定义了一些基本数据类型。让我们从这些数据类型开始了解。

  • redisObject
1
2
3
4
5
6
7
typedef struct redisObject {
    void *ptr; // 对象指针
    unsigned char type; // 对象类型，string，list，set，zset，hash等
    unsigned char encoding; // 对象编码，RAW（sds），int等
    unsigned char notused[2];
    int refcount; // 引用计数，用于内存回收
} robj;
  • redisDb
1
2
3
4
5
typedef struct redisDb {
    dict *dict; // 哈希表
    dict *expires;
    int i
} redisDb;
  • redisCommand
1
2
3
4
5
6
struct redisCommand {
    char *name;
    redisCommandProc *proc; // 执行器
    int arity; // 参数数量
    int flags; // 命令类型，bulk，inline
};

再加上上一篇所提到的事件驱动模式，redis 的主体流程就呼之欲出了：

main