Redis 常見對象類型的底層數據結構

Redis 是一個基於內存中的數據結構存儲系統，可以用作數據庫、緩存和消息中間件。Redis 支持五種常見對象類型：字符串（String）、哈希（Hash）、列表（List）、集合（Set）以及有序集合（Zset），我們在日常工作中也會經常使用它們。知其然，更要知其所以然，本文將會帶你讀懂這五種常見對象類型的底層數據結構。

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

  1. 對象類型和編碼

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

typedefstructredisObject{ // 類型 
unsignedtype: 4;// 編碼 
unsignedencoding: 4; // 底層數據結構的指針 
void*ptr; } robj;

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

*ptr 屬性指向了對象的底層數據結構，而這些數據結構由 encoding 屬性決定。

之所以由 encoding 屬性來決定對象的底層數據結構，是爲了實現同一對象類型，支持不同的底層實現。這樣就能在不同場景下，使用不同的底層數據結構，進而極大提升 Redis 的靈活性和效率。

底層數據結構後面會詳細講解，這裏簡單看一下即可。

  1. 字符串對象

字符串是我們日常工作中用得最多的對象類型，它對應的編碼可以是 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：

structsdshdr{ // 字符串長度 
intlen; // buf數組中未使用的字節數 
intfree; // 字節數組，用於保存字符串 
charbuf[]; };

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 字符串增長操作的，簡單來說就是當字節數組空間不足觸發重分配的時候，總是會預留一部分空閒空間。這樣的話，就能減少連續執行字符串增長操作時的內存重分配次數。

有兩種預分配的策略：

  1. 惰性空間釋放

惰性空間釋放是用於優化 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 編碼，然後再進行修改。

  1. 列表對象

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

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

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

3.1 鏈表

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

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

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

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

typedefstructlist{ // 表頭節點 
listNode *head; // 表尾節點 
listNode *tail; // 鏈表包含的節點數量 
unsignedlonglen; // 節點複製函數 
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）是列表鍵和哈希鍵的底層實現之一。壓縮列表主要目的是爲了節約內存，是由一系列特殊編碼的連續內存塊組成的順序型數據結構。一個壓縮列表可以包含任意多個節點，每個節點可以保存一個字節數組或者一個整數值。

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

  1. 哈希對象

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

4.1 hash-ziplist

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

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

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

3.2 hash-hashtable

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

3.3 哈希表

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

typedefstructdictht{ // 哈希表數組 dictEntry **table;
// 哈希表大小unsignedlongsize;
// 哈希表大小掩碼，用於計算索引值// 總是等於 size-1unsignedlongsizemask;
// 該哈希表已有節點數量unsignedlongused; } dictht

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

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

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

哈希表節點

哈希表節點使用 dictEntry 結構表示，每個 dictEntry 結構都保存着一個鍵值對：

typedefstructdictEntry{ // 鍵void*key;
// 值union{ void*val; unit64_tu64; nit64_ts64; } v;
// 指向下一個哈希表節點，形成鏈表structdictEntry* next; } dictEntry;

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

3.4 字典

Redis 字典由 dict 結構表示：

typedefstructdict{ // 類型特定函數
dictType *type;// 私有數據
void*privdata;// 哈希表
dictht ht[ 2];//rehash索引
// 當rehash不在進行時，值爲-1
intrehashidx; }

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] 哈希表分配空間；

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

  2. 遷移完成之後，釋放掉 ht[0]，並將現在的 ht[1] 設置爲 ht[0]，在 ht[1] 新創建一個空白哈希表，爲下一次 rehash 做準備。

哈希表的擴展和收縮時機

漸進式 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

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

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

當哈希對象保存的所有鍵值對的鍵和值的字符串長度都小於 64 個字節，並且數量小於 512 個時，使用 ziplist 編碼，否則使用 hashtable 編碼。

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

  1. 集合對象

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

4.1 set-intset

intset 編碼的集合對象底層使用整數集合實現。

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

typedefstructintset{ 
// 編碼方式
uint32_tencoding; 
// 集合包含的元素數量
uint32_tlength; 
// 保存元素的數組
int8_tcontents[]; 
} 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" 向集合對象插入數據時，該集合對象在內存的結構如下：

  1. 有序集合對象

有序集合的編碼可以是 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 結構同時包含一個字典和一個跳躍表。

typedefstructzset{ zskiplist *zs1;dict *dict;}

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

跳躍表

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

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

跳躍表節點 zskiplistNode

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

typedefstructzskiplistNode{ 
// 後退指針
structzskiplistNode* backward; 
// 分值
doublescore; 
// 成員對象
robj *obj;
// 層
structzskiplistLevel{ 
// 前進指針
structzskiplistNode* forward; 
// 跨度
unsignedintspan; 
} 
level[];
} zskiplistNode;

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

有序集合對象的 skiplist 實現

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

typedefstructzset{ zskiplist *zs1;dict *dict;}

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

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

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

  1. 總結

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

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/trnPjR6oH5o6XGd-YSd8-w

猜你喜歡