90%的人知道Redis 5種最基本的數(shù)據(jù)結(jié)構(gòu)，只有不到10%的人知道8種基本數(shù)據(jù)結(jié)構(gòu)(5種基本+bitmap+GeoHash+HyperLogLog)，只有不到5%的人知道9種基本數(shù)據(jù)結(jié)構(gòu)(5.0最新版本數(shù)據(jù)結(jié)構(gòu)Streams)，只有不到1%的人掌握了所有9種基本數(shù)據(jù)結(jié)構(gòu)以及8種內(nèi)部編碼，掌握這篇文章的知識點，讓你成為面試官眼中Redis方面最靚的仔!

說明：本文基于Redis-3.2.11版本源碼進行分析。

5種普通數(shù)據(jù)結(jié)構(gòu)

這個沒什么好說的，對Redis稍微有點了解的都知道5種最基本的數(shù)據(jù)結(jié)構(gòu)：String，List，Hash，Set，Sorted Set。不過，需要注意的是，這里依然有幾個高頻面試題。

Set和Hash的關(guān)系

答案就是Set是一個特殊的value為空的Hash。Set類型操作的源碼在t_set.c中。以新增一個元素為例(int setTypeAdd(robj *subject, sds value))，如果編碼類型是OBJ_ENCODING_HT，那么新增源碼的源碼如下，事實上就是對dict即Hash數(shù)據(jù)結(jié)構(gòu)進行操作，并且dictSetVal時value是NULL：

dictEntry *de = dictAddRaw(ht,value,NULL); 
if (de) { 
    dictSetKey(ht,de,sdsdup(value)); 
    dictSetVal(ht,de,NULL); 
    return 1; 
} 

同樣的，我們在t_hash.c中看到Hash類型新增元素時，當(dāng)判斷編碼類型是OBJ_ENCODING_HT時，也是調(diào)用dict的方法：dictAdd(o->ptr,f,v)，dictAdd最終也是調(diào)用dictSetVal()方法，只不過v即value不為NULL：

/* Add an element to the target hash table */ 
int dictAdd(dict *d, void *key, void *val) 
{ 
    dictEntry *entry = dictAddRaw(d,key,NULL); 
 
    if (!entry) return DICT_ERR; 
    dictSetVal(d, entry, val); 
    return DICT_OK; 
} 

所以，Redis中Set和Hash的關(guān)系就很清楚了，當(dāng)編碼是OBJ_ENCODING_HT時，兩者都是dict數(shù)據(jù)類型，只不過Set是value為NULL的特殊的dict。

談?wù)勀銓orted Set的理解

Sorted Set的數(shù)據(jù)結(jié)構(gòu)是一種跳表，即SkipList，如下圖所示，紅線是查找10的過程：

SkipList

如何借助Sorted set實現(xiàn)多維排序

Sorted Set默認情況下只能根據(jù)一個因子score進行排序。如此一來，局限性就很大，舉個栗子：熱門排行榜需要按照下載量&最近更新時間排序，即類似數(shù)據(jù)庫中的ORDER BY download_count, update_time DESC。那這樣的需求如果用Redis的Sorted Set實現(xiàn)呢?

事實上很簡單，思路就是將涉及排序的多個維度的列通過一定的方式轉(zhuǎn)換成一個特殊的列，即result = function(x, y, z)，即x，y，z是三個排序因子，例如下載量、時間等，通過自定義函數(shù)function()計算得到result，將result作為Sorted Set中的score的值，就能實現(xiàn)任意維度的排序需求了。

Redis內(nèi)部編碼

我們常說的String，List，Hash，Set，Sorted Set只是對外的編碼，實際上每種數(shù)據(jù)結(jié)構(gòu)都有自己底層的內(nèi)部編碼實現(xiàn)，而且是多種實現(xiàn)，這樣Redis可以在合適的場景選擇更合適的內(nèi)部編碼。

如下圖所示(圖片糾正：intset編碼，而不是inset編碼)，可以看到每種數(shù)據(jù)結(jié)構(gòu)都有2種以上的內(nèi)部編碼實現(xiàn)，例如String數(shù)據(jù)結(jié)構(gòu)就包含了raw、int和embstr三種內(nèi)部編碼。同時，有些內(nèi)部編碼可以作為多種外部數(shù)據(jù)結(jié)構(gòu)的內(nèi)部實現(xiàn)，例如ziplist就是hash、list和zset共有的內(nèi)部編碼，而set的內(nèi)部編碼可能是hashtable或者intset：

Redis內(nèi)部編碼

Redis這樣設(shè)計有兩個好處：

可以偷偷的改進內(nèi)部編碼，而對外的數(shù)據(jù)結(jié)構(gòu)和命令沒有影響，這樣一旦開發(fā)出更優(yōu)秀的內(nèi)部編碼，無需改動對外數(shù)據(jù)結(jié)構(gòu)和命令。

多種內(nèi)部編碼實現(xiàn)可以在不同場景下發(fā)揮各自的優(yōu)勢。例如ziplist比較節(jié)省內(nèi)存，但是在列表元素比較多的情況下，性能會有所下降。這時候Redis會根據(jù)配置選項將列表類型的內(nèi)部實現(xiàn)轉(zhuǎn)換為linkedlist。

String的3種內(nèi)部編碼

由上圖可知，String的3種內(nèi)部編碼分別是：int、embstr、raw。int類型很好理解，當(dāng)一個key的value是整型時，Redis就將其編碼為int類型(另外還有一個條件：把這個value當(dāng)作字符串來看，它的長度不能超過20)。如下所示。這種編碼類型為了節(jié)省內(nèi)存。Redis默認會緩存10000個整型值(#define OBJ_SHARED_INTEGERS 10000)，這就意味著，如果有10個不同的KEY，其value都是10000以內(nèi)的值，事實上全部都是共享同一個對象：

127.0.0.1:6379> set number "7890" 
OK 
127.0.0.1:6379> object encoding number 
"int" 

接下來就是ebmstr和raw兩種內(nèi)部編碼的長度界限，請看下面的源碼：

#define OBJ_ENCODING_EMBSTR_SIZE_LIMIT 44 
robj *createStringObject(const char *ptr, size_t len) { 
    if (len <= OBJ_ENCODING_EMBSTR_SIZE_LIMIT) 
        return createEmbeddedStringObject(ptr,len); 
    else 
        return createRawStringObject(ptr,len); 
} 

也就是說，embstr和raw編碼的長度界限是44，我們可以做如下驗證。長度超過44以后，就是raw編碼類型，不會有任何優(yōu)化，是多長，就要消耗多少內(nèi)存：

127.0.0.1:6379> set name "a1234567890123456789012345678901234567890123" 
OK 
127.0.0.1:6379> object encoding name 
"embstr" 
127.0.0.1:6379> set name "a12345678901234567890123456789012345678901234" 
OK 
127.0.0.1:6379> object encoding name 
"raw" 

那么為什么有embstr編碼呢?它相比raw的優(yōu)勢在哪里?embstr編碼將創(chuàng)建字符串對象所需的空間分配的次數(shù)從raw編碼的兩次降低為一次。因為embstr編碼的字符串對象的所有數(shù)據(jù)都保存在一塊連續(xù)的內(nèi)存里面，所以這種編碼的字符串對象比起raw編碼的字符串對象能更好地利用緩存帶來的優(yōu)勢。并且釋放embstr編碼的字符串對象只需要調(diào)用一次內(nèi)存釋放函數(shù)，而釋放raw編碼對象的字符串對象需要調(diào)用兩次內(nèi)存釋放函數(shù)。如下圖所示，左邊是embstr編碼，右邊是raw編碼：

embstr V.S. raw

ziplist

由前面的圖可知，List，Hash，Sorted Set三種對外結(jié)構(gòu)，在特殊情況下的內(nèi)部編碼都是ziplist，那么這個ziplist有什么神奇之處呢?

以Hash為例，我們首先看一下什么條件下它的內(nèi)部編碼是ziplist：

當(dāng)哈希類型元素個數(shù)小于hash-max-ziplist-entries配置(默認512個);

所有值都小于hash-max-ziplist-value配置(默認64個字節(jié));

如果是sorted set的話，同樣需要滿足兩個條件：

元素個數(shù)小于zset-max-ziplist-entries配置，默認128;

所有值都小于zset-max-ziplist-value配置，默認64。

實際上，ziplist充分體現(xiàn)了Redis對于存儲效率的追求。一個普通的雙向鏈表，鏈表中每一項都占用獨立的一塊內(nèi)存，各項之間用地址指針(或引用)連接起來。這種方式會帶來大量的內(nèi)存碎片，而且地址指針也會占用額外的內(nèi)存。而ziplist卻是將表中每一項存放在前后連續(xù)的地址空間內(nèi)，一個ziplist整體占用一大塊內(nèi)存。它是一個表(list)，但其實不是一個鏈表(linked list)。

ziplist的源碼在ziplist.c這個文件中，其中有一段這樣的描述 -- The general layout of the ziplist is as follows:：

<zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend> 

zlbytes：表示這個ziplist占用了多少空間，或者說占了多少字節(jié)，這其中包括了zlbytes本身占用的4個字節(jié);

zltail：表示到ziplist中最后一個元素的偏移量，有了這個值，pop操作的時間復(fù)雜度就是O(1)了，即不需要遍歷整個ziplist;

zllen：表示ziplist中有多少個entry，即保存了多少個元素。由于這個字段占用16個字節(jié)，所以最大值是2^16-1，也就意味著，如果entry的數(shù)量超過2^16-1時，需要遍歷整個ziplist才知道entry的數(shù)量;

entry：真正保存的數(shù)據(jù)，有它自己的編碼;

zlend：專門用來表示ziplist尾部的特殊字符，占用8個字節(jié)，值固定為255，即8個字節(jié)每一位都是1。

如下就是一個真實的ziplist編碼，包含了2和5兩個元素：

[0f 00 00 00] [0c 00 00 00] [02 00] [00 f3] [02 f6] [ff] 
       |             |          |       |       |     | 
    zlbytes        zltail    entries   "2"     "5"   end 

linkedlist

這是List的一種編碼數(shù)據(jù)結(jié)構(gòu)非常簡單，就是我們非常熟悉的雙向鏈表，對應(yīng)Java中的LinkedList。

skiplist

這個前面也已經(jīng)提及，就是經(jīng)典的跳表數(shù)據(jù)結(jié)構(gòu)。

hashtable

這個也很容易，對應(yīng)Java中的HashMap。

intset

Set特殊內(nèi)部編碼，當(dāng)滿足下面的條件時Set的內(nèi)部編碼就是intset而不是hashtable：

Set集合中必須是64位有符號的十進制整型;

元素個數(shù)不能超過set-max-intset-entries配置，默認512;

驗證如下：

127.0.0.1:6379> sadd scores 135 
(integer) 0 
127.0.0.1:6379> sadd scores 128 
(integer) 1 
127.0.0.1:6379> object encoding scores 
"intset" 

那么intset編碼到底是個什么東西呢?看它的源碼定義如下，很明顯，就是整型數(shù)組，并且是一個有序的整型數(shù)組。它在內(nèi)存分配上與ziplist有些類似，是連續(xù)的一整塊內(nèi)存空間，而且對于大整數(shù)和小整數(shù)采取了不同的編碼，盡量對內(nèi)存的使用進行了優(yōu)化。這樣的數(shù)據(jù)結(jié)構(gòu)，如果執(zhí)行SISMEMBER命令，即查看某個元素是否在集合中時，事實上使用的是二分查找法：

typedef struct intset { 
    uint32_t encoding; 
    uint32_t length; 
    int8_t contents[]; 
} intset; 
 
// intset編碼查找方法源碼（人為簡化），標(biāo)準(zhǔn)的二分查找法： 
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { 
    int min = 0, max = intrev32ifbe(is->length)-1, mid = -1; 
    int64_t cur = -1; 
 
    while(max >= min) { 
        mid = ((unsigned int)min + (unsigned int)max) >> 1; 
        cur = _intsetGet(is,mid); 
        if (value > cur) { 
            min = mid+1; 
        } else if (value < cur) { 
            max = mid-1; 
        } else { 
            break; 
        } 
    } 
 
    if (value == cur) { 
        if (pos) *pos = mid; 
        return 1; 
    } else { 
        if (pos) *pos = min; 
        return 0; 
    } 
} 
 
#define INTSET_ENC_INT16 (sizeof(int16_t)) 
#define INTSET_ENC_INT32 (sizeof(int32_t)) 
#define INTSET_ENC_INT64 (sizeof(int64_t)) 

3種高級數(shù)據(jù)結(jié)構(gòu)

Redis中3種高級數(shù)據(jù)結(jié)構(gòu)分別是bitmap、GEO、HyperLogLog，針對這3種數(shù)據(jù)結(jié)構(gòu)，筆者之前也有文章介紹過。其中，最重要的就是bitmap。

bitmap

這個就是Redis實現(xiàn)的BloomFilter，BloomFilter非常簡單，如下圖所示，假設(shè)已經(jīng)有3個元素a、b和c，分別通過3個hash算法h1()、h2()和h2()計算然后對一個bit進行賦值，接下來假設(shè)需要判斷d是否已經(jīng)存在，那么也需要使用3個hash算法h1()、h2()和h2()對d進行計算，然后得到3個bit的值，恰好這3個bit的值為1，這就能夠說明：d可能存在集合中。再判斷e，由于h1(e)算出來的bit之前的值是0，那么說明：e一定不存在集合中：

BloomFilter

需要說明的是，bitmap并不是一種真實的數(shù)據(jù)結(jié)構(gòu)，它本質(zhì)上是String數(shù)據(jù)結(jié)構(gòu)，只不過操作的粒度變成了位，即bit。因為String類型最大長度為512MB，所以bitmap最多可以存儲2^32個bit。

GEO

GEO數(shù)據(jù)結(jié)構(gòu)可以在Redis中存儲地理坐標(biāo)，并且坐標(biāo)有限制，由EPSG:900913 / EPSG:3785 / OSGEO:41001 規(guī)定如下：

有效的經(jīng)度從-180度到180度。

有效的緯度從-85.05112878度到85.05112878度。

當(dāng)坐標(biāo)位置超出上述指定范圍時，該命令將會返回一個錯誤。添加地理位置命令如下：

redis> GEOADD city 114.031040 22.324386 "shenzhen" 112.572154 22.267832 "guangzhou" 
(integer) 2 
redis> GEODIST city shenzhen guangzhou 
"150265.8106" 

但是，需要說明的是，Geo本身不是一種數(shù)據(jù)結(jié)構(gòu)，它本質(zhì)上還是借助于Sorted Set(ZSET)，并且使用GeoHash技術(shù)進行填充。Redis中將經(jīng)緯度使用52位的整數(shù)進行編碼，放進zset中，score就是GeoHash的52位整數(shù)值。在使用Redis進行Geo查詢時，其內(nèi)部對應(yīng)的操作其實就是zset(skiplist)的操作。通過zset的score進行排序就可以得到坐標(biāo)附近的其它元素，通過將score還原成坐標(biāo)值就可以得到元素的原始坐標(biāo)。

總之，Redis中處理這些地理位置坐標(biāo)點的思想是：二維平面坐標(biāo)點 --> 一維整數(shù)編碼值 --> zset(score為編碼值) --> zrangebyrank(獲取score相近的元素)、zrangebyscore --> 通過score(整數(shù)編碼值)反解坐標(biāo)點 --> 附近點的地理位置坐標(biāo)。

GEOHASH原理

使用wiki上的例子，緯度為42.6，經(jīng)度為-5.6的點，轉(zhuǎn)化為base32的話要如何轉(zhuǎn)呢?

首先拿緯度來進行說明，緯度的范圍為-90到90，將這個范圍劃為兩段，則為[-90,0]、[0,90]，然后看給定的緯度在哪個范圍，在前面的范圍的話，就設(shè)當(dāng)前位為0，后面的話值便為1.然后繼續(xù)將確定的范圍1分為2，繼續(xù)以確定值在前段還是后段來確定bit的值。就這樣慢慢的縮小范圍，一般最多縮小13次就可以了(經(jīng)緯度的二進制位相加最多25位，經(jīng)度13位，緯度12位)。這時的中間值，將跟給定的值最相近。如下圖所示：

Geohash

第1行，緯度42.6位于[0, 90]之間，所以bit=1;第2行，緯度42.6位于[0, 45]之間，所以bit=0;第3行，緯度42.6位于[22.5, 45]之間，所以bit=1，以此類推。這樣，取出圖中的bit位：1011 1100 1001，同樣的方法，將經(jīng)度(范圍-180到180)算出來為 ：0111 1100 0000 0。結(jié)果對其如下：

# 經(jīng)度 
0111 1100 0000 0 
# 緯度 
1011 1100 1001 

得到了經(jīng)緯度的二進制位后，下面需要將兩者進行結(jié)合：從經(jīng)度、緯度的循環(huán)，每次取其二進制的一位(不足位取0)，合并為新的二進制數(shù)：01101111 11110000 01000001 0。每5位為一個十進制數(shù)，結(jié)合base32對應(yīng)表映射為base32值為：ezs42。這樣就完成了encode的過程。

Streams

這是Redis5.0引入的全新數(shù)據(jù)結(jié)構(gòu)，用一句話概括Streams就是Redis實現(xiàn)的內(nèi)存版kafka。而且，Streams也有Consumer Groups的概念。通過Redis源碼中對stream的定義我們可知，streams底層的數(shù)據(jù)結(jié)構(gòu)是radix tree：

typedef struct stream { 
    rax *rax;               /* The radix tree holding the stream. */ 
    uint64_t length;        /* Number of elements inside this stream. */ 
    streamID last_id;       /* Zero if there are yet no items. */ 
    rax *cgroups;           /* Consumer groups dictionary: name -> streamCG */ 
} stream; 

那么這個radix tree長啥樣呢?在Redis源碼的rax.h文件中有一段這樣的描述，這樣看起來是不是就比較直觀了：

(f) "" 
*                    / 
*                 (i o) "f" 
*                 /   \ 
*    "firs"  ("rst")  (o) "fo" 
*              /        \ 
*    "first" []       [t   b] "foo" 
*                     /     \ 
*           "foot" ("er")    ("ar") "foob" 
*                    /          \ 
*          "footer" []          [] "foobar" 

Radix Tree(基數(shù)樹) 事實上就幾乎相同是傳統(tǒng)的二叉樹。僅僅是在尋找方式上，以一個unsigned int類型數(shù)為例，利用這個數(shù)的每個比特位作為樹節(jié)點的推斷。能夠這樣說，比方一個數(shù)10001010101010110101010，那么依照Radix 樹的插入就是在根節(jié)點，假設(shè)遇到0，就指向左節(jié)點，假設(shè)遇到1就指向右節(jié)點，在插入過程中構(gòu)造樹節(jié)點，在刪除過程中刪除樹節(jié)點。如下是一個保存了7個單詞的Radix Tree：