Redis源码剖析——数据库

本文将对Redis服务器的数据库实现进行介绍

服务器中的数据库

Redis服务器中一般保存了多个数据库,每个数据库用redisDb结构表示,结构的定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;

可以从Redis数据库中的定义中看到:数据库的所有键值对都存放在一个字典结构中,同时记录了用于键的删除所需要的过期时间。

在Redis服务器结构中有一个数据库数组,存放各个数据库的指针;有一个记录数据库数量的变量dbnum,服务器初始化的时候根据这个变量来创建相应数量的数据库

1
2
3
4
5
6
7
8
struct redisServer {
...
// 数据库
redisDb *db;
// 数据库数量
int dbnum;
...
}

切换数据库

每个 Redis客户端都有自己的目标数据库,每当客户端执行数据库写命令或者数据库读命令的时候,目标数据库就会成为这些命令的操作对象。默认情况下, Redis客户端的目标数据库为0号数据库,但客户端可以通过执行SELECT命令来切换目标数据库。

在客户端结构redisClient结构中用db属性记录客户端当前的目标数据库

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

redisClient.db指针指向redisServer.db数组的其中一个元素,而被指向的元素就是客户端的目标数据库。

使用select切换数据库的实现:

1
2
3
4
5
6
7
int selectDb(redisClient *c, int id) {
// 验证db编号的合法性
if (id < 0 || id >= server.dbnum)
return REDIS_ERR;
c->db = &server.db[id];
return REDIS_OK;
}

数据库的键空间

因为数据库的键空间是一个字典,所以所有针对数据库的操作,比如添加一个键值对到数据库,或者从数据库中删除一个键值对,又或者在数据库中获取某个键值对等,实际上都是通过对键空间字典进行操作来实现的

添加新键

添加一个新键值对到数据库,实际上就是将一个新键值对添加到键空间字典里面,其中键为字符串对象,而值则为任意一种类型的 Redis对象

1
2
3
4
5
6
7
8
9
10
11
12
void dbAdd(redisDb *db, robj *key, robj *val) {
// 拷贝字符串对象
sds copy = sdsdup(key->ptr);
// 加入字典
int retval = dictAdd(db->dict, copy, val);
redisAssertWithInfo(NULL,key,retval == REDIS_OK);
// 如果值对象类型为list,需要判断该键是不是引起阻塞的键
if (val->type == REDIS_LIST) signalListAsReady(db, key);
// 如果开启的集群选项,则需要做相应的处理
if (server.cluster_enabled) slotToKeyAdd(key);
}

删除键

删除数据库中的一个键,实际上就是在键空间里面删除键所对应的键值对对象。

1
2
3
4
5
6
7
8
9
10
11
12
int dbDelete(redisDb *db, robj *key) {
/* Deleting an entry from the expires dict will not free the sds of
* the key, because it is shared with the main dictionary. */
/* 如果有设定过期键,就去过期键字典中删除该键 */
if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);
if (dictDelete(db->dict,key->ptr) == DICT_OK) {
if (server.cluster_enabled) slotToKeyDel(key);
return 1;
} else {
return 0;
}
}

过期键删除策略

Reids中有LRU机制,能够实现对数据设置期限(过期时间),在期限到达的时候会执行删除机制。Redis中有三种不同的删除策略:

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

在这三种策略中,第一种和第三种为主动删除策略,而第二种则为被动删除策略。

过期时间的保存

redisDb结构的expires字典保存了数据库中所有键的过期时间,我们称这个字典为过期字典:

  • 过期字典的键是一个指针,这个指针指向键空间中的某个键对象(也即是某个数据库键)
  • 过期字典的值是一个1ong 1ong类型的整数,这个整数保存了键所指向的数据库键的过期时间—个毫秒精度的UNIX时间戳。

定时删除

定时删除策略对内存是最友好的:通过使用定时器,定时删除策略可以保证过期键会尽可能快地被删除,并释放过期键所占用的内存。

另一方面,定时删除策略的缺点是,它对CPU时间是最不友好的:在过期键比较多的情况下,删除过期键这一行为可能会占用相当一部分CPU时间,在内存不紧张但是CPU时间非常紧张的情况下,将CPU时间用在删除和当前任务无关的过期键上,无疑会对服务器的响应时间和吞吐量造成影响。

惰性删除

惰性删除策略对CPU时间来说是最友好的:程序只会在取出键时才对键进行过期检查这可以保证删除过期键的操作只会在非做不可的情况下进行,并且删除的目标仅限于当前处理的键,这个策略不会在删除其他无关的过期键上花费任何CPU时间

惰性删除策略的缺点是,它对内存是最不友好的:如果一个键已经过期,而这个键又仍然保留在数据库中,那么只要这个过期键不被删除,它所占用的内存就不会释放。

具体的实现是通过expireIfNeeded函数实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int expireIfNeeded(redisDb *db, robj *key) {
// 获取定时时间
mstime_t when = getExpire(db,key);
mstime_t now;
// 没有设置定时时间
if (when < 0) return 0; /* No expire for this key */
/* 服务器正在加载,不需要处理 */
if (server.loading) return 0;
/* lua相关 */
now = server.lua_caller ? server.lua_time_start : mstime();
/* 主从复制相关 */
if (server.masterhost != NULL) return now > when;
/* 没有过期 */
if (now <= when) return 0;
/* 删除键 */
server.stat_expiredkeys++;
propagateExpire(db,key);
notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
"expired",key,db->id);
return dbDelete(db,key);
}

定期删除

从上面对定时删除和惰性删除的讨论来看,这两种删除方式在单一使用时都有明显的缺陷:

  • 定时删除占用太多CPU时间,影响服务器的响应时间和吞吐量。
  • 惰性删除浪费太多内存,有内存泄漏的危险

定期删除策略是前两种策略的一种整合和折中

  • 定期删除策略每隔一段时间执行一次删除过期键操作,并通过限制删除操作执行的时长和频率来减少删除操作对CPU时间的影响。
  • 除此之外,通过定期删除过期键,定期删除策略有效地减少了因为过期键而带来的内存浪费。

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

  • 如果删除操作执行得太频繁,或者执行的时间太长,定期删除策略就会退化成定时删除策略,以至于将CPU时间过多地消耗在删除过期键上面。
  • 如果删除操作执行得太少,或者执行的时间太短,定期删除策略又会和惰性删除策略一样,出现浪费内存的情况