引言

這篇文章主要聊聊Redis具體功能數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，主要針對(duì)常用的五種數(shù)據(jù)結(jié)構(gòu)，string，hash，list，set和zset的實(shí)現(xiàn)。

在redis.c:180中存儲(chǔ)了Redis支持所有的指令及其實(shí)現(xiàn)函數(shù)：

struct redisCommand redisCommandTable[] = {
    {"get",getCommand,2,"r",0,NULL,1,1,1,0,0},
    {"set",setCommand,-3,"wm",0,NULL,1,1,1,0,0},
    {"setnx",setnxCommand,3,"wm",0,NULL,1,1,1,0,0},
    //...
}

第二個(gè)屬性就是指令的具體實(shí)現(xiàn)函數(shù)，進(jìn)入該函數(shù)即可閱讀相應(yīng)的指令的具體實(shí)現(xiàn)。

在調(diào)用具體的命令執(zhí)行函數(shù)前，命令就被拆成一個(gè)個(gè)參數(shù)存放到相應(yīng)的redisClient.argv中了，比如Redis命令set aaa "aaa"會(huì)被拆成數(shù)組{"set", "aaa", "aaa"}放在redisClient.argv中。

Redis數(shù)據(jù)庫的真身

redisClient結(jié)構(gòu)體中有一個(gè)db字段，它是redisDb類型，這個(gè)就是該redisClient目前選中的數(shù)據(jù)庫，不論是哪種數(shù)據(jù)類型，都會(huì)調(diào)用setKey函數(shù)將自己設(shè)置進(jìn)數(shù)據(jù)庫中：

void setKey(redisDb *db, robj *key, robj *val) {

    // 添加或覆寫數(shù)據(jù)庫中的鍵值對(duì)
    if (lookupKeyWrite(db,key) == NULL) {
        dbAdd(db,key,val);
    } else {
        dbOverwrite(db,key,val);
    }

    //...
}

void dbAdd(redisDb *db, robj *key, robj *val) {

    //....
    int retval = dictAdd(db->dict, copy, val);

    //...
 }

發(fā)現(xiàn)其實(shí)就是在往redisDb的dict字典中加入kv，dict就是Redis自己實(shí)現(xiàn)的字典結(jié)構(gòu)，其實(shí)現(xiàn)類似于高級(jí)語言中的hashmap，可見一個(gè)Redis數(shù)據(jù)庫本質(zhì)就是一個(gè)大字典，當(dāng)你創(chuàng)建的不同的數(shù)據(jù)結(jié)構(gòu)時(shí)，本質(zhì)上都是在往這個(gè)大字典中寫入kv。從setKey的簽名可以看出，這個(gè)大字典中的每一個(gè)key和value都是robj類型，這是個(gè)什么東西呢？

redisObject

robj其實(shí)是redisObject的簡稱：

typedef struct redisObject {

    // 類型
    unsigned type:4;   // 4 bit 位域

    // 編碼 （底層數(shù)據(jù)結(jié)構(gòu)類型）
    unsigned encoding:4;

    // 對(duì)象最后一次被訪問的時(shí)間
    unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */

    // 引用計(jì)數(shù)
    int refcount;

    // 指向?qū)嶋H值的指針  指向底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)
    void *ptr;

} robj;

類型type代表了該robj對(duì)用戶暴露的類型，就是引言中說的五種類型：

而encoding代表底層實(shí)際使用的數(shù)據(jù)結(jié)構(gòu)類型，而具體的底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)存儲(chǔ)在ptr字段中。

底層數(shù)據(jù)結(jié)構(gòu)

底層數(shù)據(jù)結(jié)構(gòu)是指不對(duì)用戶暴露，僅僅作為底層實(shí)現(xiàn)的一些數(shù)據(jù)結(jié)構(gòu)，Redis有如下的底層數(shù)據(jù)結(jié)構(gòu)：

• long：就是C語言中普通的long類型，當(dāng)字符串可以編碼成long類型的數(shù)字時(shí)，會(huì)采用這種結(jié)構(gòu)
• sds：就是Redis中的字符串類型
  • 所有的key的底層數(shù)據(jù)結(jié)構(gòu)都是它
  • 字符串的底層數(shù)據(jù)結(jié)構(gòu)，根據(jù)其內(nèi)存擺放特點(diǎn)又有兩種
    • raw：普通的sds
    • embstr：內(nèi)存中位置緊跟在相應(yīng)的redisObject后面，可以和redisObject一起分配與釋放
• dict：Redis自己實(shí)現(xiàn)字典，除了用于實(shí)現(xiàn)Redis內(nèi)部的功能外，還用于hash和set的底層數(shù)據(jù)結(jié)構(gòu)
• ziplist：在內(nèi)存中連續(xù)排列的一個(gè)列表結(jié)構(gòu)，可以存儲(chǔ)字符串或者數(shù)字，和別的結(jié)構(gòu)不一樣的地方是，在代碼中沒有具體的結(jié)構(gòu)體來表示，只有一些宏可以從代表ziplist的byte串取得具體屬性的值，redis.c:246。
  • 是list, hash和zset數(shù)據(jù)結(jié)構(gòu)的默認(rèn)實(shí)現(xiàn)
  • 雖然是一個(gè)緊湊的數(shù)據(jù)結(jié)構(gòu)，但卻無法像數(shù)組一樣隨機(jī)訪問，各種操作的時(shí)間復(fù)雜度和鏈表類似，在查詢時(shí)需要一個(gè)一個(gè)元素往下走
  • 該編碼相對(duì)比較復(fù)雜，網(wǎng)上有很多文章講解，這里就不專門介紹了
• list：Redis自己實(shí)現(xiàn)的一個(gè)雙向鏈表，可用于list的底層數(shù)據(jù)結(jié)構(gòu)
• intset：整數(shù)集合，其實(shí)就是個(gè)從小到大排列的整數(shù)數(shù)組，如果set中所有的元素都是數(shù)字的話，可以用于set的底層數(shù)據(jù)結(jié)構(gòu)
• skiplist：跳表，可以和dict一起用于zset的底層數(shù)據(jù)結(jié)構(gòu)，其中dict用于按成員取分值，而skiplist負(fù)責(zé)按分值取成員。

下面逐一通過圖示五種數(shù)據(jù)結(jié)構(gòu)是如何在上面這7種底層數(shù)據(jù)結(jié)構(gòu)中作選擇的。

string

set msg "hello"
set number 12235

redis-string

hash

hset o1 f1 "aaa"

redis-hash

list

lpush languages python

redis-list

set

sadd names "Lily"

redis-set

zset

zadd page_rank 10 google.com

redis-zset

在使用ziplist作為底層數(shù)據(jù)結(jié)構(gòu)時(shí)，score是以字符串的形式編碼在里面，具體為什么要這么做，我也比較困惑，ziplist本身是支持存數(shù)字的。

這個(gè)skiplist + dict的結(jié)構(gòu)其實(shí)是zset結(jié)構(gòu)體：

typedef struct zset {

    // 字典，鍵為成員，值為分值
    // 用于支持 O(1) 復(fù)雜度的按成員取分值操作
    dict *dict;

    // 跳躍表，按分值排序成員
    // 用于支持平均復(fù)雜度為 O(log N) 的按分值定位成員操作
    // 以及范圍操作
    zskiplist *zsl;

} zset;

其中dict主要用于支持像zscore這樣的按成員取分值的操作，而zsl跳躍表主要用于支持像zrange這樣的按照分?jǐn)?shù)取成員的操作。

End

作者：元青

微信公眾號(hào) 「技樂書香」