一文讀懂 Redis 常見物件型別的底層資料結構

轉自：伍陸七，

連結：cnblogs.com/chentianming/p/13838347.htm

Redis 是一個基於記憶體中的資料結構儲存系統，可以用作資料庫、快取和訊息中介軟體。Redis 支援五種常見物件型別：字串（String）、雜湊（Hash）、列表（List）、集合（Set）以及有序集合（Zset），我們在日常工作中也會經常使用它們。知其然，更要知其所以然，本文將會帶你讀懂這五種常見物件型別的底層資料結構。

本文主要內容參考自《Redis設計與實現》

1. 物件型別和編碼

Redis 使用物件來儲存鍵和值的，在Redis中，每個物件都由 redisObject 結構表示。redisObject 結構主要包含三個屬性：type、encoding 和 ptr。

typedef struct redisObject {
    // 型別
    unsigned type:4;
    // 編碼
    unsigned encoding:4;
    // 底層資料結構的指標
    void *ptr;
} robj;

其中 type 屬性記錄了物件的型別。對於 Redis 來說，鍵物件總是字串型別，值物件可以是任意支援的型別。因此，當我們說 Redis 鍵採用哪種物件型別的時候，指的是對應的值採用哪種物件型別。

*ptr 屬性指向了物件的底層資料結構，而這些資料結構由 encoding 屬性決定。

之所以由 encoding 屬性來決定物件的底層資料結構，是為了實現同一物件型別，支援不同的底層實現。這樣就能在不同場景下，使用不同的底層資料結構，進而極大提升Redis的靈活性和效率。

底層資料結構後面會詳細講解，這裡簡單看一下即可。

2. 字串物件

字串是我們日常工作中用得最多的物件型別，它對應的編碼可以是 int、raw 和 embstr。字串物件相關命令可參考：Redis命令-Strings。

如果一個字串物件儲存的是不超過 long 型別的整數值，此時編碼型別即為 int，其底層資料結構直接就是 long 型別。例如執行 set number 10086，就會建立 int 編碼的字串物件作為 number 鍵的值。

如果字串物件儲存的是一個長度大於 39 位元組的字串，此時編碼型別即為 raw，其底層資料結構是簡單動態字串（SDS）；如果長度小於等於 39 個位元組，編碼型別則為 embstr，底層資料結構就是 embstr 編碼 SDS。下面，我們詳細理解下什麼是簡單動態字串。

2.1 簡單動態字串

SDS 定義

在 Redis 中，使用 sdshdr 資料結構表示 SDS：

struct sdshdr {
    // 字串長度
    int len;
    // buf陣列中未使用的位元組數
    int free;
    // 位元組陣列，用於儲存字串
    char buf[];
};

SDS 遵循了 C 字串以空字元結尾的慣例，儲存空字元的 1 位元組不會計算在 len 屬性裡面。例如，Redis 這個字串在 SDS 裡面的資料可能是如下形式：

SDS 與 C 字串的區別

C 語言使用長度為 N+1 的字元陣列來表示長度為N的字串，並且字串的最後一個元素是空字元 \0。Redis 採用 SDS 相對於 C 字串有如下幾個優勢：

1. 常數複雜度獲取字串長度；

2. 杜絕緩衝區溢位；

3. 減少修改字串時帶來的記憶體重分配次數；

4. 二進位制安全。

常數複雜度獲取字串長度

因為 C 字串並不記錄自身的長度資訊，所以為了獲取字串的長度，必須遍歷整個字串，時間複雜度是  O(N )。而 SDS 使用 len 屬性記錄了字串的長度，因此獲取 SDS字串長度的時間複雜度是  O(1) 。

杜絕緩衝區溢位

C 字串不記錄自身長度帶來的另一個問題是， 很容易造成快取區溢位 。比如使用字串拼接函式（stract）的時候，很容易覆蓋掉字元陣列原有的資料。

與 C 字串不同，SDS 的空間分配策略完全杜絕了發生快取區溢位的可能性。當 SDS 進行字串擴充時，首先會檢查當前的位元組陣列的長度是否足夠。如果不夠的話，會先進行自動擴容，然後再進行字串操作。

減少修改字串時帶來的記憶體重分配次數

因為 C 字串的長度和底層資料是緊密關聯的，所以每次增長或者縮短一個字串，程式都要對這個陣列進行一次記憶體重分配：

• 如果是增長字串操作，需要先通過記憶體重分配來擴充套件底層陣列空間大小，不這麼做就導致快取區溢位；

• 如果是縮短字串操作，需要先通過記憶體重分配來來回收不再使用的空間，不這麼做就導致記憶體洩漏。

因為記憶體重分配涉及複雜的演算法，並且可能需要執行系統呼叫，所以通常是個比較耗時的操作。對於 Redis 來說，字串修改是一個十分頻繁的操作。如果每次都像 C 字串那樣進行記憶體重分配，對效能影響太大了，顯然是無法接受的。

SDS 通過空閒空間解除了字串長度和底層資料之間的關聯。在 SDS 中，陣列中可以包含未使用的位元組，這些位元組數量由 free 屬性記錄。 通過空閒空間，SDS 實現了空間預分配和惰性空間釋放兩種優化策略 。

1.  空間預分配

空間預分配是用於優化 SDS 字串增長操作的，簡單來說就是當位元組陣列空間不足觸發重分配的時候，總是會預留一部分空閒空間。這樣的話，就能減少連續執行字串增長操作時的記憶體重分配次數。

有兩種預分配的策略：

• len 小於 1MB 時：每次重分配時會多分配同樣大小的空閒空間；
  

• len 大於等於 1MB 時：每次重分配時會多分配 1MB 大小的空閒空間。
  

2. 惰性空間釋放

惰性空間釋放是用於優化 SDS 字串縮短操作的。簡單來說就是當字串縮短時，並不立即使用記憶體重分配來回收多出來的位元組，而是用 free 屬性記錄，等待將來使用。SDS 也提供直接釋放未使用空間的 API，在需要的時候，也能真正的釋放掉多餘的空間。

二進位制安全

C 字串中的字元必須符合某種編碼，並且除了字串末尾之外，其它位置不允許出現空字元。這些限制使得 C 字串只能儲存文字資料。

但是對於 Redis 來說，不僅僅需要儲存文字，還要支援儲存二進位制資料。為了實現這一目標，SDS 的 API 全部做到了二進位制安全（binary-safe）。

2.2 raw 和 embstr 編碼的 SDS 區別

我們在前面講過，長度大於 39 位元組的字串，編碼型別為 raw，底層資料結構是簡單動態字串（SDS）。這個很好理解，比如當我們執行 set story "Long, long, long ago there lived a king ..."（長度大於39）之後，Redis 就會建立一個 raw 編碼的 String 物件。

資料結構如下：

長度小於等於 39 個位元組的字串，編碼型別為 embstr，底層資料結構則是 embstr 編碼 SDS。embstr 編碼是專門用來儲存短字串的，它和 raw 編碼最大的不同在於：raw 編碼會呼叫兩次記憶體分配分別建立 redisObject 結構和 sdshdr 結構；而 embstr 編碼則是隻呼叫一次記憶體分配，在一塊連續的空間上同時包含 redisObject 結構和 sdshdr 結構。

2.3 編碼轉換

int 編碼和 embstr 編碼的字串物件在條件滿足的情況下會自動轉換為 raw 編碼的字串物件。

對於 int 編碼來說，當我們修改這個字串為不再是整數值的時候，此時字串物件的編碼就會從 int 變為 raw。

對於 embstr 編碼來說，只要我們修改了字串的值，此時字串物件的編碼就會從 embstr 變為 raw。

embstr 編碼的字串物件可以認為是隻讀的，因為 Redis 為其編寫任何修改程式。當我們要修改 embstr 編碼字串時，都是先將轉換為 raw 編碼，然後再進行修改。

3. 列表物件

列表物件的編碼可以是 linkedlist 或者 ziplist，對應的底層資料結構是連結串列和壓縮列表。列表物件相關命令可參考： Redis 命令-List 。

預設情況下，當列表物件儲存的所有字串元素的長度都小於 64 位元組，且元素個數小於 512 個時，列表物件採用的是 ziplist 編碼，否則使用 linkedlist 編碼。

可以通過配置檔案修改該上限值。

3.1 連結串列

連結串列是一種非常常見的資料結構，提供了高效的節點重排能力以及順序性的節點訪問方式。在 Redis 中，每個連結串列節點使用 listNode 結構表示：

typedef struct listNode {
    // 前置節點
    struct listNode *prev;
    // 後置節點
    struct listNode *next;
    // 節點值
    void *value;
} listNode

多個 listNode 通過 prev 和 next 指標組成雙端連結串列，如下圖所示：

為了操作起來比較方便，Redis 使用了 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 成員則是實現多型連結串列所需型別的特定函式。

Redis 連結串列實現的特徵總結如下：

1. 雙端 ：連結串列節點帶有 prev 和 next 指標，獲取某個節點的前置節點和後置節點的複雜度都是  O(n) ；

2. 無環 ：表頭節點的 prev 指標和表尾節點的 next 指標都指向 NULL，對連結串列的訪問以 NULL 為終點；

3. 帶表頭指標和表尾指標 ：通過 list 結構的 head 指標和 tail 指標，程式獲取連結串列的表頭節點和表尾節點的複雜度為  O(1) ；

4. 帶連結串列長度計數器 ：程式使用 list 結構的 len 屬性來對 list 持有的節點進行計數，程式獲取連結串列中節點數量的複雜度為  O(1) ；

5. 多型 ：連結串列節點使用 void* 指標來儲存節點值，可以儲存各種不同型別的值。

3.2 壓縮列表

壓縮列表（ziplist）是列表鍵和雜湊鍵的底層實現之一。壓縮列表主要目的是為了節約記憶體，是由一系列特殊編碼的連續記憶體塊組成的順序型資料結構。一個壓縮列表可以包含任意多個節點，每個節點可以儲存一個位元組陣列或者一個整數值。

如上圖所示，壓縮列表記錄了各組成部分的型別、長度以及用途。

4. 雜湊物件

雜湊物件的編碼可以是 ziplist 或者 hashtable。

4.1 hash-ziplist

ziplist 底層使用的是壓縮列表實現，上文已經詳細介紹了壓縮列表的實現原理。每當有新的鍵值對要加入雜湊物件時，先把儲存了鍵的節點推入壓縮列表表尾，然後再將儲存了值的節點推入壓縮列表表尾。比如，我們執行如下三條 HSET 命令：

HSET profile name "tom"
HSET profile age 25
HSET profile career "Programmer"

如果此時使用 ziplist 編碼，那麼該 Hash 物件在記憶體中的結構如下：

3.2 hash-hashtable

hashtable 編碼的雜湊物件使用字典作為底層實現。字典是一種用於儲存鍵值對的資料結構，Redis 的字典使用雜湊表作為底層實現，一個雜湊表裡面可以有多個雜湊表節點，每個雜湊表節點儲存的就是一個鍵值對。

3.3 雜湊表

Redis 使用的雜湊表由 dictht 結構定義：

typedef struct dictht{
    // 雜湊表陣列
    dictEntry **table;


    // 雜湊表大小
    unsigned long size;


    // 雜湊表大小掩碼，用於計算索引值
    // 總是等於 size-1
    unsigned long sizemask;


    // 該雜湊表已有節點數量
    unsigned long used;
} dictht

table 屬性是一個數組，陣列中的每個元素都是一個指向 dictEntry 結構的指標，每個 dictEntry 結構儲存著一個鍵值對。

size 屬性記錄了雜湊表的大小，即 table 陣列的大小。used 屬性記錄了雜湊表目前已有節點數量。sizemask 總是等於 size-1，這個值主要用於陣列索引。

比如下圖展示了一個大小為 4 的空雜湊表。

雜湊表節點

雜湊表節點使用 dictEntry 結構表示，每個 dictEntry 結構都儲存著一個鍵值對：

typedef struct dictEntry {
    // 鍵
    void *key;


    // 值
    union {
        void *val;
        unit64_t u64;
        nit64_t s64;
    } v;


    // 指向下一個雜湊表節點，形成連結串列
    struct dictEntry *next;
} dictEntry;

key 屬性儲存著鍵值對中的鍵，而 v 屬性則儲存了鍵值對中的值。值可以是一個指標，一個 uint64_t 整數或者是 int64_t 整數。next 屬性指向了另一個 dictEntry 節點，在陣列桶位相同的情況下，將多個 dictEntry 節點串聯成一個連結串列，以此來解決鍵衝突問題（鏈地址法）。

3.4 字典

Redis 字典由 dict 結構表示：

typedef struct dict {
    // 型別特定函式
    dictType *type;


    // 私有資料
    void *privdata;


    // 雜湊表
    dictht ht[2];


    //rehash索引
    // 當rehash不在進行時，值為-1
    int rehashidx;
}

ht 是大小為 2，且每個元素都指向 dictht 雜湊表。一般情況下，字典只會使用 ht[0] 雜湊表，ht[1] 雜湊表只會在對 ht[0] 雜湊表進行 rehash 時使用。rehashidx 記錄了 rehash 的進度，如果目前沒有進行 rehash，值為 -1。

rehash

為了使 hash 表的負載因子 (ht[0]).used/ht[0]).size) 維持在一個合理範圍，當雜湊表儲存的元素過多或者過少時，程式需要對 hash 表進行相應的擴充套件和收縮。

rehash（重新雜湊）操作就是用來完成 hash 表的擴充套件和收縮的。

rehash 的步驟如下：

1. 為 ht [1] 雜湊表分配空間；

• 如果是 擴充套件操作 ，那麼 ht[1] 的大小為第一個大於 ht[0].used*2的2n。比如ht[0].used=5，那麼此時 ht[1] 的大小就為 16（大於 10 的第一個 2n 的值是 16）；
  

• 如果是 收縮操作 ，那麼 ht[1] 的大小為第一個大於 ht[0].used 的 2n。比如ht[0].used=5，那麼此時 ht[1] 的大小就為 8（大於 5 的第一個 2n 的值是 8）。
  

2. 將儲存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 中；

3. 遷移完成之後，釋放掉 ht[0]，並將現在的 ht[1] 設定為 ht[0]，在 ht[1] 新建立一個空白雜湊表，為下一次 rehash 做準備。

雜湊表的擴充套件和收縮時機

• 當伺服器沒有執行 BGSAVE 或者 BGREWRITEAOF 命令時，負載因子大於等於 1 觸發雜湊表的擴充套件操作；

• 當伺服器在執行 BGSAVE 或者 BGREWRITEAOF 命令，負載因子大於等於 5 觸發雜湊表的擴充套件操作；

• 當雜湊表負載因子小於 0.1，觸發雜湊表的收縮操作。

漸進式 rehash

前面講過，擴充套件或者收縮需要將 ht[0] 裡面的元素全部 rehash 到 ht[1] 中，如果 ht[0] 元素很多，顯然一次性 rehash 成本會很大，從影響到 Redis 效能。

為了解決上述問題，Redis 使用了漸進式 rehash 技術，具體來說就是分多次，漸進式地將 ht[0] 裡面的元素慢慢地 rehash 到 ht[1] 中。

下面是漸進式 rehash 的詳細步驟：

1. 為 ht[1] 分配空間；

2. 在字典中維持一個索引計數器變數 rehashidx，並將它的值設定為 0，表示 rehash 正式開始；

3. 在 rehash 進行期間，每次對字典執行新增、刪除、查詢或者更新時，除了會執行相應的操作之外，還會順帶將 ht[0] 在 rehashidx 索引位上的所有鍵值對 rehash 到 ht[1] 中，rehash 完成之後，rehashidx 值加 1；

4. 隨著字典操作的不斷進行，最終會在啊某個時刻遷移完成，此時將 rehashidx 值置為 -1，表示 rehash 結束。

漸進式 rehash 一次遷移一個桶上所有的資料 。設計上採用 分而治之 的思想， 將原本集中式的操作分散到每個新增、刪除、查詢和更新操作上 ，從而避免集中式 rehash 帶來的龐大計算。

因為在漸進式 rehash 時，字典會同時使用 ht[0] 和 ht[1] 兩張表，所以此時對字典的刪除、查詢和更新操作都可能會在兩個雜湊表進行。比如，如果要查詢某個鍵時，先在 ht[0] 中查詢，如果沒找到，則繼續到 ht[1] 中查詢。

hash 物件中的 hashtable

HSET profile name "tom"
HSET profile age 25
HSET profile career "Programmer"

還是上述三條命令，儲存資料到 Redis 的雜湊物件中，如果採用 hashtable 編碼儲存的話，那麼該 Hash 物件在記憶體中的結構如下：

當雜湊物件儲存的所有鍵值對的鍵和值的字串長度都小於 64 個位元組，並且數量小於 512 個時，使用 ziplist 編碼，否則使用 hashtable 編碼。

可以通過配置檔案修改該上限值。

4. 集合物件

集合物件的編碼可以是 intset 或者 hashtable。當集合物件儲存的元素都是整數，並且個數不超過 512 個時，使用 intset 編碼，否則使用 hashtable 編碼。

4.1 set-intset

intset 編碼的集合物件底層使用整數集合實現。

整數集合（intset）是 Redis 用於儲存整數值的集合抽象資料結構，它可以儲存型別為 int16_t、int32_t 或者 int64_t 的整數值，並且保證集合中的資料不會重複。Redis 使用 intset 結構表示一個整數集合。

typedef struct intset {
    // 編碼方式
    uint32_t encoding;
    // 集合包含的元素數量
    uint32_t length;
    // 儲存元素的陣列
    int8_t contents[];
} intset;

contents 陣列是整數集合的底層實現：整數集合的每個元素都是 contents 陣列的一個數組項，各個項在陣列中按值大小從小到大有序排列，並且陣列中不包含重複項。

雖然 contents 屬性宣告為 int8_t 型別的陣列，但實際上，contents 陣列不儲存任何 int8_t 型別的值，陣列中真正儲存的值型別取決於 encoding。

如果 encoding 屬性值為 INTSET_ENC_INT16，那麼 contents 陣列就是 int16_t 型別的陣列，以此類推。

當新插入元素的型別比整數集合現有型別元素的型別大時，整數集合必須先升級，然後才能將新元素新增進來。這個過程分以下三步進行：

1. 根據新元素型別，擴充套件整數集合底層陣列空間大小；

2. 將底層陣列現有所有元素都轉換為與新元素相同的型別，並且維持底層陣列的有序性；

3. 將新元素新增到底層數組裡面。

還有一點需要注意的是， 整數集合不支援降級 。一旦對陣列進行了升級，編碼就會一直保持升級後的狀態。

舉個例子，當執行 SADD numbers 1 3 5 向集合物件插入資料時，該集合物件在記憶體的結構如下：

4.2 set-hashtable

hashtable 編碼的集合物件使用字典作為底層實現。字典的每個鍵都是一個字串物件，每個字串物件對應一個集合元素，字典的值都是 NULL。

當我們執行 SADD fruits "apple" "banana" "cherry" 向集合物件插入資料時，該集合物件在記憶體的結構如下：

5. 有序集合物件

有序集合的編碼可以是 ziplist 或者 skiplist。當有序集合儲存的元素個數小於 128 個，且所有元素成員長度都小於 64 位元組時，使用 ziplist 編碼，否則使用 skiplist 編碼。

5.1 zset-ziplist

ziplist 編碼的有序集合使用壓縮列表作為底層實現。每個集合元素使用兩個緊挨著一起的兩個壓縮列表節點表示，第一個節點儲存元素的成員（member），第二個節點儲存元素的分值（score）。

壓縮列表內的集合元素按照分值從小到大排列。如果我們執行 ZADD price 8.5 apple 5.0 banana 6.0 cherry 命令向有序集合插入元素，該有序集合在記憶體中的結構如下：

5.2 zset-skiplist

skiplist 編碼的有序集合物件使用 zset 結構作為底層實現，一個 zset 結構同時包含一個字典和一個跳躍表。

typedef struct zset {
    zskiplist *zs1;
    dict *dict;
}

繼續介紹之前，我們先了解一下什麼是跳躍表。

跳躍表

跳躍表（skiplist）是一種有序的資料結構，它通過在每個節點中維持多個指向其他節點的指標，從而達到快速訪問節點的目的。

Redis 的跳躍表由 zskiplistNode 和 zskiplist 兩個結構定義。zskiplistNode 結構表示跳躍表節點，zskiplist 儲存跳躍表節點相關資訊，比如節點的數量，以及指向表頭和表尾節點的指標等。

跳躍表節點 zskiplistNode

跳躍表節點 zskiplistNode 結構定義如下：

typedef struct zskiplistNode {
    // 後退指標
    struct zskiplistNode *backward;
    // 分值
    double score;
    // 成員物件
    robj *obj;
    // 層
    struct zskiplistLevel {
        // 前進指標
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;

下圖是一個層高為 5，包含 4 個跳躍表節點（1 個表頭節點和 3 個數據節點）組成的跳躍表：

有序集合物件的 skiplist 實現

前面講過，skiplist 編碼的有序集合物件使用 zset 結構作為底層實現。一個 zset 結構同時包含一個字典和一個跳躍表。

typedef struct zset {
    zskiplist *zs1;
    dict *dict;
}

zset 結構中的 zs1 跳躍表按分值從小到大儲存了所有集合元素，每個跳躍表節點都儲存了一個集合元素。

通過跳躍表，可以對有序集合進行基於 score 的快速範圍查詢。zset 結構中的 dict 字典為有序集合建立了從成員到分值的對映，字典的鍵儲存了成員，字典的值儲存了分值。通過字典，可以用  O(1)  複雜度查詢給定成員的分值。

假如還是執行 ZADD price 8.5 apple 5.0 banana 6.0 cherry 命令向 zset 儲存資料，如果採用 skiplist 編碼方式的話，該有序集合在記憶體中的結構如下：

6. 總結

總的來說，Redis 底層資料結構主要包括簡單動態字串（SDS）、連結串列、字典、跳躍表、整數集合和壓縮列表六種型別。並且基於這些基礎資料結構實現了字串物件、列表物件、雜湊物件、集合物件以及有序集合物件五種常見的物件型別。每一種物件型別都至少採用了 2 種資料編碼，不同的編碼使用的底層資料結構也不同。