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

数据库

一个Redis Server可以有多个Redis数据库，这点类似于MySQL, 从Redis Server的源代码中可以看到,redisDb是Server数据库的指针，指向一个数据库组成的数组，而数据库的数量则由dbnum属性来表示。客户端可以通过SELECT命令选择当前要操作的数据库。

struct redisServer {

    // ...

    // 数据库数组指针
    redisDb *db;

    // 服务器的数据库数量
    int dbnum;                      

    // ...
}

数据库的定义在redis.h/redisDb中，定义如下:

typedef struct redisDb {

    // 数据库键空间，保存着数据库中的所有键值对
    dict *dict;                 /* The keyspace for this DB */

    // 键的过期时间，字典的键为键，字典的值为过期事件 UNIX 时间戳
    dict *expires;              /* Timeout of keys with a timeout set */

    // 正处于阻塞状态的键
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */

    // 可以解除阻塞的键
    dict *ready_keys;           /* Blocked keys that received a PUSH */

    // 正在被 WATCH 命令监视的键
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */

    struct evictionPoolEntry *eviction_pool;    /* Eviction pool of keys */

    // 数据库号码
    int id;                     /* Database ID */

    // 数据库的键的平均 TTL ，统计信息
    long long avg_ttl;          /* Average TTL, just for stats */

} redisDb;

dict: 是一个字典，保存了数据库中的所有键值对，我们将这个字典称为键空间(key space)。
expires: 也是一个字典，保存的是键值与这个键值过期时间的键值对。

一个简化的结构图如下:
db结构
设置生存时间和过期时间时，最终都是计算出最后生存时间，然后把这个值存入expires字典中。过期字典中找不到证明没有设置过期时间。过期删除策略Redis主要是使用惰性删除策略与定期删除两种策略。所谓惰性删除策略就是当用户获取键时，先判断其是否过期，如果过期则删除键，返回失败，如果没过期则正常返回。定期删除策略是Redis会周期行的从过期字典中随机出一部分键值，如果过期则删除键，否则保留。

持久化

RDB持久化

RDB(redis database)持久化既可以手动执行，也可以根据服务器配置选项定期执行，该功能可以将某个时间点上的数据库状态保存到一个RDB文件中(RDB文件默认的文件名为dump.rdb)。RDB持久化功能锁生成的RDB文件是一个经过压缩的二进制文件，通过该文件还可以还原生成RDB文件时的数据库状态。
有两个Redis命令可以用于生成RDB文件，一个是SAVE, 另一个是BGSAVE。SAVE会阻塞Redis服务进程，知道RDB文件创建完毕为止，在服务器进程阻塞期间，服务器不能处理任何请求。BGSAVE命令会派生出一个子进程,然后由子进程负责创建RDB文件，服务器进程(父进程)继续处理命令请求。
RDB文件是在服务器启动时自动执行的，只要Redis服务器启动时检测到RDB文件存在，它就会自动载入RDB文件。但是如果服务器开启了AOF持久化功能，就会优先使用AOF文件。因为AOF文件的更新频率通常比RDB文件高，所以数据是最新的可能性高。
用户可以通过save选项设置多个保存条件，但只要其中任意一条被满足，服务器就会执行BGSAVE命令。例如配置为下面三个:

1
2
3

save 900 1
save 300 10
save 60 10000

只要满足900s内至少一次修改，或300s内至少10次修改，或60s内10000次修改就会自动执行BGSAVE命令。
服务器维护一个dirty计数器，用于记录距离上次成功执行SAVE或BGSAVE命令之后，服务器对数据库状态进行了多少次修改(包括写入，删除，更新等操作)。
服务器还维护一个lastsave属性，记录服务器上一次成功执行SAVE或BGSAVE命令的时间。
RDB文件结构:

+-----+----------+---------+---+---------+
|     |          |         |   |         |
|REDIS|db_version|databases|EOF|check_sum|
|     |          |         |   |         |
+-----+----------+---------+---+---------+

REDIS: RDB文件开头是REDIS部分，这个部分长度为5字节,保存着”REDIS”五个字符。通过五个字符，快速检测是否为RDB文件。
db_version: 长度为4字节，它的值是一个字符串表示的整数，记录了RDB文件的版本号。
databases: 包含着零个或任意多个数据库，以及各个数据库中的键值对数据。
EOF: 长度为1字节，这个常量标志着RDB文件正文内容的结束，当读入程序遇到这个值的时候，它知道所有数据库的所有键值对都已经载入完毕。
check_sum: 8字节长的无符号整数，保存着一个校验和，这个校验和是程序通过对前面四部分的内容计算得出的。服务器载入RDB文件时，会将载入数据所计算出的校验和与check_sum所记录的检验和进行对比，以此来检查RDB文件是否出错或者有损坏的情况。
可以使用od -c dump.rdb或od -cx dump.rdb命令来对RDB文件内容进行分析。

AOF持久化

AOF(Append Only File)持久化功能是通过保存Redis服务器所执行的写命令来记录数据库状态的。AOF持久化功能的实现可以分为命令追加(append), 文件写入，文件同步(sync)三个步骤:

命令追加: 服务器执行完一个写命令后，会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区的末尾。
AOF文件的写入与同步: 服务器的每次时间循环结束之前，都会调用flushAppendOnlyFile函数，考虑是否需要将aof_buf缓冲区中的内容写入和保存到AOF文件里。
flushAppendOnlyFile函数的行为由服务器配置的appendfsync选项的值来决定:

appendfsync选项的值	flushAppendOnlyFile函数的行为	影响
always	将aof_buf缓冲区中的所有内容写入并同步到AOF文件	性能最低，但是安全性最高，发生故障停机最多丢失一个循环事件所产生的在缓冲区中的命令
everysec(默认值)	将aof_buf缓冲区中的所有内容写入到AOF文件，如果上次同步AOF文件的时间距离现在超过1s,那么再次对AOF文件进行同步，并且这个同步操作是由一个线程专门负责执行的	性能足够快，并且出现故障停机，最多丢失一秒钟的命令数据
no	将aof_buf缓冲区中的所有内容写入到AOF文件，但并不对AOF文件进行同步，何时同步由操作系统决定	性能最好，写入AOF速度最快，但是单次同步时间最长，出现故障丢失的命令最多

由于AOF文件记录了重建数据库所需的所有写命令，所以服务器只要读入并执行一遍AOF文件里么保持的写命令，就可以还原服务器关闭之前的状态。
由于AOF持久化是通过保存被执行的写命令来记录数据库状态的，随着时间的推移，写命令越来越多，这时候就需要AOF重写来减轻文件体积的膨胀。
AOF重写首先从数据库中读取键现在的值，然后用一条命令去记录键值对，代替之前记录的这个键值对的多条命令。但是在重写列表，哈希表，集合，有序集合等多个元素的键时，如果元素的数量超过了redis/REDIS_AOF_REWRITE_ITEMS_PER_CMD常量的值，会通过多条命令来记录键的值。
一个问题是在AOF重写期间，服务器还需要处理命令请求，而新的命令可能会对现有的数据库状态进行修改，从而使得服务器当前的数据库状态和重写后的AOF文件所保存的数据库状态不一致。为了解决这个问题，Redis服务器设置了一个AOF重写缓冲区，这个缓冲区在服务器创建子进程进行重写是开始使用,当Redis服务器执行完一个写命令后，它会同事将这个命令发送给AOF缓冲区和AOF重写缓冲区。当AOF重写工作完成后，向父进程发送信号，父进程就会将AOF重写缓冲区中的所有内容写到新的AOF文件中，对新的AOF文件进行改名，原子地（atomic)覆盖现有的AOF文件，完成新旧两个AOF文件的替换。

事件

文件事件

文件事件(file event): Redis服务器通过套接字与客户端(或其他Redis服务器)进行连接，而文件事件就是服务器对套接字操作的抽象。服务器与客户端（或其他服务器)的通信会产生相应的文件事件，而服务器则通过监听并处理这些事件来完成一系列网络通信操作。
下图是Redis自己实现的文件事件处理器的四个组成部分:
db结构

文件事件处理器使用I/O多路复用(multiplexing)程序来同时监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
当被监听的套接字准备好执行连接应答(accept),读取(read),写入(write)，关闭(close)等操作时，与操作相对应的文件事件就会产生，这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

虽然文件事件处理器以单线程方式运行，但通过使用I/O多路复用程序来监听多个套接字，文件事件处理器既实现了高性能的网络通信模型，又可以很好地与Redis服务器中其他同样以单线程方式运行的模块进行对接，着保持了Redis内部单线程设计的简单性。
尽管多个文件事件可能会并发地出现，但I/O多路复用程序总会将所有产生事件的套接字都放在一个队列里，然后通过这个队列，以有序(sequentially),同步(synchronously)，每次一个套接字的方式向文件事件分派器传送套接字。
Redis的I/O多路复用程序的所有功能都是通过包装常见的select,epoll,evport和kqueue这些I/O多路复用函数库来实现的，编译时会自动选择性能高最高的I/O多路复用函数库来作为Redis的I/O多路复用程序的底层实现。

时间事件

时间事件(time event): Redis服务器中的一些操作(如serverCron函数)需要在给定的时间点执行，而时间事件就是服务器对这类定时操作的抽象。
Redis的时间事件分为两类:

定时事件: 让程序在指定的时间之后执行一次。
周期性事件: 让一端程序每隔指定的时间就执行一次。

一个时间事件主要由以下三个属性:

id: 服务器为时间事件创建的全局唯一ID(标识号)。ID号按从小到大的顺序递增，新事件的ID号比旧事件的ID号要大。
when: 毫秒精度的UNIX时间戳，记录了时间事件的到达(arrive)时间。
timeProc: 时间事件处理器，一个函数。当时间事件到达时，服务器就会调用响应的处理器来处理事件。

一个时间事件是定时事件还是周期性事件取决于时间事件处理器的返回值:

如果事件处理器返回ae.h/AE_NOMORE，那么这个事件为定时事件:该事件在达到一次之后就会被删除，之后不再到达。
如果事件处理器返回一个非AE_NOMORE的整数值，那么这个事件为周期性时间:当一个时间事件到达之后，服务器会根据事件处理器返回的值，对时间事件的when属性进行更新，让这个事件在一段时间后再次到达，并以这种方式一直更新运行下去。

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

事件的调度与执行

事件的调度和执行由ae.c/aeProcessEvents函数负责,下面是这个函数的伪代码:

def aeProcessEvents():

    // 获取到达时间离当前最接近的时间事件
    time_event = aeSearchNearestTimer()
    
    // 计算最接近的时间事件距离到达还有多少毫秒
    remaind_ms = time_event.when - unix_ts_now()
    
    // 如果事件已到达，那么remaind_ms的值就可能为负数，将它设定为0
    if remaind_ms < 0:
        remaind_ms = 0 
    
    // 根据remaind_ms的值，创建timeval结构
    timeval = create_timeval_with_ms(remaind_ms)
    
    // 阻塞并等待文件事件产生，最大阻塞时间由传入的timeval结构决定
    // 如果remaind_ms的值为0，那么aeApiPoll调用之后马上返回，不阻塞
    aeApiPoll(timeval)
   
    // 处理所有已产生的文件事件 
    processFileEvents()
    
    // 处理所有已到达的时间事件
    processTimeEvents()

事件的调度和执行规则:

aeApiPoll函数的最大阻塞时间由到达时间最接近的当前时间的时间事件决定，这个方法既可以避免服务器对时间事件并行频繁的轮询，可以确保aeApiPoll函数不会阻塞时间过长。
因为文件事件是随机出现的，如果处理完文件事件后时间事件仍未到达，继续等待并处理下一个文件事件。
对文件事件和时间事件的处理都是同步，有序，原子地执行的，服务器不会中途中断事件处理，也不会对事件进行抢占。因此耗时的事件会影响整个服务的性能。
因为时间事件是在文件事件之后执行，并且事件之间不会抢占，所以时间事件的实际处理时间通常回避时间事件设定的到达时间稍微晚一些。

客户端

通过使用I/O多路复用技术实现的文件事件处理器，Redis服务器使用单线程单进程的方式来处理命令请求，并与多个客户端进行网络通信。
关于redisClient的定义可以从redis.h中看到，客户端有很多属性。这些属性可以分为两类:

比较通用的属性，这些属性很少特定功能相关，无论客户端执行的是什么工作，它都需要这些属性。
和特定功能相关的属性。下重点介绍这些。

属性

fd(fake client): 伪客户端的fd属性的值为-1,伪客户端处理的命令请求来自于AOF文件或者lua脚本; 普通客户端fd属性值是大于-1的整数，使用套接字与服务器通信，所以fd用来记录客户端套接字的描述符。
name: 默认情况下一个连接到服务器的客户端是没有名字的，但是可以使用CLIENT setnaem命令设置一个名字，可以通过CLIENT list查看。
flags: 一部分标志记录了客户端的角色(如REDIS_MASTER代表主服务器, REDIS_SLAVE代表从服务器), 另一部分标志记录了客户端目前所处的状态(REDIS_MONITOR正在执行monitor, REDIS_MULTI标志客户端正在执行事务)。
querybuf: 用于保存客户端发送的命令请求。输入缓冲区的大小会根据输入内容动态调整，但是最大不能超过1GB,否则服务器将关闭这个客户端。
argv和argc: 服务器将客户端发送的名保存到querybuf后，对命令内容进行分析，得出命令参数及命令的参数个数分别保存到argv和argc中。
authenticated: 记录客户端是否通过了身份验证，未通过用0表示，通过用1表示。
ctime: 记录创建客户端的时间。
lastinteraction: 记录客户端与服务器最后一次进行互动的时间。
obuf_soft_limit_reached_time: 记录输出缓冲区第一次到达软性显示的时间。

执行命令所得的命令回复会被保存到客户端状态的输出缓冲区里，每个客户端都有两个输出缓冲区可用

buf和bufpos: 固定的换缓冲区，用于保存那些长度比较小的回复，如:OK, 简短的字符串值，整数值或错误回复等。buf是缓冲区，bufpos记录buf数组目前已经使用的字节数量。
reply: 可变大小的缓冲区是一个链表,用于保存比较大的回复，比如一个非常长的字符串值，列表等。

创建与关闭

创建不同客户端: 如果客户端是通过网络连接与服务器进行连接的普通客户端，那么在客户端connect函数连接到服务器时，服务器就会调用连接事件处理器为客户端创建响应的客户端状态，并将这个新的客户端状态添加到服务器状态结构clients链表的末尾。
关闭客户端: 一个普通客户端被关闭的原因有很多:
- 客户端进程退出或被杀死
- 客户端向服务器发送了带有不符合协议格式的命令请求
- 客户端成了CLIENT KILL命令的目标
- 用户为服务器设置了timeout配置选项，客户端空转时间超过timeout选项设置的值
- 客户端发送的命令请求大小超过了输入缓冲区的限制大小(1GB)
- 发送给客户端的命令回复超过输出缓冲区的限制大小。按理说输出缓冲区是没有大小限制的，但是为了防止过多占用服务器资源，采用硬性限制和软性限制两种方案限制大小。
Lua脚本的伪客户端: 服务器在初始化时负责创建Lua脚本中包含的Redis命令的伪客户端，在服务器运行的整个周期中都会存在。
AOF文件的伪客户端: 服务器载入AOF文件时，会创建用于执行AOF文件包含的Redis命令的伪客户端，并在载入完成后关闭。

服务器

命令请求的执行过程

前面讲了，客户端发送的请求会被放到输入缓冲区，然后服务器对命令进行解析，转换成协议格式，服务器将通过调用命令执行器来完成余下的步骤:

查找命令
根据上面说的argv[0]参数中对应的命令在命令表中查找参数所指定的命令，并将找到的命令保存到客户端状态的cmd属性里。
命令表是一个字典，字典的键是一个个命令名字，比如”set”,”get”,”del”等;而字典的值则是一个个redisCommand结构，每个redisCommand结构记录了一个Redis命令的实现信息。

redisCommand结构的主要属性:

属性名	类型	作用
name	char *	命令的名字，比如”set”
proc	redisCommandProc *	函数指针，指向命令的实现函数
arity	int	命令参数的个数，用于检查命令请求的格式是否正确
sflags	char *	字符串形式的标识值，这个值记录了命令的属性例如: w:表示写入命令 r:只读命令 m:可能会占用大量内存的命令 a:这是一个管理命令
flags	int	对sflags标识进行分析得出的二进制标识，由程序自动生成
calls	long long	服务器总共执行了多少次这个命令
milliseconds	long long	服务器执行这个民两个所耗费的总时长

执行预备操作
到目前为止，服务器已经将执行命令所需的命令实现函数,参数等都收集齐了，真正执行命令之前还需要一些预备操作：
- 检查客户端状态的cmd指针是否执行NULL
- 检查命令请求所给定的参数个数是否正确
- 检查客户端是否已经通过了身份验证
- 如果服务器打开了maxmemory功能，需要检查服务器的内存占用情况，在有需要的时候进行内存回收
- 其他检查和限制执行的操作等
调用命令的实现函数
当服务器决定要执行命令是client->cmd->proc(client);, 执行函数后会把回复保存到客户端的输出缓冲区，之后实现函数还会为客户端的套接字关联命令回复处理器，这个处理器负责将回复返回给客户端。
执行后续工作
在执行完实现函数后，服务器还需要执行一些后续工作:
- 如果服务器开启了慢查询日志功能，那么慢查询日志模块会坚持是否需要为刚刚执行完的命令请求添加一条新的慢查询日志。
- 根据刚刚执行命令所耗费的时长，更被执行命令redisCommand结构的milliseconds属性，并将calls计数器加一
- 如果服务器开启了AOF持久化功能，那么AOF持久化模块会将刚刚执行的命令请求写入到AOF缓冲区里。
- 如果有其他从服务器正在复制当前这个服务器，那么服务器会将刚刚执行的命令传播给所有从服务器
- 根据刚刚执行命令所耗费的时长，更被执行命令redisCommand结构的milliseconds属性，并将calls计数器加一
- 如果服务器开启了AOF持久化功能，那么AOF持久化模块会将刚刚执行的命令请求写入到AOF缓冲区里。
- 如果有其他从服务器正在复制当前这个服务器，那么服务器会将刚刚执行的命令传播给所有从服务器。

回复发送完毕后，回复处理器会清空客户端状态的输出缓冲区，未处理下一个命令请求做好准备。当客户端接收到协议格式的命令回复后，它会将这些回复转换成人类可读的格式，并打印给用户观看。

serverCron函数

Redis服务器中的serverCron函数默认每隔100毫秒执行一次，这个函数负责管理服务器的资源，并保持服务器自身的良好运转。serverCron的函数主要功能如下面所列:

更新服务器时间缓存: 为了减少获取服务器时间而进行系统调用的次数，服务器状态中的unixtime和mstime属性被用作当前时间的缓存，serverCron函数默认每100ms的频率更新这两个字段。对于设置键值过期时间，慢查询日志这种需要高精度时间的功能来说，服务器还是会再次执行系统调用。
更新LRU时钟: 服务器状态中的lruclock属性保存了服务器的LRU时钟;每个Redis对象都会有一个lru属性，保存了对象最后一次被访问的时间。这个值也是用serverCron来更新。
更新服务器每秒执行命令次数: serverCron函数中的trackOperationsPerSecond函数会以每100ms一次的频率执行，这个函数的功能是以抽样计算的方式，估算并记录服务器在最近一秒钟处理的命令请求数量。可以通过INFO stats查看。
更新服务器内存峰值记录:serverCron每次都会查看服务器当前使用的内存数量，并与stat_peak_memory保持的值进行比较，如果当前的数据比较大就更新这个值。INFO memory命令可以查看具体的数据。
处理SIGTERM信号:服务器启动时，Redis会为服务器进程的SIGTERM信号关联处理器sigtermHandler函数，这个信号处理器负责在服务器接到SIGTERM信号时，打开服务器状态的shutdown_asap标识。如果不拦截这个信号，可能会造成比如RDB持久化操作时关闭服务器。
管理客户端资源:serverCron函数每次执行都会调用clientsCron函数，clientsCron函数会对一定数量的客户端进行以下两个检查:
- 如果客户端与服务器之间的连接已经超时,那么程序释放这个客户端。
- 如果客户端在上一次执行命令请求后，输入缓冲区的大小超过了一定的长度，那么程序会释放客户端当前的输入缓冲区，并重新创建一个默认大小的输入缓冲区，从而防止客户端的输入缓冲区耗费了过多的内存。
管理数据库资源: 每次调用databasesCron函数，对服务器中一部分数据库进行检查，删除其中的过期键，并在需要时，对字典进行收缩操作。
执行被延迟的BGREWRITEAOF
检查持久化操作的运行状态
将AOF缓冲区的内容写入到AOF文件
关闭异步客户端
增加cronloops计数器的值:cronloops记录了serverCron函数执行的次数。

初始化服务器

一个Redis服务器从启动到能够接受客户端的命令请求，需要经过一系列的初始化和设置过程。过程如下:

初始化服务器状态结构:包括设置服务器的运行ID,设置服务器的默认运行频率，设置服务器的默认配置文件路径，设置服务器默认端口号，设置服务器默认持久化条件等。
载入配置选项: 可以通过给定配置函数或指定配置文件来修改服务器的默认配置。
初始化服务器数据结构:包括初始化server.clients链表，初始化执Lua脚本的执行环境server.lua等;还进行了创建共享对象，打开服务器的监听端口等操作。
还原数据库状态: 完成初始化后，服务器需要载入RDB文件或者AOF文件，并根据文件记录的内容来还原服务器的数据库状态。
执行事件循环: 初始完成后，开始执行服务器的事件循环(loop)。