按照Redis源码剖析–源码结构解析一文中给自己规定的六个阶段来学习Redis。目前前三个阶段的学习以及完成了,这些都是和系统的耦合性比较小的部分,所以看起来也比较轻松。从这篇博客开始,就进入到第四阶段的源码剖析了。Redis的各个功能的实现将会顺着我们的逐步深入而变得清晰明了,如果读者跟着我的步伐一起学习,到了这一刻,想必也是兴奋的。废话也不多说了,前面所有的数据结构都是为后面的功能实现做铺垫。那么今天,就来啃掉数据库实现这块硬骨头。

Redis数据库概述

Redis服务器在运行的时候会创建大量的RedisObject,这个对象都存放在数据库中,为了有效率的索引到某个对象,Redis数据库采用字典结构设计。假设,当我们向服务器中添加一个名为hello的集合对象时,通常可以将一个字符串对象"setHello"与其关联起来,添加到字典结构中,这样一来,当客户端请求对hello操作时,直接可以由"setHello"来获取该对象,时间复杂度为O(1)。

数据库的结构

上述关于Redis数据库设计的猜想,立刻在源码中体现出来了,但是Redis对于数据库的设计远不止数据存储那么简单,先不管其他的,来看看Redis定义的数据结构吧。

typedef struct redisDb {
    dict *dict;                 // 数据库的键空间
    dict *expires;              // 键及其过期时间
    dict *blocking_keys;        // 存放所有造成阻塞的键及其客户端
    dict *ready_keys;           // 存放push操作添加的造成阻塞的键,便于解阻塞
    dict *watched_keys;         // 被watch命令监控的键和相应的客户端,用于multi/exec
    struct evictionPoolEntry *eviction_pool;    /* Eviction pool of keys */
    int id;                     // 数据库编号
    long long avg_ttl;          // 数据库的平均生存时间
} redisDb;

在这些参数中,blocking_keysready_keysRedis源码剖析—列表t_list一文中有相应的解释,watched_keys也将会在事务一节中去分析,本篇博客主要讨论键空间、键过期时间和数据库编码这三个参数,让大家对Redis数据库有一个全方位的理解。

下图是一个RedisDb的示例,该数据库存放有五个键值对,分别是sRedis,INums,hBooks,SortNum和sNums,它们各自都有自己的值对象,另外,其中有三个键设置了过期时间,当前数据库是服务器的第0号数据库。有了这么一个概览,接下来就从源码的角度来分析Redis的这个数据库结构设计吧。

RedisDatabase
RedisDatabase

数据库的切换

每一个数据库的结构体都有一个id用来标识该数据库的编号,Redis的配置文件redis.conf中提供了如下参数来控制Redis在初始化的时候需要创建多少个数据库。

databases 16  // 表示该服务器需要创建16个数据库

在Redis服务器结构中,定义了数据库的结构,及其数据库个数。

struct redisServer {
    redisDb *db;  // 指向Redis的数据库
    int dbnum;  // 表明数据库的格式
    // ...
}

Redis提供了SELECT命令,来选择当前使用的数据库。其操作如下:

127.0.0.1:6379> select 1  // 初始为0号数据库,此时选择编码为1的数据库
OK
127.0.0.1:6379[1]> select 2 // [1]代表当前数据库编号,此时选择数据库2
OK
127.0.0.1:6379[2]> // [2]代表当前数据库编号为2

SELECT命令的源码也比较容易理解,这里就贴出来大家看看。

int selectDb(client *c, int id) {
    if (id < 0 || id >= server.dbnum)  // 验证id的有效性
        return C_ERR;
    c->db = &server.db[id]; // 切换数据库
    return C_OK; // 返回
}

数据库的键空间

Redis数据库中存放的数据都是以键值对形式存在,其充分利用了字典结构的高效索引特性,其中:

  • 字典的键:通常是一个字符串对象
  • 字典的值:可是是字符串,哈希,链表,集合和有序集合

在示例中也可以看到,每一个字符串键都对应了自己的值对象,例如hBooks对应着一个哈希对象。接下来我们去源码中找找关于键空间的操作函数。

键空间操作

Redis为数据库的键空间操作提供了下列操作函数,每个函数的功能都以注释的形式写出,后面会分析部分源码。

/* 从数据库中取出指定键对应的值对象,如不存在则返回NULL */ 
robj *lookupKey(redisDb *db, robj *key, int flags);
/* 先删除过期键,再从数据库中取出指定键对应的值对象,如不存在则返回NULL 
 * 底层调用lookupKey函数
 */
robj *lookupKeyReadWithFlags(redisDb *db, robj *key, int flags);
/* 先删除过期键,以读操作的方式从数据库中取出指定键对应的值对象
 * 如不存在则返回NULL,底层调用lookupKey函数
 */
robj *lookupKeyRead(redisDb *db, robj *key);
/* 先删除过期键,以写操作的方式从数据库中取出指定键对应的值对象
 * 如不存在则返回NULL,底层调用lookupKeyReadWithFlags函数
 */
robj *lookupKeyWrite(redisDb *db, robj *key);
/* 先删除过期键,以读操作的方式从数据库中取出指定键对应的值对象
 * 如不存在则返回NULL,底层调用lookupKeyRead函数
 * 此操作需要向客户端回复
 */
robj *lookupKeyReadOrReply(client *c, robj *key, robj *reply);
/* 先删除过期键,以写操作的方式从数据库中取出指定键对应的值对象
 * 如不存在则返回NULL,底层调用lookupKeyWrite函数
 * 此操作需要向客户端回复
 */
robj *lookupKeyWriteOrReply(client *c, robj *key, robj *reply) ;
/* 添加元素到指定数据库 */
void dbAdd(redisDb *db, robj *key, robj *val);
/* 重写指定键的值 */
void dbOverwrite(redisDb *db, robj *key, robj *val);
/* 设定指定键的值 */
void setKey(redisDb *db, robj *key, robj *val);
/* 判断指定键是否存在 */
int dbExists(redisDb *db, robj *key);
/* 随机返回数据库中的键 */
robj *dbRandomKey(redisDb *db);
/* 删除指定键 */
int dbDelete(redisDb *db, robj *key);
/* 清空所有数据库,返回键值对的个数 */
long long emptyDb(void(callback)(void*));

在server.c中可以找到Redis对于键空间的初始化操作,由于键都是字符串类型,Redis为其设定了特定的字典结构。

// 键空间字典的键为字符串对象,值为RedisObject
dictType dbDictType = {
    dictSdsHash,                // hash函数
    NULL,                       // 键复制函数
    NULL,                       // 值复制函数
    dictSdsKeyCompare,          // 键比较函数
    dictSdsDestructor,          // 键释放函数
    dictObjectDestructor   // 值释放函数
};

在服务器初始化时,关于服务器的键空间初始化操作如下:

for (j = 0; j < server.dbnum; j++) {
    // 创建每个数据库的建空间
    server.db[j].dict = dictCreate(&dbDictType,NULL);
    // ...
    // 设定当前数据库的编号
    server.db[j].id = j;
}

初始化键空间之后,就可以对该键空间操作了,下面一起来看看数据库增、删、查和改操作的源码吧。

查找键值对

查找键值对的操作都是由底层函数lookupKey完成,它的源码如下:

robj *lookupKey(redisDb *db, robj *key, int flags) {
    dictEntry *de = dictFind(db->dict,key->ptr);
    if (de) {
        // 获取该键对应的值
        robj *val = dictGetVal(de);

        // 更新指定键的最近操作时间
        if (server.rdb_child_pid == -1 &&
            server.aof_child_pid == -1 &&
            !(flags & LOOKUP_NOTOUCH))
        {
            val->lru = LRU_CLOCK();
        }
        return val;
    } else {
        return NULL;
    }
}

添加键值对

添加键值对在前面分析Redis五大数据类型的时候经常会看到,它由dbAdd函数来实现,传入的参数是待添加的数据库,键对象和值对象,其源码如下:

void dbAdd(redisDb *db, robj *key, robj *val) {
    sds copy = sdsdup(key->ptr);  // 复制键对象
    int retval = dictAdd(db->dict, copy, val); // 添加到数据库

    serverAssertWithInfo(NULL,key,retval == DICT_OK);
    // 如果值对象类型为list,需要判断该键是不是引起阻塞的键
    if (val->type == OBJ_LIST) signalListAsReady(db, key);
    // 如果开启的集群选项,则需要做相应的处理
    if (server.cluster_enabled) slotToKeyAdd(key);
 }

修改键值对

设定键值对的操作完成对指定键关联上值对象,也是前面分析五大数据类型的时候常见到的操作,其源码如下:

void setKey(redisDb *db, robj *key, robj *val) {
    if (lookupKeyWrite(db,key) == NULL) {  // 如果键不存在,添加
        dbAdd(db,key,val);
    } else {
        dbOverwrite(db,key,val);  // 反之,覆写该键的值对象
    }
    incrRefCount(val); // 增加其值对象的引用计数
    removeExpire(db,key);  // 删除过期时间
    signalModifiedKey(db,key);  // 发送键修改通知
}

删除键值对

删除键值对操作需要删除该键值对且删除过期时间字典中关于该键值对的选项。其源码如下:

int dbDelete(redisDb *db, robj *key) {
    /* 如果有设定过期键,就去过期键字典中删除该键 */
    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;
    }
}

其他关于键空间的操作,本篇博客就不一一分析了,有兴趣的去db.c文件中查看。

数据库的键过期操作

前面提到的expires指针就指向一个字典结构,该字典存放着每个键及其对应的过期时间,与键空间一样,expires字典的键是字符串对象。Redis同样为其声明了一个特定的字典结构,由于过期时间为一个整数,因此其值释放函数可以不设定。

dictType keyptrDictType = {
    dictSdsHash,                // hash函数
    NULL,                       // 键复制函数
    NULL,                       // 值复制函数
    dictSdsKeyCompare,          // 键比较函数
    NULL,          // 键释放函数
    NULL   // 值释放函数
}; 

在服务器初始化的时候,也对expires字典进行的初始化,采用keyptrDictType结构。

// 只截取了相关部分
for (j = 0; j < server.dbnum; j++) {
    // 创建每个数据库的过期时间字典
    server.db[j].expires = dictCreate(&keyptrDictType,NULL);
    // ...
    // 设定当前数据库的编号
    server.db[j].id = j;
}

那么,接下来就是设定键过期时间,删除键过期时间等操作的源码分析时间了。

设定键过期时间

设定键过期时间,需要将键及其过期时间添加到对应的字典结构中,其源码如下:

/* key表示键,when表示过期时间 */
void setExpire(redisDb *db, robj *key, long long when) {
    dictEntry *kde, *de;

    // 从键空间中查找key对应的dictEntry结构
    kde = dictFind(db->dict,key->ptr);
    // 如果键空间找不到该键,报错
    serverAssertWithInfo(NULL,key,kde != NULL);
    // 向字典中添加该键
    de = dictReplaceRaw(db->expires,dictGetKey(kde));
    // 设定该键的值为when
    dictSetSignedIntegerVal(de,when);
}

获取键过期时间

/* 获取键的过期时间 */
long long getExpire(redisDb *db, robj *key) {
    dictEntry *de;

    // 没有过期键,或者该过期键不存在,直接返回-1
    if (dictSize(db->expires) == 0 ||
       (de = dictFind(db->expires,key->ptr)) == NULL) return -1;

    // 查找该过期键,并获取过期时间,返回
    serverAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);
    return dictGetSignedIntegerVal(de);
}

删除键过期时间

删除键过期时间,首先需要在键空间查找该键还存不存在,如果不存在直接报错;反之就在expires字典中删除该键和它的过期时间。

/* 移除键的过期时间 */ 
int removeExpire(redisDb *db, robj *key) {
    // 在键空间中查找该键,如不存在直接报错
    serverAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);
    // 在expires字典中删除该键及其值
    return dictDelete(db->expires,key->ptr) == DICT_OK;
}

过期键删除策略

如果一个键设置了删除时间,那么面临的问题是以怎样的策略去删除该键。我们很容易理解下面三个删除策略:

  • 定时删除:如果一个键设置了过期时间,就为其创建一个定时器,在定时器结束时,立刻对该键执行删除操作
  • 惰性删除:在访问该键时,判断其过期时间是否到了,如果已过期,则执行删除操作。
  • 定期删除:每个一段时间,对数据库中的键进行一次遍历,删除其中的过期键,

其中,定时删除可以及时的删除过期键,但它为每一个设定了过期时间的键都开了一个定时器,使得CPU的负载变高,从而导致服务器的响应时间和吞吐量收到影响。

惰性删除有效的克服了定时删除对CPU的影响,但是,如果一个键长时间没有被访问,且这个键已经过期很久了,显然,大量的过期键会占用内存,从而导致内存上的消耗过大。

定时删除可以算是上述两种策略的折中。设定一个定时器,每隔一段时间遍历数据库,删除其中的过期键,有效的缓解了定时删除对CPU的占用以及惰性删除对内存的占用。

Redis采用了惰性删除和定时删除两种策略来对过期键进行处理,在上面的lookupKeyWrite等函数中就利用到了惰性删除策略,定时删除策略则是在根据服务器的例行处理程序serverCron来执行删除操作,该程序每100ms调用一次。

惰性删除函数

惰性删除由expireIfNeeded函数实现,其源码如下:

/* 检查key是否已经过期,如果是的话,将它从数据库中删除 
 * 并将删除命令写入AOF文件以及附属节点(主从复制和AOF持久化相关)
 * 返回0代表该键还没有过期,或者没有设置过期时间
 * 返回1代表该键因为过期而被删除
 */
int expireIfNeeded(redisDb *db, robj *key) {
    // 获取该键的过期时间
    mstime_t when = getExpire(db,key);
    mstime_t now;
    // 该键没有设定过期时间
    if (when < 0) return 0;

    // 服务器正在加载数据的时候,不要处理
    if (server.loading) return 0;

    // lua脚本相关
    now = server.lua_caller ? server.lua_time_start : mstime();

    // 主从复制相关,附属节点不主动删除key
    if (server.masterhost != NULL) return now > when;

    // 该键还没有过期
    if (now <= when) return 0;

    // 删除过期键
    server.stat_expiredkeys++;
    // 将删除命令传播到AOF文件和附属节点
    propagateExpire(db,key);
    // 发送键空间操作时间通知
    notifyKeyspaceEvent(NOTIFY_EXPIRED,
        "expired",key,db->id);
    // 将该键从数据库中删除
    return dbDelete(db,key);
}

定期删除策略

Redis定义了一个例行处理程序serverCron,该程序每隔100ms执行一次,在其执行过程中会调用databasesCron函数,这个函数里面才会调用真正的定期删除函数activeExpireCycle。该函数每次执行时遍历指定个数的数据库,然后从expires字典中随机取出一个带过期时间的键,检查它是否过期,如过期直接删除。

每隔100处理数据库的个数由CRON_DBS_PER_CALL参数决定,该参数的默认值如下:

#define CRON_DBS_PER_CALL 16  // 每次处理16个数据库

删除过期键的操作由activeExpireCycleTryExpire函数执行,其源码如下:

/* 检查键的过期时间,如过期直接删除*/
int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now) {
    // 获取过期时间
    long long t = dictGetSignedIntegerVal(de);
    if (now > t) {
        // 执行到此说明过期
        // 创建该键的副本
        sds key = dictGetKey(de);
        robj *keyobj = createStringObject(key,sdslen(key));
		// 将删除命令传播到AOF和附属节点
        propagateExpire(db,keyobj);
        // 在数据库中删除该键
        dbDelete(db,keyobj);
        // 发送事件通知
        notifyKeyspaceEvent(NOTIFY_EXPIRED,
            "expired",keyobj,db->id);
        // 临时键对象的引用计数减1
        decrRefCount(keyobj);
        // 服务器的过期键计数加1
        // 该参数影响每次处理的数据库个数
        server.stat_expiredkeys++;
        return 1;
    } else {
        return 0;
    }
}

关于删除过期键对AOF和主从复制的影响,在剖析相关功能实现的时候讲解,本篇博客不涉及到。

数据库命令

数据库的命令主要包括两类,一类是对数据库键空间的操作命令,另一类是对键过期时间的操作命令。下面分别从这两个部分讲解数据库命令。

键空间命令

键空间的操作命令的实现函数主要如下,这里只罗列出函数名及其功能。

/* 清空当前数据库 */
void flushdbCommand(client *c);
/* 清空所有数据库 */
void flushallCommand(client *c);
/* 删除指定键 */
void delCommand(client *c);
/* 判断指定件是否存在 */
void existsCommand(client *c);
/* 选择指定编号的数据库*/
void selectCommand(client *c);
/* 随机返回一个键 */
void randomkeyCommand(client *c);
/* 找出与给定模式匹配的键 */
void keysCommand(client *c);
/* 扫描数据库 */
void scanCommand(client *c);
/* 返回数据库中键的个数 */
void dbsizeCommand(client *c);
/* 返回最近一次存储的时间,与持久化有关 */
void lastsaveCommand(client *c);
/* 返回指定键对象的类型 */
void typeCommand(client *c);
/* 关闭客户端 */
void shutdownCommand(client *c);
/* 给指定键重命名,当key和newkey相同或者key不存在时返回错误
 * 当newkey存在时,将覆盖旧值
 */
void renameCommand(client *c);
/* 给指定件重命名,当且仅当newkey不存在才重命名 */
void renamenxCommand(client *c);
/* 移动指定键到另一个数据库 */
void moveCommand(client *c)

过期命令

过期时间命令全部是设定键的过期时间,看看下面的函数名及其功能。

/* 设定键的过期时间,给定参数为生存时间,单位为秒 
 * 即,该键的生存时间为给定的秒数
 */
void expireCommand(client *c);
/* 设定键的过期时间,给定参数为时间戳,单位为秒 
 * 即,该键到给定时间戳是过期
 */
void expireatCommand(client *c);
/* 设定键的过期时间,给定参数为生存时间,单位为毫秒 
 * 同上
 */
void pexpireCommand(client *c);
/* 设定键的过期时间,给定参数为时间戳,单位为毫秒
 * 同上
 */
void pexpireatCommand(client *c);

在过期命令中,Redis还提供了几个关于ttl的命令,用来获取指定键还剩下的生存时间。

void ttlCommand(client *c); // 获取指定键的剩余生存时间,单位为秒
void pttlCommand(client *c); // 获取指定键的剩余生存时间,单位为毫秒

命令格式和功能

还是按照我的习惯,附上一张命令个数和功能的对应表,让大家了解数据库操作的命令怎么运用。

命令格式 功能
FLUSHD 清空当前数据库
FLUSHALL 清空所有数据库
DBSIZE 返回当前数据库的键个数
DEL key [key …] 删除一个或多个键
EXISTS key 检查给定key是否存在
SELECT id 选择指定编码的数据库
RANDOMKEY 从当前数据库中随机返回一个键
KEYS pattern 查找左右符合给定模式pattern的key
SCAN cursor [MATCH pattern][COUNT count] 扫描当前数据库
LASTSAVE 返回最近一次成功将数据保存到磁盘上的时间
TYPE key 返回指定键的对象类型
SHUTDOWN 停止所有客户端
RENAME key newkey 重命名指定的key,newkey存在时覆盖
RENAMENX key newkey 重命名指定的key,当且仅当newkey不存在时操作
MOVE key db 移动key到指定数据库
EXPIRE key seconds 设定key的过期时间
TTL key 返回key的剩余生存空间

数据库小结

本片博客从数据库的三个方面讲了Redis数据库的实现原理,分别是数据库的切换,键空间和过期键。其中,设计到AOF持久化和主从复制等方面的知识没有进行过多的讲解,后面分析到具体的功能的时候,会对这些进行一个全面的分析。最后,总结了数据库的各类命令的执行格式和函数实现,由于实现源码都较为简单,故没有贴出来分析,各位读者可以根据函数名和功能去db.c文件中阅读以下相关源码,如有疑惑或者值得讨论的地方,可以在下方留言,期待和大家一起讨论Redis!

—2016/12/26

张程,于湖北·武汉