面試官：有一種數(shù)據(jù)類(lèi)型，Redis 要存兩次，為什么？

程序員的成長(zhǎng)之路

互聯(lián)網(wǎng)/程序員/技術(shù)/資料共享?

閱讀本文大概需要 9 分鐘。

來(lái)自：blog.csdn.net/zwx900102/article/details/113096979

前言

在 Redis 中，有一種數(shù)據(jù)類(lèi)型，當(dāng)在存儲(chǔ)的時(shí)候會(huì)同時(shí)采用兩種數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行分別存儲(chǔ)，那么 Redis 為什么要這么做呢？這么做會(huì)造成同一份數(shù)據(jù)占用兩倍空間嗎？

五種基本類(lèi)型之集合對(duì)象

Redis 中的集合對(duì)象是一個(gè)包含字符串類(lèi)型元素的無(wú)序集合，集合中元素唯一不可重復(fù)。

集合對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)有兩種：intset 和 hashtable。內(nèi)部通過(guò)編碼來(lái)進(jìn)行區(qū)分：

intset 編碼

intset（整數(shù)集合）可以保存類(lèi)型為?int16_t，int32_t，int64_t?的整數(shù)值，并且保證集合中沒(méi)有重復(fù)元素。

intset 數(shù)據(jù)結(jié)構(gòu)定義如下（源碼?inset.h?內(nèi)）：

typedef?struct?intset?{
????uint32_t?encoding;//編碼方式
????uint32_t?length;//當(dāng)前集合中的元素?cái)?shù)量
????int8_t?contents[];//集合中具體的元素
}?intset;

下圖就是一個(gè) intset 的集合對(duì)象存儲(chǔ)簡(jiǎn)圖：

encoding

在 intset 內(nèi)部的 encoding 記錄了當(dāng)前整數(shù)集合的數(shù)據(jù)存儲(chǔ)類(lèi)型，主要有三種：

• INTSET_ENC_INT16

此時(shí)?contents[]?內(nèi)的每個(gè)元素都是一個(gè) int16_t 類(lèi)型的整數(shù)值，范圍是：-32768 ~ 32767（-2 的 15 次方 ~ 2 的 15 次方 - 1）。

• INTSET_ENC_INT32

此時(shí)?contents[]?內(nèi)的每個(gè)元素都是一個(gè) int32_t 類(lèi)型的整數(shù)值，范圍是：-2147483648 ~ 2147483647（-2 的 31 次方 ~ 2 的 31 次方 - 1）。

• INTSET_ENC_INT64

此時(shí)?contents[]?內(nèi)的每個(gè)元素都是一個(gè) int64_t 類(lèi)型的整數(shù)值，范圍是：-9223372036854775808 ~ 9223372036854775807（-2 的 63 次方 ~ 2 的 63 次方 - 1）。

contents[]

contents[]?雖然結(jié)構(gòu)的定義上寫(xiě)的是 int8_t 類(lèi)型，但是實(shí)際存儲(chǔ)類(lèi)型是由上面的 encoding 來(lái)決定的。最新 Redis 面試題整理好了，點(diǎn)擊Java面試庫(kù)小程序在線刷題。

整數(shù)集合的升級(jí)

假如一開(kāi)始整數(shù)集合中的元素都是 16 位的，采用 int16_t 類(lèi)型來(lái)存儲(chǔ)，此時(shí)需要再存儲(chǔ)一個(gè) 32 位的整數(shù)，那么就需要對(duì)原先的整數(shù)集合進(jìn)行升級(jí)，升級(jí)之后才能將 32 位的整數(shù)存儲(chǔ)到整數(shù)集合內(nèi)。這就涉及到了整數(shù)集合的類(lèi)型升級(jí)，升級(jí)過(guò)程主要有 4 個(gè)步驟：

• 根據(jù)新添加元素的類(lèi)型來(lái)擴(kuò)展底層數(shù)組空間的大小，按照升級(jí)后現(xiàn)有元素的位數(shù)來(lái)分配新的空間。
• 將現(xiàn)有的元素進(jìn)行類(lèi)型轉(zhuǎn)換，并將轉(zhuǎn)換類(lèi)型后的元素從后到前逐個(gè)重新放回到數(shù)組內(nèi)。
• 將新元素放到數(shù)組的頭部或者尾部（因?yàn)橛|發(fā)升級(jí)的條件就是當(dāng)前數(shù)組的整數(shù)類(lèi)型無(wú)法存儲(chǔ)新元素，所以新元素要么比現(xiàn)有元素都大，要么就比現(xiàn)有元素都?。?。
• 將 encoding 屬性修改為最新的編碼，并且同步修改 length 屬性。

PS：和字符串對(duì)象的編碼一樣，整數(shù)集合的類(lèi)型一旦發(fā)生升級(jí)，將會(huì)保持編碼，無(wú)法降級(jí)。

升級(jí)示例

1.假如我們有一個(gè)集合存儲(chǔ)的 encoding 是?int16_t，內(nèi)部存儲(chǔ)了 3 個(gè)元素：

2.這時(shí)候需要插入一個(gè)整數(shù) 50000，發(fā)現(xiàn)存儲(chǔ)不下去，而 50000 是一個(gè)?int32_t?類(lèi)型整數(shù)，所以需要申請(qǐng)新空間，申請(qǐng)空間大小為?4 * 32 - 48=80。

3.現(xiàn)在新的數(shù)組內(nèi)要放置 4 個(gè)元素，原來(lái)的數(shù)組排在第 3，所以需要將升級(jí)后的 3 移動(dòng)到 64-95 位。

4.繼續(xù)將升級(jí)后的 2 移動(dòng)到 32-63 位。

5.繼續(xù)將升級(jí)后的 1 移動(dòng)到 0-31 位。

6.然后會(huì)將 50000 放到 96-127 位。

7.最后會(huì)修改 encoding 和 length 屬性，修改之后就完成了本次的升級(jí)。

hashtable 編碼

hashtable 結(jié)構(gòu)在前面講述哈希對(duì)象的時(shí)候進(jìn)行過(guò)詳細(xì)分析，想詳細(xì)了解的可以點(diǎn)擊這里。

intset 和 hashtable 編碼轉(zhuǎn)換

當(dāng)一個(gè)集合滿(mǎn)足以下兩個(gè)條件時(shí)，Redis 會(huì)選擇使用 intset 編碼：

• 集合對(duì)象保存的所有元素都是整數(shù)值。
• 集合對(duì)象保存的元素?cái)?shù)量小于等于 512 個(gè)（這個(gè)閾值可以通過(guò)配置文件?set-max-intset-entries?來(lái)控制）。

一旦集合中的元素不滿(mǎn)足上面兩個(gè)條件，則會(huì)選擇使用 hashtable 編碼。

集合對(duì)象常用命令

• sadd key member1 member2：將一個(gè)或多個(gè)元素 member 加入到集合 key 當(dāng)中，并返回添加成功的數(shù)目，如果元素已存在則被忽略。
• sismember key member：判斷元素 member 是否存在集合 key 中。
• srem key member1 member2：移除集合 key 中的元素，不存在的元素會(huì)被忽略。
• smove source dest member：將元素 member 從集合 source 中移動(dòng)到 dest 中，如果 member 不存在，則不執(zhí)行任何操作。
• smembers key：返回集合 key 中所有元素。

了解了操作集合對(duì)象的常用命令，我們就可以來(lái)驗(yàn)證下前面提到的哈希對(duì)象的類(lèi)型和編碼了，在測(cè)試之前為了防止其他 key 值的干擾，我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫(kù)。

依次執(zhí)行如下命令：

sadd?num?1?2?3??//設(shè)置?3?個(gè)整數(shù)的集合，會(huì)使用?intset?編碼
type?num?//查看類(lèi)型
object?encoding?num???//查看編碼

sadd?name?1?2?3?test??//設(shè)置?3?個(gè)整數(shù)和?1?個(gè)字符串的集合，會(huì)使用?hashtable?編碼
type?name?//查看類(lèi)型
object?encoding?name?//查看編碼

得到如下效果：

可以看到，當(dāng)設(shè)置的元素里面只有整數(shù)時(shí)，集合使用的就是 intset 編碼，當(dāng)設(shè)置的元素中含有非整數(shù)時(shí)，使用的就是 hashtable 編碼。

五種基本類(lèi)型之有序集合對(duì)象

Redis 中的有序集合和集合的區(qū)別是有序集合中的每個(gè)元素都會(huì)關(guān)聯(lián)一個(gè) double 類(lèi)型的分?jǐn)?shù)，然后按照分?jǐn)?shù)從小到大的順序進(jìn)行排列。換句話說(shuō)，有序集合的順序是由我們自己設(shè)值的時(shí)候通過(guò)分?jǐn)?shù)來(lái)確定的。

有序集合對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)有兩種：skiplist 和 ziplist。內(nèi)部同樣是通過(guò)編碼來(lái)進(jìn)行區(qū)分：

skiplist 編碼

skiplist 即跳躍表，有時(shí)候也簡(jiǎn)稱(chēng)為跳表。使用 skiplist 編碼的有序集合對(duì)象使用了 zset 結(jié)構(gòu)來(lái)作為底層實(shí)現(xiàn)，而zset 中同時(shí)包含了一個(gè)字典和一個(gè)跳躍表。

跳躍表

跳躍表是一種有序的數(shù)據(jù)結(jié)構(gòu)，其主要特點(diǎn)是通過(guò)在每個(gè)節(jié)點(diǎn)中維持多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的。

大部分情況下，跳躍表的效率可以等同于平衡樹(shù)，但是跳躍表的實(shí)現(xiàn)卻遠(yuǎn)遠(yuǎn)比平衡樹(shù)的實(shí)現(xiàn)簡(jiǎn)單，所以 Redis 選擇了使用跳躍表來(lái)實(shí)現(xiàn)有序集合。

下圖是一個(gè)普通的有序鏈表，我們?nèi)绻胍业?35 這個(gè)元素，只能從頭開(kāi)始遍歷到尾（鏈表中元素不支持隨機(jī)訪問(wèn)，所以不能用二分查找，而數(shù)組中可以通過(guò)下標(biāo)隨機(jī)訪問(wèn)，所以二分查找一般適用于有序數(shù)組），時(shí)間復(fù)雜度是?O(n)。

那么假如我們可以直接跳到鏈表的中間，那就可以節(jié)省很多資源了，這就是跳表的原理，如下圖所示就是一個(gè)跳表的數(shù)據(jù)結(jié)構(gòu)示例：

上圖中 level1，level2，level3 就是跳表的層級(jí)，每一個(gè) level 層級(jí)都有一個(gè)指向下一個(gè)相同 level 層級(jí)元素的指針，比如上圖我們遍歷尋找元素 35 的時(shí)候就有三種方案：

• 第 1 種就是執(zhí)行 level1 層級(jí)的指針，需要遍歷 7 次（1->8->9->12->15->20->35）才能找到元素 35。
• 第 2 種就是執(zhí)行 level2 層級(jí)的指針，只需要遍歷 5 次（1->9->12->15->35）就能找到元素 35。
• 第 3 種就是執(zhí)行 level3 層級(jí)的元素，這時(shí)候只需要遍歷 3 次（1->12->35）就能找到元素 35 了，大大提升了效率。

skiplist 的存儲(chǔ)結(jié)構(gòu)

跳躍表中的每個(gè)節(jié)點(diǎn)是一個(gè)?zskiplistNode?節(jié)點(diǎn)（源碼?server.h?內(nèi)）：

typedef?struct?zskiplistNode?{
????sds?ele;//元素
????double?score;//分值
????struct?zskiplistNode?*backward;//后退指針
????struct?zskiplistLevel?{//層
????????struct?zskiplistNode?*forward;//前進(jìn)指針
????????unsigned?long?span;//當(dāng)前節(jié)點(diǎn)到下一個(gè)節(jié)點(diǎn)的跨度（跨越的節(jié)點(diǎn)數(shù)）
????}?level[];
}?zskiplistNode;

• level（層）

level 即跳躍表中的層，其是一個(gè)數(shù)組，也就是說(shuō)一個(gè)節(jié)點(diǎn)的元素可以擁有多個(gè)層，即多個(gè)指向其他節(jié)點(diǎn)的指針，程序可以通過(guò)不同層級(jí)的指針來(lái)選擇最快捷的路徑提升訪問(wèn)速度。

level 是在每次創(chuàng)建新節(jié)點(diǎn)的時(shí)候根據(jù)冪次定律（power law）隨機(jī)生成的一個(gè)介于 1~32 之間的數(shù)字。

• forward（前進(jìn)指針）

每個(gè)層都會(huì)有一個(gè)指向鏈表尾部方向元素的指針，遍歷元素的時(shí)候需要使用到前進(jìn)指針。

• span（跨度）

跨度記錄了兩個(gè)節(jié)點(diǎn)之間的距離,需要注意的是，如果指向了 NULL 的話，則跨度為 0。

• backward（后退指針）

和前進(jìn)指針不一樣的是后退指針只有一個(gè)，所以每次只能后退至前一個(gè)節(jié)點(diǎn)（上圖中沒(méi)有畫(huà)出后退指針）。

• ele（元素）

跳躍表中元素是一個(gè) sds 對(duì)象（早期版本使用的是 redisObject 對(duì)象），元素必須唯一不能重復(fù)。

• score（分值）

節(jié)點(diǎn)的分值是一個(gè) double 類(lèi)型的浮點(diǎn)數(shù)，跳躍表中會(huì)將節(jié)點(diǎn)按照分值按照從小到大的順序排列，不同節(jié)點(diǎn)的分值可以重復(fù)。

上面介紹的只是跳躍表中的一個(gè)節(jié)點(diǎn)，多個(gè) zskiplistNode 節(jié)點(diǎn)組成了一個(gè) zskiplist 對(duì)象：

typedef?struct?zskiplist?{
????struct?zskiplistNode?*header,?*tail;//跳躍表的頭節(jié)點(diǎn)和尾結(jié)點(diǎn)指針
????unsigned?long?length;//跳躍表的節(jié)點(diǎn)數(shù)
????int?level;//所有節(jié)點(diǎn)中最大的層數(shù)
}?zskiplist;

到這里你可能以為有序集合就是用這個(gè) zskiplist 來(lái)實(shí)現(xiàn)的，然而實(shí)際上 Redis 并沒(méi)有直接使用 zskiplist 來(lái)實(shí)現(xiàn)，而是用 zset 對(duì)象再次進(jìn)行了一層包裝。

typedef?struct?zset?{
????dict?*dict;//字典對(duì)象
????zskiplist?*zsl;//跳躍表對(duì)象
}?zset;

所以最終，一個(gè)有序集合如果使用了 skiplist 編碼，其數(shù)據(jù)結(jié)構(gòu)如下圖所示：

上圖中上面一部分中的字典中的 key 就是對(duì)應(yīng)了有序集合中的元素（member），value 就對(duì)應(yīng)了分值（score）。上圖中下面一部分中跳躍表整數(shù) 1,8,9,12 也是對(duì)應(yīng)了元素（member），最后一排的 double 型數(shù)字就是分值（score）。

也就是說(shuō)字典和跳躍表中的數(shù)據(jù)都指向了我們存儲(chǔ)的元素（兩種數(shù)據(jù)結(jié)構(gòu)最終指向的是同一個(gè)地址，所以數(shù)據(jù)并不會(huì)出現(xiàn)冗余存儲(chǔ)），Redis 為什么要這么做呢？

為什么同時(shí)選擇使用字典和跳躍表

有序集合直接使用跳躍表或者單獨(dú)使用字典完全可以獨(dú)自實(shí)現(xiàn)，但是我們想一下，如果單獨(dú)使用跳躍表來(lái)實(shí)現(xiàn)，那么雖然可以使用跨度大的指針去遍歷元素來(lái)找到我們需要的數(shù)據(jù)，但是其復(fù)雜度仍然達(dá)到了 O(logN)，而字典中獲取一個(gè)元素的復(fù)雜度是 O(1)，而如果單獨(dú)使用字典雖然獲取元素很快，但是字典是無(wú)序的，所以如果要范圍查找就需要對(duì)其進(jìn)行排序，這又是一個(gè)耗時(shí)的操作，所以 Redis 綜合了兩種數(shù)據(jù)結(jié)構(gòu)來(lái)最大程度的提升性能，這也是 Redis 設(shè)計(jì)的精妙之處。

ziplist 編碼

壓縮列表在列表對(duì)象和哈希對(duì)象都有使用到，想詳細(xì)了解的可以點(diǎn)擊這里。

https://blog.csdn.net/zwx900102/article/details/112651435

ziplist 和 skiplist 編碼轉(zhuǎn)換

當(dāng)有序集合對(duì)象同時(shí)滿(mǎn)足以下兩個(gè)條件時(shí)，會(huì)使用 ziplist 編碼進(jìn)行存儲(chǔ)：

• 有序集合對(duì)象中保存的元素個(gè)數(shù)小于 128 個(gè)（可以通過(guò)配置?zset-max-ziplist-entries?修改）。
• 有序集合對(duì)象中保存的所有元素的總長(zhǎng)度小于 64 字節(jié)（可以通過(guò)配置?zset-max-ziplist-value?修改）。

有序集合對(duì)象常用命令

• zadd key score1 member1 score2 member2：將一個(gè)或多個(gè)元素（member）及其 score 添加到有序集合 key 中。
• zscore key member：返回有序集合 key 中 member 成員的 score。
• zincrby key num member：將有序集合 key 中的 member 加上 num，num 可以為負(fù)數(shù)。
• zcount key min max：返回有序集合 key 中 score 值在 [min,max] 區(qū)間的 member 數(shù)量。
• zrange key start stop：返回有序集合 key 中 score 從小到大排列后在 [start,stop] 區(qū)間的所有 member。
• zrevrange key start stop：返回有序集合 key 中 score 從大到小排列后在 [start,stop] 區(qū)間的所有 member。
• zrangebyscore key min max：返回有序集合中按 score 從小到大排列后在 [min,max] 區(qū)間的所有元素。注意這里默認(rèn)是閉區(qū)間，但是可以在 max 和 min 的數(shù)值前面加上?(?或者?[?來(lái)控制開(kāi)閉區(qū)間。
• zrevrangebyscore key max min：返回有序集合中按 score 從大到小排列后在 [min,max] 區(qū)間的所有元素。注意這里默認(rèn)是閉區(qū)間，但是可以在 max 和 min 的數(shù)值前面加上?(?或者?[?來(lái)控制開(kāi)閉區(qū)間。
• zrank key member：返回有序集合中 member 中元素排名（從小到大），返回的結(jié)果從 0 開(kāi)始計(jì)算。
• zrevrank key member：返回有序集合中 member 中元素排名（從大到小），返回的結(jié)果從 0 開(kāi)始計(jì)算。
• zlexcount key min max：返回有序集合中 min 和 max 之間的 member 數(shù)量。注意這個(gè)命令中的 min 和 max 前面必須加?(?或者?[?來(lái)控制開(kāi)閉區(qū)間，特殊值 - 和 + 分別表示負(fù)無(wú)窮和正無(wú)窮。

了解了操作有序集合對(duì)象的常用命令，我們就可以來(lái)驗(yàn)證下前面提到的哈希對(duì)象的類(lèi)型和編碼了，在測(cè)試之前為了防止其他 key 值的干擾，我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫(kù)。

在執(zhí)行命令之前，我們先把配置文件中的參數(shù)?zset-max-ziplist-entries?修改為 2，然后重啟 Redis 服務(wù)。

重啟完成之后依次執(zhí)行如下命令：

zadd?name?1?zs?2?lisi?//設(shè)置?2?個(gè)元素會(huì)使用?ziplist
type?name?//查看類(lèi)型
object?encoding?name?//查看編碼

zadd?address?1?beijing?2?shanghai?3?guangzhou?4?shenzhen??//設(shè)置4個(gè)元素則會(huì)使用?skiplist編碼
type?address??//查看類(lèi)型
object?encoding?address?//查看編碼

得到如下效果：

總結(jié)

本文主要分析了集合對(duì)象和有序集合對(duì)象的底層存儲(chǔ)結(jié)構(gòu) intset 和 skiplist 的實(shí)現(xiàn)原理，并且重點(diǎn)分析了有序集合如何實(shí)現(xiàn)排序以及為何同時(shí)使用兩種數(shù)據(jù)結(jié)構(gòu)（字典和跳表）同時(shí)進(jìn)行進(jìn)行存儲(chǔ)數(shù)據(jù)的原因。

推薦閱讀：

程序員小姐姐寫(xiě)出代碼版《本草綱目》毽子操，劉畊宏回復(fù)：很cool！

從 7 分鐘到 10 秒，Mybatis 批處理真的很強(qiáng)！

互聯(lián)網(wǎng)初中高級(jí)大廠面試題(9個(gè)G)

內(nèi)容包含Java基礎(chǔ)、JavaWeb、MySQL性能優(yōu)化、JVM、鎖、百萬(wàn)并發(fā)、消息隊(duì)列、高性能緩存、反射、Spring全家桶原理、微服務(wù)、Zookeeper......等技術(shù)棧！

?戳閱讀原文領(lǐng)??！? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??朕已閱?