Redis设计与实现--单机数据库的实现

发表于 | 更新于 | 分类于

0. 前言

这部分对Redis实现单机数据库的方法进行介绍.

1. 数据库

1.1 服务器中的数据库

1
2
3
4
5
6
7
8
9
struct redisServer{
    // ...
    // 一个数组,保存着服务器中的所有数据库
    redisDb *db;
    // ...
    // 服务器的数据库数量
    int dbnum;
    // ...
};

服务器中的数据库

1.2 切换数据库

redis客户端默认目标数据库为0号数据库,可以通过SELECT命令来切换目标数据库.
客户端状态redisClient结构的db属性记录了客户端当前的目标数据库,这个属性是指向redisdb结构的指针.

1
2
3
4
5
6
typedef struct redisClient{
    // ...
    //记录客户端当前正在使用的数据库
    redisDb *db;
    // ...
} redisClient;

切换数据库

1.3 数据库键空间

Redis是一个键值对数据库服务器,服务器中的每个数据库都由一个redis.h/redisDb结构表示,其中redisDB的dict字典保存了数据库中的所有键值对,我们将这个字典称为键空间.

1
2
3
4
5
6
typedef struct redisDb{
    // ...
    // 数据库键空间，保存着数据库中的所有键值对
    dict *dict
    // ...
} redisDb;

数据库键空间

键空间和用户所见的数据库是直接对应的:

  1. 键空间的键也就是数据库的键,每个键都是一个字符串对象.
  2. 键空间的值也就是数据库的值,每个值可以是字符串对象,列表对象,哈希表对象,集合对象和有序集合对象中任意一种Redis对象.

对键空间可以进行添加,删除,修改,查询等操作.

1.4 设置键的生存时间或过期时间

1
2
3
4
5
6
typedef struct redisDb{
    // ...
    //过期字典，保存着键的过期时间
    dict *expires;
    // ...
} redisDb;

设置键的生存时间或过期时间

1.5 过期键删除策略

三种策略:定时删除,惰性删除,定期删除.

  1. 定时删除:在设置键的过期时间的同时,创建一个定时器,让定时器在键的过期时间来临时,立即执行对键的删除操作.(内存友好)
  2. 惰性删除:放任键过期不管,但是每次从键空间中获取键时,都检查取得的健是否过期,如果过期的话,就删除该键;如果没有过期,就返回该键.(CPU友好)
  3. 定期删除:每隔一段时间,程序就对数据库进行一次检查,删除里面的过期键.至于要删除多少过期键,以及要检查多少个数据库,则由算法决定.(两者折中)

1.6 Redis的过期键删除策略

Redis使用惰性删除 + 定期删除两种策略:通过配合使用这两种删除策略,服务器以很好地在合理使用CPU时间和避免浪费内存空间之间取得平衡.

懒性删除策略

懒性删除策略

定期删除策略

在规定时间内 分多次 遍历服务器中的数据库, 从数据库的expires字典中 随机检查一部分 键的过期时间并删除其中的过期键.

1.7 AOF、RDB和复制功能对过期键的处理

RDB持久化:

  1. 生成RDB文件将会过滤已经过期的健;
  2. 载入RDB文件,如果是主服务器模式运行,则过滤过期键;如果是从服务器模式运行,则一并载入,主从数据同步会清空从节点数据,所以不会有影响.

AOF持久化:

  1. AOF重写会过滤已经过期的健;
  2. AOF写入举例

AOF写入举例

复制

复制

2. RDB持久化

Redis是内存数据库,数据存储在内存中,如果不想办法将存储在内存中的数据库状态保存到磁盘,那么一旦服务器进程退出,服务器中的数据库状态也会消失不见.

2.1 RDB文件的创建与载入

  1. 创建
    生成RDB文件,有两个命令,SAVE和BGSAVE,其中SAVE会阻塞Redis服务器进程,而BGSAVE会派生出一个子进程.
  2. 载入
    RDB文件的载入是在服务器启动时自动执行的.

2.2 自动间隔性保存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#设置保存条件
save 900 1        服务器在900秒之内,对数据库进行了至少1次修改
save 300 10      服务器在300秒之内,对数据库进行了至少10次修改
save  60  10000  服务器在60秒之内,对数据库进行了至少10000次修改

#实现
struct redisServer{
    //计入了保存条件的数组
    struct saveparam *saveparam
    //dirty修改计数器  表示服务器在上次保存后,对数据库状态共进行多少次修改
    long long dirty
    //上一次执行保存的时间
    time_t   lastsave
}

struct saveparam {
    //秒数
    time_t  seconds;
    //修改数
    int changes
}

#检查保存条件是否满足,则每隔100毫秒周期性执行ServerCron函数,遍历条件数组saveparam,对满足条件的数据库,计数器置为0,并更新上次保存时间.

自动间隔性保存

Redis根据save所设置的保存条件,自动执行BGSAVE命令,进行实现间隔性数据保存.

2.3 RDB文件结构

RDB文件记录的Redis所有数据库的所有键值对数据.并按照指定的顺序进行保存.对不同类型的键值对,RDB文件会使用不同的方式来保存它们.这里有一点需要说明,那就是数字会被转换成字符串来保存.

RDB文件结构

3. AOF持久化

除了RDB持久化,还有AOF持久化(Append Only File).
RDB持久化通过保存数据库中的键值对来记录数据库状态.
AOF持久化通过保存Redis服务器所执行的写命令来记录数据库状态.

AOF持久化

3.1 AOF持久化实现

AOF持久化功能分为:命令追加,文件写入,文件同步三个步骤.

1
2
3
4
5
6
7
// 命令追加
struct redisServer{
    // ...
    //AOF缓冲区 写命令按照一定格式会追加到缓冲区
    sds aof_buf;
    // ...
}
1
2
3
4
5
6
7
8
9
// 文件写入和同步
def eventLoop():
    while True :
        #处理文件事件，接受命令请求以及发送命令回复
        processFileEvents()
        #处理时间事件  类似于ServerCron定期执行函数
        processTimeEvents()
        #考虑是否将aof_buf中的内容写入和保存到AOF文件里面,三个选项
        flushAppendOnlyFile()

文件写入和同步

关于文件写入和同步的特殊说明: 为了提高文件的写入效率,在现代操作系统中,当用户调用write函数,操作系统通常会将数据暂存到一个内存缓冲区里,当缓冲区被填满或超过了指定时限后,才真正将缓冲区的数据写入到硬盘里.这样的操作虽然提高了效率,但也带来了安全问题:如果计算机停机,内存缓冲区中的数据会丢失;因此系统同时提供了fsync,fdatasync等同步函数,可以强制操作系统立刻将缓冲区中的数据写入到硬盘里,从而确保数据的安全性.

3.2 AOF文件的载入与数据还原

AOF文件载入

载入

3.3 AOF重写

问题:因为AOF持久化是通过保存被执行的写命令来记录数据库状态的,所以随着服务器运行时间的流逝,AOF文件中的内容会越来越多,文件的体积也会越来越大.如果不加以控制,体积很大的AOF文件很可能对Redis服务器,甚至整个宿主计算机造成影响,并且AOF文件体积越大,使用AOF文件来进行数据还原所需的时间就越多.

解决方案:Redis服务器可以创建一个新的AOF文件来替代现有的AOF文件,新旧两个AOF文件所保存的数据库状态相同.但新的AOF文件不包含冗余命令,所以体积相对较小.

具体实现:AOF重写因为是辅助性维护手段,因此,不会造成服务器阻塞,但也因此需要考虑数据一致性问题.为了解决数据不一致问题,Redis服务器设置了一个AOF重写缓冲区,这个缓冲区在服务器创建子进程之后开始使用.

AOF重写

当子进程完成AOF重写工作之后,会向父进程发送一个信号,父进程会调用一个信号处理函数并执行以下操作:
1)将AOF重写缓冲区中所有内容写入新AOF文件中,这时新AOF保存的数据库状态==服务器当前数据库状态;
2）对新的AOF文件改名,原子替换旧的AOF文件;

AOF重写

4. 事件

两类事件:文件事件和时间事件.

文件事件:Redis服务器通过套接字与客户端进行连接,而文件事件就是服务器对套接字操作的抽象,服务器与客户端的通信会产生相应的文件事件,而服务器通过监听并处理这些事件来完成一系列网络通信操作.

时间事件:Redis服务器中的一些操作需要在给定的时间点执行,而时间事件就是服务器对这类定时操作的抽象.

4.1 文件事件

文件事件

I/O多路复用程序总是会将所有产生事件的套接字都放在一个队列里面,并串行化地向文件事件分派器传送套接字.

文件事件

4.2 时间事件

服务器将所有时间事件都放在一个无序链表中,每当时间事件执行器运行时,它就会遍历整个链表,查找所有已到达的时间事件,并调用相应的事件处理器.

Redis时间事件分为两类:
定时事件:让一段程序在指定的时间之后执行一次.(目前的Redis中并没有使用)
周期性事件:让一段程序每隔指定时间就执行一次.

4.3 事件的调度与执行

事件的调度与执行

其中,在 等待文件事件产生 这个步骤处, 不会无时限的等待,而是会等待一段时间, 这个时间长度 等于 距离最接近的时间事件到达的毫秒数.

事件的调度与执行

5. 客户端

1
2
3
4
5
6
struct redisServer{
    // ...
    //一个保存所有client的链表
    list *clients;
    // ...
}

客户端

5.1 客户端属性

1
2
3
4
5
6
7
8
9
10
11
typedef  struct redisClient{
    //套接字描述符
    int fd;
    //名字
    robj *name;
    //标志，记录客户端角色，以及目前所处的状态
    int flag;
    //输入缓冲区 用于保存客户端发出的命令请求
    sds querybuf;
    //其他 如命令参数，参数个数，输出缓冲区，身份认证，时间
}redisClient;

5.2 客户端的创建与关闭

当客户端与服务器通过网络建立连接时,服务器就会调用连接处理事件,为客户端创建相应的客户端状态,并将新的客户端状态添加到服务器状态结构clients链表的尾链.

客户端属性

当满足一定的条件,客户端就会被关闭.

伪客户端:
Lua脚本的伪客户端
AOF文件的伪客户端

6. 服务器

6.1 命令请求的执行过程

一个命令请求从发送到完成主要包括以下步骤:

  1. 客户端将命令请求发送给服务器;
  2. 服务器读取命令请求,并分析出命令参数;
  3. 命令执行器根据参数查找命令的实现函数,然后执行实现函数并得出命令回复;
  4. 服务器将命令回复返回给客户端.

6.2 serverCron函数

serverCron函数默认每隔100毫秒执行一次,它的工作主要包括更新服务器状态信息,处理服务器接收的SIGTERM信号,管理客户端资源和数据库状态,检查并执行持久化操作等等.

6.3 初始化服务器

服务器从启动到能够处理客户端的命令请求需要执行以下步骤:

  1. 初始化服务器状态;
  2. 载入服务器配置;
  3. 初始化服务器数据结构;
  4. 还原数据库状态;
  5. 执行事件循环.

7. 参考文献

<< Redis设计与实现 >> (黄健宏 著)

Redis设计与实现——单机数据库的实现

谢谢你请我吃糖果!