前言
在 Redis 中,有一種資料類型,當在存儲的時候會同時采用兩種資料結構來進行分别存儲,那麼 Redis 為什麼要這麼做呢?這麼做會造成同一份資料占用兩倍空間嗎?
五種基本類型之集合對象
Redis 中的集合對象是一個包含字元串類型元素的無序集合,集合中元素唯一不可重複。
集合對象的底層資料結構有兩種:intset 和 hashtable。内部通過編碼來進行區分:
intset 編碼
intset(整數集合)可以儲存類型為
int16_t
,
int32_t
,
int64_t
的整數值,并且保證集合中沒有重複元素。
intset 資料結構定義如下(源碼
inset.h
内):
typedef struct intset {
uint32_t encoding;//編碼方式
uint32_t length;//目前集合中的元素數量
int8_t contents[];//集合中具體的元素
} intset;
下圖就是一個 intset 的集合對象存儲簡圖:
encoding
在 intset 内部的 encoding 記錄了目前整數集合的資料存儲類型,主要有三種:
- INTSET_ENC_INT16
此時
contents[]
内的每個元素都是一個 int16_t 類型的整數值,範圍是:
-32768 ~ 32767
(-2 的 15 次方 ~ 2 的 15 次方 - 1)。
- INTSET_ENC_INT32
此時
contents[]
内的每個元素都是一個 int32_t 類型的整數值,範圍是:
-2147483648 ~ 2147483647
(-2 的 31 次方 ~ 2 的 31 次方 - 1)。
- INTSET_ENC_INT64
此時
contents[]
内的每個元素都是一個 int64_t 類型的整數值,範圍是:
-9223372036854775808 ~ 9223372036854775807
(-2 的 63 次方 ~ 2 的 63 次方 - 1)。
contents[]
contents[]
contents[]
雖然結構的定義上寫的是 int8_t 類型,但是實際存儲類型是由上面的 encoding 來決定的。
整數集合的更新
假如一開始整數集合中的元素都是 16 位的,采用 int16_t 類型來存儲,此時需要再存儲一個 32 位的整數,那麼就需要對原先的整數集合進行更新,更新之後才能将 32 位的整數存儲到整數集合内。這就涉及到了整數集合的類型更新,更新過程主要有 4 個步驟:
- 根據新添加元素的類型來擴充底層數組空間的大小,按照更新後現有元素的位數來配置設定新的空間。
- 将現有的元素進行類型轉換,并将轉換類型後的元素從後到前逐個重新放回到數組内。
- 将新元素放到數組的頭部或者尾部(因為觸發更新的條件就是目前數組的整數類型無法存儲新元素,是以新元素要麼比現有元素都大,要麼就比現有元素都小)。
- 将 encoding 屬性修改為最新的編碼,并且同步修改 length 屬性。
PS:和字元串對象的編碼一樣,整數集合的類型一旦發生更新,将會保持編碼,無法降級。
更新示例
1.假如我們有一個集合存儲的 encoding 是
int16_t
,内部存儲了 3 個元素:
2.這時候需要插入一個整數 50000,發現存儲不下去,而 50000 是一個
int32_t
類型整數,是以需要申請新空間,申請空間大小為
4 * 32 - 48=80
。
3.現在新的數組内要放置 4 個元素,原來的數組排在第 3,是以需要将更新後的 3 移動到 64-95 位。
4.繼續将更新後的 2 移動到 32-63 位。
5.繼續将更新後的 1 移動到 0-31 位。
6.然後會将 50000 放到 96-127 位。
7.最後會修改 encoding 和 length 屬性,修改之後就完成了本次的更新。
hashtable 編碼
hashtable 結構在前面講述哈希對象的時候進行過詳細分析,想詳細了解的可以點選這裡。
intset 和 hashtable 編碼轉換
當一個集合滿足以下兩個條件時,Redis 會選擇使用 intset 編碼:
- 集合對象儲存的所有元素都是整數值。
- 集合對象儲存的元素數量小于等于 512 個(這個門檻值可以通過配置檔案
來控制)。set-max-intset-entries
一旦集合中的元素不滿足上面兩個條件,則會選擇使用 hashtable 編碼。
集合對象常用指令
-
:将一個或多個元素 member 加入到集合 key 當中,并傳回添加成功的數目,如果元素已存在則被忽略。sadd key member1 member2
-
:判斷元素 member 是否存在集合 key 中。sismember key member
-
:移除集合 key 中的元素,不存在的元素會被忽略。srem key member1 member2
-
:将元素 member 從集合 source 中移動到 dest 中,如果 member 不存在,則不執行任何操作。smove source dest member
-
:傳回集合 key 中所有元素。smembers key
了解了操作集合對象的常用指令,我們就可以來驗證下前面提到的哈希對象的類型和編碼了,在測試之前為了防止其他 key 值的幹擾,我們先執行 flushall 指令清空 Redis 資料庫。
依次執行如下指令:
sadd num 1 2 3 //設定 3 個整數的集合,會使用 intset 編碼
type num //檢視類型
object encoding num //檢視編碼
sadd name 1 2 3 test //設定 3 個整數和 1 個字元串的集合,會使用 hashtable 編碼
type name //檢視類型
object encoding name //檢視編碼
得到如下效果:
可以看到,當設定的元素裡面隻有整數時,集合使用的就是 intset 編碼,當設定的元素中含有非整數時,使用的就是 hashtable 編碼。
五種基本類型之有序集合對象
Redis 中的有序集合和集合的差別是有序集合中的每個元素都會關聯一個 double 類型的分數,然後按照分數從小到大的順序進行排列。換句話說,有序集合的順序是由我們自己設值的時候通過分數來确定的。
有序集合對象的底層資料結構有兩種:skiplist 和 ziplist。内部同樣是通過編碼來進行區分:
skiplist 編碼
skiplist 即跳躍表,有時候也簡稱為跳表。使用 skiplist 編碼的有序集合對象使用了 zset 結構來作為底層實作,而zset 中同時包含了一個字典和一個跳躍表。
跳躍表
跳躍表是一種有序的資料結構,其主要特點是通過在每個節點中維持多個指向其他節點的指針,進而達到快速通路節點的目的。
大部分情況下,跳躍表的效率可以等同于平衡樹,但是跳躍表的實作卻遠遠比平衡樹的實作簡單,是以 Redis 選擇了使用跳躍表來實作有序集合。
下圖是一個普通的有序連結清單,我們如果想要找到 35 這個元素,隻能從頭開始周遊到尾(連結清單中元素不支援随機通路,是以不能用二分查找,而數組中可以通過下标随機通路,是以二分查找一般适用于有序數組),時間複雜度是
O(n)
。
那麼假如我們可以直接跳到連結清單的中間,那就可以節省很多資源了,這就是跳表的原理,如下圖所示就是一個跳表的資料結構示例:
上圖中 level1,level2,level3 就是跳表的層級,每一個 level 層級都有一個指向下一個相同 level 層級元素的指針,比如上圖我們周遊尋找元素 35 的時候就有三種方案:
- 第 1 種就是執行 level1 層級的指針,需要周遊 7 次(
)才能找到元素 35。1->8->9->12->15->20->35
- 第 2 種就是執行 level2 層級的指針,隻需要周遊 5 次(
)就能找到元素 35。1->9->12->15->35
- 第 3 種就是執行 level3 層級的元素,這時候隻需要周遊 3 次(
)就能找到元素 35 了,大大提升了效率。1->12->35
skiplist 的存儲結構
跳躍表中的每個節點是一個
zskiplistNode
節點(源碼
server.h
内):
typedef struct zskiplistNode {
sds ele;//元素
double score;//分值
struct zskiplistNode *backward;//後退指針
struct zskiplistLevel {//層
struct zskiplistNode *forward;//前進指針
unsigned long span;//目前節點到下一個節點的跨度(跨越的節點數)
} level[];
} zskiplistNode;
- level(層)
level 即跳躍表中的層,其是一個數組,也就是說一個節點的元素可以擁有多個層,即多個指向其他節點的指針,程式可以通過不同層級的指針來選擇最快捷的路徑提升通路速度。
level 是在每次建立新節點的時候根據幂次定律(power law)随機生成的一個介于 1~32 之間的數字。
- forward(前進指針)
每個層都會有一個指向連結清單尾部方向元素的指針,周遊元素的時候需要使用到前進指針。
- span(跨度)
跨度記錄了兩個節點之間的距離,需要注意的是,如果指向了 NULL 的話,則跨度為 0。
- backward(後退指針)
和前進指針不一樣的是後退指針隻有一個,是以每次隻能後退至前一個節點(上圖中沒有畫出後退指針)。
- ele(元素)
跳躍表中元素是一個 sds 對象(早期版本使用的是 redisObject 對象),元素必須唯一不能重複。
- score(分值)
節點的分值是一個 double 類型的浮點數,跳躍表中會将節點按照分值按照從小到大的順序排列,不同節點的分值可以重複。
上面介紹的隻是跳躍表中的一個節點,多個 zskiplistNode 節點組成了一個 zskiplist 對象:
typedef struct zskiplist {
struct zskiplistNode *header, *tail;//跳躍表的頭節點和尾結點指針
unsigned long length;//跳躍表的節點數
int level;//所有節點中最大的層數
} zskiplist;
到這裡你可能以為有序集合就是用這個 zskiplist 來實作的,然而實際上 Redis 并沒有直接使用 zskiplist 來實作,而是用 zset 對象再次進行了一層包裝。
typedef struct zset {
dict *dict;//字典對象
zskiplist *zsl;//跳躍表對象
} zset;
是以最終,一個有序集合如果使用了 skiplist 編碼,其資料結構如下圖所示:
上圖中上面一部分中的字典中的 key 就是對應了有序集合中的元素(member),value 就對應了分值(score)。上圖中下面一部分中跳躍表整數 1,8,9,12 也是對應了元素(member),最後一排的 double 型數字就是分值(score)。
也就是說字典和跳躍表中的資料都指向了我們存儲的元素(兩種資料結構最終指向的是同一個位址,是以資料并不會出現備援存儲),Redis 為什麼要這麼做呢?
為什麼同時選擇使用字典和跳躍表
有序集合直接使用跳躍表或者單獨使用字典完全可以獨自實作,但是我們想一下,如果單獨使用跳躍表來實作,那麼雖然可以使用跨度大的指針去周遊元素來找到我們需要的資料,但是其複雜度仍然達到了 O(logN),而字典中擷取一個元素的複雜度是 O(1),而如果單獨使用字典雖然擷取元素很快,但是字典是無序的,是以如果要範圍查找就需要對其進行排序,這又是一個耗時的操作,是以 Redis 綜合了兩種資料結構來最大程度的提升性能,這也是 Redis 設計的精妙之處。
ziplist 編碼
壓縮清單在清單對象和哈希對象都有使用到
ziplist 和 skiplist 編碼轉換
當有序集合對象同時滿足以下兩個條件時,會使用 ziplist 編碼進行存儲:
- 有序集合對象中儲存的元素個數小于 128 個(可以通過配置
修改)。zset-max-ziplist-entries
- 有序集合對象中儲存的所有元素的總長度小于 64 位元組(可以通過配置
修改)。zset-max-ziplist-value
有序集合對象常用指令
-
:将一個或多個元素(member)及其 score 添加到有序集合 key 中。zadd key score1 member1 score2 member2
-
:傳回有序集合 key 中 member 成員的 score。zscore key member
-
:将有序集合 key 中的 member 加上 num,num 可以為負數。zincrby key num member
-
:傳回有序集合 key 中 score 值在 [min,max] 區間的 member 數量。zcount key min max
-
:傳回有序集合 key 中 score 從小到大排列後在 [start,stop] 區間的所有 member。zrange key start stop
-
:傳回有序集合 key 中 score 從大到小排列後在 [start,stop] 區間的所有 member。zrevrange key start stop
-
:傳回有序集合中按 score 從小到大排列後在 [min,max] 區間的所有元素。注意這裡預設是閉區間,但是可以在 max 和 min 的數值前面加上 zrangebyscore key min max
或者 (
來控制開閉區間。[
-
:傳回有序集合中按 score 從大到小排列後在 [min,max] 區間的所有元素。注意這裡預設是閉區間,但是可以在 max 和 min 的數值前面加上 zrevrangebyscore key max min
或者 (
來控制開閉區間。[
-
:傳回有序集合中 member 中元素排名(從小到大),傳回的結果從 0 開始計算。zrank key member
-
:傳回有序集合中 member 中元素排名(從大到小),傳回的結果從 0 開始計算。zrevrank key member
-
:傳回有序集合中 min 和 max 之間的 member 數量。注意這個指令中的 min 和 max 前面必須加 zlexcount key min max
或者 (
來控制開閉區間,特殊值 - 和 + 分别表示負無窮和正無窮。[
了解了操作有序集合對象的常用指令,我們就可以來驗證下前面提到的哈希對象的類型和編碼了,在測試之前為了防止其他 key 值的幹擾,我們先執行 flushall 指令清空 Redis 資料庫。
在執行指令之前,我們先把配置檔案中的參數
zset-max-ziplist-entries
修改為 2,然後重新開機 Redis 服務。
重新開機完成之後依次執行如下指令:
zadd name 1 zs 2 lisi //設定 2 個元素會使用 ziplist
type name //檢視類型
object encoding name //檢視編碼
zadd address 1 beijing 2 shanghai 3 guangzhou 4 shenzhen //設定4個元素則會使用 skiplist編碼
type address //檢視類型
object encoding address //檢視編碼
得到如下效果: