【Redis系列5】Redis(有序)集合對象之intset(整數集合)和skiplist(跳躍表)實作原理分析

Redis集合對象之intset和skiplist實作原理分析

• 前言
• 集合對象
• • intset編碼
  • • encoding
    • contents[]
    • 整數集合的更新
    • 更新舉例
  • hashtable編碼
  • intset和hashtable編碼轉換
• 有序集合對象
• • skiplist編碼
  • • 跳躍表
    • • skiplist的存儲結構
    • 為什麼同時選擇使用字典和跳躍表
  • ziplist編碼
  • ziplist和skiplist編碼轉換
• 總結

前言

上一篇我們分析了清單對象的底層存儲結構

linkedlist

，

ziplist

和

quicklist

的實作原理，并将這三種資料結構進行了分析對比。這一篇我們繼續分析Redis中5種常用資料類型的第3種基本資料類型

哈希對象

的底層存儲結構。

集合對象

集合對象的底層資料結構有兩種：

intset

和

hashtable

。内部通過編碼來進行區分：

編碼屬性	描述	object encoding指令傳回值
OBJ_ENCODING_INTSET	使用整數集合實作的集合對象	intset
OBJ_ENCODING_HT	使用字典實作的集合對象	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

encoding

記錄了目前集合的編碼方式，主要有三種：

• INTSET_ENC_INT16

  此時

  contents[]

  内的每個元素都是一個

  int16_t

  類型的整數值，範圍是：-32768 ~ 32767(-215 ~ 215-1)

• INTSET_ENC_INT32

  此時

  contents[]

  内的每個元素都是一個

  int32_t

  類型的整數值，範圍是：-2147483648 ~ 2147483647(-231 ~ 231-1)

• INTSET_ENC_INT64

  此時

  contents[]

  内的每個元素都是一個

  int64_t

  類型的整數值，範圍是：-9223372036854775808 ~ 9223372036854775807(-263 ~ 263-1)

contents[]

contents[]

雖然結構的定義上寫的是

int8_t

類型，但是實際存儲類型是由上面的

encoding

來決定的。

整數集合的更新

假如一開始整數集合中的元素都是16位的，采用了

int16_t

類型來存儲，此時需要再存儲一個32位的整數，那麼就需要對原先的整數集合進行更新，更新之後才能将32位的整數放入整數集合内。

更新主要有4個步驟：

• 1、根據新添加元素的類型來擴充底層數組空間的大小，按照更新後現有元素的位數來配置設定新的空間。
• 2、将現有的元素進行類型轉換，并将轉換類型後的元素從後到前逐個重新放回到數組内。
• 3、将新元素放到數組的頭部或者尾部（因為觸發更新的條件就是目前數組的整數類型無法存儲新元素，是以新元素要麼比現有元素都大，要麼就比現有元素都小）。
• 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

編碼：

• 1、集合對象儲存的所有元素都是整數值。
• 2、集合對象儲存的元素數量小于等于512個(這個門檻值可以通過配置檔案

  set-max-intset-entries

  來控制)。

  一旦集合中的元素不滿足上面兩個條件，則會選擇使用

  hashtable

  編碼。

有序集合對象

有序集合對象的底層資料結構有兩種：

skiplist

和

ziplist

。内部同樣是通過編碼來進行區分：

編碼屬性	描述	object encoding指令傳回值
OBJ_ENCODING_SKIPLIST	使用跳躍表實作的有序集合對象	skiplist
OBJ_ENCODING_ZIPLIST	使用壓縮清單實作的有序集合對象	ziplist

skiplist編碼

skiplist

即跳躍表，有時候也簡稱為跳表，使用

skiplist

編碼的有序集合對象使用了

zset

結構來作為底層實作，而

zset

中同時包含了一個字典和一個跳躍表。

跳躍表

跳躍表是一種有序的資料結構，其主要特點是通過在每個節點中維持多個指向其他節點的指針，進而達到快速通路節點的目的。

大部分情況下，跳躍表的效率可以等同于平衡樹，但是跳躍表的實作卻遠遠比平衡樹的實作簡單，是以Redis選擇了使用跳躍表來實作有序集合。

下圖是一個普通的有序連結清單，我們如果要找17，隻能從頭開始周遊到尾(連結清單中元素不支援随機通路，是以不能用二分查找，而數組中可以通過下标随機通路，是以二分查找一般适用于有序數組)，時間複雜度是O(n)。

那麼假如我們可以直接跳到連結清單的中間，那就可以節省很多資源了，這就是跳表的原理，如下圖所示就是一個跳表的資料結構示例：

上圖中level1，level2，level3就是跳表的層級，每一個level層級都有一個指向下一個相同level層級元素的指針，比如上圖我們周遊尋找元素35的時候就有三種方案：

• 第1種就是執行level1層級的指針，需要周遊7次才能找到元素35。
• 第2種就是執行level2層級的指針，隻需要周遊5次就能找到元素35。
• 第3種就是執行level3層級的元素，這時候隻需要周遊3次就能找到元素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對象(早起版本使用的是robj對象)，元素必須唯一不能重複

• 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就是對應了有序集合中的元素(memer)，value就對應了分值(score)。

下圖中的跳躍表整數1,8,9,12也是對應了元素(memer)，最後一排的double型數字就是分值(score)。

也就是說字典和跳躍表中的資料都指向了我們存儲的元素(兩種資料結構最終指向的是同一份數，是以資料并不會出現備援存儲)，Redis為什麼要這麼做呢？

為什麼同時選擇使用字典和跳躍表

有序集合直接使用跳躍表或者單獨使用字典完全可以獨自實作，但是我們想一下，如果單獨使用跳躍表來實作，那麼雖然可以使用跨度大的指針去周遊元素來找到我們需要的資料，但是其複雜度仍然達到了O(logN)，而字典中擷取一個元素的複雜度是O(1)，而如果單獨使用字典雖然擷取元素很快，但是字典是無序的，是以如果要範圍查找就需要對其進行排序，這又是一個耗時的操作，是以Redis綜合了兩種資料結構來最大程度的提升性能。

ziplist編碼

壓縮清單在清單對象和哈希對象都有使用到，想詳細了解的可以點選這裡。

ziplist和skiplist編碼轉換

當有序集合對象同時滿足以下兩個條件時，會使用

ziplist

編碼進行存儲：

• 1、有序集合對象中儲存的元素個數小于128個（可以通過配置

  zset-max-ziplist-entries

  修改）。
• 2、有序集合對象中儲存的所有元素的總長度小于64位元組（可以通過配置

  zset-max-ziplist-value

  修改）。

總結

本文主要分析了集合對象和有序集合對象的底層存儲結構

intset

和

skiplist

的實作原理，并且重點分析了有序集合如何實作排序以及為何同時使用兩種資料結構進行存儲的原因。