redis设计与实现——数据库

发表于

redis设计与实现——数据库

服务器中的数据库

redis服务器将所有的数据库都保存在服务器状态redis.h/redisServer结构的db数组里，每一个redisDb代表一个数据库，redis默认创建16个数据库。

1
2
3
4
5
6
7
8
9
10
11
12
struct redisServer {
  // ...
	redisDb *db; // 保存着服务器中所有的数据库
  int dbnum;   /* Total number of configured DBs */
};

// 初始化db配置
#define CONFIG_DEFAULT_DBNUM     16
void initServerConfig(void) {
  // ...
  server.dbnum = CONFIG_DEFAULT_DBNUM;
}

切换数据库

由于每个Redis客户端都有自己的目标数据库，客户端通过SELECT命令来切换目标数据库。而server.h的结构体client中就有一个指向redisDb的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 同样client会含有指向db的指针
typedef struct client {
  //...
  redisDb *db; /*指向当前被选中的db */
} client;

// 通过select命令切换数据库
int selectDb(client *c, int id) {
    if (id < 0 || id >= server.dbnum)
        return C_ERR;
    c->db = &server.db[id];
    return C_OK;
}

目前没有命令可以获取当前db的index，但可以通过设置唯一名字并获取clientInfo的方法动态获取index：https://stackoverflow.com/questions/50534492/redis-how-to-get-current-database-name

数据库键空间

Redis是一个键值对数据库服务器，由上面可知每个数据库都由一个redisDb结构表示，其中redisDb的dict字段保存了数据库中的所有键值对。

1
2
3
4
5
6
7
8
9
10
typedef struct redisDb {
    dict *dict;                 /* key空间 */
    dict *expires;              /* 国企高管时间 */
    dict *blocking_keys;        /* 客户端正在等待数据的key*/
    dict *ready_keys;           /* 接受了push命令的key */
    dict *watched_keys;         /* 被监控的key*/
    int id;                     /* Database ID */
    long long avg_ttl;          /* 用来做统计，平均ttl */
    list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

添加新键

添加新键值对，实际上就是将键值对添加到键空间字段中，key为字符串对象，值为任意一种类型的redis对象。

以set命令为例：

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
void setGenericCommand(client *c, int flags, robj *key, robj *val, robj *expire, int unit, robj *ok_reply, robj *abort_reply) {
    long long milliseconds = 0; /* initialized to avoid any harmness warning */
		// 如果设置了国旗时间则校验expire是否为数字
    if (expire) {
        if (getLongLongFromObjectOrReply(c, expire, &milliseconds, NULL) != C_OK)
            return;
        if (milliseconds <= 0) {
            addReplyErrorFormat(c,"invalid expire time in %s",c->cmd->name);
            return;
        }
        if (unit == UNIT_SECONDS) milliseconds *= 1000;
    }
		// 实现NX和XX两种添加方式
  	// #define OBJ_SET_NX (1<<0)     /* Set if key not exists. */	
		//#define OBJ_SET_XX (1<<1)     /* Set if key exists. */
    if ((flags & OBJ_SET_NX && lookupKeyWrite(c->db,key) != NULL) ||
        (flags & OBJ_SET_XX && lookupKeyWrite(c->db,key) == NULL))
    {
        addReply(c, abort_reply ? abort_reply : shared.null[c->resp]);
        return;
    }
    setKey(c->db,key,val);// 设置key
    server.dirty++;
    if (expire) setExpire(c,c->db,key,mstime()+milliseconds);//设置国旗时间
    notifyKeyspaceEvent(NOTIFY_STRING,"set",key,c->db->id);
    if (expire) notifyKeyspaceEvent(NOTIFY_GENERIC,
        "expire",key,c->db->id);
    addReply(c, ok_reply ? ok_reply : shared.ok);

在设置过期时间的操作中，可以看到，虽然key和expire是分开存放在redisDb结构体中的，但实际上两者指向了同一个对象。

1
2
3
4
5
6
7
8
9
void setExpire(redisDb *db, robj *key, long long when) {    // 设置过期时间
    dictEntry *kde, *de;

    /* Reuse the sds from the main dict in the expire dict */
    kde = dictFind(db->dict,key->ptr);  // 找到对应的字典节点
    serverAssertWithInfo(NULL,key,kde != NULL);
    de = dictReplaceRaw(db->expires,dictGetKey(kde));   // 将过期时间expire加入到dict，其中共用同一个字符串对象实例
    dictSetSignedIntegerVal(de,when);
}

其他的删改查操作，都是在dict字段上面封装了一层。

设置键的生存时间或过期时间

设置过期时间

通过EXPIRE或PEXPIRE命令可以为key设置秒级或毫秒级的生存时间（Time To Live，TTL）。也可以用EXPRIEAT或者PEXPIREAT设置一个过期时间戳。事实上，这三个命令的底层实现都是通过时间戳的设置方式来完成过期时间设置的。

参考源码，这个函数是EXPIRE, PEXPIRE, EXPIREAT和PEXPIREAT四个命令的底层实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void expireGenericCommand(client *c, long long basetime, int unit) {
    robj *key = c->argv[1], *param = c->argv[2];
    long long when; /* 毫秒级别的unix时间戳 */

    if (getLongLongFromObjectOrReply(c, param, &when, NULL) != C_OK)
        return;

    if (unit == UNIT_SECONDS) when *= 1000;
    when += basetime;

    /* No key, return zero. */
    if (lookupKeyWrite(c->db,key) == NULL) {
        addReply(c,shared.czero);
        return;
    }

    // ....
}

保存过期时间

redisDb结构的expires字段保存了数据库中所有key的过期时间，这是一个字典，其key是一个指向某个键对象的指针，而value则是一个long long类型的整数，一个毫秒级别的unix时间戳。

移除过期时间

使用PERSIST命令可以移除一个键的过期时间，实际上就是删除expires字段中该键与过期时间的项。

1
2
3
4
5
6
7
8
9
10
11
12
13
void persistCommand(client *c) {
    if (lookupKeyWrite(c->db,c->argv[1])) {
      	// 调用 dictDelete(db->expires,key->ptr)  删除
        if (removeExpire(c->db,c->argv[1])) {
            addReply(c,shared.cone);
            server.dirty++;
        } else {
            addReply(c,shared.czero);
        }
    } else {
        addReply(c,shared.czero);
    }
}

计算并返回剩余生存时间

TTL和PTTL命令则是返回以秒为单位或者毫秒为单位的键剩余时间，实现比较简单，就是计算键的过期时间与当前时间之间的差。

过期键删除策略

Redis采用了两种删除策略：惰性删除和定期删除。其中，惰性删除是一种对CPU时间最友好的策略，程序只会在取出键时才会对键进行过期检查。

惰性删除策略的实现

过期键的惰性删除策略都必须要经常函数db.c/expireIfNeeded函数实现。

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
int expireIfNeeded(redisDb *db, robj *key) {
    if (!keyIsExpired(db,key)) return 0; // key不存在，什么都不处理

    if (server.masterhost != NULL) return 1; // 只对master库进行删除

    /* 删除key */
    server.stat_expiredkeys++;
  	// 当一个主库key被删除时，会向从库发一条del命令和被启动的AOF文件追加del
    propagateExpire(db,key,server.lazyfree_lazy_expire);
    notifyKeyspaceEvent(NOTIFY_EXPIRED,
        "expired",key,db->id);
    return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) :
                                         dbSyncDelete(db,key);
}

int dbAsyncDelete(redisDb *db, robj *key) {
    /* 删除expire字段的dict不会释放空间，因为该字典与主字典是共享内存 */
    if (dictSize(db->expires) > 0) dictDelete(db->expires,key->ptr);
		
  	// 如果对象很小，以惰性删除的方式实际上更慢
    dictEntry *de = dictUnlink(db->dict,key->ptr);
    if (de) {
        robj *val = dictGetVal(de);
        size_t free_effort = lazyfreeGetFreeEffort(val);

        /* 创建一个后台任务，添加对象到lazy free list里 */
        if (free_effort > LAZYFREE_THRESHOLD && val->refcount == 1) {
            atomicIncr(lazyfree_objects,1);
            bioCreateBackgroundJob(BIO_LAZY_FREE,val,NULL,NULL);
            dictSetVal(db->dict,de,NULL);
        }
    }

    /* 释放键值对 */
    if (de) {
        dictFreeUnlinkedEntry(db->dict,de);
        if (server.cluster_enabled) slotToKeyDel(key);//集群删除
        return 1;
    } else {
        return 0;
    }
}

调用dictDelete的时候不会删除dict对象，只会删除expires对象，尽管它们公用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
// 同步删除，通过调用dictDelte实现
int dbSyncDelete(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;
    }
}

// 在实现删除expire字段，但不删除共享key的实现上，主要利用了dict底层结构中的dictType字段，该字段定义了dict的各种操作。
typedef struct dictType {   // 各种字典操作
    unsigned int (*hashFunction)(const void *key);  // 计算hash值的函数
    void *(*keyDup)(void *privdata, const void *key);   // 键复制
    void *(*valDup)(void *privdata, const void *obj);   // 值复制
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);  // 键比较
    void (*keyDestructor)(void *privdata, void *key);   // 键销毁
    void (*valDestructor)(void *privdata, void *obj);   // 值销毁
} dictType;

// 而在初始化expires时，则将keyDestructor和valDestructor设置为了NULL

定期删除策略的实现

过期键的定期删除策略时由expire.c/activeExpireCycle()实现的，它会在规定的时间内，多次去遍历服务器中的各个数据库，从数据库的expires字段中随机抽查一部分键的过期时间。

AOF、ROB和复制功能对过期键的处理

  • 产生的新RDB文件和重写的AOF文件都不会包含已过期的键；
  • 当主服务器删除一个键之后，会向所有从服务器发del命令；
  • 当一个过期键被删除之后，服务器会追加一条del命令到现有AOF文件的末尾；
  • 从服务器即使发现过期键也不删除，而是等待master节点发来del命令；