今天我才知道Redis有9種基本數(shù)據(jù)類(lèi)型，據(jù)說(shuō)只有5%的人知道，漲知識(shí)了
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)部編碼，掌握這篇文章的知識(shí)點(diǎn)，讓你成為面試官眼中Redis方面最靚的仔!
說(shuō)明：本文基于Redis-3.2.11版本源碼進(jìn)行分析。
5種普通數(shù)據(jù)結(jié)構(gòu)
這個(gè)沒(méi)什么好說(shuō)的，對(duì)Redis稍微有點(diǎn)了解的都知道5種最基本的數(shù)據(jù)結(jié)構(gòu)：String，List，Hash，Set，Sorted Set。不過(guò)，需要注意的是，這里依然有幾個(gè)高頻面試題。
Set和Hash的關(guān)系
答案就是Set是一個(gè)特殊的value為空的Hash。Set類(lèi)型操作的源碼在t_set.c中。以新增一個(gè)元素為例(int setTypeAdd(robj *subject, sds value))，如果編碼類(lèi)型是OBJ_ENCODING_HT，那么新增源碼的源碼如下，事實(shí)上就是對(duì)dict即Hash數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作，并且dictSetVal時(shí)value是NULL：
- dictEntry *de = dictAddRaw(ht,value,NULL);
- if (de) {
- dictSetKey(ht,de,sdsdup(value));
- dictSetVal(ht,de,NULL);
- return 1;
- }
同樣的，我們?cè)趖_hash.c中看到Hash類(lèi)型新增元素時(shí)，當(dāng)判斷編碼類(lèi)型是OBJ_ENCODING_HT時(shí)，也是調(diào)用dict的方法：dictAdd(o->ptr,f,v)，dictAdd最終也是調(diào)用dictSetVal()方法，只不過(guò)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時(shí)，兩者都是dict數(shù)據(jù)類(lèi)型，只不過(guò)Set是value為NULL的特殊的dict。
談?wù)勀銓?duì)Sorted Set的理解
Sorted Set的數(shù)據(jù)結(jié)構(gòu)是一種跳表，即SkipList，如下圖所示，紅線是查找10的過(guò)程：
SkipList
如何借助Sorted set實(shí)現(xiàn)多維排序
Sorted Set默認(rèn)情況下只能根據(jù)一個(gè)因子score進(jìn)行排序。如此一來(lái)，局限性就很大，舉個(gè)栗子：熱門(mén)排行榜需要按照下載量&最近更新時(shí)間排序，即類(lèi)似數(shù)據(jù)庫(kù)中的ORDER BY download_count, update_time DESC。那這樣的需求如果用Redis的Sorted Set實(shí)現(xiàn)呢?
事實(shí)上很簡(jiǎn)單，思路就是將涉及排序的多個(gè)維度的列通過(guò)一定的方式轉(zhuǎn)換成一個(gè)特殊的列，即result = function(x, y, z)，即x，y，z是三個(gè)排序因子，例如下載量、時(shí)間等，通過(guò)自定義函數(shù)function()計(jì)算得到result，將result作為Sorted Set中的score的值，就能實(shí)現(xiàn)任意維度的排序需求了。
Redis內(nèi)部編碼
我們常說(shuō)的String，List，Hash，Set，Sorted Set只是對(duì)外的編碼，實(shí)際上每種數(shù)據(jù)結(jié)構(gòu)都有自己底層的內(nèi)部編碼實(shí)現(xiàn)，而且是多種實(shí)現(xiàn)，這樣Redis可以在合適的場(chǎng)景選擇更合適的內(nèi)部編碼。
如下圖所示(圖片糾正：intset編碼，而不是inset編碼)，可以看到每種數(shù)據(jù)結(jié)構(gòu)都有2種以上的內(nèi)部編碼實(shí)現(xiàn)，例如String數(shù)據(jù)結(jié)構(gòu)就包含了raw、int和embstr三種內(nèi)部編碼。同時(shí)，有些內(nèi)部編碼可以作為多種外部數(shù)據(jù)結(jié)構(gòu)的內(nèi)部實(shí)現(xiàn)，例如ziplist就是hash、list和zset共有的內(nèi)部編碼，而set的內(nèi)部編碼可能是hashtable或者intset：
Redis內(nèi)部編碼
Redis這樣設(shè)計(jì)有兩個(gè)好處：
可以偷偷的改進(jìn)內(nèi)部編碼，而對(duì)外的數(shù)據(jù)結(jié)構(gòu)和命令沒(méi)有影響，這樣一旦開(kāi)發(fā)出更優(yōu)秀的內(nèi)部編碼，無(wú)需改動(dòng)對(duì)外數(shù)據(jù)結(jié)構(gòu)和命令。
多種內(nèi)部編碼實(shí)現(xiàn)可以在不同場(chǎng)景下發(fā)揮各自的優(yōu)勢(shì)。例如ziplist比較節(jié)省內(nèi)存，但是在列表元素比較多的情況下，性能會(huì)有所下降。這時(shí)候Redis會(huì)根據(jù)配置選項(xiàng)將列表類(lèi)型的內(nèi)部實(shí)現(xiàn)轉(zhuǎn)換為linkedlist。
String的3種內(nèi)部編碼
由上圖可知，String的3種內(nèi)部編碼分別是：int、embstr、raw。int類(lèi)型很好理解，當(dāng)一個(gè)key的value是整型時(shí)，Redis就將其編碼為int類(lèi)型(另外還有一個(gè)條件：把這個(gè)value當(dāng)作字符串來(lái)看，它的長(zhǎng)度不能超過(guò)20)。如下所示。這種編碼類(lèi)型為了節(jié)省內(nèi)存。Redis默認(rèn)會(huì)緩存10000個(gè)整型值(#define OBJ_SHARED_INTEGERS 10000)，這就意味著，如果有10個(gè)不同的KEY，其value都是10000以內(nèi)的值，事實(shí)上全部都是共享同一個(gè)對(duì)象：
- 127.0.0.1:6379> set number "7890"
- OK
- 127.0.0.1:6379> object encoding number
- "int"
接下來(lái)就是ebmstr和raw兩種內(nèi)部編碼的長(zhǎng)度界限，請(qǐng)看下面的源碼：
- #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);
- }
也就是說(shuō)，embstr和raw編碼的長(zhǎng)度界限是44，我們可以做如下驗(yàn)證。長(zhǎng)度超過(guò)44以后，就是raw編碼類(lèi)型，不會(huì)有任何優(yōu)化，是多長(zhǎng)，就要消耗多少內(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)勢(shì)在哪里?embstr編碼將創(chuàng)建字符串對(duì)象所需的空間分配的次數(shù)從raw編碼的兩次降低為一次。因?yàn)閑mbstr編碼的字符串對(duì)象的所有數(shù)據(jù)都保存在一塊連續(xù)的內(nèi)存里面，所以這種編碼的字符串對(duì)象比起raw編碼的字符串對(duì)象能更好地利用緩存帶來(lái)的優(yōu)勢(shì)。并且釋放embstr編碼的字符串對(duì)象只需要調(diào)用一次內(nèi)存釋放函數(shù)，而釋放raw編碼對(duì)象的字符串對(duì)象需要調(diào)用兩次內(nèi)存釋放函數(shù)。如下圖所示，左邊是embstr編碼，右邊是raw編碼：
embstr V.S. raw
ziplist
由前面的圖可知，List，Hash，Sorted Set三種對(duì)外結(jié)構(gòu)，在特殊情況下的內(nèi)部編碼都是ziplist，那么這個(gè)ziplist有什么神奇之處呢?
以Hash為例，我們首先看一下什么條件下它的內(nèi)部編碼是ziplist：
當(dāng)哈希類(lèi)型元素個(gè)數(shù)小于hash-max-ziplist-entries配置(默認(rèn)512個(gè));
所有值都小于hash-max-ziplist-value配置(默認(rèn)64個(gè)字節(jié));
如果是sorted set的話，同樣需要滿足兩個(gè)條件：
元素個(gè)數(shù)小于zset-max-ziplist-entries配置，默認(rèn)128;
所有值都小于zset-max-ziplist-value配置，默認(rèn)64。
實(shí)際上，ziplist充分體現(xiàn)了Redis對(duì)于存儲(chǔ)效率的追求。一個(gè)普通的雙向鏈表，鏈表中每一項(xiàng)都占用獨(dú)立的一塊內(nèi)存，各項(xiàng)之間用地址指針(或引用)連接起來(lái)。這種方式會(huì)帶來(lái)大量的內(nèi)存碎片，而且地址指針也會(huì)占用額外的內(nèi)存。而ziplist卻是將表中每一項(xiàng)存放在前后連續(xù)的地址空間內(nèi)，一個(gè)ziplist整體占用一大塊內(nèi)存。它是一個(gè)表(list)，但其實(shí)不是一個(gè)鏈表(linked list)。
ziplist的源碼在ziplist.c這個(gè)文件中，其中有一段這樣的描述 -- The general layout of the ziplist is as follows:：
- <zlbytes> <zltail> <zllen> <entry> <entry> ... <entry> <zlend>
zlbytes：表示這個(gè)ziplist占用了多少空間，或者說(shuō)占了多少字節(jié)，這其中包括了zlbytes本身占用的4個(gè)字節(jié);
zltail：表示到ziplist中最后一個(gè)元素的偏移量，有了這個(gè)值，pop操作的時(shí)間復(fù)雜度就是O(1)了，即不需要遍歷整個(gè)ziplist;
zllen：表示ziplist中有多少個(gè)entry，即保存了多少個(gè)元素。由于這個(gè)字段占用16個(gè)字節(jié)，所以最大值是2^16-1，也就意味著，如果entry的數(shù)量超過(guò)2^16-1時(shí)，需要遍歷整個(gè)ziplist才知道entry的數(shù)量;
entry：真正保存的數(shù)據(jù)，有它自己的編碼;
zlend：專(zhuān)門(mén)用來(lái)表示ziplist尾部的特殊字符，占用8個(gè)字節(jié)，值固定為255，即8個(gè)字節(jié)每一位都是1。
如下就是一個(gè)真實(shí)的ziplist編碼，包含了2和5兩個(gè)元素：
- [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)非常簡(jiǎn)單，就是我們非常熟悉的雙向鏈表，對(duì)應(yīng)Java中的LinkedList。
skiplist
這個(gè)前面也已經(jīng)提及，就是經(jīng)典的跳表數(shù)據(jù)結(jié)構(gòu)。
hashtable
這個(gè)也很容易，對(duì)應(yīng)Java中的HashMap。
intset
Set特殊內(nèi)部編碼，當(dāng)滿足下面的條件時(shí)Set的內(nèi)部編碼就是intset而不是hashtable：
Set集合中必須是64位有符號(hào)的十進(jìn)制整型;
元素個(gè)數(shù)不能超過(guò)set-max-intset-entries配置，默認(rèn)512;
驗(yàn)證如下：
- 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編碼到底是個(gè)什么東西呢?看它的源碼定義如下，很明顯，就是整型數(shù)組，并且是一個(gè)有序的整型數(shù)組。它在內(nèi)存分配上與ziplist有些類(lèi)似，是連續(xù)的一整塊內(nèi)存空間，而且對(duì)于大整數(shù)和小整數(shù)采取了不同的編碼，盡量對(duì)內(nèi)存的使用進(jìn)行了優(yōu)化。這樣的數(shù)據(jù)結(jié)構(gòu)，如果執(zhí)行SISMEMBER命令，即查看某個(gè)元素是否在集合中時(shí)，事實(shí)上使用的是二分查找法：
- typedef struct intset {
- uint32_t encoding;
- uint32_t length;
- int8_t contents[];
- } intset;
- // intset編碼查找方法源碼（人為簡(jiǎn)化），標(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種高級(jí)數(shù)據(jù)結(jié)構(gòu)
Redis中3種高級(jí)數(shù)據(jù)結(jié)構(gòu)分別是bitmap、GEO、HyperLogLog，針對(duì)這3種數(shù)據(jù)結(jié)構(gòu)，筆者之前也有文章介紹過(guò)。其中，最重要的就是bitmap。
bitmap
這個(gè)就是Redis實(shí)現(xiàn)的BloomFilter，BloomFilter非常簡(jiǎn)單，如下圖所示，假設(shè)已經(jīng)有3個(gè)元素a、b和c，分別通過(guò)3個(gè)hash算法h1()、h2()和h2()計(jì)算然后對(duì)一個(gè)bit進(jìn)行賦值，接下來(lái)假設(shè)需要判斷d是否已經(jīng)存在，那么也需要使用3個(gè)hash算法h1()、h2()和h2()對(duì)d進(jìn)行計(jì)算，然后得到3個(gè)bit的值，恰好這3個(gè)bit的值為1，這就能夠說(shuō)明：d可能存在集合中。再判斷e，由于h1(e)算出來(lái)的bit之前的值是0，那么說(shuō)明：e一定不存在集合中：
BloomFilter
需要說(shuō)明的是，bitmap并不是一種真實(shí)的數(shù)據(jù)結(jié)構(gòu)，它本質(zhì)上是String數(shù)據(jù)結(jié)構(gòu)，只不過(guò)操作的粒度變成了位，即bit。因?yàn)镾tring類(lèi)型最大長(zhǎng)度為512MB，所以bitmap最多可以存儲(chǔ)2^32個(gè)bit。
GEO
GEO數(shù)據(jù)結(jié)構(gòu)可以在Redis中存儲(chǔ)地理坐標(biāo)，并且坐標(biāo)有限制，由EPSG:900913 / EPSG:3785 / OSGEO:41001 規(guī)定如下：
有效的經(jīng)度從-180度到180度。
有效的緯度從-85.05112878度到85.05112878度。
當(dāng)坐標(biāo)位置超出上述指定范圍時(shí)，該命令將會(huì)返回一個(gè)錯(cuò)誤。添加地理位置命令如下：
- redis> GEOADD city 114.031040 22.324386 "shenzhen" 112.572154 22.267832 "guangzhou"
- (integer) 2
- redis> GEODIST city shenzhen guangzhou
- "150265.8106"
但是，需要說(shuō)明的是，Geo本身不是一種數(shù)據(jù)結(jié)構(gòu)，它本質(zhì)上還是借助于Sorted Set(ZSET)，并且使用GeoHash技術(shù)進(jìn)行填充。Redis中將經(jīng)緯度使用52位的整數(shù)進(jìn)行編碼，放進(jìn)zset中，score就是GeoHash的52位整數(shù)值。在使用Redis進(jìn)行Geo查詢時(shí)，其內(nèi)部對(duì)應(yīng)的操作其實(shí)就是zset(skiplist)的操作。通過(guò)zset的score進(jìn)行排序就可以得到坐標(biāo)附近的其它元素，通過(guò)將score還原成坐標(biāo)值就可以得到元素的原始坐標(biāo)。
總之，Redis中處理這些地理位置坐標(biāo)點(diǎn)的思想是：二維平面坐標(biāo)點(diǎn) --> 一維整數(shù)編碼值 --> zset(score為編碼值) --> zrangebyrank(獲取score相近的元素)、zrangebyscore --> 通過(guò)score(整數(shù)編碼值)反解坐標(biāo)點(diǎn) --> 附近點(diǎn)的地理位置坐標(biāo)。
GEOHASH原理
使用wiki上的例子，緯度為42.6，經(jīng)度為-5.6的點(diǎn)，轉(zhuǎn)化為base32的話要如何轉(zhuǎn)呢?
首先拿緯度來(lái)進(jìn)行說(shuō)明，緯度的范圍為-90到90，將這個(gè)范圍劃為兩段，則為[-90,0]、[0,90]，然后看給定的緯度在哪個(gè)范圍，在前面的范圍的話，就設(shè)當(dāng)前位為0，后面的話值便為1.然后繼續(xù)將確定的范圍1分為2，繼續(xù)以確定值在前段還是后段來(lái)確定bit的值。就這樣慢慢的縮小范圍，一般最多縮小13次就可以了(經(jīng)緯度的二進(jìn)制位相加最多25位，經(jīng)度13位，緯度12位)。這時(shí)的中間值，將跟給定的值最相近。如下圖所示：
Geohash
第1行，緯度42.6位于[0, 90]之間，所以bit=1;第2行，緯度42.6位于[0, 45]之間，所以bit=0;第3行，緯度42.6位于[22.5, 45]之間，所以bit=1，以此類(lèi)推。這樣，取出圖中的bit位：1011 1100 1001，同樣的方法，將經(jīng)度(范圍-180到180)算出來(lái)為 ：0111 1100 0000 0。結(jié)果對(duì)其如下：
- # 經(jīng)度
- 0111 1100 0000 0
- # 緯度
- 1011 1100 1001
得到了經(jīng)緯度的二進(jìn)制位后，下面需要將兩者進(jìn)行結(jié)合：從經(jīng)度、緯度的循環(huán)，每次取其二進(jìn)制的一位(不足位取0)，合并為新的二進(jìn)制數(shù)：01101111 11110000 01000001 0。每5位為一個(gè)十進(jìn)制數(shù)，結(jié)合base32對(duì)應(yīng)表映射為base32值為：ezs42。這樣就完成了encode的過(guò)程。
Streams
這是Redis5.0引入的全新數(shù)據(jù)結(jié)構(gòu)，用一句話概括Streams就是Redis實(shí)現(xiàn)的內(nèi)存版kafka。而且，Streams也有Consumer Groups的概念。通過(guò)Redis源碼中對(duì)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;
那么這個(gè)radix tree長(zhǎng)啥樣呢?在Redis源碼的rax.h文件中有一段這樣的描述，這樣看起來(lái)是不是就比較直觀了：
- (f) ""
- * /
- * (i o) "f"
- * / \
- * "firs" ("rst") (o) "fo"
- * / \
- * "first" [] [t b] "foo"
- * / \
- * "foot" ("er") ("ar") "foob"
- * / \
- * "footer" [] [] "foobar"
Radix Tree(基數(shù)樹(shù)) 事實(shí)上就幾乎相同是傳統(tǒng)的二叉樹(shù)。僅僅是在尋找方式上，以一個(gè)unsigned int類(lèi)型數(shù)為例，利用這個(gè)數(shù)的每個(gè)比特位作為樹(shù)節(jié)點(diǎn)的推斷。能夠這樣說(shuō)，比方一個(gè)數(shù)10001010101010110101010，那么依照Radix 樹(shù)的插入就是在根節(jié)點(diǎn)，假設(shè)遇到0，就指向左節(jié)點(diǎn)，假設(shè)遇到1就指向右節(jié)點(diǎn)，在插入過(guò)程中構(gòu)造樹(shù)節(jié)點(diǎn)，在刪除過(guò)程中刪除樹(shù)節(jié)點(diǎn)。如下是一個(gè)保存了7個(gè)單詞的Radix Tree：
