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

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

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

對象類型和編碼

Redis使用對象來存儲鍵和值的,在Redis中,每個對象都由redisObject結構表示redisObject結構主要包含三個屬性:typeencodingptr

typedef struct redisObject {
    // 類型
    unsigned type:4;
    // 編碼
    unsigned encoding:4;
    // 底層數據結構的指針
    void *ptr;
} robj;

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

類型常量 對象類型名稱
REDIS_STRING 字符串對象
REDIS_LIST 列表對象
REDIS_HASH 哈希對象
REDIS_SET 集合對象
REDIS_ZSET 有序集合對象

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

編碼常量 編碼對應的底層數據結構
REDIS_ENCODING_INT long類型的整數
REDIS_ENCODING_EMBSTR emstr編碼的簡單動態字符串
REDIS_ENCODING_RAW 簡單動態字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 雙端鏈表
REDIS_ENCODING_ZIPLIST 壓縮列表
REDIS_ENCODING_INTSET 整數集合
REDIS_ENCODING_SKIPLIST 跳躍表和字典

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

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

字符串對象

字符串是我們日常工作中用得最多的對象類型,它對應的編碼可以是intrawembstr字符串對象相關命令可參考:Redis命令-Strings

如果一個字符串對象保存的是不超過long類型的整數值,此時編碼類型即為int,其底層數據結構直接就是long類型。例如執行set number 10086,就會創建int編碼的字符串對象作為number鍵的值。
redis-encoding-int

如果字符串對象保存的是一個長度大於39位元組的字符串,此時編碼類型即為raw,其底層數據結構是簡單動態字符串(SDS);如果長度小於等於39個位元組,編碼類型則為embstr,底層數據結構就是embstr編碼SDS。下面,我們詳細理解下什麼是簡單動態字符串。

簡單動態字符串

SDS定義

Redis中,使用sdshdr數據結構表示SDS

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

SDS遵循了C字符串以空字符結尾的慣例,保存空字符的1位元組不會計算在len屬性裏面。例如,Redis這個字符串在SDS裏面的數據可能是如下形式:
sdshdr

SDS與C字符串的區別

C語言使用長度為N+1的字符數組來表示長度為N的字符串,並且字符串的最後一個元素是空字符\0Redis採用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. len小於1MB時:每次重分配時會多分配同樣大小的空閑空間;
    2. len大於等於1MB時:每次重分配時會多分配1MB大小的空閑空間。
  2. 惰性空間釋放
    惰性空間釋放是用於優化SDS字符串縮短操作的,簡單來說就是當字符串縮短時,並不立即使用內存重分配來回收多出來的位元組,而是用free屬性記錄,等待將來使用。SDS也提供直接釋放未使用空間的API,在需要的時候,也能真正的釋放掉多餘的空間。
二進制安全

C字符串中的字符必須符合某種編碼,並且除了字符串末尾之外,其它位置不允許出現空字符,這些限制使得C字符串只能保存文本數據。但是對於Redis來說,不僅僅需要保存文本,還要支持保存二進制數據。為了實現這一目標,SDSAPI全部做到了二進制安全(binary-safe)。

raw和embstr編碼的SDS區別

我們在前面講過,長度大於39位元組的字符串,編碼類型為raw,底層數據結構是簡單動態字符串(SDS)。這個很好理解,比如當我們執行set story "Long, long, long ago there lived a king ..."(長度大於39)之後,Redis就會創建一個raw編碼的String對象。數據結構如下:
在這裡插入圖片描述

長度小於等於39個位元組的字符串,編碼類型為embstr,底層數據結構則是embstr編碼SDSembstr編碼是專門用來保存短字符串的,它和raw編碼最大的不同在於:raw編碼會調用兩次內存分配分別創建redisObject結構和sdshdr結構,而embstr編碼則是只調用一次內存分配,在一塊連續的空間上同時包含redisObject結構和sdshdr結構
embstr

編碼轉換

int編碼和embstr編碼的字符串對象在條件滿足的情況下會自動轉換為raw編碼的字符串對象。
對於int編碼來說,當我們修改這個字符串為不再是整數值的時候,此時字符串對象的編碼就會從int變為raw;對於embstr編碼來說,只要我們修改了字符串的值,此時字符串對象的編碼就會從embstr變為raw

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

列表對象

列表對象的編碼可以是linkedlist或者ziplist,對應的底層數據結構是鏈表和壓縮列表。列表對象相關命令可參考:Redis命令-List
默認情況下,當列表對象保存的所有字符串元素的長度都小於64位元組,且元素個數小於512個時,列表對象採用的是ziplist編碼,否則使用linkedlist編碼。

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

鏈表

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

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

多個listNode通過prevnext指針組成雙端鏈表,如下圖所示:
listnode

為了操作起來比較方便,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,而dupfreematch成員則是實現多態鏈表所需類型的特定函數。
list

Redis鏈表實現的特徵總結如下:

  1. 雙端:鏈表節點帶有prevnext指針,獲取某個節點的前置節點和後置節點的複雜度都是O(n)
  2. 無環:表頭節點的prev指針和表尾節點的next指針都指向NULL,對鏈表的訪問以NULL為終點。
  3. 帶表頭指針和表尾指針:通過list結構的head指針和tail指針,程序獲取鏈表的表頭節點和表尾節點的複雜度為O(1)
  4. 帶鏈表長度計數器:程序使用list結構的len屬性來對list持有的節點進行計數,程序獲取鏈表中節點數量的複雜度為O(1)
  5. 多態:鏈表節點使用void*指針來保存節點值,可以保存各種不同類型的值。

壓縮列表

壓縮列表(ziplist)是列表鍵和哈希鍵的底層實現之一。壓縮列表主要目的是為了節約內存,是由一系列特殊編碼的連續內存塊組成的順序型數據結構。一個壓縮列表可以包含任意多個節點,每個節點可以保存一個位元組數組或者一個整數值。
在這裡插入圖片描述
如上圖所示,壓縮列表記錄了各組成部分的類型、長度以及用途。

屬性 類型 長度 用途
zlbytes uint_32_t 4位元組 記錄整個壓縮列表佔用的內存位元組數
zltail uint_32_t 4位元組 記錄壓縮列表表尾節點距離起始地址有多少位元組,通過這個偏移量,程序無需遍歷整個壓縮列表就能確定表尾節點地址
zlen uint_16_t 2位元組 記錄壓縮列表包含的節點數量
entryX 列表節點 不定 壓縮列表的各個節點,節點長度由保存的內容決定
zlend uint_8_t 1位元組 特殊值(0xFFF),用於標記壓縮列表末端

哈希對象

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

hash-ziplist

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

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

如果此時使用ziplist編碼,那麼該Hash對象在內存中的結構如下:
在這裡插入圖片描述

hash-hashtable

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

哈希表

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的空哈希表。
dictht

哈希表節點

哈希表節點使用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節點串聯成一個鏈表,以此來解決鍵衝突問題。(鏈地址法)

字典

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。
dict

rehash

為了使hash表的負載因子(ht[0]).used/ht[0]).size)維持在一個合理範圍,當哈希表保存的元素過多或者過少時,程序需要對hash表進行相應的擴展和收縮。rehash(重新散列)操作就是用來完成hash表的擴展和收縮的。rehash的步驟如下:

  1. ht[1]哈希表分配空間
    1. 如果是擴展操作,那麼ht[1]的大小為第一個大於ht[0].used*2的2n。比如`ht[0].used=5`,那麼此時`ht[1]`的大小就為16。(大於10的第一個2n的值是16)
    2. 如果是收縮操作,那麼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做準備。

哈希表的擴展和收縮時機

  1. 當服務器沒有執行BGSAVE或者BGREWRITEAOF命令時,負載因子大於等於1觸發哈希表的擴展操作。
  2. 當服務器在執行BGSAVE或者BGREWRITEAOF命令,負載因子大於等於5觸發哈希表的擴展操作。
  3. 當哈希表負載因子小於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編碼。

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

集合對象

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

set-intset

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

整數集合(intset)是Redis用於保存整數值的集合抽象數據結構,它可以保存類型為int16_tint32_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向集合對象插入數據時,該集合對象在內存的結構如下:
//chentianming11.github.io/images/redis/set-intset.png

set-hashtable

hashtable編碼的集合對象使用字典作為底層實現,字典的每個鍵都是一個字符串對象,每個字符串對象對應一個集合元素,字典的值都是NULL。當我們執行SADD fruits "apple" "banana" "cherry"向集合對象插入數據時,該集合對象在內存的結構如下:
在這裡插入圖片描述

有序集合對象

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

zset-ziplist

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

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

zset-skiplist

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

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

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

跳躍表

跳躍表(skiplist)是一種有序的數據結構,它通過在每個節點中維持多個指向其他節點的指針,從而達到快速訪問節點的目的。Redis的跳躍表由zskiplistNodezskiplist兩個結構定義,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個數據節點)組成的跳躍表:
在這裡插入圖片描述
每次創建一個新的跳躍表節點的時候,會根據冪次定律(越大的數出現的概率越低)隨機生成一個1-32之間的值作為當前節點的”層高”。每層元素都包含2個數據,前進指針和跨度。
1. 前進指針
每層都有一個指向表尾方向的前進指針,用於從表頭向表尾方向訪問節點。
2. 跨度
層的跨度用於記錄兩個節點之間的距離。
2. 後退指針(BW)
節點的後退指針用於從表尾向表頭方向訪問節點,每個節點只有一個後退指針,所以每次只能後退一個節點。
3. 分值和成員
節點的分值(score)是一個double類型的浮點數,跳躍表中所有節點都按分值從小到大排列。節點的成員(obj)是一個指針,指向一個字符串對象。在跳躍表中,各個節點保存的成員對象必須是唯一的,但是多個節點的分值確實可以相同。

需要注意的是,表頭節點不存儲真實數據,並且層高固定為32,從表頭節點第一個不為NULL最高層開始,就能實現快速查找

跳躍表 zskiplist

實際上,僅靠多個跳躍表節點就可以組成一個跳躍表,但是Redis使用了zskiplist結構來持有這些節點,這樣就能夠更方便地對整個跳躍表進行操作。比如快速訪問表頭和表尾節點,獲得跳躍表節點數量等等。zskiplist結構定義如下:

typedef struct zskiplist {

    // 表頭節點和表尾節點
    struct skiplistNode *header, *tail;
    // 節點數量
    unsigned long length;
    // 最大層數
    int level;
} zskiplist;

下圖是一個完整的跳躍表結構示例:
在這裡插入圖片描述

有序集合對象的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編碼方式的話,該有序集合在內存中的結構如下:
在這裡插入圖片描述

總結

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

原創不易,覺得文章寫得不錯的小夥伴,點個贊👍 鼓勵一下吧~

Tags: