Redis學習（一）基礎資料結構

       Redis使用了6種簡單基礎資料結構（簡單動态字元串、連結清單、字典、跳躍表、整數集合、壓縮清單）分别組合實作了字元串（string）、散列（hash）、清單（list）、集合（set）和有序集合（sorted set）這五種類型的鍵的底層實作資料結構對象。

目錄

簡單動态字元串

連結清單

字典

跳躍表

整數集合

壓縮清單

簡單動态字元串

Redis 沒有直接使用 C 語言傳統的字元串表示（以空字元結尾的字元數組，以下簡稱 C 字元串）， 而是自己建構了一種名為簡單動态字元串（simple dynamic string，SDS）的抽象類型， 并将 SDS 用作 Redis 的預設字元串表示。

1、SDS定義

struct sdshdr {

    // 記錄 buf 數組中已使用位元組的數量
    // 等于 SDS 所儲存字元串的長度
    int len;

    // 記錄 buf 數組中未使用位元組的數量
    int free;

    // 位元組數組，用于儲存字元串
    char buf[];

};
           

• free

   屬性的值為   ， 表示這個 SDS 沒有配置設定任何未使用空間。

• len

   屬性的值為 

  5

   ， 表示這個 SDS 儲存了一個五位元組長的字元串。

• buf

   屬性是一個 

  char

   類型的數組， 數組的前五個位元組分别儲存了 

  'R'

   、 

  'e'

   、 

  'd'

   、 

  'i'

   、 

  's'

   五個字元， 而最後一個位元組則儲存了空字元 

  '\0'

   。

2、SDS緩沖區

為了杜絕緩沖區溢出， SDS采取記憶體重配置設定政策：當 SDS API 需要對 SDS 進行修改時， API 會先檢查 SDS 的空間是否滿足修改所需的要求， 如果不滿足的話， API 會自動将 SDS 的空間擴充至執行修改所需的大小， 然後才執行實際的修改操作。

但是記憶體重配置設定涉及複雜的算法， 并且可能需要執行系統調用， 是以通常是一個比較耗時的操作，SDS采用空間預配置設定和惰性空間釋放兩種政策來優化。

空間預配置設定

頻繁的重新配置設定記憶體會導緻性能的降低，是以Redis在對SDS進行空間擴充時， 程式不僅會為 SDS 配置設定修改所必須要的空間， 還會為 SDS 配置設定額外的未使用空間。

空間預配置設定通過 len(SDS所儲存字元串的長度)和free(buf 數組中未使用位元組的數量)來實作：

• 如果對 SDS 進行修改之後， SDS 的長度（也即是 

  len

   屬性的值）将小于 

  1 MB

   ， 那麼程式配置設定和 

  len

   屬性同樣大小的未使用空間， 這時 SDS 

  len

   屬性的值将和 

  free

   屬性的值相同。 舉個例子， 如果進行修改之後， SDS 的 

  len

   将變成 

  13

   位元組， 那麼程式也會配置設定 

  13

  位元組的未使用空間， SDS 的 

  buf

   數組的實際長度将變成 

  13 + 13 + 1 = 27

   位元組（額外的一位元組用于儲存空字元）。
• 如果對 SDS 進行修改之後， SDS 的長度将大于等于 

  1 MB

   ， 那麼程式會配置設定 

  1 MB

   的未使用空間。 舉個例子， 如果進行修改之後， SDS 的 

  len

   将變成 

  30 MB

   ， 那麼程式會配置設定 

  1 MB

   的未使用空間， SDS 的 

  buf

   數組的實際長度将為 

  30 MB + 1 MB + 1 byte

   。

在擴充 SDS 空間之前， SDS API 會先檢查未使用空間是否足夠， 如果足夠的話， API 就會直接使用未使用空間， 而無須執行記憶體重配置設定。

惰性空間釋放

惰性空間釋放用于優化 SDS 的字元串縮短操作： 當 SDS 的 API 需要縮短 SDS 儲存的字元串時， 程式并不立即使用記憶體重配置設定來回收縮短後多出來的位元組， 而是使用 

free

 屬性将這些位元組的數量記錄起來， 并等待将來使用。

SDS 并沒有釋放多出來的 

8

 位元組空間， 而是将這 

8

 位元組空間作為未使用空間free保留在了 SDS 裡面， 如果将來要對 SDS 進行增長操作的話， 這些未使用空間就可能會派上用場。

這樣操作将不需要執行記憶體重配置設定，提高了性能，而且 SDS 也提供了相應的 API ， 讓我們可以在有需要時， 真正地釋放 SDS 裡面的未使用空間， 是以不用擔心惰性空間釋放政策會造成記憶體浪費。

3、SDS API

函數	作用	時間複雜度
sdsnew	建立一個包含給定 C 字元串的 SDS 。	O(N) ，  N  為給定 C 字元串的長度。
sdsempty	建立一個不包含任何内容的空 SDS 。	O(1)
sdsfree	釋放給定的 SDS 。	O(1)
sdslen	傳回 SDS 的已使用空間位元組數。	這個值可以通過讀取 SDS 的  len  屬性來直接獲得， 複雜度為 O(1) 。
sdsavail	傳回 SDS 的未使用空間位元組數。	這個值可以通過讀取 SDS 的  free  屬性來直接獲得， 複雜度為 O(1) 。
sdsdup	建立一個給定 SDS 的副本（copy）。	O(N) ，  N  為給定 SDS 的長度。
sdsclear	清空 SDS 儲存的字元串内容。	因為惰性空間釋放政策，複雜度為 O(1) 。
sdscat	将給定 C 字元串拼接到 SDS 字元串的末尾。	O(N) ，  N  為被拼接 C 字元串的長度。
sdscatsds	将給定 SDS 字元串拼接到另一個 SDS 字元串的末尾。	O(N) ，  N  為被拼接 SDS 字元串的長度。
sdscpy	将給定的 C 字元串複制到 SDS 裡面， 覆寫 SDS 原有的字元串。	O(N) ，  N  為被複制 C 字元串的長度。
sdsgrowzero	用空字元将 SDS 擴充至給定長度。	O(N) ，  N  為擴充新增的位元組數。
sdsrange	保留 SDS 給定區間内的資料， 不在區間内的資料會被覆寫或清除。	O(N) ，  N  為被保留資料的位元組數。
sdstrim	接受一個 SDS 和一個 C 字元串作為參數， 從 SDS 左右兩端分别移除所有在 C 字元串中出現過的字元。	O(M*N) ，  M  為 SDS 的長度，  N  為給定 C 字元串的長度。
sdscmp	對比兩個 SDS 字元串是否相同。	O(N) ，  N  為兩個 SDS 中較短的那個 SDS 的長度。

4、總結

• Redis 隻會使用 C 字元串作為字面量， 在大多數情況下， Redis 使用 SDS （Simple Dynamic String，簡單動态字元串）作為字元串表示。
• 比起 C 字元串， SDS 具有以下優點：
  1. 常數複雜度擷取字元串長度。
  2. 杜絕緩沖區溢出。
  3. 減少修改字元串長度時所需的記憶體重配置設定次數。
  4. 二進制安全。
  5. 相容部分 C 字元串函數。

連結清單

typedef struct listNode {

    // 前置節點
    struct listNode *prev;

    // 後置節點
    struct listNode *next;

    // 節點的值
    void *value;

} listNode;
           

list對象統一對整個連結清單進行維護：

typedef struct list {

    // 表頭節點
    listNode *head;

    // 表尾節點
    listNode *tail;

    // 連結清單所包含的節點數量
    unsigned long len;

    // 節點值複制函數
    void *(*dup)(void *ptr);

    // 節點值釋放函數
    void (*free)(void *ptr);

    // 節點值對比函數
    int (*match)(void *ptr, void *key);

} list;
           

list

 結構為連結清單提供了表頭指針 

head

 、表尾指針 

tail

 ， 以及連結清單長度計數器 

len

 ， 而 

dup

 、 

free

 和 

match

 成員則是用于實作多态連結清單所需的類型特定函數：

• dup

   函數用于複制連結清單節點所儲存的值；

• free

   函數用于釋放連結清單節點所儲存的值；

• match

   函數則用于對比連結清單節點所儲存的值和另一個輸入值是否相等。

Redis 的連結清單實作的特性可以總結如下：

• 雙端： 連結清單節點帶有 

  prev

   和 

  next

   指針， 擷取某個節點的前置節點和後置節點的複雜度都是 O(1) 。
• 無環： 表頭節點的 

  prev

   指針和表尾節點的 

  next

   指針都指向 

  NULL

   ， 對連結清單的通路以 

  NULL

   為終點。
• 帶表頭指針和表尾指針： 通過 

  list

   結構的 

  head

   指針和 

  tail

   指針， 程式擷取連結清單的表頭節點和表尾節點的複雜度為 O(1) 。
• 帶連結清單長度計數器： 程式使用 

  list

   結構的 

  len

   屬性來對 

  list

   持有的連結清單節點進行計數， 程式擷取連結清單中節點數量的複雜度為 O(1)。
• 多态： 連結清單節點使用 

  void*

   指針來儲存節點值， 并且可以通過 

  list

   結構的 

  dup

   、 

  free

   、 

  match

   三個屬性為節點值設定類型特定函數， 是以連結清單可以用于儲存各種不同類型的值。

總結

• 連結清單被廣泛用于實作 Redis 的各種功能， 比如清單鍵， 釋出與訂閱， 慢查詢， 螢幕， 等等。
• 每個連結清單節點由一個 

  listNode

   結構來表示， 每個節點都有一個指向前置節點和後置節點的指針， 是以 Redis 的連結清單實作是雙端連結清單。
• 每個連結清單使用一個 

  list

   結構來表示， 這個結構帶有表頭節點指針、表尾節點指針、以及連結清單長度等資訊。
• 因為連結清單表頭節點的前置節點和表尾節點的後置節點都指向 

  NULL

   ， 是以 Redis 的連結清單實作是無環連結清單。
• 通過為連結清單設定不同的類型特定函數， Redis 的連結清單可以用于儲存各種不同類型的值。

字典

Redis 的字典使用哈希表作為底層實作， 一個哈希表裡面可以有多個哈希表節點， 每個哈希表節點儲存了字典中的一個鍵值對。

typedef struct dictht {

    // 哈希表數組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩碼，用于計算索引值
    // 總是等于 size - 1
    unsigned long sizemask;

    // 該哈希表已有節點的數量
    unsigned long used;

} dictht;

typedef struct dictEntry {

    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個哈希表節點，形成連結清單
    struct dictEntry *next;

} dictEntry;
           

table

 屬性是一個數組， 數組中的每個元素都是一個指向 

dictEntry

 結構的指針， 每個 

dictEntry

 結構儲存着一個鍵值對。

size

 屬性記錄了哈希表的大小， 也即是 

table

 數組的大小， 而 

used

 屬性則記錄了哈希表目前已有節點（鍵值對）的數量。

sizemask

 屬性的值總是等于 

size-1

 ， 這個屬性和哈希值一起決定一個鍵應該被放到 

table

 數組的哪個索引上面(與&操作)。

對于

哈希表節點 

dictEntry中

，

key

 屬性儲存着鍵值對中的鍵， 而 

v

 屬性則儲存着鍵值對中的值， 其中鍵值對的值可以是一個指針， 或者是一個 

uint64_t

 整數， 又或者是一個 

int64_t

 整數。

next

 屬性是指向另一個哈希表節點的指針， 這個指針可以将多個哈希值相同的鍵值對連接配接在一次， 以此來解決哈希沖突（collision）的問題。

Redis 中的字典由哈希表和一些字典屬性組成：

typedef struct dict {

    // 類型特定函數
    dictType *type;

    // 私有資料
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 當 rehash 不在進行時，值為 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;
           

type

 屬性和 

privdata

 屬性是針對不同類型的鍵值對， 為建立多态字典而設定的：

• type

   屬性是一個指向 

  dictType

   結構的指針， 每個 

  dictType

   結構儲存了一簇用于操作特定類型鍵值對的函數， Redis 會為用途不同的字典設定不同的類型特定函數。
• 而 

  privdata

   屬性則儲存了需要傳給那些類型特定函數的可選參數。

ht

 屬性是一個包含兩個項的數組，數組中的每個項都是一個 

dictht

 哈希表。一般情況下， 字典隻使用 

ht[0]

 哈希表， 

ht[1]

 哈希表隻會在對 

ht[0]

 哈希表進行 rehash 時使用。除了 

ht[1]

 之外， 另一個和 rehash 有關的屬性就是 

rehashidx

 ： 它記錄了 rehash 目前的進度， 如果目前沒有在進行 rehash ， 那麼它的值為 

-1

 。

雜湊演算法

# 使用字典設定的哈希函數，計算鍵 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 屬性和哈希值，計算出索引值
# 根據情況不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask; //sizemask等于ht哈希數組長度減1
           

Redis 的哈希表使用鍊位址法（separate chaining）來解決鍵沖突： 每個哈希表節點都有一個 

next

 指針， 多個哈希表節點可以用 

next

 指針構成一個單向連結清單，節點的插入采用的是頭插法，程式總是将新節點添加到連結清單的表頭位置。

rehash

擴充和收縮哈希表的工作可以通過執行 rehash （重新散列）操作來完成， Redis 對字典的哈希表執行 rehash 的步驟如下：

1. 為字典的 

   ht[1]

    哈希表配置設定空間， 這個哈希表的空間大小取決于要執行的操作， 以及 

   ht[0]

    目前包含的鍵值對數量 （也即是 

   ht[0].used

    屬性的值）：
   • 如果執行的是擴充操作， 那麼 

     ht[1]

      的大小為第一個大于等于 

     ht[0].used * 2

      的 2^n （想上取2^n整）；
   • 如果執行的是收縮操作， 那麼 

     ht[1]

      的大小為第一個大于等于 

     ht[0].used

      的 2^n 。
2. 将儲存在 

   ht[0]

    中的所有鍵值對 rehash 到 

   ht[1]

    上面： rehash 指的是重新計算鍵的哈希值和索引值， 然後将鍵值對放置到 

   ht[1]

    哈希表的指定位置上。
3. 當 

   ht[0]

    包含的所有鍵值對都遷移到了 

   ht[1]

    之後 （

   ht[0]

    變為空表）， 釋放 

   ht[0]

    ， 将 

   ht[1]

    設定為 

   ht[0]

    ， 并在 

   ht[1]

    新建立一個空白哈希表， 為下一次 rehash 做準備。

當以下條件中的任意一個被滿足時， 程式會自動開始對哈希表執行擴充操作：

1. 伺服器目前沒有在執行 BGSAVE 指令或者 BGREWRITEAOF 指令， 并且哈希表的負載因子大于等于 

   1

    ；
2. 伺服器目前正在執行 BGSAVE 指令或者 BGREWRITEAOF 指令， 并且哈希表的負載因子大于等于 

   5

    ；

其中哈希表的負載因子可以通過公式計算：

# 負載因子 = 哈希表已儲存節點數量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
           

根據 BGSAVE 指令或 BGREWRITEAOF 指令是否正在執行， 伺服器執行擴充操作所需的負載因子并不相同， 這是因為在執行 BGSAVE指令或 BGREWRITEAOF 指令的過程中，伺服器會提高執行擴充操作所需的負載因子， 進而盡可能地避免在子程序存在期間進行哈希表擴充操作，避免不必要的記憶體寫入操作，最大限度地節約記憶體。

另一方面， 當哈希表的負載因子小于 

0.1

 時， 程式自動開始對哈希表執行收縮操作。

漸進式rehash

 rehash 動作并不是一次性、集中式地完成的， 而是分多次、漸進式地完成的，因為一次性所有鍵值對全部 rehash 到 

ht[1]中時，

龐大的計算量可能會導緻伺服器在一段時間内停止服務。

以下是哈希表漸進式 rehash 的詳細步驟：

1. 為 

   ht[1]

    配置設定空間， 讓字典同時持有 

   ht[0]

    和 

   ht[1]

    兩個哈希表。
2. 在字典中維持一個索引計數器變量 

   rehashidx

    ， 并将它的值設定為   ， 表示 rehash 工作正式開始。
3. 在 rehash 進行期間， 每次對字典執行添加、删除、查找或者更新操作時， 程式除了執行指定的操作以外， 還會順帶将 

   ht[0]

    哈希表在 

   rehashidx

    索引上的所有鍵值對 rehash 到 

   ht[1]

    ， 當 rehash 工作完成之後， 程式将 

   rehashidx

    屬性的值增一。
4. 随着字典操作的不斷執行， 最終在某個時間點上， 

   ht[0]

    的所有鍵值對都會被 rehash 至 

   ht[1]

    ， 這時程式将 

   rehashidx

    屬性的值設為 

   -1

    ， 表示 rehash 操作已完成。

在進行漸進式 rehash 的過程中， 字典會同時使用 

ht[0]

 和 

ht[1]

 兩個哈希表， 是以在漸進式 rehash 進行期間， 字典的删除（delete）、查找（find）、更新（update）等操作會在兩個哈希表上進行： 比如說， 要在字典裡面查找一個鍵的話， 程式會先在 

ht[0]

裡面進行查找， 如果沒找到的話， 就會繼續到 

ht[1]

 裡面進行查找， 諸如此類。

另外， 在漸進式 rehash 執行期間， 新添加到字典的鍵值對一律會被儲存到 

ht[1]

 裡面， 而 

ht[0]

 則不再進行任何添加操作： 這一措施保證了 

ht[0]

 包含的鍵值對數量會隻減不增， 并随着 rehash 操作的執行而最終變成空表。

總結

• 字典被廣泛用于實作 Redis 的各種功能， 其中包括資料庫和哈希鍵。
• Redis 中的字典使用哈希表作為底層實作， 每個字典帶有兩個哈希表， 一個用于平時使用， 另一個僅在進行 rehash 時使用。
• 當字典被用作資料庫的底層實作， 或者哈希鍵的底層實作時， Redis 使用 MurmurHash2 算法來計算鍵的哈希值。
• 哈希表使用鍊位址法來解決鍵沖突， 被配置設定到同一個索引上的多個鍵值對會連接配接成一個單向連結清單。
• 在對哈希表進行擴充或者收縮操作時， 程式需要将現有哈希表包含的所有鍵值對 rehash 到新哈希表裡面， 并且這個 rehash 過程并不是一次性地完成的， 而是漸進式地完成的。

跳躍表

Redis 的跳躍表由

zskiplistNode

 和 

zskiplist

 兩個結構定義， 其中 

zskiplistNode

 結構用于表示跳躍表節點， 而 

zskiplist

 結構則用于儲存跳躍表節點的相關資訊， 比如節點的數量， 以及指向表頭節點和表尾節點的指針。 

跳躍表節點

typedef struct zskiplistNode {

    // 後退指針
    struct zskiplistNode *backward;

    // 分值
    double score;

    // 成員對象
    robj *obj;

    // 層
    struct zskiplistLevel {

        // 前進指針
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;
           

層

跳躍表節點的 

level

 數組可以包含多個元素， 每個元素都包含一個指向其他節點的指針， 程式可以通過這些層來加快通路其他節點的速度， 一般來說， 層的數量越多， 通路其他節點的速度就越快。

每次建立一個新跳躍表節點的時候， 程式都根據幂次定律 （越大的數出現的機率越小） 随機生成一個介于 

1

 和 

32

 之間的值作為 

level

 數組的大小， 這個大小就是層的“高度”。

前進指針

每個層都有一個指向表尾方向的前進指針（

level[i].forward

 屬性）， 用于從表頭向表尾方向通路節點。

跨度

層的跨度（

level[i].span

 屬性）用于記錄兩個節點之間的距離：

• 兩個節點之間的跨度越大， 它們相距得就越遠。
• 指向 

  NULL

   的所有前進指針的跨度都為   ， 因為它們沒有連向任何節點。

初看上去， 很容易以為跨度和周遊操作有關， 但實際上并不是這樣 —— 周遊操作隻使用前進指針就可以完成了， 跨度實際上是用來計算排位（rank）的： 在查找某個節點的過程中， 将沿途通路過的所有層的跨度累計起來， 得到的結果就是目标節點在跳躍表中的排位。

後退指針

節點的後退指針（

backward

 屬性）用于從表尾向表頭方向通路節點： 跟可以一次跳過多個節點的前進指針不同， 因為每個節點隻有一個後退指針， 是以每次隻能後退至前一個節點。

分值和成員

節點的分值（

score

 屬性）是一個 

double

 類型的浮點數， 跳躍表中的所有節點都按分值從小到大來排序。

節點的成員對象（

obj

 屬性）是一個指針， 它指向一個字元串對象， 而字元串對象則儲存着一個 SDS 值。

在同一個跳躍表中， 各個節點儲存的成員對象必須是唯一的， 但是多個節點儲存的分值卻可以是相同的： 分值相同的節點将按照成員對象在字典序中的大小來進行排序， 成員對象較小的節點會排在前面（靠近表頭的方向）， 而成員對象較大的節點則會排在後面（靠近表尾的方向）。

跳躍表

與連結清單一樣雖然僅靠多個跳躍表節點就可以組成一個跳躍表，但有一個跳躍表對象來維護這些節點可以更友善處理。

typedef struct zskiplist {

    // 表頭節點和表尾節點
    struct zskiplistNode *header, *tail;

    // 表中節點的數量
    unsigned long length;

    // 表中層數最大的節點的層數（不包括表頭節點）
    int level;

} zskiplist;
           

header

 和 

tail

 指針分别指向跳躍表的表頭和表尾節點， 通過這兩個指針， 程式定位表頭節點和表尾節點的複雜度為 O(1) 。

通過使用 

length

 屬性來記錄節點的數量， 程式可以在 O(1) 複雜度内傳回跳躍表的長度。

level

 屬性則用于在 O(1) 複雜度内擷取跳躍表中層高最大的那個節點的層數量， 注意表頭節點的層高并不計算在内。

總結

• 跳躍表是有序集合的底層實作之一， 除此之外它在 Redis 中沒有其他應用。
• Redis 的跳躍表實作由 

  zskiplist

   和 

  zskiplistNode

   兩個結構組成， 其中 

  zskiplist

   用于儲存跳躍表資訊（比如表頭節點、表尾節點、長度）， 而 

  zskiplistNode

   則用于表示跳躍表節點。
• 每個跳躍表節點的層高都是 

  1

   至 

  32

   之間的随機數。
• 在同一個跳躍表中， 多個節點可以包含相同的分值， 但每個節點的成員對象必須是唯一的。
• 跳躍表中的節點按照分值大小進行排序， 當分值相同時， 節點按照成員對象的大小進行排序。

整數集合

整數集合（intset）是集合鍵的底層實作之一： 當一個集合隻包含整數值元素， 并且這個集合的元素數量不多時， Redis 就會使用整數集合作為集合鍵的底層實作。

整數集合是 Redis 用于儲存整數值的集合抽象資料結構， 它可以儲存類型為 

int16_t

 、 

int32_t

 或者 

int64_t

 的整數值， 并且保證集合中不會出現重複元素。

typedef struct intset {

    // 編碼方式
    uint32_t encoding;

    // 集合包含的元素數量
    uint32_t length;

    // 儲存元素的數組
    int8_t contents[];

} intset;
           

contents

 數組是整數集合的底層實作： 整數集合的每個元素都是 

contents

 數組的一個數組項（item）， 各個項在數組中按值的大小從小到大有序地排列， 并且數組中不包含任何重複項。

length

 屬性記錄了整數集合包含的元素數量， 也即是 

contents

 數組的長度。

雖然 

intset

 結構将 

contents

 屬性聲明為 

int8_t

 類型的數組， 但實際上 

contents

 數組并不儲存任何 

int8_t

 類型的值 —— 

contents

 數組的真正類型取決于 

encoding

 屬性的值：

• 如果 

  encoding

   屬性的值為 

  INTSET_ENC_INT16

   ， 那麼 

  contents

   就是一個 

  int16_t

   類型的數組， 數組裡的每個項都是一個 

  int16_t

   類型的整數值 （最小值為 

  -32,768

   ，最大值為 

  32,767

   ）。
• 如果 

  encoding

   屬性的值為 

  INTSET_ENC_INT32

   ， 那麼 

  contents

   就是一個 

  int32_t

   類型的數組， 數組裡的每個項都是一個 

  int32_t

   類型的整數值 （最小值為 

  -2,147,483,648

   ，最大值為 

  2,147,483,647

   ）。
• 如果 

  encoding

   屬性的值為 

  INTSET_ENC_INT64

   ， 那麼 

  contents

   就是一個 

  int64_t

   類型的數組， 數組裡的每個項都是一個 

  int64_t

   類型的整數值 （最小值為 

  -9,223,372,036,854,775,808

   ，最大值為 

  9,223,372,036,854,775,807

   ）。

更新

每當我們要将一個新元素添加到整數集合裡面， 并且新元素的類型比整數集合現有所有元素的類型都要長時， 整數集合需要先進行更新（upgrade）， 然後才能将新元素添加到整數集合裡面。

更新整數集合并添加新元素共分為三步進行：

1. 根據新元素的類型， 擴充整數集合底層數組的空間大小， 并為新元素配置設定空間。
2. 将底層數組現有的所有元素都轉換成與新元素相同的類型， 并将類型轉換後的元素放置到正确的位上， 而且在放置元素的過程中， 需要繼續維持底層數組的有序性質不變。
3. 将新元素添加到底層數組裡面。

更新之後新元素的擺放位置

因為引發更新的新元素的長度總是比整數集合現有所有元素的長度都大， 是以這個新元素的值要麼就大于所有現有元素， 要麼就小于所有現有元素：

• 在新元素小于所有現有元素的情況下， 新元素會被放置在底層數組的最開頭（索引   ）；
• 在新元素大于所有現有元素的情況下， 新元素會被放置在底層數組的最末尾（索引 

  length-1

   ）。

整數集合的更新政策提升了整數集合的靈活性，且盡可能地節約記憶體。

另外，整數集合不支援降級操作， 一旦對數組進行了更新， 編碼就會一直保持更新後的狀态。

總結

• 整數集合是集合鍵的底層實作之一。
• 整數集合的底層實作為數組， 這個數組以有序、無重複的方式儲存集合元素， 在有需要時， 程式會根據新添加元素的類型， 改變這個數組的類型。
• 更新操作為整數集合帶來了操作上的靈活性， 并且盡可能地節約了記憶體。
• 整數集合隻支援更新操作， 不支援降級操作。

壓縮清單

壓縮清單（ziplist）是清單鍵和哈希鍵的底層實作之一。壓縮清單是 Redis 為了節約記憶體而開發的， 由一系列特殊編碼的連續記憶體塊組成的順序型（sequential）資料結構。

一個壓縮清單可以包含任意多個節點（entry）， 每個節點可以儲存一個位元組數組或者一個整數值。

屬性	類型	長度	用途
zlbytes	uint32_t	4  位元組	記錄整個壓縮清單占用的記憶體位元組數：在對壓縮清單進行記憶體重配置設定， 或者計算  zlend 的位置時使用。
zltail	uint32_t	4  位元組	記錄壓縮清單表尾節點距離壓縮清單的起始位址有多少位元組： 通過這個偏移量，程式無須周遊整個壓縮清單就可以确定表尾節點的位址。
zllen	uint16_t	2  位元組	記錄了壓縮清單包含的節點數量： 當這個屬性的值小于  UINT16_MAX  （ 65535 ）時， 這個屬性的值就是壓縮清單包含節點的數量； 當這個值等于  UINT16_MAX  時， 節點的真實數量需要周遊整個壓縮清單才能計算得出。
entryX	清單節點	不定	壓縮清單包含的各個節點，節點的長度由節點儲存的内容決定。
zlend	uint8_t	1  位元組	特殊值  0xFF  （十進制  255  ），用于标記壓縮清單的末端。

節點構成

每個壓縮清單節點可以儲存一個位元組數組或者一個整數值，每個節點都由 

previous_entry_length

 、 

encoding

 、 

content

 三個部分組成。

previous_entry_length

節點的 

previous_entry_length

 屬性以位元組為機關， 記錄了壓縮清單中前一個節點的長度。

previous_entry_length

 屬性的長度可以是 

1

 位元組或者 

5

 位元組：

• 如果前一節點的長度小于 

  254

   位元組， 那麼 

  previous_entry_length

   屬性的長度為 

  1

   位元組： 前一節點的長度就儲存在這一個位元組裡面。
• 如果前一節點的長度大于等于 

  254

   位元組， 那麼 

  previous_entry_length

   屬性的長度為 

  5

   位元組： 其中屬性的第一位元組會被設定為 

  0xFE

   （十進制值 

  254

  ）， 而之後的四個位元組則用于儲存前一節點的長度。

因為節點的 

previous_entry_length

 屬性記錄了前一個節點的長度， 是以程式可以通過指針運算， 根據目前節點的起始位址來計算出前一個節點的起始位址，壓縮清單的從表尾向表頭周遊操作就是使用這一原理實作。

encoding

節點的 

encoding

 屬性記錄了節點的 

content

 屬性所儲存資料的類型以及長度：

• 一位元組、兩位元組或者五位元組長， 值的最高位為 

  00

   、 

  01

   或者 

  10

   的是位元組數組編碼： 這種編碼表示節點的 

  content

   屬性儲存着位元組數組， 數組的長度由編碼除去最高兩位之後的其他位記錄；
• 一位元組長， 值的最高位以 

  11

   開頭的是整數編碼： 這種編碼表示節點的 

  content

   屬性儲存着整數值， 整數值的類型和長度由編碼除去最高兩位之後的其他位記錄；

content

節點的 

content

 屬性負責儲存節點的值， 節點值可以是一個位元組數組或者整數， 值的類型和長度由節點的 

encoding

 屬性決定。

• 編碼的最高兩位 

  00

   表示節點儲存的是一個位元組數組；
• 編碼的後六位 

  001011

   記錄了位元組數組的長度 

  11

   ；

• content

   屬性儲存着節點的值 

  "hello world"

   。

連鎖更新

 由于每個節點的 

previous_entry_length

 屬性都記錄了前一個節點的長度，且

previous_entry_length

 的長度可以是1位元組或5位元組，那麼存在這樣一種情況：在一個壓縮清單中，有多個連續的長度介于 

250

 位元組到 

253

 位元組之間的節點 

e1

 至 

eN

 。

因為 

e1

 至 

eN

 的所有節點的長度都小于 

254

 位元組， 是以記錄這些節點的長度隻需要 

1

 位元組長的 

previous_entry_length

 屬性， 換句話說， 

e1

 至 

eN

 的所有節點的 

previous_entry_length

 屬性都是 

1

 位元組長的。

這時， 如果我們将一個長度大于等于 

254

 位元組的新節點 

new

 設定為壓縮清單的表頭節點， 那麼 

new

 将成為 

e1

 的前置節點，又因 

e1

 的 

previous_entry_length

 屬性僅長 

1

 位元組， 它沒辦法儲存新節點 

new

 的長度，是以程式将對壓縮清單執行空間重配置設定操作， 并将 

e1

節點的 

previous_entry_length

 屬性從原來的 

1

 位元組長擴充為 

5

 位元組長。

這會導緻，

e1的長度超過253位元組

（

e1

原本的長度介于 

250

 位元組至 

253

 位元組之間），e2為了記錄下 

e1

 的長度，也會發生同樣的問題，最終為了讓每個節點的 

previous_entry_length

 屬性都符合壓縮清單對節點的要求，程式需要不斷地對壓縮清單執行空間重配置設定操作，直到 

eN

 為止。Redis 将這種在特殊情況下産生的連續多次空間擴充操作稱之為“連鎖更新”（cascade update）。

因為連鎖更新在最壞情況下需要對壓縮清單執行 

N

 次空間重配置設定操作， 而每次空間重配置設定的最壞複雜度為 O(N) ， 是以連鎖更新的最壞複雜度為 O(N^2) 。

要注意的是， 盡管連鎖更新的複雜度較高， 但它真正造成性能問題的幾率是很低的：

• 首先， 壓縮清單裡要恰好有多個連續的、長度介于 

  250

   位元組至 

  253

   位元組之間的節點， 連鎖更新才有可能被引發， 在實際中， 這種情況并不多見；
• 其次， 即使出現連鎖更新， 但隻要被更新的節點數量不多， 就不會對性能造成任何影響： 比如說， 對三五個節點進行連鎖更新是絕對不會影響性能的；

總結

• 壓縮清單是一種為節約記憶體而開發的順序型資料結構。
• 壓縮清單被用作清單鍵和哈希鍵的底層實作之一。
• 壓縮清單可以包含多個節點，每個節點可以儲存一個位元組數組或者整數值。
• 添加新節點到壓縮清單， 或者從壓縮清單中删除節點， 可能會引發連鎖更新操作， 但這種操作出現的幾率并不高。

參考文章：

《Redis設計與實作》

  http://redisbook.com/