Redis對(duì)象類型簡(jiǎn)介

Redis是一種key/value型數(shù)據(jù)庫(kù)，其中，每個(gè)key和value都是使用對(duì)象表示的。比如，我們執(zhí)行以下代碼：

[plain]

redis>SET?message?“hello?redis” ?

redis>SET message "hello redis"
其中的key是message，是一個(gè)包含了字符串”message”的對(duì)象。而value是一個(gè)包含了”hello redis”的對(duì)象。

Redis共有五種對(duì)象的類型，分別是：

類型常量 對(duì)象的名稱
REDIS_STRING?字符串對(duì)象?
REDIS_LIST?列表對(duì)象?
REDIS_HASH?哈希對(duì)象?
REDIS_SET?集合對(duì)象?
REDIS_ZSET?有序集合對(duì)象?

Redis中的一個(gè)對(duì)象的結(jié)構(gòu)體表示如下：

[cpp]

/*?

*?Redis?對(duì)象?

*/??

typedef?struct?redisObject?{ ?

//?類型??

unsigned?type:4; ? ? ? ? ?

//?不使用(對(duì)齊位)??

unsigned?notused:2; ?

//?編碼方式??

unsigned?encoding:4; ?

//?LRU?時(shí)間（相對(duì)于?server.lruclock）??

unsigned?lru:22; ?

//?引用計(jì)數(shù)??

int?refcount; ?

//?指向?qū)ο蟮闹??

void?*ptr; ?

}?robj; ?

/* * Redis 對(duì)象 */ typedef struct redisObject { // 類型 unsigned type:4; // 不使用(對(duì)齊位) unsigned notused:2; // 編碼方式 unsigned encoding:4; // LRU 時(shí)間（相對(duì)于 server.lruclock） unsigned lru:22; // 引用計(jì)數(shù) int refcount; // 指向?qū)ο蟮闹?void *ptr; } robj;

type表示了該對(duì)象的對(duì)象類型，即上面五個(gè)中的一個(gè)。但為了提高存儲(chǔ)效率與程序執(zhí)行效率，每種對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)都可能不止一種。encoding就表示了對(duì)象底層所使用的編碼。下面先介紹每種底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，再介紹每種對(duì)象類型都用了什么底層結(jié)構(gòu)并分析他們之間的關(guān)系。

Redis對(duì)象底層數(shù)據(jù)結(jié)構(gòu)

底層數(shù)據(jù)結(jié)構(gòu)共有八種，如下表所示：

編碼常量 編碼所對(duì)應(yīng)的底層數(shù)據(jù)結(jié)構(gòu)
REDIS_ENCODING_INT?long類型的整數(shù)?
REDIS_ENCODING_EMBSTR?embstr編碼的簡(jiǎn)單動(dòng)態(tài)字符串?
REDIS_ENCODING_RAW?簡(jiǎn)單動(dòng)態(tài)字符串?
REDIS_ENCODING_HT?字典?
REDIS_ENCODING_LINKEDLIST?雙端鏈表?
REDIS_ENCODING_ZIPLIST?壓縮列表?
REDIS_ENCODING_INTSET?整數(shù)集合?
REDIS_ENCODING_SKIPLIST?跳躍表和字典?
字符串對(duì)象

字符串對(duì)象的編碼可以是int、raw或者embstr。

如果一個(gè)字符串的內(nèi)容可以轉(zhuǎn)換為long，那么該字符串就會(huì)被轉(zhuǎn)換成為long類型，對(duì)象的ptr就會(huì)指向該long，并且對(duì)象類型也用int類型表示。

普通的字符串有兩種，embstr和raw。embstr應(yīng)該是Redis 3.0新增的數(shù)據(jù)結(jié)構(gòu),在2.8中是沒(méi)有的。如果字符串對(duì)象的長(zhǎng)度小于39字節(jié)，就用embstr對(duì)象。否則用傳統(tǒng)的raw對(duì)象?？梢詮南旅孢@段代碼看出：

[cpp]

#define?REDIS_ENCODING_EMBSTR_SIZE_LIMIT?39??

robj?*createStringObject(char?*ptr,?size_t?len)?{??

if?(len?<=?REDIS_ENCODING_EMBSTR_SIZE_LIMIT)??

return?createEmbeddedStringObject(ptr,len);??

else??

return?createRawStringObject(ptr,len);??

} ?

#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39 robj *createStringObject(char *ptr, size_t len) { if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT) return createEmbeddedStringObject(ptr,len); else return createRawStringObject(ptr,len); }embstr的好處有如下幾點(diǎn)：

embstr的創(chuàng)建只需分配一次內(nèi)存，而raw為兩次（一次為sds分配對(duì)象，另一次為objet分配對(duì)象，embstr省去了第一次）。

相對(duì)地，釋放內(nèi)存的次數(shù)也由兩次變?yōu)橐淮巍?/p>

embstr的objet和sds放在一起，更好地利用緩存帶來(lái)的優(yōu)勢(shì)。

需要注意的是，redis并未提供任何修改embstr的方式，即embstr是只讀的形式。對(duì)embstr的修改實(shí)際上是先轉(zhuǎn)換為raw再進(jìn)行修改。
?

raw和embstr的區(qū)別可以用下面兩幅圖所示：

列表對(duì)象

列表對(duì)象的編碼可以是ziplist或者linkedlist。

ziplist是一種壓縮鏈表，它的好處是更能節(jié)省內(nèi)存空間，因?yàn)樗鎯?chǔ)的內(nèi)容都是在連續(xù)的內(nèi)存區(qū)域當(dāng)中的。當(dāng)列表對(duì)象元素不大，每個(gè)元素也不大的時(shí)候，就采用ziplist存儲(chǔ)。但當(dāng)數(shù)據(jù)量過(guò)大時(shí)就ziplist就不是那么好用了。因?yàn)闉榱吮ＷC他存儲(chǔ)內(nèi)容在內(nèi)存中的連續(xù)性，插入的復(fù)雜度是O(N)，即每次插入都會(huì)重新進(jìn)行realloc。如下圖所示，對(duì)象結(jié)構(gòu)中ptr所指向的就是一個(gè)ziplist。整個(gè)ziplist只需要malloc一次，它們?cè)趦?nèi)存中是一塊連續(xù)的區(qū)域。

linkedlist是一種雙向鏈表。它的結(jié)構(gòu)比較簡(jiǎn)單，節(jié)點(diǎn)中存放pre和next兩個(gè)指針，還有節(jié)點(diǎn)相關(guān)的信息。當(dāng)每增加一個(gè)node的時(shí)候，就需要重新malloc一塊內(nèi)存。

哈希對(duì)象

哈希對(duì)象的底層實(shí)現(xiàn)可以是ziplist或者h(yuǎn)ashtable。

ziplist中的哈希對(duì)象是按照key1,value1,key2,value2這樣的順序存放來(lái)存儲(chǔ)的。當(dāng)對(duì)象數(shù)目不多且內(nèi)容不大時(shí)，這種方式效率是很高的。

hashtable的是由dict這個(gè)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的

[cpp]

typedef?struct?dict?{??

dictType?*type;??

void?*privdata;??

dictht?ht[2];??

long?rehashidx;?/*?rehashing?not?in?progress?if?rehashidx?==?-1?*/??

int?iterators;?/*?number?of?iterators?currently?running?*/??

}?dict; ?

typedef struct dict { ??? dictType *type; ??? void *privdata; ??? dictht ht[2]; ??? long rehashidx; /* rehashing not in progress if rehashidx == -1 */ ??? int iterators; /* number of iterators currently running */ } dict;dict是一個(gè)字典，其中的指針dicht ht[2] 指向了兩個(gè)哈希表

[cpp]

typedef?struct?dictht?{??

dictEntry?**table;??

unsigned?long?size;??

unsigned?long?sizemask;??

unsigned?long?used;??

}?dictht;??

?

typedef struct dictht { dictEntry **table; unsigned long size; unsigned long sizemask; unsigned long used; } dictht;dicht[0] 是用于真正存放數(shù)據(jù)，dicht[1]一般在哈希表元素過(guò)多進(jìn)行rehash的時(shí)候用于中轉(zhuǎn)數(shù)據(jù)。

dictht中的table用語(yǔ)真正存放元素了，每個(gè)key/value對(duì)用一個(gè)dictEntry表示，放在dictEntry數(shù)組中。

?

集合對(duì)象

集合對(duì)象的編碼可以是intset或者h(yuǎn)ashtable。

intset是一個(gè)整數(shù)集合，里面存的為某種同一類型的整數(shù)，支持如下三種長(zhǎng)度的整數(shù)：

[cpp]

#define?INTSET_ENC_INT16?(sizeof(int16_t))??

#define?INTSET_ENC_INT32?(sizeof(int32_t))??

#define?INTSET_ENC_INT64?(sizeof(int64_t)) ?

#define INTSET_ENC_INT16 (sizeof(int16_t))
有序集合對(duì)象

有序集合的編碼可能兩種，一種是ziplist，另一種是skiplist與dict的結(jié)合。

ziplist作為集合和作為哈希對(duì)象是一樣的，member和score順序存放。按照score從小到大順序排列。它的結(jié)構(gòu)不再?gòu)?fù)述。

skiplist是一種跳躍表，它實(shí)現(xiàn)了有序集合中的快速查找，在大多數(shù)情況下它的速度都可以和平衡樹(shù)差不多。但它的實(shí)現(xiàn)比較簡(jiǎn)單，可以作為平衡樹(shù)的替代品。它的結(jié)構(gòu)比較特殊。下面分別是跳躍表skiplist和它內(nèi)部的節(jié)點(diǎn)skiplistNode的結(jié)構(gòu)體：

[cpp]

/*?

*?跳躍表?

*/??

typedef?struct?zskiplist?{??

//?頭節(jié)點(diǎn)，尾節(jié)點(diǎn)??

struct?zskiplistNode?*header,?*tail;??

//?節(jié)點(diǎn)數(shù)量??

unsigned?long?length;??

//?目前表內(nèi)節(jié)點(diǎn)的最大層數(shù)??

int?level;??

}?zskiplist;??

/*?ZSETs?use?a?specialized?version?of?Skiplists?*/??

/*?

*?跳躍表節(jié)點(diǎn)?

*/??

typedef?struct?zskiplistNode?{??

//?member?對(duì)象??

robj?*obj;??

//?分值??

double?score;??

//?后退指針??

struct?zskiplistNode?*backward;??

//?層??

struct?zskiplistLevel?{??

//?前進(jìn)指針??

struct?zskiplistNode?*forward;??

//?這個(gè)層跨越的節(jié)點(diǎn)數(shù)量??

unsigned?int?span;??

}?level[];??

}?zskiplistNode; ?

/* * 跳躍表 */ typedef struct zskiplist { // 頭節(jié)點(diǎn)，尾節(jié)點(diǎn) struct zskiplistNode *header, *tail; // 節(jié)點(diǎn)數(shù)量 unsigned long length; // 目前表內(nèi)節(jié)點(diǎn)的最大層數(shù) int level; } zskiplist; /* ZSETs use a specialized version of Skiplists */ /* * 跳躍表節(jié)點(diǎn) */ typedef struct zskiplistNode { // member 對(duì)象 robj *obj; // 分值 double score; // 后退指針 struct zskiplistNode *backward; // 層 struct zskiplistLevel { // 前進(jìn)指針 struct zskiplistNode *forward; // 這個(gè)層跨越的節(jié)點(diǎn)數(shù)量 unsigned int span; } level[]; } zskiplistNode;head和tail分別指向頭節(jié)點(diǎn)和尾節(jié)點(diǎn)，然后每個(gè)skiplistNode里面的結(jié)構(gòu)又是分層的(即level數(shù)組)

用圖表示，大概是下面這個(gè)樣子：

每一列都代表一個(gè)節(jié)點(diǎn)，保存了member和score，按score從小到大排序。每個(gè)節(jié)點(diǎn)有不同的層數(shù)，這個(gè)層數(shù)是在生成節(jié)點(diǎn)的時(shí)候隨機(jī)生成的數(shù)值。每一層都是一個(gè)指向后面某個(gè)節(jié)點(diǎn)的指針。這種結(jié)構(gòu)使得跳躍表可以跨越很多節(jié)點(diǎn)來(lái)快速訪問(wèn)。

前面說(shuō)到了，有序集合ZSET是有跳躍表和hashtable共同形成的。

[cpp]

typedef?struct?zset?{??

//?字典??

dict?*dict;??

//?跳躍表??

zskiplist?*zsl;??

}?zset; ?

typedef struct zset { // 字典 dict *dict; // 跳躍表 zskiplist *zsl; } zset;為什么要用這種結(jié)構(gòu)呢。試想如果單一用hashtable，那可以快速查找、添加和刪除元素，但沒(méi)法保持集合的有序性。如果單一用skiplist，有序性可以得到保障，但查找的速度太慢O（logN）。結(jié)尾

簡(jiǎn)單介紹了Redis的五種對(duì)象類型和它們的底層實(shí)現(xiàn)。事實(shí)上，Redis的高效性和靈活性正是得益于對(duì)于同一個(gè)對(duì)象類型采取不同的底層結(jié)構(gòu)，并在必要的時(shí)候?qū)Χ哌M(jìn)行轉(zhuǎn)換；以及各種底層結(jié)構(gòu)對(duì)內(nèi)存的合理利用。