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

redis3.0 标有注解的源码：https://github.com/huangz1990/redis-3.0-annotated

数据库

从Redis服务端的实现角度介绍，包括db存储，切换，键的存储及过期相关处理。

服务器中的数据库

Redis把所有库信息都保存在redis.h/redisServer结构的db数组中，数组类型是redis.h/redisDB，dbnum决定着应该创建多少数据库中的db，clients维护着所有连接Redis的客户端：

struct redisServer{
    //服务器的数据库数量
    int dbnum;
    //一个数组，保存着服务器中的所有数据库
    redisDb *db;
    //客户端状态链表
    list *clients;
    //...
}

服务器数据库实例如图所示：

当切换库时，其实就是redisClient.db对redisServer.db数组的目标数据库指针的移动。下面展示了从0号库切为1号库的过程。通过指针的切换，实现对库的共享：

数据库的键空间

redis将所有key进行统一管理，按照所属的库划分，放在redisDb的字典中（按照上面画的数据结构，redis每一个库都对应一个redisDb）。redisDb结构的dict字典保存了该数据库中的所有键值对，也称为键空间。键空间的数据结构如下：

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

键空间的键就是数据库的键，每个键都是一个字符串对象，键空间的值就是字符串对象，列表对象，哈希表对象，集合对象和有序集合对象（上一章主要是对值的存储结构介绍）。

下图展示了键空间的存储：

当执行一些插入指令时，就是对dict中key的新增；同理，删除键后，dict中的键值对对象都会被删除。

读写键空间时的维护操作(9.3.6详讲)

对键的读写时，服务器会做相应的善后操作，比如更新缓存的命中率，更新LRU（最后一次使用）时间，对已过期的键先进行删除操作，修改时对客户端watch的键进行dirty标记，更新dirty键计数器的值，当开启通知功能后，键修改时需要按配置发送相应通知。

键过期时间相关操作

通过EXPIRE或PEXPIRE，客户端可以以秒或毫秒为精度设置过期时间（Time To Live，TTL）。通过EXPIREAT或PEXPIREAT，客户端可以设置时间戳作为过期时间。

使用TTL或PTTL也可查看某个键的剩余生存时间，还有多久过期：

redis> SET key value
OK

redis> EXPIRE key 500
(integer) 1

redis> TTL key
(integer) 498

Redis是如何保存过期时间的，又是如何删除过期键的将在下面论述。

设置过期时间

Redis提供了4个命令设置过期时间：

• EXPIRE ：将key的生存时间设为ttl秒。
• PEXPIRE ：将key的生存时间设为ttl毫秒。
• EXPIREAT ：将key的过期时间设置为timestamp秒数时间戳。
• PEXPIREAT ：将key的过期时间设置为timestamp毫秒数时间戳。

其实几个命令底层都是经过换算后，用PEXPIREAT实现的。

实现转换关系图：

存储过期时间

redisDb中有一个expires的字典数据结构保存所有键的过期时间，也称为过期字典。过期字典的值是一个long long类型的整数，保存了键所指向的数据库键的过期时间（毫秒精度的Unix时间戳）。

typedef struct redisDb{
    //过期字典，保存着键的过期时间
    dict *expires;
    ...
} redisDb;

图中键空间和过期的键其实复用了一个键对象，这里方便展示就拆开来，假设我们给键alphabet和book都设置了过期时间：

移除过期时间

PERSIST命令可以移除一个键的过期时间，在过期字段中查找给定键，并解除键和值在过期字典中的关联。

redis> SET key value
OK

redis> EXPIRE key 500
(integer) 1

redis> TTL key
(integer) 498

redis> PERSIST message
(integer) 1

redis> TTL key
(integer) -1

计算并返回剩余生存时间

TTL以秒为单位返回剩余时间，PTTL以毫秒返回键的剩余时间。二者的计算都是通过计算键的过期时间与当前时间之差来实现的。

过期键删除策略

如果一个键过期了，那么在什么时候被删除？列举几个常见淘汰策略：

1. 定时删除：设置键的过期时间时，创建定时器，过期时，以定时器立刻执行键的删除。
2. 惰性删除：不着急删除过期键，每次获取时都会进行过期校验。
3. 定期删除：隔一段时间，程序就对数据库检查，删除过期键。

定时删除

定时删除策略对内存友好，但对CPU不友好。过期键比较多时，删除会占用资源，特别是和删除当前任务无关的过期键，影响性能。Redis定时器需要创建时间事件，时间事件底层由无序链表实现，查找复杂度为O(N)，如果需要高效处理必然要创建大量的定时器，并不现实。

惰性删除

惰性删除对CPU友好，但对内存不友好。不需要把时间浪费在非相关键的删除上。当键非常多时，会导致内存泄漏，因为只有用到时才会判断，删除。

定期删除

定期删除是一种折衷的方式，隔一段时间执行一次，并限制删除操作执行的时长和频率减少对CPU的占用；定期删除还能减少庞大的过期键对内存的占用。如何确定时长和频率是难点，过长或过少，会退变为定时删除和惰性删除。

Redis的过期键删除策略

Redis使用了惰性删除和定期删除两种策略配合，服务器可以合理地在使用CPU时间和避免内存浪费之间权衡。

• 惰性删除策略的实现

  该策略由db.c/expireIfNeeded函数实现，如同指令过滤器，在执行读写键指令时都会调用该函数检查键是否过期，如果过期则删除。

• 定期删除策略的实现

  该策略由redis.c/activeExpireCycle函数实现，当服务器周期性调用redis.c/serverCron函数时，activeExpireCycle函数就会被调用，规定时间内，多次遍历服务器的各个数据库，从expires字典中随机检查一部分键的过期时间，并删除过期键。activeExpireCycle函数的主要工作可以拆分为：

  1. 每次运行，都从一定数量的数据库中取出一定数量的随机键检查并删除过期键。
  2. 全局遍历记录检查进度，有记忆功能，全局变量存储的是几号库。
  3. 当所有数据库都被检查一遍后，重置全局变量，进行新一轮检查。

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

载入RDB文件：

• 若服务器以主服务器模式运行，那么在载入RDB文件时，程序会对文件中保存的键进行检查，未过期的键会被载入到数据库中，而过期键则会被忽略，所以过期键不会对主服务器载入RDB文件产生影响
• 若以从服务器模式运行，那么在载入RDB文件时，文件中保存的所有键，不论是否过期，都会被载入到数据库中。不过，主从服务器在进行数据同步时，从服务器的数据库会被清空，所以过期键不会对从服务器载入RDB文件产生影响

写入AOF文件：

• 若某个键已过期但未被删除，那么AOF文件不会因这个过期键产生任何影响
• 若某个键已过期并被删除后，程序会向AOF文件追加一条DEL命令

重写AOF文件：

• 与生成RDB文件类似，在重写AOF文件过程中，程序会对数据库中的键进行检查，已过期的键不会被保存到重写后的AOF文件中

复制：

• 主服务器删除一个过期键后，会向所有从服务器发送一个DEL命令，告知从服务器删除该过期键
• 从服务器在执行客户端发送的读命令时，即使遇到过期键也不会做什么，而时像处理未过期键一样处理该键，将其值返回。只有在收到主服务器发过来的DEL命令后，从服务器才会删除该过期键。

数据库通知

Redis发布订阅功能可以让客户端获取数据库中键的变化及命令的执行情况。关注某个键执行了什么命令的通知称为键空间通知。关注某个命令被什么键执行的通知称为事件通知。

主要就是围绕通知功能，简单看下发送通知及其实现。

发送通知

该功能由notify.c/notifyKeyspaceEvent函数实现：

通过几个入参：要发送的通知类型，事件名称，产生事件的键，产生事件的数据库号。来构造事件通知内容和接收频道名，Redis许多指令的执行函数都会调用这个函数，传递该命令引发的事件相关信息。

发送通知的实现

1. 通过服务器配置的值判断，如果给定通知类型不是服务器允许的就直接返回。
2. 如果是服务器允许发送的，检测是否允许发送键空间通知，允许则构建发送事件并通知。
3. 检测是否允许发送键事件通知，如果允许则构建并发送通知。

RDB持久化

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

为解决这个问题，Redis提供了持久化的功能，可将内存中的数据库保存到磁盘，防止意外丢失。RDS持久化（默认持久化策略）就是将某一时间点上的状态保存到一个RDB文件里。RDB文件是经过压缩的二进制文件，可通过该文件还原成数据库状态。

RDB文件的创建与载入

有两个命令可用于生成RDB文件（SAVE和BGSAVE）。他们之间的区别是：SAVE会阻塞Redis服务器进程，直到RDB文件创建完毕为止，阻塞期间，服务器不能处理任何命令请求。而BGSAVE会fork出一个子进程，由子进程负责创建RDB文件，父进程继续处理命令请求。当子进程完成之后，向父进程发送信号。

创建就是执行SAVE/BGSAVE底层调用rdbSave函数的过程，载入就是服务启动时读取RDB文件底层调用rdbLoad函数的过程。

适用场景

• 适合大规模的数据恢复
• 对数据完整性和一致性要求不高

缺陷

• 在一定间隔时间做一次备份，所以如果redis挂了，就会丢失最后一次快照后的所有修改。
• fork的时候，当数据集较大时，可能会导致整个服务器停止服务几百毫秒，甚至是1秒钟。

BGSAVE执行时的服务器状态

BGSAVE命令执行期间，对SAVE，BGSAVE，BGREWRITEAOF（AOF持久化命令）三个命令的处理方式如下：

• 由于SAVE，BGSAVE底层都是调用rdbSave来持久化文件的，而且父子进程同时执行两个rdbSave调用会产生竞态条件，所以这两个指令会被服务器拒绝。
• BGREWRITEAOF会被延迟到BGSAVE执行结束后执行。

如果BGREWRITEAOF正在执行，服务器会拒绝BGSAVE命令。由于BGREWRITEAOF和BGSAVE都会产生子进程且有大量的磁盘写入，出于性能考虑不会同时执行。

简单来说，就是BGSAVE执行期间，拒绝SAVE，BGSAVE；延迟执行BGREWRITEAOF。BGREWRITEAOF执行期间，拒绝BGSAVE。

RDB与AOF共存的载入情况

RDB文件的载入是在服务器启动时执行，Redis并没有专门提供载入RDB文件的命令。由于AOF文件的更新频率更高，因此开启AOF持久化功能后，启动时优先加载AOF还原数据，只有在AOF处于关闭状态，才使用RDB文件恢复数据。

自动间隔性保存

服务器允许用户通过配置文件设置隔一定时间自动执行BGSAVE。可通过save选项设多个保存条件，默认的配置如下：

save 900 1
save 300 10
save 60 10000

只要满足任意条件，900s内对数据库进行1次修改或300s内…BGSAVE就会被执行。

那么，服务器是如何根据save选项来自动执行BGSAVE的？
从实现角度考虑，我们需要记录配置、评判依据和依据更新驱动。记录配置由saveparams实现；评判依据是dirty计数器和lastsave属性；依据更新驱动就是serverCron对评判依据的动态更新。
save配置都会在redisServer的saveparam数组中体现：

struct redisServer{
    //记录了保存条件的数组
    struct saveparam *saveparams;
    ...
};
struct saveparam{
    //秒数
    time_t seconds;
    //修改数
    int changes;
};

dirty计数器和lastsave属性

这两个属性由redisServer持有：

• dirty计数器记录距离上次成功执行SAVE或BGSAVE后数据库被修改了几次。
• lastsave是一个UNIX时间戳，记录上次成功执行SAVE或BGSAVE的时间。

struct redisServer{
    //修改计数器
    long long dirty;
    //上一次执行保存的时间
    time_t lastsave;
    //...
};

检查条件是否满足

Redis的周期性操作函数serverCron每隔100毫秒会执行一次，其中一项工作就是检查save选项设置的保存条件是否满足要求，满足则执行BGSAVE。

RDB文件结构

REDIS：长度5字节，保存”REDIS”5个字符（为书写方便，其实是5个单独字符），通过这个判断该文件是否为RDB文件。

db_version：长度4字节，是字符串表示的整数记录RDB的版本号。

database：包含0个或多个数据库及各数据库中键值对数据。表示那些数据库是有数据的。

EOF：常量长度1字节，标志RDB文件正文的结束。读取时遇到该值，表示键值对的载入已经结束了。

check_sum：是一个8字节的无符号整数，保存一个同过前几位变量计算出来的校验和。每次加载都会进行计算校验，通过这个来判断文件是否损坏。

database部分

每个非空数据库在RDB文件中都可表示为SELECTDB，db_number，key_value_pairs三部分

• selectdb：1字节，标志位，标志着下一位存储的是数据库号码。
• db_number：是一个数据库号码。
• key_value_pairs：保存了数据库中所有键值对数据，如果有过期时间，则过期时间也会保存。

key_value_pairs部分

不带过期时间的键值对在RDB文件由TYPE，key，value组成，带过期时间则含有EXPIRETIME_MS，ms：

EXPIRETIME_MS：标志位，长度为1字节，告知程序下一个读入的是以毫秒为单位的过期时间。
ms：是8字节长的带符号整数，记录UNIX时间戳，即过期时间。
type：记录value的类型，长度1字节，这个常量其实就是Redis对象类型和底层编码的组装：

• REDIS RDBTYPE_STRING
• REDIS_ RDB_TYPE_LIST
• REDIS_RDB_TYPE_SET
• REDIS_RDB_TYPE_ZSET
• REDIS_RDB_TYPE_HASH
• REDIS_RDB_TYPE_LIST_ ZIPLIST
• REDIS_RDB_TYPE_SET_INTSET
• REDIS_RDB_TYPE_ZSET_ZIPLIST
• REDIS_RDB_TYPE_HASH_ZIPLIST

服务器会根据TYPE来决定如何读入和解释value的数据。

key就不用做过多解释~

value的编码

根据TYPE的不同，value的存储结构也大不相同。这里不详细展开，只需要知道，对于字符串对象，如果大于20字节，就会用LZF算法压缩。除字符串对象和整数集合，其他存储方式的开头都是节点数量，告诉程序应读入多少节点/键值对。（详细内容可查阅10.3.3节）

分析RDB文件

Redis自带RDB文件检查工具redis-check-dump。可以帮助在系统故障后分析快照文件，也就是RDB文件。

AOF持久化

AOF持久化是通过保存Redis服务器所执行的写命令来记录数据库状态。服务器启动时，可通过载入和执行AOF文件中保存的命令来还原服务器关闭前的数据库状态。

AOF持久化的实现

AOF持久化可分为命令追加，文件写入，文件同步三个步骤。

命令追加

开启AOF持久化后，服务器执行完一个写命令后，会以协议格式将被执行的写命令追加到服务器状态的aof_buf缓冲区末尾：

struct redisServer{
    //AOF缓冲区
    sds aof_buf;
    ...
};

AOF文件的写入与同步

Redis服务器进程就是一个事件循环，负责接收客户端命令请求及命令回复，时间事件负责执行像serverCron函数这样需要定时运行的函数。服务器每结束一个事件循环前，都会调用flushAppendOnlyFile函数，考虑是否有必要将aof缓冲区中的内容写入和保存至AOF文件里。

这个判断的依据就是根据配置文件的appendfsync值决定：

• always：将aof_buf缓冲区的所有内容写入并同步到AOF文件。
• everysec：将aof_buf缓冲区中的所有内容写入到AOF文件，如果此时与上次同步AOF文件的时间超过一秒，就再次对AOF文件进行同步，并由一个线程专门负责。
• no：将aof_buf缓冲区中的所有内容写入到AOF文件，但并不对AOF文件进行同步，何时同步由操作系统决定。

为什么有写入和同步的区分？写入≠同步

为提高写效率，操作系统一般将写入数据暂时保存在内存缓冲区，等缓冲区填满或超过指定时间后才会真正地将数据同步到磁盘里。操作系统提供了fsync和fdatasync两个同步函数，可强制操作系统同步数据，保证数据安全性。

也就是说，每一次的事件循环，aof_buf中的指令都会被写入操作系统的缓冲区，根据appendfsync配置，当操作系统缓冲区满足一定条件后，才被真实地写入磁盘内。

AOF文件的载入与数据还原

步骤如下：

1. 创建一个没有网络连接的伪客户端。（由于Redis命令只能在客户端上下文中执行，并且AOF文件在本地而不是网络）。
2. 解析AOF文件并取出一条写命令。
3. 使用伪客户端执行被读出的写命令
4. 持续执行2和3，直到所有写命令都已经执行完毕

AOF重写

因为AOF持久化会将所有的写命令都记录，所以会有冗余情况，比如频繁地创建删除键值对，或者对同一个键的值频繁更新，都会导致文件的内容越来越多。所以需要一种瘦身的机制确保AOF里存的都是必不可少的精华。

Redis提供AOF文件重写功能，让服务器创建一个新的AOF文件，替代现有的AOF文件，减少冗余命令。

AOF文件重写的实现

在新的AOF文件的重写过程中，不会读取旧AOF文件，而是通过读取数据库状态来实现的。首先从数据库中读取键现在的值，然后用一条命令记录键值对，代替之前记录的多条命令。

注：在重写时会先检查键所包含的元素数量，因为多元素的键在命令转换时可能会导致客户端输入缓冲区溢出。该限制由配置中对应的一个常量控制，默认超过64个就用多条指令记录。

AOF后台重写过程

AOF重写的过程中会有大量的写入操作，为了避免Redis服务器长时间的阻塞，重写工作将被放到子进程中进行。这样的好处是：

• 父进程仍然可继续处理请求。
• 子进程有自己的数据副本，而非子线程，可以避免一些线程安全性问题的出现。

子进程在执行AOF重写期间，服务器进程还需要继续处理命令请求，而新的命令可能会对现有的数据库状态进行修改，导致当前数据库状态与重写后的AOF文件保存的状态不一致。为解决这个问题，设置了AOF重写缓冲区。

当重写子进程创建后，Redis服务器执行完写命令就会将其写入AOF缓冲区和AOF重写缓冲区，子进程执行重写期间，服务器进程要执行3个工作：

1. 执行客户端发来的命令。
2. 将执行后的写命令追加到AOF缓冲区。
3. 将执行后的写命令追加到AOF重写缓冲区。

当子进程完成重写后，会向父进程发送一个信号，父进程接收并调用信号处理函数，将重写缓冲区的所有内容写到新AOF文件中，原子地覆盖现有的AOF文件。因此整个AOF文件重写的过程中，只有信号处理函数执行时，才会阻塞，将性能损耗降到最低。

事件

Redis服务器是一个事件驱动程序，主要有两种：

• 文件事件：Redis服务器通过套接字与客户端连接，文件事件就是服务器对套接字操作的抽象。服务器与客户端通信会产生相应文件事件，服务器通过监听这些事件来完成一系列网络通信操作。
• 时间事件：Redis服务器有一些需要在给定时间内执行的操作，而时间事件就是对这类定时操作的抽象。

简单来说，文件事件就是套接字操作相关的事件；时间事件就是定时操作相关事件。

文件事件

Redis基于Reactor模式开发的网络事件处理器，就是文件事件处理器。大致是使用I/O多路复用程序同时监听多个套接字，根据套接字目前执行的任务为套接字关联不同的事件处理器；当被监听的套接字准备好应答，读取，写入，关闭等操作时。与之对应的文件事件就会产生，文件事件处理器就开始发挥作用了，调用事先关联好的事件处理器来处理事件。

利用多路复用，虽然以单线程的方式运行，但文件事件处理器实现了高性能的网络通信模型，又能很好的与Redis服务器中其他模块对接，保持了设计的简单性。

文件事件处理器的组成

由套接字，I/O多路复用程序，文件事件分派器，事件处理器组成。

I/O多路复用程序负责监听多个套接字，并向文件事件分派器传送那些产生了事件的套接字。I/O多路复用程序总是将所有产生事件的套接字放入到一个队列中，以有序，同步，一次一个套接字向文件事件分派器传送的姿态来运行。只有当上一个套接字产生事件被事件处理器执行完了，才会继续传送下一个套接字。

下图展示了多路复用程序使用队列传输套接字：

I/O多路复用的实现

Redis为所有多路复用的函数库进行包装，每个多路复用函数库在其中都对应一个单独文件：ae_select.c,ae_epoll.c,ae_kqueue.c。为每个多路复用函数都实现了相同的API，所以多路复用程序的底层实现是可以互换的。Redis在多路复用程序源码中用宏定义了相应规则，使得程序在编译时自动选择系统中性能最高的I/O多路复用函数库。

有关多路复用的知识可以参考：https://zhuanlan.zhihu.com/p/127170201

事件的类型

多路复用程序可监听的套接字事件可分为ae.h/AE_READABLE事件和ae.h/AE_WRITABLE事件。

• 当套接字变得可读时（客户端对套接字执行write，close，accept后），套接字产生AE_READABLE事件。
• 当套接字变得可写时（客户端对套接字执行read操作后），套接字产生AE_WRITABLE事件。

I/O多路复用程序允许服务器同时监听者两个事件，如果某个套接字同时产生了两种事件，文件事件分派其会优先处理AE_READABLE，再处理AE_WRITABLE

文件事件的处理器

根据客户端的需要，事件处理器分为连接应答处理器，命令请求处理器，命令回复处理器，复制处理器。这里只介绍前三者。

1. 连接应答处理器

   networking.c/acceptTcpHandler函数是Redis的连接应答处理器，用于连接服务器监听套接字的客户端进行应答。

   Redis服务器初始化时，程序就将连接应答处理器和服务器监听套接字的AE_READABLE事件关联，当客户端调用sys/socket.h/connect函数时连接服务器监听套接字时，套接字就会产生AE_READABLE事件，引发连接应答处理器执行，并执行相应的套接字应答操作。

   简单来说就是客户端连接被监听的套接字时，套接字产生并触发读事件，连接应答处理器就会执行。

2. 命令请求处理器

   networking.c/readQueryFromClient函数是Redis命令请求处理器，主要负责从套接字中读入客户端发送的命令请求内容。

   当客户端成功连接到服务器后，服务器会将AE_READABLE事件和命令请求处理器关联。当客户端向服务器发送命令请求时，套接字产生AE_READABLE事件，引发命令请求处理器执行，执行相应套接字的读入操作。

   简单来说就是客户端发送命令请求时，套接字产生并触发读事件，命令请求处理器就会执行。

3. 命令回复处理器

   networking.c/sendReplyToClient函数是Redis的命令回复处理器，负责将服务器执行命令后得到的命令回复通过套接字返回给客户端。

   当需要回复命令结果时，服务器会将客户端套接字的AE_WRITEBLE事件和命令回复处理器关联，当客户端准备好接收回复时就会产生AE_WRITABLE事件，引发命令回复处理器执行。执行结束，服务器会解除命令回复处理器与客户端的套接字AE_WRITABLE事件之间的关联。

   简单来说就是服务器发送命令回复时，套接字产生并触发写事件，命令回复处理器就会执行。

总结

一次完整的基于文件事件的服务器与客户端交互，相关处理器的处理过程：

1. 客户端发起连接，产生读事件，触发连接应答处理器执行。创建套接字，客户端状态并将该套接字的读事件与命令请求处理器关联。
2. 客户端发送命令，产生读事件，触发命令请求处理器。读取执行命令，得到回复并将该套接字的写事件与命令回复处理器关联。
3. 客户端读取命令回复，产生写事件，触发命令回复处理器。将回复写入套接字，解除写事件与命令回复处理器的关联。

时间事件

时间事件可分为定时事件和周期性事件：

• 定时事件:只在指定时间到达时执行一次。如xx时间后执行一次。
• 周期性事件:每隔一段时间执行一次。如每隔xx秒执行一次。

注：Redis一般只用周期性事件。

时间事件的组成

一个时间事件主要由以下三个属性组成：

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

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

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

实现

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

因为事件ID只能增大，所以新插入的id总是最大的。

serverCron函数

很多情况下，Redis需要定期进行资源检查，状态同步等操作，就需要定期操作，而定期操作都是由serverCron函数负责的，也是时间事件的应用实例。默认每隔100ms执行，具体工作包括：

• 更新服务器的各类统计信息，比如时间、内存占用、数据库占用情况等。以及清理数据库中的过期键值对。
• 关闭和清理连接失效的客户端。
• 尝试进行AOF或RDB持久化操作。
• 如果服务器是主服务器，那么对从服务器进行定期同步。
• 如果处于集群模式，对集群进行定期同步和连接测试。

下面简单从几个方面出发，介绍serverCron的本职工作。

更新服务器时间缓存

Redis不少功能依赖于系统当前时间，每次获取系统时间都会进行系统调用，为减少系统调用次数，服务器使用了unixtime和mstime作为当前时间的缓存。

struct redisServer{

    //保存了秒级精度的系统当前UNIX时间戳
    time_t unixtime;
    //保存了毫秒级的系统当前UNIC时间戳
    long long mstime;
    ...
}

由于serverCron默认100毫秒更新一次unixtime和mstime，导致其精度不高，只使用于精度要求不高的场景：

• 服务器打印日志，更新服务器的LRU时钟，决定执行持久化，计算上限时间等。
• 设置过期时间，添加慢查询日志需要高高进度，服务器还是会进行系统调用。

更新LRU时钟

每个Redis对象也会有lru属性，记录上一次被命令访问的时间。如果要计算一个键的空转时长，就要通过lrulock记录的时间减去对象的lru属性记录时间。

struct redisServer{

    //默认每10秒更新一次的时钟缓存，
    //用于计算键的空转时长
    unsigned lrulock:22;
    ...
}
typedef struct redisObject{
    //对象最后一个被命令访问的时间
    unsigned lru:22;
    ...
} 

更新服务器每秒执行命令数

抽样计算函数以100毫秒一次，估算最近一秒钟的处理请求数。每次都会根据4个变量（上次抽样时间、当前时间、上次抽样已执行命令数、当前已执行命令数）来计算调用之间平均每毫秒处理几个命令，乘以1000就是1秒内处理命令的估计值。这个估计值会被放入redisServer的ops_sec_samples数组中。当我们需要知道秒内的指令数时，就会计算这个数组的平均数，因此结果是一个估算值。

更新服务器内存峰值记录

struct redisServer{

    //已使用内存峰值
    size_t stat_peak_memory;
    ...
}

stat_peak_memory记录内存峰值，每次serverCron函数执行就会判断是否需要刷新内存峰值，如果当前使用的多就刷新。

管理客户端资源

serverCron每次执行都会调用clientsCron函数对客户端进行检查：如果已经超时则关闭；如果输入缓冲区大小超过一定长度则重新创建默认大小的输入缓冲区。

管理数据库资源

serverCron每次执行都会调用databaseCron函数，会对服务器的一部分数据库检查，删除过期键；对字典收缩。

执行被延迟的BGREWRITEAOF

struct redisServer{

    //AOF延迟标志位，如果为1，则有AOF操作被延迟
    int aof_rewrite_shceduled;
    ...
}

由aof_rewrite_shceduled标志位决定，如果处于BGSAVE命令执行期间，BGREWRITEAOF会被延迟到BGSAVE执行后执行。

检查持久化操作的运行状态

struct redisServer{

    //执行BGSAVE命令的子进程，没有为-1
    pid_t rdb_child_pid;
    //执行BGREWRITEAOF命令的子进程，没有为-1
    pid_t aof_child_pid;
    ...
}

rdb_child_pid和aof_child_pid只要一个不为-1，则检查子进程是否有信号发来。如果有信号到达则进行后续操作，比如新RDB文件的替换，重写的AOF文件替换等。

如果rdb_child_pid和aof_child_pid都为-1，则进行检查：

• 是否有BGREWRITEAOF被延迟，有的话就进行BGREWRITEAOF操作。
• 自动保存条件是否满足，满足且未执行其他持久化操作则执行BGSAVE。
• AOF重写条件是否满足，满足且未执行其他持久化操作则开始一次新的BGREWRITEAOF操作。

事件的调度与执行

当服务器同时存在时间事件和文件事件，调度时该如何选择，花费多久？

事件的调度由ae.c/aeProcessEvents函数负责。对于每一次事件循环，主要过程是：

1. 拿到最近的时间事件并计算还有多少毫秒。
2. 创建时间任务结构；阻塞等待文件事件产生，最大阻塞时间由最近时间事件到达毫秒数决定。
3. 先处理已产生的文件事件再处理到达的时间事件。

执行原则/设计利弊：

1. aeApiPoll函数（redis封装的多路复用函数）的最大阻塞时间由到达时间最接近当前时间的时间事件决定，这个方法既可以避免服务器对时间事件进行频繁的轮询(忙等待)，也可以确保aeApiPoll函数不会阻塞过长时间。
2. 因为文件事件是随机出现的，如果等待并处理完一次文件事件之后，仍未有任何时间事件到达，那么服务器将再次等待并处理文件事件。
3. 对文件事件和时间事件的处理都是同步、有序、原子地执行的，服务器不会中途中断事件处理，也不会对事件进行抢占，因此，不管是文件事件的处理器,还是时间事件的处理器，它们都会尽可地减少程序的阻塞时间，并在有需要时主动让出执行权，从而降低造成事件饥饿的可能性

客户端

本文第一章提到过Redis服务器的状态结构clients属性是链表，记录了所有与服务器相连的客户端结构，对客户端执行批量操作或查找操作，都可以通过clients链表完成：

struct redisServer{
    //一个链表，保存了所有客户端状态
    list *clents
    ...
};

客户端属性

客户端的属性主要分为通用和特定的，这里主要介绍通用的。简单来说有套接字描述符，标志，输入缓冲区，命令与参数，输出缓冲区，时间等。

typedef struct redisClient{
    //套接字描述符
    int fd;
    //标志
    int flags;
    //输入缓冲区
    sds querybuf;
    //单个命令拆分的数组
    robj **argv;
    //argv数组的长度
    int argc;
    //命令函数
    struct redisCommand *cmd;
    //固定大小输出缓冲区，默认16K
    char buf[REDIS_REPLY_CHUNK_BYTES];
    //buf已使用字节数
    int bufpos;
    //大小可变输出缓冲区
    list *reply
    //创建客户端的时间
    time_t ctime;
    //与服务器互动的最后时间
    time_t lastinteraction;
    //软性限制时间
    time_t obuf_soft_limit_reached_time;
    ...
}redis client;

套接字描述符fd

根据客户端类型不同：

• fd为-1表示伪客户端。
• fd为大于-1的整数时表示普通客户端。

伪客户端就是用于处理的命令请求来源于AOF或Lua脚本，不需要套接字连接，也就不需要套接字记录符。普通客户端就是所有来源于网络需要套接字连接的客户端。

标志flags

标志flags记录了客户端的角色。有主从标志，Lua伪客户端标志，执行MONITOR标志…标志可以以二进制来拼接：flags:||…

输入缓冲区querybuf

输入缓冲区存储客户端输入的指令，大小根据输入内容动态缩小扩大，最大不可超过1G，否则导致服务器关闭该客户端。

命令与参数(argv，argc）

在将客户端输入的命令保存到querybuf后，服务器将对命令进行解析，并将得到的命令参数以及命令参数的个数存放到数组argv和整数argc中，其数据结构是这样的：

当客户端输入命令后，服务器根据argv[0]的值在命令表中查找（命令不区分大小写）对应命令的函数并给cmd赋值，cmd就是对应的命令函数相关的操作信息。

命令表是一个字典，字典的键是一个SDS结构，保存了命令的名字，字典的值是命令的redisCommand结构，这个结构保存了命令的实现函数、命令的标志、命令需要的参数个数以及总执行次数和总消耗时长等统计信息。

输出缓冲区（buf，bufpos，reply）

输出缓冲区有两个，一个大小固定，一个大小可变。大小固定的存储长度小的回复，比如OK，错误返回等。大小可变缓冲区保存长度较大的回复，比如长列表，大集合。

大小可变缓冲区由reply链表实现，利用链表结构存储若干和字符串对象，使得长度不会受到限制。

其数据结构如下：

时间（ctime，lastinteraction，obuf_soft_limit_reached_time）

• ctime属性记录了创建客户端的事件
• lastinteraction属性记录了客户端与服务器最后一次进行互动的事件
• obuf_soft_limit_reached_time记录了输出缓冲区第一次到达软性限制的时间

服务器使用两种模式来限制客户端输出缓冲区的大小:

• 硬性限制( hard limit):如果输出缓冲区的大小超过了硬性限制所设置的大小，那么服务器立即关闭客户端。
• 软性限制(softlimit):软性限制比硬性限制小，服务器会根据输出缓冲区大小介于软硬性限制之间的时间决定是否关闭客户端 。

客户端的创建与关闭

由于客户端有不同类型，所以创建和关闭的方式也不相同。

创建普通客户端

客户端连接时调用connect函数，服务器就会调用连接事件处理器，为客户端创建相应的客户端状态，并将该新的客户端状态添加到client链表末尾。

关闭普通客户端

普通客户端可因其中一个原因关闭：

• 客户端进程退出或者被杀死
• 客户端向服务器发送了带有不符合协议格式的命令请求
• 客户端成为了CLIENT KILL命令的目标
• 用户为服务器设置了timeout配置选项且当客户端的空转时间超过timeout时。不过timeout选项有一些例外情况：若客户端是主服务器，从服务器，正在被BLPOP等命令阻塞，或正在执行SUBSCRIBE、PSUBSCRIBE等订阅命令，那么即使客户端的空转时间超过了timeout选项的值，客户端也不会被服务器关闭。
• 客户端发送的命令请求的大小超过了输入缓冲区的限制大小(默认为1GB)
• 输出缓冲区的大小超过了硬性限制所设置的大小
• 输出缓冲区的大小超过了软性限制所设置的大小，但还没超过硬性限制的时间超过指定时间。

Lua脚本的伪客户端

服务器初始化时创建，随服务器结束关闭。

AOF文件的伪客户端

载入AOF文件时创建，载入结束关闭。

服务器

简而言之，这章就是在解释客户端输入Redis指令到返回结果的执行过程。

初始化服务器

首先是Redis服务器初始化操作，服务器从启动到能够处理客户端的命令请求需要执行以下步骤：

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

初始化服务器状态结构

主要是对redisServer结构体的初始化，包括设置服务器运行ID，运行频率，设置配置文件路径，设置持久化条件，命令表创建等。

载入配置选项

根据用户设定的配置，对redisServer相关变量的值进行修改，比如端口号，数据库数量，RDB的压缩是否开启等等。其他属性还是沿用默认值。

初始化服务器数据结构

对除了命令表外的数据结构（包括客户端链表，db数组，订阅信息，Lua脚本执行环境，慢查询日志相关属性等等）进行初始化。

服务器必须先载入用户配置，才能对其他数据结构进行准确初始化。否则，若是先初始化再根据用户配置设定相关值，那么若是用户配置的值和默认值不同，且该配置和数据结构有关，那么服务器就要重新调整和修改已创建的数据结构。这样就会比较麻烦。

还原数据库状态

载入RDB或AOF文件的数据恢复过程。

执行事件循环

至此，服务器可接收客户端请求并发送信息。

命令执行过程

以SET key value为例，命令的执行过程是：

1. 客户端发送命令。
2. 服务器接收并处理请求，对数据库操作，回复OK。
3. 服务器将命令回复OK返回给给客户端。
4. 客户端接收命令并打印结果。

下面将按照步骤拆解为发送，读取查找，执行预备操作，调用实现函数，执行后续工作，回复，打印操作讲解。

发送

客户端接收命令请求时，会将命令根据协议转为固定格式再发送给服务器。

读取

当套接字因客户端的写入变得可读时，服务器会先读取协议格式内容并保存到输入缓冲区。命令分析，提取参数及个数，存入argv和argc属性。最后调用命令执行器。

命令执行器-查找命令的实现

命令表是一个字典，键是命令名字，值是redisCommand结构。几个重要属性如下：

• name：命令名称。
• proc：指向命令实现函数。
• arity：命令参数个数，包括命令名称。
• sflags：命令属性。

查找命令表的过程就是找到redisCommand，把指针指向它：

命令执行器-执行预备操作

在命令真正执行前需要有预备操作保证命令可以被正确，顺利地执行。这个环节相当于一层过滤，比如检查命令是否正确，参数是否正确，身份验证是否通过，内存是否够用等等。保证配置生效，准确执行。

命令执行器-调用命令的实现函数

执行过程就是调用之前找到并指向的执行函数。通过client->cmd->proc(client);调用。然后将回复保存在客户端状态的输出缓冲区中，关联该套接字的命令回复处理器。

命令执行器-执行后续工作

有一些善后工作还将继续，比如慢查询日志记录，执行时长记录，AOF持久化，主服务器将命令传给从服务器。当这些都处理完后，服务器就继续从文件事件处理器中取出并执行下一个命令请求。

将命令回复发送给客户端

当客户端套接字变为可写状态，服务器执行命令回复处理器，将输出缓冲区的回复发送给客户端。

客户端接收并打印命令回复

将回复转为人类可读的格式，打印给用户看。

总结

数据库章节主要介绍键值对的宏观存储是怎么实现的和过期策略。通过RedisServer进行组织，用字典存键值对，具体数据结构按照对象的编码存储。客户端与服务器主要通过共享指针的方式来共享库对象。键的过期时间是按照单独的键过期字典存储的，设置过期时间的命令都会转换为PEXPIREAT来实现。Redis使用惰性删除和定期删除作为移除策略。每次对键的读取都会判断是否过期，定期抽查并删除过期键。

RDB持久化章节主要介绍持久化机制和发生时机，BGSAVE指令对其他指令的排斥性，RDB文件结构。RDB文件载入时，主服务器会检查键是否过期。RDB的实现分为SAVE和BGSAVE，SAVE会阻塞，BGSAVE是通过fork子进程来写RDB文件的方式，来记录Redis的数据库快照。BGSAVE随着serverCron函数的执行，每次都会判断是否有必要执行。

AOF持久化章节主要介绍持久化机制，时机，重写过程。AOF文件载入时不会判断键是否过期，只是执行文件中的命令。AOF开启后，执行一个写命令就会被追加到aof_buf中。AOF持久化过程是根据其同步策略配置，一次事件循环，一定会将aof_buf中的命令写到操作系统缓冲区，在根据配置考虑是否需要强制写入磁盘。AOF重写是对文件的瘦身计划，为了解决子进程执行AOF文件重写前后数据库状态不一致的问题，AOF重写缓冲区会记录在这期间对数据库的变更，子进程结束后发信号，主进程接收后会进入阻塞阶段，同步重写缓冲区至新的AOF文件。

事件章节主要介绍文件事件和时间事件。文件时间是对套接字操作的事件，时间事件是对定时操作相关的事件。文件事件利用I/O多路复用程序监听多个套接字，根据相应的可读/可写事件来触发并移交给文件事件分派器，分派器会给具体的事件处理器处理。然后介绍了时间事件的组成，serverCron的职能，主要负责对资源的检查，更新，判断操作。对于两种事件同时出现情况的处理机制，利用等待时间事件的空隙作为文件事件的最大阻塞时间，然后先处理随机的文件事件，再处理时间事件。不浪费CPU资源，提高效率。

客户端章节主要介绍redisClient的属性，包括套接字描述符，输入缓冲区，时间等。然后介绍普通客户端的创建和关闭原因，是通过对应的事件处理器进行的。其他的伪客户端主要是AOF伪客户端按卸磨杀驴的套路，在载入时创建，载入结束后关闭。

服务器章节主要描述了Redis一条指令的执行过程，从初始化到具体的过程细化，发送命令，读取命令，查找命令字典，执行预备操作，调用实现函数，善后工作，发送回复，客户端打印。