单机数据库的实现

Redis数据库

Redis数据库的实现

struct redisServer {

  //...

  //保存服务器中的所有数据库, 数组

  redisDB *db;

  //服务器的数据库数量

  int dbnum;

  //...

};

/**

 * 客户端状态

 */

typedef struct redisClient {

  //...

  //记录客户端正在使用的数据库

  redisDB *db;

  //...

} redisClient;

过期键删除策略

定时删除：创建大量的定时器，从而实现定时删除策略

内存友好：通过使用定时器，定时删除可以保证过期键会尽可能快地被删除，并释放占用的内存。

CPU不友好：在过期键较多的情况下，删除过期键这一行为会占用相当一部分的CPU时间。
惰性删除：程序只会在取出键时才进行过期检查，并且删除已过期的键

内存不友好：如果一个键已过期，又恰好没有被访问，则一直占用内存。

CPU友好：只有在取出键时检查，不会删除任何其他无关的过期键
定期删除：前两种策略的trade-off

定期删除策略每隔一段时间执行一次删除过期键操作，并通过限制删除操作执行的时长和频率来减少删除操作对CPU的影响。

定期删除的难点：确定删除操作执行的时长和频率

Redis服务器实际使用的是惰性删除和定期删除两种策略

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

RDB持久化

生成RDB文件：已过期的键不会保存到新创建的RDB文件中。
载入RDB文件：如果以主服务器模式运行，载入时会对文件中保存的键进行检查，未过期的键会被载入，而过期的键则会被忽略；如果以从服务器模式运行，文件中保存的所有的键都会被载入到数据库，不过主从服务器在进行数据同步时，从服务器的数据会被清空。

AOF持久化

AOF文件写入：当过期键被惰性删除或者定期删除之后，程序会向AOF文件追加一条DEL命令。
AOF文件重写：执行AOF重写过程中，程序会对数据库中的键进行检查，已过期的键不会被保存。

复制

当服务器运行在复制模型下，从服务器的过期键删除动作由主服务器控制

主服务器删除一个过期键之后，显式地向所有从服务器发送DEL命令，告知从服务器删除该过期键。
从服务器在执行客户端发送的命令时，即使碰到过期键也不会删除，像处理未过期的键一样处理。
从服务器只有接收到主服务器的DEL命令时，才会删除过期键。

Redis数据库通知

键空间通知(key-space notification)

关注“某个键执行了什么命令”的通知，如"SET message abc"，表message键执行了set命令。

127.0.0.1:6379> SUBSCRIBE __keyspace@0__:message

1) "subscribe"                 # 订阅消息

2) "__keyspace@0__:message"

3) (integer) 1

1) "message"                   # 键message执行set命令

2) "__keyspace@0__:message"

3) "set"

1) "message"                   # 键message执行expire命令

2) "__keyspace@0__:message"

3) "expire"

1) "message"                   # 键message执行del命令

2) "__keyspace@0__:message"

3) "del"

键事件通知(key-event notification)

关注"某个命令被什么键执行"的通知，如"DEL message"，表示DEL命令被执行message键执行。

127.0.0.1:6379> SUBSCRIBE __keyevent@0__:del

1) "subscribe"             # 订阅消息

2) "__keyspace@0__:del"

3) (integer) 1

1) "message"               # 键key执行del命令

2) "__keyevent@0__:del"

3) "key"

1) "message"               # 键number执行del命令

2) "__keyevent@0__:del"

3) "number"

1) "message"               # 键message执行del命令

2) "__keyevent@0__:del"

3) "message"

服务器配置notify-keyspace-events选项决定服务器发送通知的类型

AKE: 发送所有类型的键空间通知和键事件通知
AK: 发送所有类型的键空间通知
AE: 发送所有类型的键事件通知
K$: 只发送和字符串键有关的键空间通知
El: 只发送和列表键有关的键事件通知

RDB持久化

RDB文件的创建与载入

RDB文件生成命令

SAVE: 阻塞Redis服务器，直到RDB文件创建完毕为止
BGSAVE: 派生一个子进程，由子进程负责创建RDB文件，服务器进程继续处理命令请求

RDB文件载入

Redis服务器在启动时检测到RDB文件存在，它就会自动载入RDB文件

AOF与RDB优先级

如果服务器开启了AOF持久化功能，那么服务器会优先使用AOF文件来还原数据库状态
只有在AOF持久化处于关闭状时，服务器才会使用RDB文件来还原数据库状态

自动间隔性保存

struct redisServer {

  //...

  // 保存条件数组

  struct saveparam *saveparams;

  // 计数器

  long long dirty;

  // 上一次执行保存的时间

  time_t lastsave;

   //...

}

只要满足下面条件的任意一个(默认设置)，BGSAVE命令就会被执行：

服务器在900秒之内，对数据库至少1次修改
服务器在300秒之内，对数据库至少10次修改
服务器在60秒之内，对数据库至少10000次修改

dirty计数器

记录距离上一次成功执行SAVE或BGSAVE命令之后，服务器对数据库状态进行了多少次修改。

lastsave属性

unix时间戳，记录服务器上一次成功执行SAVE命令或BGSAVE命令的时间。

检查RDB保存条件

# 检查保存条件

def serverCron():

  # ...

  for saveparam in server.saveparams:

    # 计算距离上次保存操作的时间

    save_interval = unixtime_now() - server.lastsave

    if server.dirty >= savaparam.changes and save_interval > saveparam.seconds:

        BGSVAE()

  # ...

RDB文件结构

RDB组成部分	作用
REDIS	常量，5字节
db_version	字符串表示的整数，4字节
databases	包含任意多个数据库，以及各个数据库中的键值对数据
EOF	常量，标志RDB文件正文内容的结束，1字节
check_sum	无符号整数，程序通过上面四个部分内容计算得出的校验和，8字节

databases部分

每个database可以由三部分组成：

database组成部分	作用
SELECTDB	常量，程序遇到这个值表示接下来要读入一个数据库号码，1字节
db_number	保存着数据库号码，1字节、2字节或5字节
key_value_pairs	保存着数据库中所有的键值对

key_value_pairs部分

每个key_value_pairs部分都保存了一个或以上数量的键值对；如果键值对带有过期时间的话，那么也会保存。

不带过期时间的键值对

key_value_pairs组成部分	作用
TYPE	记录value的类型，1字节
key	键对象，总是一个字符串对象
value	值对象

带过期时间的键值对

key_value_pairs组成部分	作用
EXPIRETIME_MS	常量，告知程序接下来读入一个以毫秒为单位的过期时间，1字节
ms	记录着一个以毫秒为单位的UNIX时间戳，8字节有符号整数
TYPE	记录value的类型，1字节
key	键对象，总是一个字符串对象
value	值对象

AOF持久化

Append Only File

RDB持久化通过保存数据库中的键值对来记录数据库状态不同；AOF持久化是通过保存Redis服务器所执行的写命令来记录数据库状态。

AOF持久化的实现

命令追加

服务器在执行完一个写命令之后，会以协议格式将被执行的写命令追加到服务器状态的aof-buf缓冲区的末尾。

文件写入

服务器在处理文件事件时可能会执行写命令，使得一些内容被追加到aof_buf缓冲区，所以在服务器每次结束一个事件循环之前，都会调用flushAppendOnlyFile函数，考虑是否将缓冲区的内如写入和保存到AOF文件。

appendfsync选项的值	flushAppendOnlyFile函数的行为
always	将aof_buf缓冲区中的所有内容写入并同步到到AOF文件
everysec	将aof_buf缓冲区中的所有内容写入到AOF文件，如果距离上次同步AOF文件的时间超过一秒钟，那么再次对AOF文件进行同步，并且这个同步操作是由一个线程专门负责执行
no	将aof_buf缓冲区中的所有内容写入到AOF文件，但不进行同步，何时同步由操作系统决定

文件的写入和同步

现代操作系统中，为了提高文件的写入效率，当用户调用write函数写入文件时，操作系统通常会将写入数据暂时保存在一个内存缓冲区里面，等到内存缓冲区的空间被填满或者超过了指定时间后，才真正地将缓冲区中的数据写入到磁盘里面。

AOF文件的载入与数据还原

创建一个不带网络连接的伪客户端，Redis的命令只能在客户端上下文中执行
从AOF文件中读取写命令
使用伪客户端执行读出的写命令
重复步骤2，3，直到AOF文件中的所有写命令处理完毕

AOF文件重写

AOF持久化通过保存被执行的写命令来记录数据库的状态，所有随着服务器运行时间变长，AOF文件中的内容会越来越多，文件的体积也会越来越大。体积过大的AOF文件可能对Redis服务器造成影响，且AOF文件越大读入时还原数据库状态所需时间也越长。所以Redis提供了AOF文件重写功能。

AOF文件重写功能

AOF文件重写功能通过读取服务器当前的数据库状态来实现

Redis服务器创建一个新的AOF文件代替现有的AOF文件
新旧AOF文件保存的数据库状态相同，但新AOF文件不会包含任何冗余命令
为了避免造成客户端输入缓冲区溢出，重写程序在处理列表、集合、有序集合、哈希表可能存在多个元素的键时，会先检查元素的数量是否超过了REDIS_AOF_REWRITE_ITEMS_PER_CMD常量值，如果超过了则会使用多条命令；如果没超过则使用1条命令即可

AOF后台重写

Redis将AOF重写程序放到子进程执行的优势：

子进程进行AOF重写期间，服务器进程可以继续处理命令请求
子进程带有服务器进程的数据副本，使用子进程而不是线程，可以在避免使用锁的情况下，保证数据的安全性

AOF重写过程中数据库状态发送变化，如何保证重写后的AOF文件和当前数据库状态的一致性：

Redis服务器设置了一个AOF重写缓冲区，这个缓冲区在子进程创建之后开始使用，当Redis服务器执行完一下写命令后，它会同时将写命令发送给AOF缓冲区和AOF重写缓冲区
AOF缓冲区的内容会被定期写入和同步到AOF文件，对当前的AOF文件处理如常进行
AOF重写缓冲区的所有内容会被写入重写后的AOF文件，此时新AOF文件保存的数据库状态就和当前数据库一致
最后，对新的AOF文件进行改名，原子地覆盖现有的AOF文件，完成新旧文件的替换

事件

文件事件

File Event：Redis服务器通过套接字(ip : port)与客户端或者其他Redis服务器进行连接。服务器与客户端或者其他Redis服务器通信会产生相应的文件事件，而服务器通过监听并处理这些事件来完成一些列网络通信操作。文件事件就是服务器对套接字操作的抽象。

文件事件内部结构

typedef struct aeFileEvent {

  // 监听事件类型：AE_READABLE, AE_WRITABLE, AE_READABLE | AE_WRITABLE

  int mask;

  // 读事件处理器

  aeFileProc* rfileProc;

  // 写事件处理器

  aeFileProc* wfileProc;

  // 多路复用库的私有数据

  void* clientData;

} aeFileEvent;

文件事件处理器

Redis基于Reactor模式开发了自己的网络事件处理器。
文件处理器使用I/O多路复用程序来同时监听多个套接字。
当被监听的套接字准备好执行连接应答(accept)、读取(read)、写入(write)、关闭(close)等操作时，与之对应的文件事件就会产生，文件处理器则会调用套接字关联好的事件处理器来处理事件。

I/O多路复用

I/O多路复用是针对单线程并发的，多路是指多个网络连接，复用是指使用同一个线程。

文件事件类型

当有Client申请socket连接时，会注册一个AE_READABLE事件
当接受Client命令请求时，会注册一个AE_READABLE事件
当服务器返回处理结果时，会注册一个AE_WRITEABLE事件

事件的处理器

连接应答处理器：acceptTcpHandler函数
命令请求处理器：readQueryFromClient函数
命令回复处理器：sendReplyToClient函数

时间事件

Time Event：Redis服务器中的一些操作需要在给定的时间点执行(如serverCron函数)。时间事件就是服务器对这类定时操作的抽象。

时间事件内部结构

typedef struct aeTimeEvent {

  // 服务器为时间事件创建全局唯一ID, 从小到大自增

  long long id;

  // 记录什么时候执行该事件

  long when_sec;

  long when_ms;

  // 时间事件处理器

  aeTimeProc* timeProc;

  void* clientData;

  struct aeTimeEvent* prev;

  struct aeTimeEvent* next;    //双向链表

} aeTimeEvent;

时间事件类型

定时事件：让一段程序在指定时间后执行一次
周期事件：让一段程序每隔指定时间执行一次

时间事件执行

服务器将所有时间事件都放在一个无序列表(没有按照事件执行时间排序, 即when属性)，每当时间事件执行器运行时，则遍历整个链表，查找所有已到达的时间事件并调用对应的处理器。
正常模式下Redis服务器只有serverCron一个时间事件，所以无序列表不会影响时间事件执行的性能。

事件的调度与执行

服务器中同时存在文件事件和时间事件，所以服务器需要对这两种事件进行调度，决定何时处理文件事件、何时处理时间事件。

调度函数伪代码

def aeProcessEvents():

  time_event = aeSearchNearestTimer()    # 获取离当前时间最接近的时间事件

  remained_ms = time_event.when - unix_ms_now()

  # 如果事件已到达，则设为0

  if remained_ms < 0:

    remained_ms = 0

  timeval = create_timeval_with_ms(remained_ms)

  # 阻塞并等待文件事件产生，最大阻塞时间由传入的timeval决定

  aeApiPoll(timeval)

  processFileEvents()    # 处理所有已产生的文件事件

  processTimeEvents()    # 处理所有已达到的时间事件

Attention

文件事件和时间事件的处理都是同步、有序、原子地执行，服务器不会中断事件处理，也不会对事件抢占。
无论是文件事件还是时间事件的处理器，都会尽可能减少程序的阻塞时间，并在需要时主动让出执行权，从而降低事件饥饿的可能性。
如命令回复处理器将回复写入到客户端套接字时，如果写入数据超过一个预设常量则会主动用break跳出循环，将余下的数据留到下次再写

Redis读书笔记（三）的相关教程结束。