# 数据库
[TOC=2,3]
本章将对 Redis 数据库的构造和实现进行讨论。
除了说明数据库是如何储存数据对象之外，本章还会讨论键的过期信息是如何保存，而 Redis 又是如何删除过期键的。
### 数据库的结构
Redis 中的每个数据库，都由一个 `redis.h/redisDb` 结构表示：
~~~
typedef struct redisDb {
// 保存着数据库以整数表示的号码
int id;
// 保存着数据库中的所有键值对数据
// 这个属性也被称为键空间（key space）
dict *dict;
// 保存着键的过期信息
dict *expires;
// 实现列表阻塞原语，如 BLPOP
// 在列表类型一章有详细的讨论
dict *blocking_keys;
dict *ready_keys;
// 用于实现 WATCH 命令
// 在事务章节有详细的讨论
dict *watched_keys;
} redisDb;
~~~
下文将详细讨论 `id` 、 `dict` 和 `expires` 三个属性，以及针对这三个属性所执行的数据库操作。
### 数据库的切换
`redisDb` 结构的 `id` 域保存着数据库的号码。
这个号码很容易让人将它和切换数据库的 [SELECT](http://redis.readthedocs.org/en/latest/connection/select.html#select "(in Redis 命令参考 v2.8)") 命令联系在一起，但是，实际上，`id` 属性并不是用来实现 [SELECT](http://redis.readthedocs.org/en/latest/connection/select.html#select "(in Redis 命令参考 v2.8)") 命令，而是给 Redis 内部程序使用的。
当 Redis 服务器初始化时，它会创建出 `redis.h/REDIS_DEFAULT_DBNUM` 个数据库，并将所有数据库保存到 `redis.h/redisServer.db` 数组中，每个数据库的 `id` 为从 `0` 到 `REDIS_DEFAULT_DBNUM - 1` 的值。
当执行 `SELECT number` 命令时，程序直接使用 `redisServer.db[number]` 来切换数据库。
但是，一些内部程序，比如 AOF 程序、复制程序和 RDB 程序，需要知道当前数据库的号码，如果没有 `id` 域的话，程序就只能在当前使用的数据库的指针，和 `redisServer.db` 数组中所有数据库的指针进行对比，以此来弄清楚自己正在使用的是那个数据库。
以下伪代码描述了这个对比过程：
~~~
def PSEUDO_GET_CURRENT_DB_NUMBER(current_db_pointer):
i = 0
for db_pointer in redisServer.db:
if db_pointer == current_db_pointer:
break
i += 1
return i
~~~
有了 `id` 域的话，程序就可以通过读取 `id` 域来了解自己正在使用的是哪个数据库，这样就不用对比指针那么麻烦了。
### 数据库键空间
因为 Redis 是一个键值对数据库（key-value pairs database），所以它的数据库本身也是一个字典（俗称 key space）：
- 字典的键是一个[字符串](#)对象。
- 字典的值则可以是包括[字符串](#)、[列表](#)、[哈希表](#)、[集合](#)或[有序集](#)在内的任意一种 Redis 类型对象。
在 `redisDb` 结构的 `dict` 属性中，保存着数据库的所有键值对数据。
下图展示了一个包含 `number` 、 `book` 、 `message` 三个键的数据库 ——其中 `number` 键是一个列表，列表中包含三个整数值；`book` 键是一个哈希表，表中包含三个键值对；而 `message` 键则指向另一个字符串：
![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effddf93b.svg)
### 键空间的操作
因为数据库本身是一个字典，所以对数据库的操作基本上都是对字典的操作，加上以下一些维护操作：
- 更新键的命中率和不命中率，这个值可以用 [INFO](http://redis.readthedocs.org/en/latest/server/info.html#info "(in Redis 命令参考 v2.8)") 命令查看；
- 更新键的 LRU 时间，这个值可以用 [OBJECT](http://redis.readthedocs.org/en/latest/key/object.html#object "(in Redis 命令参考 v2.8)") 命令来查看；
- 删除过期键（稍后会详细说明）；
- 如果键被修改了的话，那么将键设为脏（用于事务监视），并将服务器设为脏（等待 RDB 保存）；
- 将对键的修改发送到 AOF 文件和附属节点，保持数据库状态的一致；
作为例子，以下几个小节会展示键的添加、删除、更新、取值等几个主要操作。
### 添加新键
添加一个新键对到数据库，实际上就是将一个新的键值对添加到键空间字典中，其中键为字符串对象，而值则是任意一种 Redis 类型值对象。
举个例子，如果数据库的目前状态如下图所示（和前面展示的数据库状态图一样）：
![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effdeec5c.svg)
那么在客户端执行 `SET date 2013.2.1` 命令之后，数据库更新为下图状态：
![digraph db_after_insert_new_key { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" |<date>StringObject\n \"date\" |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; date [label = "<head>StringObject | \"2013.2.1\"", fillcolor = "#FFC1C1"]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:date -> date; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe04320.svg)
### 删除键
删除数据库中的一个键，实际上就是删除字典空间中对应的键对象和值对象。
举个例子，如果数据库的目前状态如下图所示（和前面展示的数据库状态图一样）：
![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe0c971.svg)
那么在客户端执行 `DEL message` 命令之后，数据库更新为下图状态：
![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" | NULL", fillcolor = "#FFC1C1"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe165fe.svg)
### 更新键
当对一个已存在于数据库的键执行更新操作时，数据库释放键原来的值对象，然后将指针指向新的值对象。
举个例子，如果数据库的目前状态如下图所示（和前面展示的数据库状态图一样）：
![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe2257a.svg)
那么在客户端执行 `SET message "blah blah"` 命令之后，数据库更新为下图状态：
![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"blah blah\"", fillcolor = "#FFC1C1"]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe2b4c6.svg)
### 取值
在数据库中取值实际上就是在字典空间中取值，再加上一些额外的类型检查：
- 键不存在，返回空回复；
- 键存在，且类型正确，按照通讯协议返回值对象；
- 键存在，但类型不正确，返回类型错误。
举个例子，如果数据库的目前状态如下图所示（和前面展示的数据库状态图一样）：
![digraph db { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict | ...", fillcolor = "#A8E270"]; dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head;}](https://box.kancloud.cn/2015-09-13_55f4effe333bf.svg)
当客户端执行 `GET message` 时，服务器返回 `"hello moto"` 。
当客户端执行 `GET not-exists-key` 时，服务器返回空回复。
当服务器执行 `GET book` 时，服务器返回类型错误。
### 其他操作
除了上面展示的键值操作之外，还有很多针对数据库本身的命令，也是通过对键空间进行处理来完成的：
- [FLUSHDB](http://redis.readthedocs.org/en/latest/server/flushdb.html#flushdb "(in Redis 命令参考 v2.8)") 命令：删除键空间中的所有键值对。
- [RANDOMKEY](http://redis.readthedocs.org/en/latest/key/randomkey.html#randomkey "(in Redis 命令参考 v2.8)") 命令：从键空间中随机返回一个键。
- [DBSIZE](http://redis.readthedocs.org/en/latest/server/dbsize.html#dbsize "(in Redis 命令参考 v2.8)") 命令：返回键空间中键值对的数量。
- [EXISTS](http://redis.readthedocs.org/en/latest/key/exists.html#exists "(in Redis 命令参考 v2.8)") 命令：检查给定键是否存在于键空间中。
- [RENAME](http://redis.readthedocs.org/en/latest/key/rename.html#rename "(in Redis 命令参考 v2.8)") 命令：在键空间中，对给定键进行改名。
等等。
### 键的过期时间
在前面的内容中，我们讨论了很多涉及数据库本身、以及对数据库中的键值对进行处理的操作，但是，关于数据库如何保存键的过期时间，以及如何处理过期键这一问题，我们还没有讨论到。
通过 [EXPIRE](http://redis.readthedocs.org/en/latest/key/expire.html#expire "(in Redis 命令参考 v2.8)") 、 [PEXPIRE](http://redis.readthedocs.org/en/latest/key/pexpire.html#pexpire "(in Redis 命令参考 v2.8)") 、 [EXPIREAT](http://redis.readthedocs.org/en/latest/key/expireat.html#expireat "(in Redis 命令参考 v2.8)") 和 [PEXPIREAT](http://redis.readthedocs.org/en/latest/key/pexpireat.html#pexpireat "(in Redis 命令参考 v2.8)") 四个命令，客户端可以给某个存在的键设置过期时间，当键的过期时间到达时，键就不再可用：
~~~
redis> SETEX key 5 value
OK
redis> GET key
"value"
redis> GET key // 5 秒过后
(nil)
~~~
命令 [TTL](http://redis.readthedocs.org/en/latest/key/ttl.html#ttl "(in Redis 命令参考 v2.8)") 和 [PTTL](http://redis.readthedocs.org/en/latest/key/pttl.html#pttl "(in Redis 命令参考 v2.8)") 则用于返回给定键距离过期还有多长时间：
~~~
redis> SETEX key 10086 value
OK
redis> TTL key
(integer) 10082
redis> PTTL key
(integer) 10068998
~~~
在接下来的内容中，我们将探讨和键的过期时间相关的问题：比如键的过期时间是如何保存的，而过期键又是如何被删除的，等等。
### 过期时间的保存
在数据库中，所有键的过期时间都被保存在 `redisDb` 结构的 `expires` 字典里：
~~~
typedef struct redisDb {
// ...
dict *expires;
// ...
} redisDb;
~~~
`expires` 字典的键是一个指向 `dict` 字典（键空间）里某个键的指针，而字典的值则是键所指向的数据库键的到期时间，这个值以 `long long` 类型表示。
下图展示了一个含有三个键的数据库，其中 `number` 和 `book` 两个键带有过期时间：
![digraph db_with_expire_time { rankdir = LR; node [shape = record, style = filled]; edge [style = bold]; // node redisDb [label = "redisDb | id |<dict> dict |<expires> expires | ...", fillcolor = "#A8E270"]; // dict dict [label = "<head>dict\n(key space) |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" |<message>StringObject\n \"message\"", fillcolor = "#95BBE3"]; number [label = "<head>ListObject | { 123 | 456 | 789 }", fillcolor = "#FADCAD"]; book [label = "<head>HashObject |<name>StringObject\n \"name\" |<author>StringObject\n \"author\" |<publisher>StringObject\n \"publisher\"", fillcolor = "#F2F2F2"]; book_name [label = "<head>StringObject | \"Mastering C++ in 21 days\""]; book_author [label = "<head>StringObject | \"Someone\""]; book_publisher [label = "<head>StringObject | \"Oh-Really? Publisher\""]; message [label = "<head>StringObject | \"hello moto\""]; // dict edge redisDb:dict -> dict:head; dict:number -> number:head; dict:book -> book:head; dict:message -> message:head; book:name -> book_name:head; book:author -> book_author:head; book:publisher -> book_publisher:head; // expires expires [label = "<head>dict |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" | NULL ", fillcolor = "#95BBE3"]; expire_of_number [label = "<head>long long | 1360454400000 "]; expire_of_book [label = "<head>long long | 1360800000000 "]; // expires edge redisDb:expires -> expires:head; expires:number -> expire_of_number:head; expires:book -> expire_of_book:head;}](https://box.kancloud.cn/2015-09-13_55f4effe3c4b3.svg)
Note
为了展示的方便，图中重复出现了两次 `number` 键和 `book` 键。在实际中，键空间字典的键和过期时间字典的键都指向同一个字符串对象，所以不会浪费任何空间。
### 设置生存时间
Redis 有四个命令可以设置键的生存时间（可以存活多久）和过期时间（什么时候到期）：
- [EXPIRE](http://redis.readthedocs.org/en/latest/key/expire.html#expire "(in Redis 命令参考 v2.8)") 以秒为单位设置键的生存时间；
- [PEXPIRE](http://redis.readthedocs.org/en/latest/key/pexpire.html#pexpire "(in Redis 命令参考 v2.8)") 以毫秒为单位设置键的生存时间；
- [EXPIREAT](http://redis.readthedocs.org/en/latest/key/expireat.html#expireat "(in Redis 命令参考 v2.8)") 以秒为单位，设置键的过期 UNIX 时间戳；
- [PEXPIREAT](http://redis.readthedocs.org/en/latest/key/pexpireat.html#pexpireat "(in Redis 命令参考 v2.8)") 以毫秒为单位，设置键的过期 UNIX 时间戳。
虽然有那么多种不同单位和不同形式的设置方式，但是 `expires` 字典的值只保存“以毫秒为单位的过期 UNIX 时间戳”，这就是说，通过进行转换，所有命令的效果最后都和 [PEXPIREAT](http://redis.readthedocs.org/en/latest/key/pexpireat.html#pexpireat "(in Redis 命令参考 v2.8)") 命令的效果一样。
举个例子，从 [EXPIRE](http://redis.readthedocs.org/en/latest/key/expire.html#expire "(in Redis 命令参考 v2.8)") 命令到 [PEXPIREAT](http://redis.readthedocs.org/en/latest/key/pexpireat.html#pexpireat "(in Redis 命令参考 v2.8)") 命令的转换可以用伪代码表示如下：
~~~
def EXPIRE(key, sec):
# 将 TTL 从秒转换为毫秒
ms = sec_to_ms(sec)
# 获取以毫秒计算的当前 UNIX 时间戳
ts_in_ms = get_current_unix_timestamp_in_ms()
# 毫秒 TTL 加上毫秒时间戳，就是 key 到期的时间戳
PEXPIREAT(ms + ts_in_ms, key)
~~~
其他函数的转换方式也是类似的。
作为例子，下图展示了一个 `expires` 字典示例，字典中 `number` 键的过期时间是 2013 年 2 月 10 日（农历新年），而 `book` 键的过期时间则是 2013 年 2 月 14 日（情人节）：
![digraph expires { rankdir = LR; node [shape = record, style =filled]; edge [style = bold]; // node redisDb [label = "redisDb | id | ... |<expires> expires | ...", fillcolor = "#A8E270"]; // expires expires [label = "<head>dict |<number>StringObject\n \"number\" | NULL |<book>StringObject\n \"book\" | NULL ", fillcolor = "#95BBE3"]; expire_of_number [label = "<head>long long | 1360454400000 "]; expire_of_book [label = "<head>long long | 1360800000000 "]; // expires edge redisDb:expires -> expires:head; expires:number -> expire_of_number:head; expires:book -> expire_of_book:head;}](https://box.kancloud.cn/2015-09-13_55f4effe464fd.svg)
这两个键的过期时间可能是用以上四个命令的任意一个设置的，但它们都以统一的格式被保存在 `expires` 字典中。
### 过期键的判定
通过 `expires` 字典，可以用以下步骤检查某个键是否过期：
1. 检查键是否存在于 `expires` 字典：如果存在，那么取出键的过期时间；
1. 检查当前 UNIX 时间戳是否大于键的过期时间：如果是的话，那么键已经过期；否则，键未过期。
可以用伪代码来描述这一过程：
~~~
def is_expired(key):
# 取出键的过期时间
key_expire_time = expires.get(key)
# 如果过期时间不为空，并且当前时间戳大于过期时间，那么键已经过期
if expire_time is not None and current_timestamp() > key_expire_time:
return True
# 否则，键未过期或没有设置过期时间
return False
~~~
### 过期键的清除
我们知道了过期时间保存在 `expires` 字典里，又知道了该如何判定一个键是否过期，现在剩下的问题是，如果一个键是过期的，那它什么时候会被删除？
这个问题有三种可能的答案：
1. 定时删除：在设置键的过期时间时，创建一个定时事件，当过期时间到达时，由事件处理器自动执行键的删除操作。
1. 惰性删除：放任键过期不管，但是在每次从 `dict` 字典中取出键值时，要检查键是否过期，如果过期的话，就删除它，并返回空；如果没过期，就返回键值。
1. 定期删除：每隔一段时间，对 `expires` 字典进行检查，删除里面的过期键。
### 定时删除
定时删除策略对内存是最友好的：因为它保证过期键会在第一时间被删除，过期键所消耗的内存会立即被释放。
这种策略的缺点是，它对 CPU 时间是最不友好的：因为删除操作可能会占用大量的 CPU 时间 ——在内存不紧张、但是 CPU 时间非常紧张的时候（比如说，进行交集计算或排序的时候），将 CPU 时间花在删除那些和当前任务无关的过期键上，这种做法毫无疑问会是低效的。
除此之外，目前 Redis 事件处理器对时间事件的实现方式 —— 无序链表，查找一个时间复杂度为 \(O(N)\) —— 并不适合用来处理大量时间事件。
### 惰性删除
惰性删除对 CPU 时间来说是最友好的：它只会在取出键时进行检查，这可以保证删除操作只会在非做不可的情况下进行 ——并且删除的目标仅限于当前处理的键，这个策略不会在删除其他无关的过期键上花费任何 CPU 时间。
惰性删除的缺点是，它对内存是最不友好的：如果一个键已经过期，而这个键又仍然保留在数据库中，那么 `dict` 字典和 `expires` 字典都需要继续保存这个键的信息，只要这个过期键不被删除，它占用的内存就不会被释放。
在使用惰性删除策略时，如果数据库中有非常多的过期键，但这些过期键又正好没有被访问的话，那么它们就永远也不会被删除（除非用户手动执行），这对于性能非常依赖于内存大小的 Redis 来说，肯定不是一个好消息。
举个例子，对于一些按时间点来更新的数据，比如日志（log），在某个时间点之后，对它们的访问就会大大减少，如果大量的这些过期数据积压在数据库里面，用户以为它们已经过期了（已经被删除了），但实际上这些键却没有真正的被删除（内存也没有被释放），那结果肯定是非常糟糕。
### 定期删除
从上面对定时删除和惰性删除的讨论来看，这两种删除方式在单一使用时都有明显的缺陷：定时删除占用太多 CPU 时间，惰性删除浪费太多内存。
定期删除是这两种策略的一种折中：
- 它每隔一段时间执行一次删除操作，并通过限制删除操作执行的时长和频率，籍此来减少删除操作对 CPU 时间的影响。
- 另一方面，通过定期删除过期键，它有效地减少了因惰性删除而带来的内存浪费。
### Redis 使用的策略
Redis 使用的过期键删除策略是惰性删除加上定期删除，这两个策略相互配合，可以很好地在合理利用 CPU 时间和节约内存空间之间取得平衡。
因为前面已经说了这两个策略的概念了，下面两节就来探讨这两个策略在 Redis 中的具体实现。
### 过期键的惰性删除策略
实现过期键惰性删除策略的核心是 `db.c/expireIfNeeded` 函数 ——所有命令在读取或写入数据库之前，程序都会调用 `expireIfNeeded` 对输入键进行检查，并将过期键删除：
![digraph expire_check { node [style = filled, shape = plaintext]; edge [style = bold]; // node write_commands [label = "SET 、\n LPUSH 、\n SADD 、 \n 等等", fillcolor = "#FADCAD"]; read_commands [label = "GET 、\n LRANGE 、\n SMEMBERS 、 \n 等等", fillcolor = "#FADCAD"]; expire_if_needed [label = "调用 expire_if_needed() \n 删除过期键", shape = box, fillcolor = "#A8E270"]; process [label = "执行实际的命令流程"]; // edge write_commands -> expire_if_needed [label = "写请求"]; read_commands -> expire_if_needed [label = "读请求"]; expire_if_needed -> process;}](https://box.kancloud.cn/2015-09-13_55f4effe4fc41.svg)
比如说， `GET` 命令的执行流程可以用下图来表示：
![digraph get_with_expire { node [style = filled, shape = plaintext]; edge [style = bold]; // node get [label = "GET key", fillcolor = "#FADCAD"]; expire_if_needed [label = "调用\n expire_if_needed() \n 如果键已经过期 \n 那么将它删除", shape = diamond, fillcolor = "#A8E270"]; expired_and_deleted [label = "key 不存在\n 向客户端返回 NIL"]; not_expired [label = "向客户端返回 key 的值"]; get -> expire_if_needed; expire_if_needed -> expired_and_deleted [label = "已过期"]; expire_if_needed -> not_expired [label = "未过期"];}](https://box.kancloud.cn/2015-09-13_55f4effe5a585.svg)
`expireIfNeeded` 的作用是，如果输入键已经过期的话，那么将键、键的值、键保存在 `expires` 字典中的过期时间都删除掉。
用伪代码描述的 `expireIfNeeded` 定义如下：
~~~
def expireIfNeeded(key):
# 对过期键执行以下操作 。。。
if key.is_expired():
# 从键空间中删除键值对
db.dict.remove(key)
# 删除键的过期时间
db.expires.remove(key)
# 将删除命令传播到 AOF 文件和附属节点
propagateDelKeyToAofAndReplication(key)
~~~
### 过期键的定期删除策略
对过期键的定期删除由 `redis.c/activeExpireCycle` 函执行：每当 Redis 的例行处理程序 `serverCron` 执行时，`activeExpireCycle` 都会被调用 ——这个函数在规定的时间限制内，尽可能地遍历各个数据库的 `expires` 字典，随机地检查一部分键的过期时间，并删除其中的过期键。
整个过程可以用伪代码描述如下：
~~~
def activeExpireCycle():
# 遍历数据库（不一定能全部都遍历完，看时间是否足够）
for db in server.db:
# MAX_KEY_PER_DB 是一个 DB 最大能处理的 key 个数
# 它保证时间不会全部用在个别的 DB 上（避免饥饿）
i = 0
while (i < MAX_KEY_PER_DB):
# 数据库为空，跳出 while ，处理下个 DB
if db.is_empty(): break
# 随机取出一个带 TTL 的键
key_with_ttl = db.expires.get_random_key()
# 检查键是否过期，如果是的话，将它删除
if is_expired(key_with_ttl):
db.deleteExpiredKey(key_with_ttl)
# 当执行时间到达上限，函数就返回，不再继续
# 这确保删除操作不会占用太多的 CPU 时间
if reach_time_limit(): return
i += 1
~~~
### 过期键对 AOF 、RDB 和复制的影响
前面的内容讨论了过期键对 CPU 时间和内存的影响，现在，是时候说说过期键在 RDB 文件、 AOF 文件、 AOF 重写以及复制中的影响了：
过期键会被保存在更新后的 RDB 文件、 AOF 文件或者重写后的 AOF 文件里面吗？
附属节点会会如何处理过期键？处理的方式和主节点一样吗？
以上这些问题就是本节要解答的。
### 更新后的 RDB 文件
在创建新的 RDB 文件时，程序会对键进行检查，过期的键不会被写入到更新后的 RDB 文件中。
因此，过期键对更新后的 RDB 文件没有影响。
### AOF 文件
在键已经过期，但是还没有被惰性删除或者定期删除之前，这个键不会产生任何影响，AOF 文件也不会因为这个键而被修改。
当过期键被惰性删除、或者定期删除之后，程序会向 AOF 文件追加一条 `DEL` 命令，来显式地记录该键已被删除。
举个例子，如果客户端使用 `GET message` 试图访问 `message` 键的值，但 `message` 已经过期了，那么服务器执行以下三个动作：
1. 从数据库中删除 `message` ；
1. 追加一条 `DEL message` 命令到 AOF 文件；
1. 向客户端返回 `NIL` 。
### AOF 重写
和 RDB 文件类似，当进行 AOF 重写时，程序会对键进行检查，过期的键不会被保存到重写后的 AOF 文件。
因此，过期键对重写后的 AOF 文件没有影响。
### 复制
当服务器带有附属节点时，过期键的删除由主节点统一控制：
- 如果服务器是主节点，那么它在删除一个过期键之后，会显式地向所有附属节点发送一个 `DEL` 命令。
- 如果服务器是附属节点，那么当它碰到一个过期键的时候，它会向程序返回键已过期的回复，但并不真正的删除过期键。因为程序只根据键是否已经过期、而不是键是否已经被删除来决定执行流程，所以这种处理并不影响命令的正确执行结果。当接到从主节点发来的 `DEL` 命令之后，附属节点才会真正的将过期键删除掉。
附属节点不自主对键进行删除是为了和主节点的数据保持绝对一致，因为这个原因，当一个过期键还存在于主节点时，这个键在所有附属节点的副本也不会被删除。
这种处理机制对那些使用大量附属节点，并且带有大量过期键的应用来说，可能会造成一部分内存不能立即被释放，但是，因为过期键通常很快会被主节点发现并删除，所以这实际上也算不上什么大问题。
### 数据库空间的收缩和扩展
因为数据库空间是由字典来实现的，所以数据库空间的扩展/收缩规则和字典的扩展/收缩规则完全一样，具体的信息可以参考《[字典](#)》章节。
因为对字典进行收缩的时机是由使用字典的程序决定的，所以 Redis 使用 `redis.c/tryResizeHashTables` 函数来检查数据库所使用的字典是否需要进行收缩：每次 `redis.c/serverCron` 函数运行的时候，这个函数都会被调用。
`tryResizeHashTables` 函数的完整定义如下：
~~~
/*
* 对服务器中的所有数据库键空间字典、以及过期时间字典进行检查，
* 看是否需要对这些字典进行收缩。
*
* 如果字典的使用空间比率低于 REDIS_HT_MINFILL
* 那么将字典的大小缩小，让 USED/BUCKETS 的比率 <= 1
*/
void tryResizeHashTables(void) {
int j;
for (j = 0; j < server.dbnum; j++) {
// 缩小键空间字典
if (htNeedsResize(server.db[j].dict))
dictResize(server.db[j].dict);
// 缩小过期时间字典
if (htNeedsResize(server.db[j].expires))
dictResize(server.db[j].expires);
}
}
~~~
### 小结
- 数据库主要由 `dict` 和 `expires` 两个字典构成，其中 `dict` 保存键值对，而 `expires` 则保存键的过期时间。
- 数据库的键总是一个字符串对象，而值可以是任意一种 Redis 数据类型，包括字符串、哈希、集合、列表和有序集。
- `expires` 的某个键和 `dict` 的某个键共同指向同一个字符串对象，而 `expires` 键的值则是该键以毫秒计算的 UNIX 过期时间戳。
- Redis 使用惰性删除和定期删除两种策略来删除过期的键。
- 更新后的 RDB 文件和重写后的 AOF 文件都不会保留已经过期的键。
- 当一个过期键被删除之后，程序会追加一条新的 `DEL` 命令到现有 AOF 文件末尾。
- 当主节点删除一个过期键之后，它会显式地发送一条 `DEL` 命令到所有附属节点。
- 附属节点即使发现过期键，也不会自作主张地删除它，而是等待主节点发来 `DEL` 命令，这样可以保证主节点和附属节点的数据总是一致的。
- 数据库的 `dict` 字典和 `expires` 字典的扩展策略和普通字典一样。它们的收缩策略是：当节点的填充百分比不足 10% 时，将可用节点数量减少至大于等于当前已用节点数量。
