面試官：小明呀，redis 有幾種數(shù)據(jù)結(jié)構(gòu)呀？

小明：8 種

面試官：那你說(shuō)一下分別是什么？

小明：raw,int,ht,zipmap,linkedlist,ziplist,intset,skiplist,embstr

面試官：額，你在說(shuō)什么？

小明：在回答你的問(wèn)題呀，這個(gè)問(wèn)題我可是有過(guò)研究的，不會(huì)錯(cuò)的

面試官：好吧，今天的面試先到這里，你回去等通知吧

小明：...

上面發(fā)生的對(duì)話，到底是面試官有問(wèn)題，還是小明有問(wèn)題呢？其實(shí)是都有問(wèn)題的，面試官的提問(wèn)不準(zhǔn)確，小明的回答也不準(zhǔn)確。

但可以看出，面試官的水平一般，因?yàn)槁牭竭@些名詞并不知道小明說(shuō)的是 redis 底層的編碼類型，進(jìn)而錯(cuò)失了深入挖掘小明技術(shù)潛力的機(jī)會(huì)。而小明也有些自作聰明，忽略了面試官想考察的知識(shí)點(diǎn)，把自己最近看的一些皮毛拿出來(lái)秀了秀，結(jié)果導(dǎo)致了一場(chǎng)誤會(huì)。

就著上面這個(gè)引子，我們本篇文章就來(lái)聊聊，redis 中的數(shù)據(jù)結(jié)構(gòu)那些事。

redis 源碼選取的版本：3.0.0

本篇文章的目標(biāo)：知道 redis 的編碼類型這個(gè)概念，并按照源碼級(jí)的深度去理解為什么要設(shè)置不同的編碼類型，但不會(huì)過(guò)多展開各種底層數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)

redis 的對(duì)象類型與編碼類型

redis 的對(duì)象類型，就是面試中?？嫉?redis 數(shù)據(jù)類型有哪些 這個(gè)問(wèn)題所問(wèn)的準(zhǔn)確說(shuō)法，這個(gè)對(duì)于我們這些只會(huì)面試不會(huì)開發(fā)的程序員來(lái)說(shuō)，簡(jiǎn)直再熟悉不過(guò)啦，就是字符串、哈希、列表、集合、有序集合，這個(gè)在 redis 源碼中能找到準(zhǔn)確的定義：

redis.c 

/* Object types */  
#define REDIS_STRING 0  
#define REDIS_LIST 1  
#define REDIS_SET 2  
#define REDIS_ZSET 3  
#define REDIS_HASH 4 

好多人對(duì) redis 數(shù)據(jù)結(jié)構(gòu)的理解可能就止步于此了，但其實(shí)這只是 redis 對(duì)外暴露的抽象結(jié)構(gòu)，其底層實(shí)現(xiàn)要看其編碼類型來(lái)決定使用該編碼類型對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)。

如果一個(gè)對(duì)象類型只有一種底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方式，那么這個(gè)編碼類型就完全多余了，早期的 redis 的確沒有這個(gè)概念。但后來(lái)為了優(yōu)化性能，一種對(duì)象類型可能對(duì)應(yīng)多種不同的編碼實(shí)現(xiàn)，于是乎關(guān)于 redis 底層數(shù)據(jù)結(jié)構(gòu)的知識(shí)點(diǎn)，就開始復(fù)雜起來(lái)了。編碼類型在 redis 源碼中也有準(zhǔn)確定義：

redis.c 

/* Objects encoding. Some kind of objects like Strings and Hashes can be  
 * internally represented in multiple ways. The 'encoding' field of the object  
 * is set to one of this fields for this object. */  
#define REDIS_ENCODING_RAW 0     /* Raw representation */  
#define REDIS_ENCODING_INT 1     /* Encoded as integer */  
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */  
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */  
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */  
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */  
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */  
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */  
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */ 

其實(shí)我們不用尋找任何額外的二手資料來(lái)解釋編碼類型的作用，直接看源碼中的英文注釋即可。

對(duì)象編碼（編碼類型）：有些對(duì)象類型如字符串、哈希，其內(nèi)部實(shí)現(xiàn)可以有多種方式，一個(gè) redis 對(duì)象的 encoding 字段可以設(shè)置下面幾個(gè)值來(lái)表示這個(gè)對(duì)象的底層編碼類型

同一個(gè)對(duì)象類型，可以有不同的編碼類型作為底層實(shí)現(xiàn)。而同一種編碼類型，也可以支持上層的多種對(duì)象類型。他們的關(guān)系如下:

redis對(duì)象類型與編碼類型

讀到這里你一定有至少三個(gè)疑問(wèn)：

•  為什么一種對(duì)象類型要對(duì)應(yīng)多種編碼類型，是為了解決什問(wèn)題？
•  redis 怎么知道什么時(shí)候該用這種編碼類型，什么時(shí)候該用那種編碼類型呢，并且編碼類型可以隨時(shí)改變么？
•  各種編碼類型的實(shí)現(xiàn)原理是什么？（本章不做重點(diǎn)，會(huì)貫穿全文介紹一些基本思想，具體的各種實(shí)現(xiàn)會(huì)在其他篇章專門講解）

別急，這一部分只是讓你知道，redis 面對(duì)使用者暴露的只是一個(gè)抽象的數(shù)據(jù)結(jié)構(gòu)，并不代表其底層的具體實(shí)現(xiàn)。接下來(lái)帶你慢慢深入。

為什么一種對(duì)象類型要對(duì)應(yīng)多種編碼類型

寫 redis 的大牛也是程序員，總不能他給自己增加了代碼的復(fù)雜性，又對(duì)性能提升毫無(wú)幫助吧？畢竟 redis 這種中間組件必須以性能來(lái)取勝同類產(chǎn)品。沒錯(cuò)，就是為了 性能提升。

直觀感受編碼類型的不同

首先我們來(lái)直觀感受一下同一對(duì)象對(duì)應(yīng)不同編碼類型這一場(chǎng)景，這里用到了 object encoding xxx 這個(gè) redis 命令來(lái)查看某一個(gè) key 其 value 對(duì)象所使用的編碼類型 

127.0.0.1:6379> set number 100  
OK  
127.0.0.1:6379> object encoding number  
"int"  
127.0.0.1:6379> set number "100"  
OK  
127.0.0.1:6379> object encoding number  
"int"  
127.0.0.1:6379> set number abc  
OK  
127.0.0.1:6379> object encoding number  
"embstr"  
127.0.0.1:6379> set number aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa  
OK  
127.0.0.1:6379> object encoding number  
"raw"  
127.0.0.1:6379> set number 9999999999999999999999999  
OK  
127.0.0.1:6379> object encoding number  
"embstr"  
127.0.0.1:6379> set number 99999999999999999999999999999999999999999999999999999999999999  
OK  
127.0.0.1:6379> object encoding number  
"raw" 

我們用我們最常使用的字符串做了測(cè)試，觀察到其編碼類型隨著我設(shè)置的 value 值不同而改變，我整理了如下表格來(lái)表示上面的測(cè)試結(jié)果

當(dāng)然，我是因?yàn)橹雷址木幋a類型的條件，踩專門選取了這些有代表性的值進(jìn)行測(cè)試，我們可以總結(jié)出一個(gè)規(guī)律

•  不論是 100 還是 "100"，編碼類型都是 int，說(shuō)明 redis 在判斷是否可以用整數(shù)這個(gè)編碼類型表示對(duì)象的時(shí)候，就只是看這個(gè)值是否能轉(zhuǎn)換成一個(gè)整數(shù)
•  比較短的字符串 abc 被編碼為 embstr，比較長(zhǎng)的字符串 aaaaaaa..a 被編碼為 raw，說(shuō)明長(zhǎng)短字符串的編碼類型不一樣，由此可以猜測(cè) redis 可能是對(duì)短的字符串進(jìn)行了存儲(chǔ)上的優(yōu)化策略（當(dāng)然目前只是合理猜測(cè)，還有可能是對(duì)長(zhǎng)字符串進(jìn)行了某種優(yōu)化）
•  整數(shù) 999...9 和更長(zhǎng)的整數(shù) 9999999...9 也都被轉(zhuǎn)換成了相應(yīng)的表示字符串的類型，說(shuō)明可以用整數(shù)編碼類型表示的值，是有一定大小限制的

redis 對(duì)字符串編碼類型的優(yōu)化淺析

上面的實(shí)驗(yàn)我們了解到，字符串對(duì)象的編碼類型確實(shí)有三種：int，raw，embstr。

int 類型分析起來(lái)沒什么意思，想想就知道肯定是能用整型存儲(chǔ)的，盡量用整型存儲(chǔ)，一定比字符串方式更節(jié)省空間嘛。下面我們分析一下，長(zhǎng)字符串和短字符串的編碼類型做了區(qū)分，這是為什么呢？

不只是字符串類型，包括哈希、列表這些對(duì)象類型，都是用一個(gè)統(tǒng)一的結(jié)構(gòu)體 redisObject 來(lái)表示的。他的結(jié)構(gòu)如下：

redis.h 

typedef struct redisObject {  
    unsigned type:4; // 對(duì)象類型  
    unsigned encoding:4; // 編碼類型  
    void *ptr; // 值的指針  
    ...（省略一些不重要的字段）  
} robj; 

占了 4 位的 type 表示 對(duì)象類型（5 種那個(gè)），同樣占了 4 位的 encoding 字段表示 編碼類型（8 種那個(gè)），指針字段 ptr 表示實(shí)際值的 內(nèi)存地址。

如果該對(duì)象的編碼類型為整數(shù)（encoding=REDIS_ENCODING_INT），那么這個(gè) ptr 指向的將會(huì)是一個(gè) long 類型的變量。

util.c 

if (!string2ll(s,slen,&llval))  
    return 0;  
...  
*lval = (long)llval;  
return 1; 

object.c 

...  
o->ptr = (void*) value; 

如果該對(duì)象的編碼類型為 raw 或者 embstr，那么這個(gè) ptr 指向的將會(huì)是一個(gè) sdshdr 結(jié)構(gòu)的變量

sds.h 

struct sdshdr {  
    unsigned int len; // 字符串長(zhǎng)度  
    unsigned int free; // buf空閑數(shù)  
    char buf[]; // 字符數(shù)組  
}; 

既然都是指向同一個(gè)結(jié)構(gòu)，那是怎么優(yōu)化的呢？那就得進(jìn)入如下兩個(gè)方法具體看看了

object.c 

robj *createStringObject(char *ptr, size_t len) {  
    if (len <= 39)  
        return createEmbeddedStringObject(ptr,len);  
    else  
        return createRawStringObject(ptr,len);  
} 

你看，這段代碼非常清晰，字符串長(zhǎng)度 <=39 時(shí)，就創(chuàng)建 embstr 類型的字符串對(duì)象，否則創(chuàng)建 raw 類型的字符串對(duì)象。那么這兩個(gè)創(chuàng)建方式的區(qū)別，一定就隱藏在這兩個(gè)方法里，我們點(diǎn)進(jìn)去！

embstr 類型 

robj *createEmbeddedStringObject(char *ptr, size_t len) {  
    robj *o = zmalloc(sizeof(robj)+sizeof(struct sdshdr)+len+1);  
    struct sdshdr *sh = (void*)(o+1);  
    o->type = REDIS_STRING;  
    o->encoding = REDIS_ENCODING_EMBSTR;  
    o->ptr = sh+1;  
    ... （一些賦值操作）  
    return o;  
} 

raw 類型 

robj *createRawStringObject(char *ptr, size_t len) {  
    return createObject(REDIS_STRING,sdsnewlen(ptr,len));  
}  
sds sdsnewlen(const void *init, size_t initlen) { 
    ...  
    struct sdshdr *sh = zmalloc(sizeof(struct sdshdr)+initlen+1);  
    ...  
}  
robj *createObject(int type, void *ptr) {  
    robj *o = zmalloc(sizeof(*o));  
    o->typetype = type;  
    o->encoding = REDIS_ENCODING_RAW;  
    o->ptrptr = ptr; 
    ...（一些賦值操作）  
    return o;  
} 

對(duì)于閱讀源碼比較多的同學(xué)，可能立刻就察覺到了他們的區(qū)別。其實(shí)很簡(jiǎn)單，就是 raw 類型這種方式，為 redisObject 和 sdshdr 結(jié)構(gòu)分別申請(qǐng)了內(nèi)存空間，而 embstr 只申請(qǐng)了一次內(nèi)存空間，然后將這兩個(gè)結(jié)構(gòu)緊挨著放。除此之外沒有其他任何區(qū)別了。直觀圖如下：

看到這，一切就都解釋通了，非常簡(jiǎn)單，就只是申請(qǐng)內(nèi)存這一步的區(qū)別而已。但對(duì)于我們這些什么簡(jiǎn)單的事情都要包裝成高端大氣話術(shù)的程序員來(lái)說(shuō)，還是要想辦法裝一下，我們總結(jié)出使用 embstr 編碼相比于 raw 編碼的好處：

•  embstr 只申請(qǐng)了一次內(nèi)存，而 raw 需要申請(qǐng)兩次，因此節(jié)約了一次申請(qǐng)內(nèi)存的消耗
•  釋放 embstr 只需要釋放一次內(nèi)存，而 raw 需要兩次，因此節(jié)約了一次釋放內(nèi)存的消耗
•  embstr 的 redisObject 和 sdshdr 放在一塊連續(xù)的內(nèi)存里，因此更能利用 緩存 帶來(lái)的優(yōu)勢(shì)

怎么樣，源碼級(jí)的理解，加上迷倒面試官的總結(jié)話術(shù)，夠意思吧。

不同編碼類型的條件

上個(gè)部分我們通過(guò)字符串，觀察了不同的編碼類型，也理解了為什么要有不同的編碼類型的實(shí)現(xiàn)。接下來(lái)我們總結(jié)下其他的對(duì)象與編碼類型，原理就不深入源碼分析了，和字符串的基本思想是一樣的。

字符串的編碼類型

•  int：8 個(gè)字節(jié)的長(zhǎng)整型
•  embstr：小于等于 39 字節(jié)的字符串
•  raw：大于 39 字節(jié)的字符串

哈希的編碼類型

•  ziplist：元素個(gè)數(shù)小于 512，且所有值都小于 64 字節(jié)
•  hashtable：除上述條件外

列表的編碼類型

•  ziplist：元素個(gè)數(shù)小于 512，且所有值都小于 64 字節(jié)
•  hashtable：除上述條件外

集合的編碼類型

•  intset：元素個(gè)數(shù)小于 512，且所有值都是整數(shù)
•  hashtable：除上述條件外

有序集合的編碼類型

•  ziplist：元素個(gè)數(shù)小于 128，且所有值都小于 64 字節(jié)
•  hashtable：除上述條件外

由于不展開講解，純記憶的東西我覺得用最干凈的辦法描述給大家即可，無(wú)多余部分。具體數(shù)據(jù)結(jié)構(gòu)的細(xì)節(jié)，我會(huì)用其他文章來(lái)講解。

此時(shí)，經(jīng)過(guò)一番修煉的小明，再次遇到了一位專業(yè)的面試官

專業(yè)的面試官：小明呀，redis 有幾種數(shù)據(jù)結(jié)...

進(jìn)化的小明：面試官面試官，你這個(gè)問(wèn)題分兩種情況，redis 的對(duì)象類型，也就是我們常說(shuō)的對(duì)外暴露的數(shù)據(jù)類型，有 5 種，分別是.... 底層對(duì)應(yīng)的編碼類型，在 3.0.0 源碼中有 8 種，分別是....

專業(yè)的面試官：誰(shuí)讓你搶答了？

進(jìn)化的小明：...

專業(yè)的面試官：行了，今天的面試先到這里，你回去等通知吧

進(jìn)化的小明：...