Redis 的五種基本類(lèi)型(原理篇)

良心公眾號(hào)

關(guān)注不迷路

Redis 是一個(gè)速度非?？斓姆顷P(guān)系型數(shù)據(jù)庫(kù)，它可以存儲(chǔ)鍵?(key)?與 5 種不同類(lèi)型的值?(value)?之間的映射，可以將存儲(chǔ)在內(nèi)存的鍵值對(duì)數(shù)據(jù)持久化到硬盤(pán)，可以使用復(fù)制特性來(lái)擴(kuò)展讀性能，還可以使用客戶端分片來(lái)擴(kuò)展性能。

《Redis In Action》Josiah L. Carlson 著

在之前的?Redis 的五種基本類(lèi)型（實(shí)戰(zhàn)篇）一文中，主要是從實(shí)踐的角度出發(fā)，利用思維導(dǎo)圖的形式，盤(pán)點(diǎn)了五種基本類(lèi)型的實(shí)踐操作及一些適用場(chǎng)景。本文則將從原理的角度，對(duì) Redis 的五種基本類(lèi)型抽絲剝繭，深入考察其原理，從而對(duì)其有更加深刻的認(rèn)識(shí)(跟面試官談笑風(fēng)生)。

如下圖所示，圖中展示了 Redis 的 key-value 的存儲(chǔ)結(jié)構(gòu)和五種基本數(shù)據(jù)類(lèi)型。

而 Redis 對(duì)于上述五種數(shù)據(jù)類(lèi)型的支持，是依靠下圖中所示的六種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。

那么問(wèn)題來(lái)了，Redis 支持的數(shù)據(jù)類(lèi)型是五種，但底層的涉及的數(shù)據(jù)結(jié)構(gòu)卻有六種，這是為什么呢？讓我們帶著這個(gè)小小的疑問(wèn)，來(lái)開(kāi)啟對(duì)上述六種數(shù)據(jù)結(jié)構(gòu)的探索吧。

01

SDS (簡(jiǎn)單動(dòng)態(tài)字符串)

對(duì)于 String 類(lèi)型的底層實(shí)現(xiàn)，Redis 并沒(méi)有直接使用 C 語(yǔ)言的字符串表示， 而是構(gòu)建了一種被稱為 SDS (簡(jiǎn)單動(dòng)態(tài)字符串) 的抽象類(lèi)型。其底層數(shù)據(jù)結(jié)構(gòu)如下所示：

struct sdshdr {????//?記錄?buf?數(shù)組中已使用字節(jié)的數(shù)量    int len;    // 記錄 buf 數(shù)組中未使用字節(jié)的數(shù)量    int free;
    // 字節(jié)數(shù)組，用于保存字符串????char?buf[];};

基于上述 SDS 的數(shù)據(jù)結(jié)構(gòu)，結(jié)合源碼中部分方法的具體實(shí)現(xiàn)?(在此并未列出)，我們可以看出，Redis 的 簡(jiǎn)單動(dòng)態(tài)字符串?dāng)?shù)據(jù)結(jié)構(gòu)有如下特點(diǎn)：

• 由于 len 字段記錄了 buf 數(shù)組中已使用的字節(jié)數(shù)，因此，獲取字符串長(zhǎng)度的復(fù)雜度為 O(1) 。

• 由于 len 字段和 free 字段分別記錄了 buf 數(shù)組中已使用和未使用的字節(jié)數(shù)，在進(jìn)行字符串修改或者拼接的時(shí)候，會(huì)預(yù)先進(jìn)行 buf 數(shù)組空間使用情況的判斷，因此，其 API 是安全的，不會(huì)造成緩沖區(qū)溢出。

• 同樣，由于 len 字段和 free 字段分別記錄了 buf 數(shù)組中已使用和未使用的字節(jié)數(shù)，因此，對(duì)于字符串是否結(jié)束的判斷，并不以 '\0' 表示的空字符串為依據(jù)，因此，Redis 不僅可以保存文本數(shù)據(jù)，還可以保存二進(jìn)制數(shù)據(jù) (例如圖片、音頻、視頻、壓縮文件等)。

• SDS 采用了空間預(yù)分配和惰性空間釋放的內(nèi)存管理策略，從而使得修改字符串長(zhǎng)度 N?次最多需要執(zhí)行 N?次內(nèi)存重分配。

02

List (鏈表)

對(duì)于 List 類(lèi)型的底層實(shí)現(xiàn)，由于 C 語(yǔ)言并沒(méi)有內(nèi)置鏈表的數(shù)據(jù)結(jié)構(gòu)，因此，Redis 自己實(shí)現(xiàn)了鏈表的數(shù)據(jù)結(jié)構(gòu)。

基礎(chǔ)的鏈表結(jié)點(diǎn) listNode 數(shù)據(jù)結(jié)構(gòu)，如下所示：

typedef?struct?listNode?{????//?前驅(qū)節(jié)點(diǎn)    struct listNode *prev;
????//?后繼節(jié)點(diǎn)    struct listNode *next;
????//?節(jié)點(diǎn)值????void?*value;} listNode;

Redis 在實(shí)現(xiàn) listNode 的基礎(chǔ)上，對(duì)其進(jìn)行封裝，得到了 list 數(shù)據(jù)結(jié)構(gòu)，如下所示：

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

基于上述 listNode 和 list?的數(shù)據(jù)結(jié)構(gòu)，結(jié)合源碼中部分方法的具體實(shí)現(xiàn)?(在此并未列出)，我們可以看出，Redis 的鏈表數(shù)據(jù)結(jié)構(gòu)有如下特點(diǎn)：

• 雙向無(wú)環(huán)鏈表：listNode 數(shù)據(jù)結(jié)構(gòu)帶有 prev 和 next 指針， 分別用于指向當(dāng)前的節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，因此，獲取某個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)的時(shí)間復(fù)雜度都是 O(1)。表頭節(jié)點(diǎn)的 prev 指針和表尾節(jié)點(diǎn)的 next 指針都指向 NULL， 對(duì)鏈表的訪問(wèn)以 NULL 為終點(diǎn)。

• 表頭指針和表尾指針：list 數(shù)據(jù)結(jié)構(gòu)帶有 head 指針和 tail 指針， 分別用于獲取鏈表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)，其時(shí)間復(fù)雜度為 O(1)。

• 鏈表長(zhǎng)度計(jì)數(shù)器：list 數(shù)據(jù)結(jié)構(gòu)的 len 字段用于存儲(chǔ)鏈表當(dāng)前的節(jié)點(diǎn)數(shù)量，因此，獲取鏈表中節(jié)點(diǎn)數(shù)量的復(fù)雜度為 O(1)。

• 多態(tài)：鏈表節(jié)點(diǎn)使用 void*?指針來(lái)保存節(jié)點(diǎn)值， 并且可以通過(guò) list 數(shù)據(jù)結(jié)構(gòu)所提供的 dup，free，match 三個(gè)屬性為節(jié)點(diǎn)值設(shè)置類(lèi)型特定函數(shù)， 因此，鏈表可以用于保存各種不同類(lèi)型的值。

03

Dict?(字典)

Redis 的字典數(shù)據(jù)結(jié)構(gòu)使用哈希表作為底層實(shí)現(xiàn)，其代碼如下所示：

typedef struct dict {    // 類(lèi)型特定方法    dictType *type;    // 私有數(shù)據(jù)    void *privdata;    // 哈希表    dictht ht[2];    // rehash 索引    int rehashidx;}?dict;

可以看出，Redis 的 dict 數(shù)據(jù)結(jié)構(gòu)是通過(guò) dictht 哈希表來(lái)實(shí)現(xiàn)的，從代碼中可以看出，ht 屬性是一個(gè)包含兩個(gè)元素的數(shù)組，數(shù)組中的每個(gè)元素都是一個(gè) dictht 哈希表，之所以有兩個(gè)元素的原因是，通常情況下，dict 只使用 ht[0] 哈希表，當(dāng)需要對(duì) ht[0] 哈希表進(jìn)行 rehash 時(shí)，才需要用到 ht[1] 哈希表。其中，dictht 數(shù)據(jù)結(jié)構(gòu)的代碼如下所示：

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

可以看出，dictht 數(shù)據(jù)結(jié)構(gòu)底層的主體是 table 數(shù)組，其存儲(chǔ)的元素類(lèi)型是一個(gè)被稱為 dictEntry 的數(shù)據(jù)結(jié)構(gòu)。每一個(gè) dictEntry 結(jié)構(gòu)保存一對(duì)鍵值對(duì)。其代碼如下所示：

typedef?struct?dictEntry?{????//?鍵????void?*key;????????//?值????union?{????????void?*val;????????uint64_tu64;????????int64_ts64;????} v;????????//?指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表????struct?dictEbtry?*next;}?dictEntry;

可以看出，dictEntry 中的 key 屬性用于存儲(chǔ)鍵值對(duì)的鍵，v 屬性用于存儲(chǔ)鍵值對(duì)的值?；诖?，從而實(shí)現(xiàn)了對(duì)字典類(lèi)型的支持。

基于上述 dict，dictht，dictEntry?的數(shù)據(jù)結(jié)構(gòu)，結(jié)合源碼中部分方法的具體實(shí)現(xiàn) (在此并未列出)，我們可以看出，Redis 的字典數(shù)據(jù)結(jié)構(gòu)有如下特點(diǎn)：

• Redis 中的字典使用哈希表作為底層實(shí)現(xiàn)， 每個(gè)字典帶有兩個(gè)哈希表， 一個(gè)用于平時(shí)使用， 另一個(gè)僅在進(jìn)行 rehash 時(shí)使用。

• 哈希表使用鏈地址法來(lái)解決鍵沖突， 被分配到同一個(gè)索引上的多個(gè)鍵值對(duì)會(huì)連接成一個(gè)單向鏈表。

• 在對(duì)哈希表進(jìn)行擴(kuò)展或者收縮操作時(shí)， 程序需要將現(xiàn)有哈希表包含的所有鍵值對(duì) rehash 到新哈希表里面， 并且這個(gè) rehash 過(guò)程并不是一次性地完成的， 而是漸進(jìn)式地完成的。

04

Skiplist (跳表)

跳表是面試過(guò)程中考察的熱點(diǎn)數(shù)據(jù)結(jié)構(gòu)，它是一種有序的數(shù)據(jù)結(jié)構(gòu)，通過(guò)在每個(gè)節(jié)點(diǎn)上維護(hù)多個(gè)指向其他節(jié)點(diǎn)的指針，從而達(dá)到快速訪問(wèn)節(jié)點(diǎn)的目的。由于跳表支持平均 O(logn)，最壞 O(n) 的查找時(shí)間復(fù)雜度，在大部分情況下，其性能甚至不差于平衡樹(shù)，因此，在面試過(guò)程中，經(jīng)常會(huì)被拿來(lái)和平衡樹(shù)進(jìn)行比較，比如，為什么 Redis 實(shí)現(xiàn)有序集合采用的是跳表，而不是紅黑樹(shù)？對(duì)紅黑書(shū)不太了解的小伙伴請(qǐng)戳這里——如果你問(wèn)我紅黑樹(shù)的話，我可就不困了！在了解跳表的具體實(shí)現(xiàn)之后，這個(gè)問(wèn)題就比較清楚了！

Redis 通過(guò) zskiplist 的結(jié)構(gòu)體實(shí)現(xiàn)了跳表，其代碼如下所示：

typedef?struct?zskiplist?{????//?表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)????struct?zskiplistNode?*header,?*tail;????????// 表中節(jié)點(diǎn)數(shù)量????unsigned?long length;????????//?表中層數(shù)最大的節(jié)點(diǎn)的層數(shù)????int?level;}?zskiplist;

可以看出，zskiplist 維護(hù)了兩個(gè)類(lèi)型為 zskiplistNode 的節(jié)點(diǎn)指針，分別用來(lái)指向表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)。zskiplistNode 數(shù)據(jù)結(jié)構(gòu)的代碼實(shí)現(xiàn)如下所示：

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

基于上述 zskiplist 和 zskiplistNode?的數(shù)據(jù)結(jié)構(gòu)，結(jié)合源碼中部分方法的具體實(shí)現(xiàn)，我們可以看出，Redis 的跳表數(shù)據(jù)結(jié)構(gòu)有如下特點(diǎn)：

• 跳表是有序集合的底層實(shí)現(xiàn)之一，其實(shí)現(xiàn)由 zskiplist 和 zskiplistNode 兩個(gè)結(jié)構(gòu)組成， 其中 zskiplist 用于保存跳躍表信息（比如表頭節(jié)點(diǎn)、表尾節(jié)點(diǎn)、長(zhǎng)度）， zskiplistNode 表示跳躍表節(jié)點(diǎn)。

• 每個(gè)跳躍表節(jié)點(diǎn)的層高都是 1 至 32 之間的隨機(jī)數(shù)。

• 在同一個(gè)跳躍表中， 多個(gè)節(jié)點(diǎn)可以包含相同的分值， 但每個(gè)節(jié)點(diǎn)的成員對(duì)象必須唯一。

• 跳躍表中的節(jié)點(diǎn)按照分值大小進(jìn)行排序， 當(dāng)分值相同時(shí)， 節(jié)點(diǎn)按照成員對(duì)象的大小進(jìn)行排序。

Redis 之所以采用跳表而非紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)有序集合的原因主要有兩個(gè)：

• 跳表實(shí)現(xiàn)比紅黑樹(shù)實(shí)現(xiàn)更加簡(jiǎn)單；

• 跳表的數(shù)據(jù)結(jié)構(gòu)決定它比紅黑樹(shù)可以更好地支持范圍查詢。

05

Intset (整數(shù)集合)

Redis 通過(guò)使用整數(shù)集合的數(shù)據(jù)結(jié)構(gòu)來(lái)保存整數(shù)值，整數(shù)集合可以保存的類(lèi)型為 int16_t，int32_t，或者 int64_t 的整數(shù)值，并能保證集合中不會(huì)出現(xiàn)重復(fù)元素。其代碼如下所示：

typedef?struct?intset?{    // 編碼方式    uint32_t encoding;
    // 集合包含的元素?cái)?shù)量    uint32_t length;
    // 保存元素的數(shù)組????int8_t?contents[];} intset;

可以看出，整數(shù)集合的數(shù)據(jù)結(jié)構(gòu)，其底層主體是 contents 數(shù)組，用于存儲(chǔ)整數(shù)集合中的每個(gè)元素，元素在數(shù)組中按從小到大的順序有序排列，并且數(shù)組中不包含重復(fù)元素。

對(duì)于整數(shù)集合，由于其支持保存?int16_t，int32_t，或者 int64_t 的整數(shù)值，因此它涉及一個(gè)比較有趣的操作——升級(jí)。

所謂的升級(jí)，是指當(dāng)我們向整數(shù)集合中添加一個(gè)新元素時(shí)，如果待添加的元素比整數(shù)集合中所有元素的類(lèi)型都要長(zhǎng)時(shí)，就需要先對(duì)整數(shù)集合進(jìn)行升級(jí)，然后再進(jìn)行添加。升級(jí)的步驟分為以下三步：

• 根據(jù)新元素的類(lèi)型，擴(kuò)展 contents 數(shù)組的空間大小，并為新元素分配空間；

• 對(duì) contents 數(shù)組中存儲(chǔ)的所有元素進(jìn)行類(lèi)型轉(zhuǎn)換，然后將其存放進(jìn)數(shù)組中，并保證有序性；

• 將新元素添加至 contents 數(shù)組。

升級(jí)操作的目的在于，在保證操作靈活性的前提下，盡量節(jié)約內(nèi)存空間。

整數(shù)集合不支持降級(jí)。

基于上述 intset?的數(shù)據(jù)結(jié)構(gòu)，結(jié)合源碼中部分方法的具體實(shí)現(xiàn)，我們可以看出，Redis 的整數(shù)集合數(shù)據(jù)結(jié)構(gòu)有如下特點(diǎn)：

• 整數(shù)集合是集合鍵的底層實(shí)現(xiàn)之一。

• 整數(shù)集合的底層實(shí)現(xiàn)為數(shù)組， 這個(gè)數(shù)組以有序、無(wú)重復(fù)的方式保存集合元素。

• 在添加新元素時(shí)，需要先判斷是否需要進(jìn)行升級(jí)，?不支持降級(jí)操作。

06

Ziplist (壓縮列表)

壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。

當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)，并且每個(gè)列表向要么是小整數(shù)值，要么是短字符串時(shí)，Redis 會(huì)采用壓縮列表來(lái)作為列表鍵的底層實(shí)現(xiàn)。

當(dāng)一個(gè)哈希鍵只包含少量鍵值對(duì)，并且每個(gè)鍵值對(duì)的鍵和值要么是小整數(shù)值，要么是短字符串時(shí)，Redis 會(huì)采用壓縮列表來(lái)作為哈希鍵的底層實(shí)現(xiàn)。

可以看出，Redis 為了保證極致的性能，在不同的場(chǎng)景下，采用了不同的實(shí)現(xiàn)方式，這也就是文章一開(kāi)始所提到的，為什么 Redis 支持五種數(shù)據(jù)類(lèi)型，卻有六種底層實(shí)現(xiàn)。

Redis 的壓縮列表數(shù)據(jù)結(jié)構(gòu)有如下特點(diǎn)：

• 壓縮列表是一種為節(jié)約內(nèi)存而開(kāi)發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)。

• 壓縮列表被用作列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。

• 壓縮列表可以包含多個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者整數(shù)值。

綜上所述，redis 的五種數(shù)據(jù)類(lèi)型所涉及到的底層數(shù)據(jù)結(jié)構(gòu)就總結(jié)到這里了。

歡迎關(guān)注【有理想的菜雞】公眾號(hào)，大家一起討論技術(shù)，共同成長(zhǎng)！

【參考資料】

《Redis 設(shè)計(jì)與實(shí)現(xiàn)》黃健宏 著

https://github.com/redis/redis

學(xué)習(xí) | 工作 |?分享

??長(zhǎng)按關(guān)注“有理想的菜雞”

只有你想不到，沒(méi)有你學(xué)不到