淺析Redis數(shù)據(jù)結(jié)構(gòu)
Labs 導(dǎo)讀
Redis ( Remote Dictionary Server)遠(yuǎn)程字典服務(wù)，是一款通過Key-Value存儲的NoSql數(shù)據(jù)庫，數(shù)據(jù)緩存在內(nèi)存中，支持網(wǎng)絡(luò)、可持久化日志，提供多種語言的API，常用的場景有高速緩存、分布式數(shù)據(jù)共享、分布式鎖、限流和消息隊(duì)列等。通常項(xiàng)目研發(fā)中，結(jié)合springframework封裝的RedisTemplate API使用。
Part 01、 環(huán)境搭建
● 操作系統(tǒng)：CentOS7
● 集成環(huán)境：CLion
● 編譯環(huán)境：GCC9
● 代碼版本：redis-6.2.6
1.1 環(huán)境安裝
操作系統(tǒng)和集成環(huán)境的可自行安裝。由于Centos 7默認(rèn)gcc版本較低，因此需要升級GCC版本，通過如下命令可完成編譯環(huán)境的升級：
# 安裝centos-release-scl
% yum -y install centos-release-scl
# 安裝devtoolset GGC9
% yum -y install devtoolset-9-gcc devtoolset-9-gcc-c++ devtoolset-9-binutils
# 激活對應(yīng)的devtoolset
% echo “source /opt/rh/devtoolset-9/enable” >> /etc/profile
# 查看版本
% gcc -v1.2 編譯和運(yùn)行
從官方網(wǎng)站下載源碼，解壓，編譯和運(yùn)行。
% wget http://download.redis.io/releases/redis-6.2.6.tar.gz
% tar -zxvf redis-6.2.6.tar.gz -C /home/jay/redis/redis-6.2.6/ && rm -rf redis-6.2.6.tar.gz
% cd /home/jay/redis/redis-6.2.6/
% make
% make install
# 啟動Redis
% cd src
% ./redis-server
# 驗(yàn)證
% cd src
% ./redis-cli
圖片
使用Clion建立C工程，并導(dǎo)入源代碼，確保GCC9是對應(yīng)的編譯環(huán)境，以調(diào)試模式啟動“redis-server”模塊，使用“redis-cli”客戶端連接服務(wù)端，設(shè)置斷點(diǎn)，鍵入相應(yīng)的命令進(jìn)行調(diào)試。
圖片
Part 02、 數(shù)據(jù)庫的組織結(jié)構(gòu)
首先從宏觀層面了解數(shù)據(jù)庫的結(jié)構(gòu)及組織關(guān)系。redisDB,dict,dictht,dictEntry,
redisObject等相關(guān)數(shù)據(jù)庫結(jié)構(gòu)定義在server.h, dict.h,sds.h和zipList.h等頭文件中。
//server.h
typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
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 */
dict *watched_keys; /* WATCHED keys for MULTI/EXEC CAS */
int id; /* Database ID */
long long avg_ttl; /* Average TTL, just for stats */
unsigned long expires_cursor; /* Cursor of the active expire cycle. */
list *defrag_later; /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;下圖通過UML類圖的方式，梳理各個數(shù)據(jù)結(jié)構(gòu)之間的組織關(guān)系。
圖片
通過上圖，可以了解到如下內(nèi)容：
（1） RedisDB可有多個，通過“redis.conf”中的“databases”參數(shù)進(jìn)行配置，默認(rèn)是16個；
（2） 每個RedisDB有兩個"dictht"哈希表組成，分別是ht[0]和ht[1]，這樣做的目的是為了rehash，主要解決擴(kuò)容和縮容的問題，通過ht[0]和ht[1]相互搬遷數(shù)據(jù)完成rehash工作，而且每次命令只搬遷一個索引下面的數(shù)據(jù)，減少系統(tǒng)操作時間，避免因數(shù)據(jù)量過大而影響性能；其實(shí)現(xiàn)在“dict.c”的dictRehash函數(shù)中。
（3） HASH表中存儲的每個元素是“dictEntry”結(jié)構(gòu)組成的鏈表。通過鏈?zhǔn)剑鉀Q兩個key的哈希值正好落在同一個哈希桶中的哈希沖突問題。
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
/*在HASH桶中找到非空的索引后，開始鏈表的數(shù)據(jù)移動工作*/
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
uint64_t h;
nextde = de->next;
/* 在新的hash表中找到對應(yīng)鍵值的索引 */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
/* 把要增加的數(shù)據(jù)放在新的hash表對應(yīng)索引鏈表的開始 */
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
/* 更新計(jì)數(shù)器 */
d->ht[0].used--;
d->ht[1].used++;
/* 鏈表中的下一個Node */
de = nextde;
}
/* 因數(shù)據(jù)已完成移動，因此清空老的hash表對應(yīng)的桶 */
d->ht[0].table[d->rehashidx] = NULL;
/* 指向下一個桶 */
d->rehashidx++;
}
/* 如果已經(jīng)rehashed了所有的表，釋放HT[0]的表空間，將HT[1]設(shè)置為當(dāng)前的表，重置HT[1] */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}（4） “dictEntry”中的"key"由sds（簡單動態(tài)字符串）結(jié)構(gòu)組成。redis根據(jù)數(shù)據(jù)的長度，定義了不同類型的sds結(jié)構(gòu)。例如：sdshdr8，sdshdr16,sdshdr32,sdshdr64；這樣的結(jié)構(gòu)定義，既節(jié)省了空間，也解決了二進(jìn)制安全（例如C語言的‘\0’）和緩沖區(qū)溢出（通過alloc-len可計(jì)算剩余空間）等問題。
//SDS.H
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};（5） redis有“STRING, LIST,SET,ZSET,HASH,MODULE,STREAM”七種數(shù)據(jù)類型；有“sds, quicklist,ziplist,dict,zskiplist,stream”七種底層數(shù)據(jù)結(jié)構(gòu)；每種數(shù)據(jù)類型根據(jù)存儲數(shù)據(jù)的大小，多少等，分別由不同的底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。例如list數(shù)據(jù)類型，由“quicklist，ziplist”分別實(shí)現(xiàn)；HASH數(shù)據(jù)類型，由“dict，ziplist”分別實(shí)現(xiàn)。
（6） dictEntry”中的"*val"指向redisObject"結(jié)構(gòu)，此結(jié)構(gòu)中“redisObject->type”存儲的是數(shù)據(jù)類型；“redisObject->encoding”存儲的是底層的數(shù)據(jù)結(jié)構(gòu)類型；redisObject->ptr”存儲具體的數(shù)據(jù)；相應(yīng)的實(shí)現(xiàn)在“object.c”中。
//object.c
robj *createQuicklistObject(void) {
quicklist *l = quicklistCreate();
robj *o = createObject(OBJ_LIST,l);
o->encoding = OBJ_ENCODING_QUICKLIST;
return o;
}
robj *createZiplistObject(void) {
unsigned char *zl = ziplistNew();
robj *o = createObject(OBJ_LIST,zl);
o->encoding = OBJ_ENCODING_ZIPLIST;
return o;
}
robj *createSetObject(void) {
dict *d = dictCreate(&setDictType,NULL);
robj *o = createObject(OBJ_SET,d);
o->encoding = OBJ_ENCODING_HT;
return o;
}
robj *createIntsetObject(void) {
intset *is = intsetNew();
robj *o = createObject(OBJ_SET,is);
o->encoding = OBJ_ENCODING_INTSET;
return o;
}
robj *createHashObject(void) {
unsigned char *zl = ziplistNew();
robj *o = createObject(OBJ_HASH, zl);
o->encoding = OBJ_ENCODING_ZIPLIST;
return o;
}Part 03、 源碼調(diào)試
3.1 入口
正如所有的C代碼一樣，入口是service.c中的main函數(shù)。
圖片
3.2 redis命令入口
所有的redis命令定義在“redisCommandTable”數(shù)組中，類型為"redisCommand"，通過函數(shù)指針的方式調(diào)用。例如下圖中的Get和Set命令。
圖片
圖片
Part 04、 總結(jié)
以上分別從環(huán)境搭建，數(shù)據(jù)庫的結(jié)構(gòu)組織關(guān)系和源碼調(diào)試進(jìn)行了介紹，如果你對redis源代碼感興趣，行動起來吧！
