在 Redis 中,有一種數(shù)據(jù)類型,當(dāng)在存儲的時候會同時采用兩種數(shù)據(jù)結(jié)構(gòu)來進(jìn)行分別存儲,那么 Redis 為什么要這么做呢?這么做會造成同一份數(shù)據(jù)占用兩倍空間嗎?
五種基本類型之集合對象
Redis 中的集合對象是一個包含字符串類型元素的無序集合,集合中元素唯一不可重復(fù)。
集合對象的底層數(shù)據(jù)結(jié)構(gòu)有兩種:intset 和 hashtable。內(nèi)部通過編碼來進(jìn)行區(qū)分:
intset 編碼
intset(整數(shù)集合)可以保存類型為 int16_t,int32_t,int64_t的整數(shù)值,并且保證集合中沒有重復(fù)元素。intset 數(shù)據(jù)結(jié)構(gòu)定義如下(源碼 inset.h內(nèi)):
下圖就是一個 intset 的集合對象存儲簡圖:
encoding
在 intset 內(nèi)部的 encoding 記錄了當(dāng)前整數(shù)集合的數(shù)據(jù)存儲類型,主要有三種:
INTSET_ENC_INT16
此時contents[]內(nèi)的每個元素都是一個 int16_t 類型的整數(shù)值,范圍是:-32768 ~ 32767(-2 的 15 次方 ~ 2 的 15 次方 - 1)。
INTSET_ENC_INT32
此時contents[]內(nèi)的每個元素都是一個 int32_t 類型的整數(shù)值,范圍是:-2147483648 ~ 2147483647(-2 的 31 次方 ~ 2 的 31 次方 - 1)。
INTSET_ENC_INT64
此時contents[]內(nèi)的每個元素都是一個 int64_t 類型的整數(shù)值,范圍是:-9223372036854775808 ~ 9223372036854775807(-2 的 63 次方 ~ 2 的 63 次方 - 1)。
contents[]
contents[]雖然結(jié)構(gòu)的定義上寫的是 int8_t 類型,但是實際存儲類型是由上面的 encoding 來決定的。
整數(shù)集合的升級
假如一開始整數(shù)集合中的元素都是 16 位的,采用 int16_t 類型來存儲,此時需要再存儲一個 32 位的整數(shù),那么就需要對原先的整數(shù)集合進(jìn)行升級,升級之后才能將 32 位的整數(shù)存儲到整數(shù)集合內(nèi)。這就涉及到了整數(shù)集合的類型升級,升級過程主要有 4 個步驟:
根據(jù)新添加元素的類型來擴(kuò)展底層數(shù)組空間的大小,按照升級后現(xiàn)有元素的位數(shù)來分配新的空間。
將現(xiàn)有的元素進(jìn)行類型轉(zhuǎn)換,并將轉(zhuǎn)換類型后的元素從后到前逐個重新放回到數(shù)組內(nèi)。
將新元素放到數(shù)組的頭部或者尾部(因為觸發(fā)升級的條件就是當(dāng)前數(shù)組的整數(shù)類型無法存儲新元素,所以新元素要么比現(xiàn)有元素都大,要么就比現(xiàn)有元素都?。?/p>
將 encoding 屬性修改為最新的編碼,并且同步修改 length 屬性。
PS:和字符串對象的編碼一樣,整數(shù)集合的類型一旦發(fā)生升級,將會保持編碼,無法降級。
升級示例
1.假如我們有一個集合存儲的 encoding 是int16_t,內(nèi)部存儲了 3 個元素:
2.這時候需要插入一個整數(shù) 50000,發(fā)現(xiàn)存儲不下去,而 50000 是一個int32_t類型整數(shù),所以需要申請新空間,申請空間大小為4 * 32 - 48=80。
3.現(xiàn)在新的數(shù)組內(nèi)要放置 4 個元素,原來的數(shù)組排在第 3,所以需要將升級后的 3 移動到 64-95 位。
4.繼續(xù)將升級后的 2 移動到 32-63 位。
5.繼續(xù)將升級后的 1 移動到 0-31 位。
6.然后會將 50000 放到 96-127 位。
7.最后會修改 encoding 和 length 屬性,修改之后就完成了本次的升級。
hashtable 編碼
hashtable 結(jié)構(gòu)在前面講述哈希對象的時候進(jìn)行過詳細(xì)分析
intset 和 hashtable 編碼轉(zhuǎn)換
當(dāng)一個集合滿足以下兩個條件時,Redis 會選擇使用 intset 編碼:
集合對象保存的所有元素都是整數(shù)值。
集合對象保存的元素數(shù)量小于等于 512 個(這個閾值可以通過配置文件set-max-intset-entries來控制)。
一旦集合中的元素不滿足上面兩個條件,則會選擇使用 hashtable 編碼。
集合對象常用命令
sadd key member1 member2:將一個或多個元素 member 加入到集合 key 當(dāng)中,并返回添加成功的數(shù)目,如果元素已存在則被忽略。
sismember key member:判斷元素 member 是否存在集合 key 中。
srem key member1 member2:移除集合 key 中的元素,不存在的元素會被忽略。
smove source dest member:將元素 member 從集合 source 中移動到 dest 中,如果 member 不存在,則不執(zhí)行任何操作。
smembers key:返回集合 key 中所有元素。
了解了操作集合對象的常用命令,我們就可以來驗證下前面提到的哈希對象的類型和編碼了,在測試之前為了防止其他 key 值的干擾,我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫。依次執(zhí)行如下命令:
得到如下效果:
可以看到,當(dāng)設(shè)置的元素里面只有整數(shù)時,集合使用的就是 intset 編碼,當(dāng)設(shè)置的元素中含有非整數(shù)時,使用的就是 hashtable 編碼。
五種基本類型之有序集合對象
Redis 中的有序集合和集合的區(qū)別是有序集合中的每個元素都會關(guān)聯(lián)一個 double 類型的分?jǐn)?shù),然后按照分?jǐn)?shù)從小到大的順序進(jìn)行排列。換句話說,有序集合的順序是由我們自己設(shè)值的時候通過分?jǐn)?shù)來確定的。有序集合對象的底層數(shù)據(jù)結(jié)構(gòu)有兩種:skiplist 和 ziplist。內(nèi)部同樣是通過編碼來進(jìn)行區(qū)分:
skiplist 編碼
skiplist 即跳躍表,有時候也簡稱為跳表。使用 skiplist 編碼的有序集合對象使用了 zset 結(jié)構(gòu)來作為底層實現(xiàn),而zset 中同時包含了一個字典和一個跳躍表。
跳躍表
跳躍表是一種有序的數(shù)據(jù)結(jié)構(gòu),其主要特點是通過在每個節(jié)點中維持多個指向其他節(jié)點的指針,從而達(dá)到快速訪問節(jié)點的目的。大部分情況下,跳躍表的效率可以等同于平衡樹,但是跳躍表的實現(xiàn)卻遠(yuǎn)遠(yuǎn)比平衡樹的實現(xiàn)簡單,所以 Redis 選擇了使用跳躍表來實現(xiàn)有序集合。下圖是一個普通的有序鏈表,我們?nèi)绻胍业?35 這個元素,只能從頭開始遍歷到尾(鏈表中元素不支持隨機(jī)訪問,所以不能用二分查找,而數(shù)組中可以通過下標(biāo)隨機(jī)訪問,所以二分查找一般適用于有序數(shù)組),時間復(fù)雜度是O(n)。
那么假如我們可以直接跳到鏈表的中間,那就可以節(jié)省很多資源了,這就是跳表的原理,如下圖所示就是一個跳表的數(shù)據(jù)結(jié)構(gòu)示例:
上圖中 level1,level2,level3 就是跳表的層級,每一個 level 層級都有一個指向下一個相同 level 層級元素的指針,比如上圖我們遍歷尋找元素 35 的時候就有三種方案:
第 1 種就是執(zhí)行 level1 層級的指針,需要遍歷 7 次(1->8->9->12->15->20->35)才能找到元素 35。
第 2 種就是執(zhí)行 level2 層級的指針,只需要遍歷 5 次(1->9->12->15->35)就能找到元素 35。
第 3 種就是執(zhí)行 level3 層級的元素,這時候只需要遍歷 3 次(1->12->35)就能找到元素 35 了,大大提升了效率。
skiplist 的存儲結(jié)構(gòu)
跳躍表中的每個節(jié)點是一個 zskiplistNode節(jié)點(源碼 server.h內(nèi)):
level(層)
level 即跳躍表中的層,其是一個數(shù)組,也就是說一個節(jié)點的元素可以擁有多個層,即多個指向其他節(jié)點的指針,程序可以通過不同層級的指針來選擇最快捷的路徑提升訪問速度。
level 是在每次創(chuàng)建新節(jié)點的時候根據(jù)冪次定律(power law)隨機(jī)生成的一個介于 1~32 之間的數(shù)字。
forward(前進(jìn)指針)
每個層都會有一個指向鏈表尾部方向元素的指針,遍歷元素的時候需要使用到前進(jìn)指針。
span(跨度)
跨度記錄了兩個節(jié)點之間的距離,需要注意的是,如果指向了 NULL 的話,則跨度為 0。
backward(后退指針)
和前進(jìn)指針不一樣的是后退指針只有一個,所以每次只能后退至前一個節(jié)點(上圖中沒有畫出后退指針)。
ele(元素)
跳躍表中元素是一個 sds 對象(早期版本使用的是 redisObject 對象),元素必須唯一不能重復(fù)。
score(分值)
節(jié)點的分值是一個 double 類型的浮點數(shù),跳躍表中會將節(jié)點按照分值按照從小到大的順序排列,不同節(jié)點的分值可以重復(fù)。
上面介紹的只是跳躍表中的一個節(jié)點,多個 zskiplistNode 節(jié)點組成了一個 zskiplist 對象:
到這里你可能以為有序集合就是用這個 zskiplist 來實現(xiàn)的,然而實際上 Redis 并沒有直接使用 zskiplist 來實現(xiàn),而是用 zset 對象再次進(jìn)行了一層包裝。
所以最終,一個有序集合如果使用了 skiplist 編碼,其數(shù)據(jù)結(jié)構(gòu)如下圖所示:
上圖中上面一部分中的字典中的 key 就是對應(yīng)了有序集合中的元素(member),value 就對應(yīng)了分值(score)。上圖中下面一部分中跳躍表整數(shù) 1,8,9,12 也是對應(yīng)了元素(member),最后一排的 double 型數(shù)字就是分值(score)。
也就是說字典和跳躍表中的數(shù)據(jù)都指向了我們存儲的元素(兩種數(shù)據(jù)結(jié)構(gòu)最終指向的是同一個地址,所以數(shù)據(jù)并不會出現(xiàn)冗余存儲),Redis 為什么要這么做呢?
為什么同時選擇使用字典和跳躍表
有序集合直接使用跳躍表或者單獨使用字典完全可以獨自實現(xiàn),但是我們想一下,如果單獨使用跳躍表來實現(xiàn),那么雖然可以使用跨度大的指針去遍歷元素來找到我們需要的數(shù)據(jù),但是其復(fù)雜度仍然達(dá)到了 O(logN),而字典中獲取一個元素的復(fù)雜度是 O(1),而如果單獨使用字典雖然獲取元素很快,但是字典是無序的,所以如果要范圍查找就需要對其進(jìn)行排序,這又是一個耗時的操作,所以 Redis 綜合了兩種數(shù)據(jù)結(jié)構(gòu)來最大程度的提升性能,這也是 Redis 設(shè)計的精妙之處。
ziplist 編碼
壓縮列表在列表對象和哈希對象都有使用到,想詳細(xì)了解的可以點擊這里。
https://blog.csdn.net/zwx900102/article/details/112651435
ziplist 和 skiplist 編碼轉(zhuǎn)換
當(dāng)有序集合對象同時滿足以下兩個條件時,會使用 ziplist 編碼進(jìn)行存儲:
有序集合對象中保存的元素個數(shù)小于 128 個(可以通過配置zset-max-ziplist-entries修改)。
有序集合對象中保存的所有元素的總長度小于 64 字節(jié)(可以通過配置zset-max-ziplist-value修改)。
有序集合對象常用命令
zadd key score1 member1 score2 member2:將一個或多個元素(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ù)值前面加上(或者[來控制開閉區(qū)間。
zrevrangebyscore key max min:返回有序集合中按 score 從大到小排列后在 [min,max] 區(qū)間的所有元素。注意這里默認(rèn)是閉區(qū)間,但是可以在 max 和 min 的數(shù)值前面加上(或者[來控制開閉區(qū)間。
zrank key member:返回有序集合中 member 中元素排名(從小到大),返回的結(jié)果從 0 開始計算。
zrevrank key member:返回有序集合中 member 中元素排名(從大到?。?,返回的結(jié)果從 0 開始計算。
zlexcount key min max:返回有序集合中 min 和 max 之間的 member 數(shù)量。注意這個命令中的 min 和 max 前面必須加(或者[來控制開閉區(qū)間,特殊值 - 和 + 分別表示負(fù)無窮和正無窮。
了解了操作有序集合對象的常用命令,我們就可以來驗證下前面提到的哈希對象的類型和編碼了,在測試之前為了防止其他 key 值的干擾,我們先執(zhí)行 flushall 命令清空 Redis 數(shù)據(jù)庫。在執(zhí)行命令之前,我們先把配置文件中的參數(shù)
zset-max-ziplist-entries
修改為 2,然后重啟 Redis 服務(wù)。重啟完成之后依次執(zhí)行如下命令:
得到如下效果:
總結(jié)
本文主要分析了集合對象和有序集合對象的底層存儲結(jié)構(gòu) intset 和 skiplist 的實現(xiàn)原理,并且重點分析了有序集合如何實現(xiàn)排序以及為何同時使用兩種數(shù)據(jù)結(jié)構(gòu)(字典和跳表)同時進(jìn)行進(jìn)行存儲數(shù)據(jù)的原因。
審核編輯:劉清
-
編碼器
+關(guān)注
關(guān)注
44文章
3529瀏覽量
133309 -
數(shù)據(jù)存儲
+關(guān)注
關(guān)注
5文章
947瀏覽量
50761 -
編碼轉(zhuǎn)換
+關(guān)注
關(guān)注
0文章
4瀏覽量
6894
發(fā)布評論請先 登錄
相關(guān)推薦
評論