首页 > 代码库 > redis 源码学习(核心数据结构剖析)

redis 源码学习(核心数据结构剖析)

redis是个key, value数据库,是个内存数据库。目前是个互联网公司的架构标配。

支持的数据对象有string, list, set, zest和hash object。


数据结构:

数据库的核心结构是dict(实现是使用hashmap):

key: string

value: string或者list或者set或者zest或者hash object。

dict数据结构定义:

typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩码,用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;
table是个哈希表数组,每个元素是个dictEntry(哈希节点)指针,dictEntry的定义如下:

typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点,形成链表
    struct dictEntry *next;

} dictEntry;
其中,key是哈希表的键, value是val指向的对象(string, list, set, zest和hash object),或者是64位无符号的整形,或者64位有符号的整形, next是指向下个哈希节点的指针。

数据结构图表示如下:

技术分享

数据库:

上面介绍了数据库的核心数据结构,现在从数据库的服务启动角度剖析下。
启动的入口main函数:
int main(int argc, char **argv) {

	//...

	//初始化服务
	initServer();

	//...

}
initServer函数:
void initServer(){
    //...

    /* Create the Redis databases, and initialize other internal state. */
    // 创建并初始化数据库结构
    for (j = 0; j < server.dbnum; j++) {
        server.db[j].dict = dictCreate(&dbDictType,NULL);
        server.db[j].expires = dictCreate(&keyptrDictType,NULL);
        server.db[j].blocking_keys = dictCreate(&keylistDictType,NULL);
        server.db[j].ready_keys = dictCreate(&setDictType,NULL);
        server.db[j].watched_keys = dictCreate(&keylistDictType,NULL);
        server.db[j].eviction_pool = evictionPoolAlloc();
        server.db[j].id = j;
        server.db[j].avg_ttl = 0;
    }

    //...
}
其中: struct reidsServer server;//server对象的定义。

redisServer结构:

struct redisServer {
	// …

	// redis数据库数组
	redisDb *db;
<span style="white-space:pre">	</span>// 数据库的数量
<span style="white-space:pre">	</span>int dbnum;

	//...
}
一个redisServer可以定义dbnum个数据库,在使用的过程中可以切换,使用select命令,比如:select 0, select 1。。。

redisDb的数据结构:

/* Redis database representation. There are multiple databases identified
 * by integers from 0 (the default database) up to the max configured
 * database. The database number is the 'id' field in the structure. */
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;

可以看出核心就是个哈希表dict。


redis 源码学习(核心数据结构剖析)