Redis源码剖析——数据库

数据库的实现

服务器状态rediServer结构体如下：

struct redisServer {

    // 配置文件的绝对路径
    char *configfile;       

    // serverCron() 每秒调用的次数
    int hz;          
    // 数据库
    redisDb *db;

    // 命令表（受到 rename 配置选项的作用）
    dict *commands;      
    ..........................
}

此结构体保存了服务器所需的所有信息
其中数据库redisDb结构体如下：

typedef struct redisDb {

    // 数据库键空间，保存着数据库中的所有键值对
    dict *dict;

    // 键的过期时间，字典的键为键，字典的值为过期事件 UNIX 时间戳
    dict *expires;          

    // 正处于阻塞状态的键
    dict *blocking_keys;        
    // 可以解除阻塞的键
    dict *ready_keys;          

    // 正在被 WATCH 命令监视的键
    dict *watched_keys;      

    struct evictionPoolEntry *eviction_pool;    
    // 数据库号码
    int id;        

    // 数据库的键的平均 TTL ，统计信息
    long long avg_ttl;  

} redisDb;

数据库的切换

每个客户端都操作自己的目标数据库，SELETE命令可以实现数据库的切换
客户端状态表示如下

typedef struct redisClient {

    // 套接字描述符
    int fd;

    // 当前正在使用的数据库
    redisDb *db;

    // 当前正在使用的数据库的 id （号码）
    int dictid;

    // 客户端的名字
    robj *name;
    ...........
}

客户端的db指针指向服务器db数组中的一个数据库
用图表示如下:

若此时执行SELETE 2 命令，状态如下图

所以数据库切换的代码实现很简单，改指针指向即可

// 将客户端的目标数据库切换为 id 所指定的数据库
int selectDb(redisClient *c, int id) {

    // 确保 id 在正确范围内
    if (id < 0 || id >= server.dbnum)
        return REDIS_ERR;

    // 切换数据库（更新指针）
    c->db = &server.db[id];

    return REDIS_OK;
}

数据库的键空间

数据库中的数据以键值对形式存在，采用字典实现
键通常为字符串对象，值为Redis的五大对象之一
下面介绍键值对的增删查改操作，本质都是对字典的操作

查找键

/*
 * 从数据库 db 中取出键 key 的值（对象）
 * 如果 key 的值存在，那么返回该值；否则，返回 NULL 。
 */
robj *lookupKey(redisDb *db, robj *key) {

    // 查找键空间
    dictEntry *de = dictFind(db->dict,key->ptr);

    // 节点存在
    if (de) {
        // 取出值
        robj *val = dictGetVal(de);
        // 更新时间信息（只在不存在子进程时执行，防止破坏 copy-on-write 机制）
        if (server.rdb_child_pid == -1 && server.aof_child_pid == -1)
            val->lru = LRU_CLOCK();

        // 返回值
        return val;
    } else {

        // 节点不存在

        return NULL;
    }
}

增加键值对

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);

    // 如果开启了集群模式，那么将键保存到槽里面
    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);
}

void dbOverwrite(redisDb *db, robj *key, robj *val) {
    dictEntry *de = dictFind(db->dict,key->ptr);

    // 节点必须存在，否则中止
    redisAssertWithInfo(NULL,key,de != NULL);

    // 覆写旧值
    dictReplace(db->dict, key->ptr, val);
}

int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, auxentry;

    // 尝试直接将键值对添加到字典
    // 如果键 key 不存在的话，添加会成功
    if (dictAdd(d, key, val) == DICT_OK)
        return 1;

    // 运行到这里，说明键 key 已经存在，那么找出包含这个 key 的节点
    entry = dictFind(d, key);

    // 先保存原有的值的指针
    auxentry = *entry;
    // 然后设置新的值
    dictSetVal(d, entry, val);
    // 然后释放旧值
    dictFreeVal(d, &auxentry);

    return 0;
}

删除键值对

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;
    }
}

键过期操作

redisDb结构的expires字典保存了键的过期时间
键指向数据库的某个键对象，值是 long long 类型的整数，保存了过期时间

设定键过期时间

void setExpire(redisDb *db, robj *key, long long when) {

    dictEntry *kde, *de;

    // 取出键
    kde = dictFind(db->dict,key->ptr);

    redisAssertWithInfo(NULL,key,kde != NULL);

    // 根据键取出键的过期时间
    de = dictReplaceRaw(db->expires,dictGetKey(kde));

    // 设置键的过期时间
    // 这里是直接使用整数值来保存过期时间，不是用 INT 编码的 String 对象
    dictSetSignedIntegerVal(de,when);
}

获取键过期时间

long long getExpire(redisDb *db, robj *key) {
    dictEntry *de;

    // 获取键的过期时间
    // 如果过期时间不存在，那么直接返回
    if (dictSize(db->expires) == 0 ||
       (de = dictFind(db->expires,key->ptr)) == NULL) return -1;

    redisAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);

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

删除键过期时间

int removeExpire(redisDb *db, robj *key) {
    // 确保键字典中存在键
    redisAssertWithInfo(NULL,key,dictFind(db->dict,key->ptr) != NULL);

    // 删除过期时间
    return dictDelete(db->expires,key->ptr) == DICT_OK;
}

过期键删除策略

• 定时删除
  在设置键的过期时间的同时，创建一个定时器，让定时器在键的过期时间来临时，立即执行删除
• 惰性删除
  放任过期键不管，每次获取键时都检查键是否过期，过期则删除
• 定期删除
  每隔一段时间就对数据库进行检查，删除里面的过期键。检查多少数据库，删除多少过期键则由具体算法决定

三种方法优劣如下：

删除策略	优点	缺点
定时删除	内存最友好	cpu最不友好，内存充足但过期键较多时，影响服务器响应时间和吞吐量
惰性删除	cpu最友好	浪费内存空间
定期删除	定期检查过期键，限制删除操作执行的时间和频率来减少删除操作对cpu时间的影响	难以确定执行的时长和频率

可以看出定期删除时定时和惰性的综合，难在难以确定时长和频率

Redis的删除策略

Redis综合了惰性删除和定期删除，合理使用cpu时间和内存空间，达到平衡

惰性删除的实现

所有读写数据库的命令在执行之前都会调用expireIfNeeded函数

/*
 * 检查 key 是否已经过期，如果是的话，将它从数据库中删除。
 * 返回 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;

    now = server.lua_caller ? server.lua_time_start : mstime();

    // 当服务器运行在 replication 模式时
    // 附属节点并不主动删除 key
    // 它只返回一个逻辑上正确的返回值
    // 真正的删除操作要等待主节点发来删除命令时才执行
    // 从而保证数据的同步
    if (server.masterhost != NULL) return now > when;

    // 运行到这里，表示键带有过期时间，并且服务器为主节点

    // 如果未过期，返回 0
    if (now <= when) return 0;

    server.stat_expiredkeys++;

    // 向 AOF 文件和附属节点传播过期信息
    propagateExpire(db,key);

    // 发送事件通知
    notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
        "expired",key,db->id);

    // 将过期键从数据库中删除
    return dbDelete(db,key);
}

定期删除的实现

服务器每秒执行serverCron函数server.hz次，serverCron函数会调用databasesCron函数，databasesCron会调用activeExpireCycle函数

/* 
 * 函数尝试删除数据库中已经过期的键。
 * 当带有过期时间的键比较少时，函数运行得比较保守，
 * 如果带有过期时间的键比较多，那么函数会以更积极的方式来删除过期键，
 * 从而可能地释放被过期键占用的内存。
 *
 * 每次循环中被测试的数据库数目不会超过 REDIS_DBCRON_DBS_PER_CALL(默认16) 。
 *
 * 如果 timelimit_exit 为真，那么说明还有更多删除工作要做，
 * 那么在 beforeSleep() 函数调用时，程序会再次执行这个函数。
 *
 * 过期循环的类型：
      如果循环的类型为 ACTIVE_EXPIRE_CYCLE_FAST 
          那么函数会以“快速过期”模式执行，
          执行的时间不会长过 EXPIRE_FAST_CYCLE_DURATION 毫秒，
          并且在 EXPIRE_FAST_CYCLE_DURATION 毫秒之内不会再重新执行。

      如果循环的类型为 ACTIVE_EXPIRE_CYCLE_SLOW 
          那么函数会以“正常过期”模式执行，
          函数的执行时限为 REDIS_HS 常量的一个百分比，
          这个百分比由 REDIS_EXPIRELOOKUPS_TIME_PERC 定义。
 */

void activeExpireCycle(int type) {
    // 静态变量，用来累积函数连续执行时的数据
    static unsigned int current_db = 0; 
    static int timelimit_exit = 0;
    // 上一次快速过期的运行开始时间 
    static long long last_fast_cycle = 0;

    unsigned int j, iteration = 0;
    // 默认每次处理的数据库数量
    unsigned int dbs_per_call = REDIS_DBCRON_DBS_PER_CALL;
    // 函数开始的时间
    long long start = ustime(), timelimit;

    // 快速模式
    if (type == ACTIVE_EXPIRE_CYCLE_FAST) {
        // 如果上次函数没有触发 timelimit_exit ，那么不执行处理
        if (!timelimit_exit) return;
        // 如果距离上次执行未够一定时间，那么不执行处理
        if (start < last_fast_cycle + ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2) return;
        // 运行到这里，说明执行快速处理，记录当前时间
        last_fast_cycle = start;
    }

    /* 
      一般情况下，函数只处理 REDIS_DBCRON_DBS_PER_CALL 个数据库，
      除非：
         1)当前数据库的数量小于 REDIS_DBCRON_DBS_PER_CALL
         2)如果上次处理遇到了时间上限，那么这次需要对所有数据库进行扫描，
         这可以避免过多的过期键占用空间
     */
    if (dbs_per_call > server.dbnum || timelimit_exit)
        dbs_per_call = server.dbnum;

    // 函数处理的微秒时间上限
    // ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC 默认为 25 ，也即是 25 % 的 CPU 时间
    timelimit = 1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100;
    timelimit_exit = 0;
    if (timelimit <= 0) timelimit = 1;

    // 如果是运行在快速模式之下
    // 那么最多只能运行 FAST_DURATION 微秒 
    // 默认值为 1000 （微秒）
    if (type == ACTIVE_EXPIRE_CYCLE_FAST)
        timelimit = ACTIVE_EXPIRE_CYCLE_FAST_DURATION; 

    // 遍历数据库
    for (j = 0; j < dbs_per_call; j++) {
        int expired;
        // 指向要处理的数据库
        redisDb *db = server.db+(current_db % server.dbnum);
        // 为 DB 计数器加一，如果进入 do 循环之后因为超时而跳出
        // 那么下次会直接从下个 DB 开始处理
        current_db++;

        do {
            unsigned long num, slots;
            long long now, ttl_sum;
            int ttl_samples;

            // 获取数据库中带过期时间的键的数量
            // 如果该数量为 0 ，直接跳过这个数据库
            if ((num = dictSize(db->expires)) == 0) {
                db->avg_ttl = 0;
                break;
            }
            // 获取数据库中键值对的数量
            slots = dictSlots(db->expires);
            // 当前时间
            now = mstime();

            // 这个数据库的使用率低于 1% ，扫描起来太费力了（大部分都会 MISS）
            // 跳过，等待字典收缩程序运行
            if (num && slots > DICT_HT_INITIAL_SIZE &&
                (num*100/slots < 1)) break;

            // 已处理过期键计数器
            expired = 0;
            // 键的总 TTL 计数器
            ttl_sum = 0;
            // 总共处理的键计数器
            ttl_samples = 0;

            // 每次最多只能检查 LOOKUPS_PER_LOOP 个键
            if (num > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP)
                num = ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP;

            // 开始遍历数据库
            while (num--) {
                dictEntry *de;
                long long ttl;

                // 从 expires 中随机取出一个带过期时间的键
                if ((de = dictGetRandomKey(db->expires)) == NULL) break;
                // 计算 TTL
                ttl = dictGetSignedIntegerVal(de)-now;
                // 如果键已经过期，那么删除它，并将 expired 计数器增一
                if (activeExpireCycleTryExpire(db,de,now)) expired++;
                if (ttl < 0) ttl = 0;
                // 累积键的 TTL
                ttl_sum += ttl;
                // 累积处理键的个数
                ttl_samples++;
            }

            // 为这个数据库更新平均 TTL 统计数据
            if (ttl_samples) {
                // 计算当前平均值
                long long avg_ttl = ttl_sum/ttl_samples;

                // 如果这是第一次设置数据库平均 TTL ，那么进行初始化
                if (db->avg_ttl == 0) db->avg_ttl = avg_ttl;
                // 取数据库的上次平均 TTL 和今次平均 TTL 的平均值
                db->avg_ttl = (db->avg_ttl+avg_ttl)/2;
            }

            // 我们不能用太长时间处理过期键，
            // 所以这个函数执行一定时间之后就要返回

            // 更新遍历次数
            iteration++;

            // 每遍历 16 次执行一次
            if ((iteration & 0xf) == 0 && 
                (ustime()-start) > timelimit)
            {
                // 如果遍历次数正好是 16 的倍数
                // 并且遍历的时间超过了 timelimit
                // 那么断开 timelimit_exit
                timelimit_exit = 1;
            }

            // 已经超时了，返回
            if (timelimit_exit) return;

            // 如果已删除的过期键占当前总数据库带过期时间的键数量的 25 %
            // 那么不再遍历
        } while (expired > ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP/4);
    }
}

这个函数很重要，解释下过程

函数参数type有两种，FAST模式和SLOW模式
在FAST模式下如果上次的函数不是因为超时而退出则函数返回
如果距离上次执行未够ACTIVE_EXPIRE_CYCLE_FAST_DURATION*2ms，即2000ms则返回

函数每次默认处理REDIS_DBCRON_DBS_PER_CALL（16）个数据库
有三个静态变量current_db，timelimit_exit，last_fast_cycle，分别表示下一个要遍历的数据库编号，上一次调用是否超时，上一次FAST模式的开始时间

在SLOW模式下能运行25%的cpu时间，在FAST模式下最多运行ACTIVE_EXPIRE_CYCLE_FAST_DURATION（1000）微秒

如果过期键中键的数量占哈希表大小比例低于1%则终止，没有扫描的必要
对每次数据库每次只检查ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP（20）个键

遍历数据库操作如下：
1. 随机取出一个键，如果键已经过期则删除，删除计数器expipred加一
2. 累积键 TTL，累积键的处理个数

如果已删除的键超过ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP / 4，则这个数据库遍历终止，遍历下一个数据库

其中删除函数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));

        // 传播过期命令
        propagateExpire(db,keyobj);
        // 从数据库中删除该键
        dbDelete(db,keyobj);
        // 发送事件
        notifyKeyspaceEvent(REDIS_NOTIFY_EXPIRED,
            "expired",keyobj,db->id);
        decrRefCount(keyobj);
        // 更新计数器
        server.stat_expiredkeys++;
        return 1;
    } else {

        // 键未过期
        return 0;
    }
}

其中传播命令，发送通知，AOF持久化，RDB持久化操作在后面源码阅读中再解释

小节

了解了数据库的切换以及增删查改操作，特别是对于过期键的处理策略。
之后学习AOF持久化，RDB持久化