我說redis有8種數(shù)據(jù)類型，面試官讓我回去等消息

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

小明：8 種

面試官：那你說一下分別是什么？

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

面試官：額，你在說什么？

小明：在回答你的問題呀，這個問題我可是有過研究的，不會錯的

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

小明：...

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

但可以看出，面試官的水平一般，因為聽到這些名詞并不知道小明說的是 redis 底層的編碼類型，進而錯失了深入挖掘小明技術(shù)潛力的機會。而小明也有些自作聰明，忽略了面試官想考察的知識點，把自己最近看的一些皮毛拿出來秀了秀，結(jié)果導(dǎo)致了一場誤會。

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

redis 源碼選取的版本：3.0.0

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

redis 的對象類型與編碼類型

redis 的對象類型，就是面試中常考的 redis 數(shù)據(jù)類型有哪些 這個問題所問的準(zhǔn)確說法，這個對于我們這些只會面試不會開發(fā)的程序員來說，簡直再熟悉不過啦，就是字符串、哈希、列表、集合、有序集合，這個在 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

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

如果一個對象類型只有一種底層數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方式，那么這個編碼類型就完全多余了，早期的 redis 的確沒有這個概念。但后來為了優(yōu)化性能，一種對象類型可能對應(yīng)多種不同的編碼實現(xiàn)，于是乎關(guān)于 redis 底層數(shù)據(jù)結(jié)構(gòu)的知識點，就開始復(fù)雜起來了。編碼類型在 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?*/

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

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

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

讀到這里你一定有至少三個疑問：

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

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

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

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

直觀感受編碼類型的不同

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

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"

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

當(dāng)然，我是因為知道字符串的編碼類型的條件，踩專門選取了這些有代表性的值進行測試，我們可以總結(jié)出一個規(guī)律

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

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

上面的實驗我們了解到，字符串對象的編碼類型確實有三種：int，raw，embstr。

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

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

redis.h

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

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

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

util.c

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

object.c

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

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

sds.h

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

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

object.c

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

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

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->type?=?type;
????o->encoding?=?REDIS_ENCODING_RAW;
????o->ptr?=?ptr;
????...（一些賦值操作）
????return?o;
}

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

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

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

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

不同編碼類型的條件

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

字符串的編碼類型

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

哈希的編碼類型

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

列表的編碼類型

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

集合的編碼類型

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

有序集合的編碼類型

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

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

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

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

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

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

進化的小明：...

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

進化的小明：...

點個在看支持我吧，轉(zhuǎn)發(fā)就更好了