面試官問我Redis的數據類型，我回答了8種
面試官：小明呀，redis 有幾種數據結構呀？
小明：8 種
面試官：那你說一下分別是什么？
小明：raw,int,ht,zipmap,linkedlist,ziplist,intset,skiplist,embstr
面試官：額，你在說什么？
小明：在回答你的問題呀，這個問題我可是有過研究的，不會錯的
面試官：好吧，今天的面試先到這里，你回去等通知吧
小明：...
上面發(fā)生的對話，到底是面試官有問題，還是小明有問題呢？其實是都有問題的，面試官的提問不準確，小明的回答也不準確。
但可以看出，面試官的水平一般，因為聽到這些名詞并不知道小明說的是 redis 底層的編碼類型，進而錯失了深入挖掘小明技術潛力的機會。而小明也有些自作聰明，忽略了面試官想考察的知識點，把自己最近看的一些皮毛拿出來秀了秀，結果導致了一場誤會。
就著上面這個引子，我們本篇文章就來聊聊，redis 中的數據結構那些事。
redis 源碼選取的版本：3.0.0
本篇文章的目標：知道 redis 的編碼類型這個概念，并按照源碼級的深度去理解為什么要設置不同的編碼類型，但不會過多展開各種底層數據結構的細節(jié)
redis 的對象類型與編碼類型
redis 的對象類型，就是面試中常考的 redis 數據類型有哪些 這個問題所問的準確說法，這個對于我們這些只會面試不會開發(fā)的程序員來說，簡直再熟悉不過啦，就是字符串、哈希、列表、集合、有序集合，這個在 redis 源碼中能找到準確的定義：
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 數據結構的理解可能就止步于此了，但其實這只是 redis 對外暴露的抽象結構，其底層實現要看其編碼類型來決定使用該編碼類型對應的數據結構。
如果一個對象類型只有一種底層數據結構的實現方式，那么這個編碼類型就完全多余了，早期的 redis 的確沒有這個概念。但后來為了優(yōu)化性能，一種對象類型可能對應多種不同的編碼實現，于是乎關于 redis 底層數據結構的知識點，就開始復雜起來了。編碼類型在 redis 源碼中也有準確定義：
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 */
其實我們不用尋找任何額外的二手資料來解釋編碼類型的作用，直接看源碼中的英文注釋即可。
對象編碼（編碼類型）：有些對象類型如字符串、哈希，其內部實現可以有多種方式，一個 redis 對象的 encoding 字段可以設置下面幾個值來表示這個對象的底層編碼類型
同一個對象類型，可以有不同的編碼類型作為底層實現。而同一種編碼類型，也可以支持上層的多種對象類型。他們的關系如下:
redis對象類型與編碼類型
讀到這里你一定有至少三個疑問：
- 為什么一種對象類型要對應多種編碼類型，是為了解決什問題？
- redis 怎么知道什么時候該用這種編碼類型，什么時候該用那種編碼類型呢，并且編碼類型可以隨時改變么？
- 各種編碼類型的實現原理是什么？（本章不做重點，會貫穿全文介紹一些基本思想，具體的各種實現會在其他篇章專門講解）
別急，這一部分只是讓你知道，redis 面對使用者暴露的只是一個抽象的數據結構，并不代表其底層的具體實現。接下來帶你慢慢深入。
為什么一種對象類型要對應多種編碼類型
寫 redis 的大牛也是程序員，總不能他給自己增加了代碼的復雜性，又對性能提升毫無幫助吧？畢竟 redis 這種中間組件必須以性能來取勝同類產品。沒錯，就是為了 性能提升。
直觀感受編碼類型的不同
首先我們來直觀感受一下同一對象對應不同編碼類型這一場景，這里用到了 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"
我們用我們最常使用的字符串做了測試，觀察到其編碼類型隨著我設置的 value 值不同而改變，我整理了如下表格來表示上面的測試結果
| value | 編碼類型 |
|---|---|
| 100 | int |
| "100" | int |
| abc | embstr |
| aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa | raw |
| 9999999999999999999999999 | embstr |
| 99999999999999999999999999999999999999999 | raw |
當然，我是因為知道字符串的編碼類型的條件，踩專門選取了這些有代表性的值進行測試，我們可以總結出一個規(guī)律
- 不論是 100 還是 "100"，編碼類型都是 int，說明 redis 在判斷是否可以用整數這個編碼類型表示對象的時候，就只是看這個值是否能轉換成一個整數
- 比較短的字符串 abc 被編碼為 embstr，比較長的字符串 aaaaaaa..a 被編碼為 raw，說明長短字符串的編碼類型不一樣，由此可以猜測 redis 可能是對短的字符串進行了存儲上的優(yōu)化策略（當然目前只是合理猜測，還有可能是對長字符串進行了某種優(yōu)化）
- 整數 999...9 和更長的整數 9999999...9 也都被轉換成了相應的表示字符串的類型，說明可以用整數編碼類型表示的值，是有一定大小限制的
redis 對字符串編碼類型的優(yōu)化淺析
上面的實驗我們了解到，字符串對象的編碼類型確實有三種：int，raw，embstr。
int 類型分析起來沒什么意思，想想就知道肯定是能用整型存儲的，盡量用整型存儲，一定比字符串方式更節(jié)省空間嘛。下面我們分析一下，長字符串和短字符串的編碼類型做了區(qū)分，這是為什么呢？
不只是字符串類型，包括哈希、列表這些對象類型，都是用一個統(tǒng)一的結構體 redisObject 來表示的。他的結構如下：
redis.h
- typedef struct redisObject {
- unsigned type:4; // 對象類型
- unsigned encoding:4; // 編碼類型
- void *ptr; // 值的指針
- ...（省略一些不重要的字段）
- } robj;
占了 4 位的 type 表示 對象類型（5 種那個），同樣占了 4 位的 encoding 字段表示 編碼類型（8 種那個），指針字段 ptr 表示實際值的 內存地址。
如果該對象的編碼類型為整數（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 結構的變量
sds.h
- struct sdshdr {
- unsigned int len; // 字符串長度
- unsigned int free; // buf空閑數
- char buf[]; // 字符數組
- };
既然都是指向同一個結構，那是怎么優(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->typetype = type;
- o->encoding = REDIS_ENCODING_RAW;
- o->ptrptr = ptr;
- ...（一些賦值操作）
- return o;
- }
對于閱讀源碼比較多的同學，可能立刻就察覺到了他們的區(qū)別。其實很簡單，就是 raw 類型這種方式，為 redisObject 和 sdshdr 結構分別申請了內存空間，而 embstr 只申請了一次內存空間，然后將這兩個結構緊挨著放。除此之外沒有其他任何區(qū)別了。直觀圖如下：
看到這，一切就都解釋通了，非常簡單，就只是申請內存這一步的區(qū)別而已。但對于我們這些什么簡單的事情都要包裝成高端大氣話術的程序員來說，還是要想辦法裝一下，我們總結出使用 embstr 編碼相比于 raw 編碼的好處：
- embstr 只申請了一次內存，而 raw 需要申請兩次，因此節(jié)約了一次申請內存的消耗
- 釋放 embstr 只需要釋放一次內存，而 raw 需要兩次，因此節(jié)約了一次釋放內存的消耗
- embstr 的 redisObject 和 sdshdr 放在一塊連續(xù)的內存里，因此更能利用 緩存 帶來的優(yōu)勢
怎么樣，源碼級的理解，加上迷倒面試官的總結話術，夠意思吧。
不同編碼類型的條件
上個部分我們通過字符串，觀察了不同的編碼類型，也理解了為什么要有不同的編碼類型的實現。接下來我們總結下其他的對象與編碼類型，原理就不深入源碼分析了，和字符串的基本思想是一樣的。
字符串的編碼類型
- int：8 個字節(jié)的長整型
- embstr：小于等于 39 字節(jié)的字符串
- raw：大于 39 字節(jié)的字符串
哈希的編碼類型
- ziplist：元素個數小于 512，且所有值都小于 64 字節(jié)
- hashtable：除上述條件外
列表的編碼類型
- ziplist：元素個數小于 512，且所有值都小于 64 字節(jié)
- hashtable：除上述條件外
集合的編碼類型
- intset：元素個數小于 512，且所有值都是整數
- hashtable：除上述條件外
有序集合的編碼類型
- ziplist：元素個數小于 128，且所有值都小于 64 字節(jié)
- hashtable：除上述條件外
由于不展開講解，純記憶的東西我覺得用最干凈的辦法描述給大家即可，無多余部分。具體數據結構的細節(jié)，我會用其他文章來講解。
此時，經過一番修煉的小明，再次遇到了一位專業(yè)的面試官
專業(yè)的面試官：小明呀，redis 有幾種數據結...
進化的小明：面試官面試官，你這個問題分兩種情況，redis 的對象類型，也就是我們常說的對外暴露的數據類型，有 5 種，分別是.... 底層對應的編碼類型，在 3.0.0 源碼中有 8 種，分別是....
專業(yè)的面試官：誰讓你搶答了？
進化的小明：...
專業(yè)的面試官：行了，今天的面試先到這里，你回去等通知吧
進化的小明：...
