0%

Redis源代码阅读:key的查找过程

Redis的get命令是最常用的命令之一,本文基于Redis 3.0版本,对字符串类型的key的查找过程源代码进行注释和解读。

以字符串类型为例,查找一个字符串key使用get命令,按照规律,代码在getCommand()函数中。在redis源代码中搜索getCommand,找到对应函数的位置为t_stirng.c:160:

1
2
3
void getCommand(redisClient *c) {
getGenericCommand(c);
}

该函数的参数是一个redisClient,其中包含了命令参数(c->argv)、所选数据库(c->db)等信息。查看getGenericCommand()函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int getGenericCommand(redisClient *c) {
robj *o;

/**
* 查找key,如果找不到就返回null
* 参数 c->argv[1] 是get命令的中的key
* 参数 shared.nullbulk 是个常量,查找不到key时,返回shared.nullbulk
*/
if ((o = lookupKeyReadOrReply(c,c->argv[1],shared.nullbulk)) == NULL)
return REDIS_OK;

if (o->type != REDIS_STRING) {
// 处理类型不是字符串的情况,例如get一个列表
addReply(c,shared.wrongtypeerr);
return REDIS_ERR;
} else {
// 查找到了key就把结果回复到客户端
addReplyBulk(c,o);
return REDIS_OK;
}
}

lookupKeyReadOrReply()函数比较简单,查找不到就回复reply给客户端。能查找到就返回redisObject对象(即robj)。

1
2
3
4
5
robj *lookupKeyReadOrReply(redisClient *c, robj *key, robj *reply) {
robj *o = lookupKeyRead(c->db, key);
if (!o) addReply(c,reply);
return o;
}

lookupKeyRead()函数的参数有2个,分别是redis数据库和key:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
robj *lookupKeyRead(redisDb *db, robj *key) {
robj *val;
// 查找key之前先判断是否过期,对应了redis的key过期策略:惰性删除
expireIfNeeded(db,key);

// 查找key
val = lookupKey(db,key);

// 统计命中次数
if (val == NULL)
server.stat_keyspace_misses++;
else
server.stat_keyspace_hits++;
return val;
}

先看看判断key过期的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int expireIfNeeded(redisDb *db, robj *key) {
// 获取过期时间,key没有设置过期时间会返回-1
mstime_t when = getExpire(db,key);
mstime_t now;

// 当 when = -1 时,即没有设置key的过期时间,直接返回
if (when < 0) return 0;

// 加载rdb/aof文件时,不执行key过期逻辑
if (server.loading) return 0;

// lua脚本执行期间,只有第一次访问需要执行key过期,保证数据一致性。
now = server.lua_caller ? server.lua_time_start : mstime();

/**
* 如果当前redis实例是个从库,直接返回是否过期
* 但即使过期,也不执行删除操作
* 当key过期时,主库会发送 DEL 命令给从库来删除key
*
* 可能导致从库读取到已过期的key
*/
if (server.masterhost != NULL) return now > when;

// 还没过期,返回0
if (now <= when) return 0;

/* 统计过期删除的key数量,并执行删除key */
server.stat_expiredkeys++;
propagateExpire(db,key);
notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED, "expired",key,db->id);
return dbDelete(db,key);
}

再看看获取key过期时间的方法getExpire()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 获取key的过期时间
* 如果key没有设置过期时间,返回 -1
*/
long long getExpire(redisDb *db, robj *key) {
dictEntry *de;

/**
* key的过期时间保存在一个字典中(db->expires)
* 字典长度为0,或者在过期时间字典中找不到key,直接返回 -1
* dictFind()是查找字典中指定的key的函数,后续也会用到
*/
if (dictSize(db->expires) == 0 ||
(de = dictFind(db->expires,key->ptr)) == NULL) return -1;

/* 断言:在过期字典中存在的key,在redis数据库中一定存在 */
redisAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);

// 返回过期时间
return dictGetSignedIntegerVal(de);
}

上面是判断过期key、删除过期key的逻辑。接着看查找key的逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
robj *lookupKey(redisDb *db, robj *key) {
/**
* redis的key保存在字典 db->dict 中,与查找key的过期时间类似,调用dictFind()函数查找字典中指定的key的函数
* dictEntry是字典中的一个节点,其中保存了redis的key和value
*/
dictEntry *de = dictFind(db->dict,key->ptr);
if (de) {
/**
* 获取这个节点的值,值是一个RedisObject,可能是字符串、列表、集合等
*/
robj *val = dictGetVal(de);

/**
* 更新key的访问时间,用于LRU算法
* 但在执行rdb/aof备份时,不更新访问时间,避免写时复制COW浪费性能和内存
*/
if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)
val->lru = LRU_CLOCK();

// 查找成功,返回RedisObject
return val;
} else {
return NULL;
}
}

关键部分在字典的查找函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;

// 字典长度为0,直接返回NULL
if (d->ht[0].size == 0) return NULL;

/**
* 如果正在执行渐进式rehash(哈希表扩容/收缩),
* 则执行`_dictRehashStep()`将1个key复制到新的哈希表中
*/
if (dictIsRehashing(d)) _dictRehashStep(d);

// 调用hash算法计算key的哈希值
h = dictHashKey(d, key);

/**
* 字典有2个哈希表,正常情况下只使用其中1个,即d->ht[0]
* 在执行哈希表扩容/收缩时,需要把哈希表中的key从 d->ht[0] 复制到 d->ht[1] 中
* 在复制过程中查找key时,如果在 d->ht[0]中查找不到,要再去 d->ht[1] 中查找
*/
for (table = 0; table <= 1; table++) {
/**
* 根据哈希值和哈希表的sizemask计算索引值,即在哈希表中的位置
* sizemask是一个正整数,等于哈希表的长度-1
* 当哈希值和sizemask进行 按位与 操作时,结果不会超过 sizemask
*/
idx = h & d->ht[table].sizemask;

// 根据索引值找到哈希表中的节点
he = d->ht[table].table[idx];

/**
* 获取到哈希表节点后,还需要遍历链表才能获取到所需要的key
* 因为哈希算法可能产生冲突(即不同的key计算出相同的idx),
* 发生冲突时,相同idx的key使用链表连接。
*/
while(he) {
// 对比链表节点的key与要找的key是否一致,一致时说明找到了,返回
if (dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}

/**
* 如果在执行渐进式rehash,则查找下一个哈希表 d->ht[1]
* 否则查找失败,返回NULL
*/
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}