Redis 是一個基于內存中的數據結構存儲系統(tǒng)，可以用作數據庫、緩存和消息中間件。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 類型。例如執(zhí)行 set number 10086，就會創(chuàng)建 int 編碼的字符串對象作為 number 鍵的值。

如果字符串對象保存的是一個長度大于 39 字節(jié)的字符串，此時編碼類型即為 raw，其底層數據結構是簡單動態(tài)字符串（SDS）；如果長度小于等于 39 個字節(jié)，編碼類型則為 embstr，底層數據結構就是 embstr 編碼 SDS。下面，我們詳細理解下什么是簡單動態(tài)字符串。

2.1 簡單動態(tài)字符串

SDS 定義

在 Redis 中，使用 sdshdr 數據結構表示 SDS：

struct sdshdr { // 字符串長度 int len; // buf數組中未使用的字節(jié)數 int free; // 字節(jié)數組，用于保存字符串 char buf[];};

SDS 遵循了 C 字符串以空字符結尾的慣例，保存空字符的 1 字節(jié)不會計算在 len 屬性里面。例如，Redis 這個字符串在 SDS 里面的數據可能是如下形式：

SDS 與 C 字符串的區(qū)別

C 語言使用長度為 N+1 的字符數組來表示長度為N的字符串，并且字符串的最后一個元素是空字符 。Redis 采用 SDS 相對于 C 字符串有如下幾個優(yōu)勢：

常數復雜度獲取字符串長度；

杜絕緩沖區(qū)溢出；

減少修改字符串時帶來的內存重分配次數；

二進制安全。

常數復雜度獲取字符串長度

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

杜絕緩沖區(qū)溢出

C 字符串不記錄自身長度帶來的另一個問題是，很容易造成緩存區(qū)溢出。比如使用字符串拼接函數（stract）的時候，很容易覆蓋掉字符數組原有的數據。

與 C 字符串不同，SDS 的空間分配策略完全杜絕了發(fā)生緩存區(qū)溢出的可能性。當 SDS 進行字符串擴充時，首先會檢查當前的字節(jié)數組的長度是否足夠。如果不夠的話，會先進行自動擴容，然后再進行字符串操作。

減少修改字符串時帶來的內存重分配次數

因為 C 字符串的長度和底層數據是緊密關聯(lián)的，所以每次增長或者縮短一個字符串，程序都要對這個數組進行一次內存重分配：

如果是增長字符串操作，需要先通過內存重分配來擴展底層數組空間大小，不這么做就導致緩存區(qū)溢出；

如果是縮短字符串操作，需要先通過內存重分配來來回收不再使用的空間，不這么做就導致內存泄漏。

因為內存重分配涉及復雜的算法，并且可能需要執(zhí)行系統(tǒng)調用，所以通常是個比較耗時的操作。對于 Redis 來說，字符串修改是一個十分頻繁的操作。如果每次都像 C 字符串那樣進行內存重分配，對性能影響太大了，顯然是無法接受的。

SDS 通過空閑空間解除了字符串長度和底層數據之間的關聯(lián)。在 SDS 中，數組中可以包含未使用的字節(jié)，這些字節(jié)數量由 free 屬性記錄。通過空閑空間，SDS 實現了空間預分配和惰性空間釋放兩種優(yōu)化策略。

1.空間預分配

空間預分配是用于優(yōu)化 SDS 字符串增長操作的，簡單來說就是當字節(jié)數組空間不足觸發(fā)重分配的時候，總是會預留一部分空閑空間。這樣的話，就能減少連續(xù)執(zhí)行字符串增長操作時的內存重分配次數。

有兩種預分配的策略：

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

len 大于等于 1MB 時：每次重分配時會多分配 1MB 大小的空閑空間。

2. 惰性空間釋放

惰性空間釋放是用于優(yōu)化 SDS 字符串縮短操作的。簡單來說就是當字符串縮短時，并不立即使用內存重分配來回收多出來的字節(jié)，而是用 free 屬性記錄，等待將來使用。SDS 也提供直接釋放未使用空間的 API，在需要的時候，也能真正的釋放掉多余的空間。

二進制安全

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

但是對于 Redis 來說，不僅僅需要保存文本，還要支持保存二進制數據。為了實現這一目標，SDS 的 API 全部做到了二進制安全（binary-safe）。

2.2 raw 和 embstr 編碼的 SDS 區(qū)別

我們在前面講過，長度大于 39 字節(jié)的字符串，編碼類型為 raw，底層數據結構是簡單動態(tài)字符串（SDS）。這個很好理解，比如當我們執(zhí)行 set story "Long, long, long ago there lived a king ..."（長度大于39）之后，Redis 就會創(chuàng)建一個 raw 編碼的 String 對象。

數據結構如下：

長度小于等于 39 個字節(jié)的字符串，編碼類型為 embstr，底層數據結構則是 embstr 編碼 SDS。embstr 編碼是專門用來保存短字符串的，它和 raw 編碼最大的不同在于：raw 編碼會調用兩次內存分配分別創(chuàng)建 redisObject 結構和 sdshdr 結構；而 embstr 編碼則是只調用一次內存分配，在一塊連續(xù)的空間上同時包含 redisObject 結構和 sdshdr 結構。

2.3 編碼轉換

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

對于 int 編碼來說，當我們修改這個字符串為不再是整數值的時候，此時字符串對象的編碼就會從 int 變?yōu)?raw。

對于 embstr 編碼來說，只要我們修改了字符串的值，此時字符串對象的編碼就會從 embstr 變?yōu)?raw。

embstr 編碼的字符串對象可以認為是只讀的，因為 Redis 為其編寫任何修改程序。當我們要修改 embstr 編碼字符串時，都是先將轉換為 raw 編碼，然后再進行修改。

3. 列表對象

列表對象的編碼可以是 linkedlist 或者 ziplist，對應的底層數據結構是鏈表和壓縮列表。列表對象相關命令可參考：Redis 命令-List。

默認情況下，當列表對象保存的所有字符串元素的長度都小于 64 字節(jié)，且元素個數小于 512 個時，列表對象采用的是 ziplist 編碼，否則使用 linkedlist 編碼。

可以通過配置文件修改該上限值。

3.1 鏈表

鏈表是一種非常常見的數據結構，提供了高效的節(jié)點重排能力以及順序性的節(jié)點訪問方式。在 Redis 中，每個鏈表節(jié)點使用 listNode 結構表示：

typedef struct listNode { // 前置節(jié)點 struct listNode *prev; // 后置節(jié)點 struct listNode *next; // 節(jié)點值 void *value;} listNode

多個 listNode 通過 prev 和 next 指針組成雙端鏈表，如下圖所示：

為了操作起來比較方便，Redis 使用了 list 結構持有鏈表。

typedef struct list { // 表頭節(jié)點 listNode *head; // 表尾節(jié)點 listNode *tail; // 鏈表包含的節(jié)點數量 unsigned long len; // 節(jié)點復制函數 void *(*dup)(void *ptr); // 節(jié)點釋放函數 void (*free)(void *ptr); // 節(jié)點對比函數 int (*match)(void *ptr, void *key);} list;

list 結構為鏈表提供了表頭指針 head、表尾指針 tail，以及鏈表長度計數器 len，而 dup、free 和 match 成員則是實現多態(tài)鏈表所需類型的特定函數。

Redis 鏈表實現的特征總結如下：

雙端：鏈表節(jié)點帶有 prev 和 next 指針，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復雜度都是O(n)；

無環(huán)：表頭節(jié)點的 prev 指針和表尾節(jié)點的 next 指針都指向 NULL，對鏈表的訪問以 NULL 為終點；

帶表頭指針和表尾指針：通過 list 結構的 head 指針和 tail 指針，程序獲取鏈表的表頭節(jié)點和表尾節(jié)點的復雜度為O(1)；

帶鏈表長度計數器：程序使用 list 結構的 len 屬性來對 list 持有的節(jié)點進行計數，程序獲取鏈表中節(jié)點數量的復雜度為O(1)；

多態(tài)：鏈表節(jié)點使用 void* 指針來保存節(jié)點值，可以保存各種不同類型的值。

3.2 壓縮列表

壓縮列表（ziplist）是列表鍵和哈希鍵的底層實現之一。壓縮列表主要目的是為了節(jié)約內存，是由一系列特殊編碼的連續(xù)內存塊組成的順序型數據結構。一個壓縮列表可以包含任意多個節(jié)點，每個節(jié)點可以保存一個字節(jié)數組或者一個整數值。

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

4. 哈希對象

哈希對象的編碼可以是 ziplist 或者 hashtable。

4.1 hash-ziplist

ziplist 底層使用的是壓縮列表實現，上文已經詳細介紹了壓縮列表的實現原理。每當有新的鍵值對要加入哈希對象時，先把保存了鍵的節(jié)點推入壓縮列表表尾，然后再將保存了值的節(jié)點推入壓縮列表表尾。比如，我們執(zhí)行如下三條 HSET 命令：

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

如果此時使用 ziplist 編碼，那么該 Hash 對象在內存中的結構如下：

3.2 hash-hashtable

hashtable 編碼的哈希對象使用字典作為底層實現。字典是一種用于保存鍵值對的數據結構，Redis 的字典使用哈希表作為底層實現，一個哈希表里面可以有多個哈希表節(jié)點，每個哈希表節(jié)點保存的就是一個鍵值對。

3.3 哈希表

Redis 使用的哈希表由 dictht 結構定義：

typedef struct dictht{ // 哈希表數組 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩碼，用于計算索引值 // 總是等于 size-1 unsigned long sizemask; // 該哈希表已有節(jié)點數量 unsigned long used;} dictht

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

size 屬性記錄了哈希表的大小，即 table 數組的大小。used 屬性記錄了哈希表目前已有節(jié)點數量。sizemask 總是等于 size-1，這個值主要用于數組索引。

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

哈希表節(jié)點

哈希表節(jié)點使用 dictEntry 結構表示，每個 dictEntry 結構都保存著一個鍵值對：

typedef struct dictEntry { // 鍵 void *key; // 值 union { void *val; unit64_t u64; nit64_t s64; } v; // 指向下一個哈希表節(jié)點，形成鏈表 struct dictEntry *next;} dictEntry;

key 屬性保存著鍵值對中的鍵，而 v 屬性則保存了鍵值對中的值。值可以是一個指針，一個 uint64_t 整數或者是 int64_t 整數。next 屬性指向了另一個 dictEntry 節(jié)點，在數組桶位相同的情況下，將多個 dictEntry 節(jié)點串聯(lián)成一個鏈表，以此來解決鍵沖突問題（鏈地址法）。

3.4 字典

Redis 字典由 dict 結構表示：

typedefstructdict{ // 類型特定函數 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] 新創(chuàng)建一個空白哈希表，為下一次 rehash 做準備。

哈希表的擴展和收縮時機

當服務器沒有執(zhí)行 BGSAVE 或者 BGREWRITEAOF 命令時，負載因子大于等于 1 觸發(fā)哈希表的擴展操作；

當服務器在執(zhí)行 BGSAVE 或者 BGREWRITEAOF 命令，負載因子大于等于 5 觸發(fā)哈希表的擴展操作；

當哈希表負載因子小于 0.1，觸發(fā)哈希表的收縮操作。

漸進式 rehash

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

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

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

為 ht[1] 分配空間；

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

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

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

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

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

hash 對象中的 hashtable

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

還是上述三條命令，保存數據到 Redis 的哈希對象中，如果采用 hashtable 編碼保存的話，那么該 Hash 對象在內存中的結構如下：

當哈希對象保存的所有鍵值對的鍵和值的字符串長度都小于 64 個字節(jié)，并且數量小于 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 類型的數組，以此類推。

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

根據新元素類型，擴展整數集合底層數組空間大小；

將底層數組現有所有元素都轉換為與新元素相同的類型，并且維持底層數組的有序性；

將新元素添加到底層數組里面。

還有一點需要注意的是，整數集合不支持降級。一旦對數組進行了升級，編碼就會一直保持升級后的狀態(tài)。

舉個例子，當執(zhí)行 SADD numbers 1 3 5 向集合對象插入數據時，該集合對象在內存的結構如下：

4.2 set-hashtable

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

當我們執(zhí)行 SADD fruits "apple" "banana" "cherry" 向集合對象插入數據時，該集合對象在內存的結構如下：

5. 有序集合對象

有序集合的編碼可以是 ziplist 或者 skiplist。當有序集合保存的元素個數小于 128 個，且所有元素成員長度都小于 64 字節(jié)時，使用 ziplist 編碼，否則使用 skiplist 編碼。

5.1 zset-ziplist

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

壓縮列表內的集合元素按照分值從小到大排列。如果我們執(zhí)行 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;}

繼續(xù)介紹之前，我們先了解一下什么是跳躍表。

跳躍表

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

Redis 的跳躍表由 zskiplistNode 和 zskiplist 兩個結構定義。zskiplistNode 結構表示跳躍表節(jié)點，zskiplist 保存跳躍表節(jié)點相關信息，比如節(jié)點的數量，以及指向表頭和表尾節(jié)點的指針等。

跳躍表節(jié)點 zskiplistNode

跳躍表節(jié)點 zskiplistNode 結構定義如下：

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

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

有序集合對象的 skiplist 實現

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

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

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

通過跳躍表，可以對有序集合進行基于 score 的快速范圍查找。zset 結構中的 dict 字典為有序集合創(chuàng)建了從成員到分值的映射，字典的鍵保存了成員，字典的值保存了分值。通過字典，可以用O(1)復雜度查找給定成員的分值。

假如還是執(zhí)行 ZADD price 8.5 apple 5.0 banana 6.0 cherry 命令向 zset 保存數據，如果采用 skiplist 編碼方式的話，該有序集合在內存中的結構如下：

6. 總結

總的來說，Redis 底層數據結構主要包括簡單動態(tài)字符串（SDS）、鏈表、字典、跳躍表、整數集合和壓縮列表六種類型。并且基于這些基礎數據結構實現了字符串對象、列表對象、哈希對象、集合對象以及有序集合對象五種常見的對象類型。每一種對象類型都至少采用了 2 種數據編碼，不同的編碼使用的底層數據結構也不同。

責任編輯：xj

原文標題：一文讀懂 Redis 常見對象類型的底層數據結構

文章出處：【微信公眾號：數據分析與開發(fā)】歡迎添加關注！文章轉載請注明出處。