Redis底層數(shù)據(jù)類型

1. 前言

Redis的鍵值對中的常見數(shù)據(jù)類型有String （字符串）、List（列表）、Hash（哈希）、Set（集合）、Zset（有序集合）。那么其對應(yīng)的底層數(shù)據(jù)結(jié)構(gòu)有SDS(simple dynamic string)、鏈表、字典、跳躍表、壓縮列表、快速列表，整數(shù)集合等。

下面我們來了解一下其底層數(shù)據(jù)結(jié)構(gòu)的精妙之處。

2. Redis底層數(shù)據(jù)結(jié)構(gòu)

2.1 SDS

Redis自定義了一種簡單動態(tài)字符串（simple dynamic string），將其作為Redis的默認(rèn)字符串表示。

其主要結(jié)構(gòu)如下：

• len表示這個(gè)SDS字符串長度，如果buff字節(jié)數(shù)組中保存了5個(gè)字符那么長度就是5。同時(shí)也方便獲取SDS的長度。
• alloc表示分配的字符數(shù)組長度。其值一般是大于SDS字符串長度（len），由于 Redis的設(shè)計(jì)場景就是會頻繁的訪問，修改數(shù)據(jù)，所以無論是數(shù)據(jù)增大或者是縮小都需要盡量減少重新分配內(nèi)存的操作 。所以SDS會預(yù)留一些空間，在下一次修改數(shù)據(jù)的時(shí)候可以直接使用原先預(yù)分配的內(nèi)存，同時(shí)在每次數(shù)據(jù)操作的時(shí)候也會動態(tài)的增加或者減少預(yù)留內(nèi)存空間，。Redis3.0的版本的SDS結(jié)構(gòu)中使用free， 表示未分配的空間，但也是同一個(gè)設(shè)計(jì)思想。
• flags 標(biāo)志位，低3位表示類型，其余5位未使用。
• buf 實(shí)際存儲數(shù)據(jù)的數(shù)組，可以保存字符，也可以保存二進(jìn)制數(shù)據(jù)。

redis6.0中SDS定義如下 (越來越節(jié)約使用內(nèi)存了，內(nèi)存是省出來的！)

typedef char *sds;

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

相對于C語言的字符串，SDS具有以下優(yōu)點(diǎn)。

• 獲取字符串的長度復(fù)雜度更低（常數(shù)復(fù)雜度）（復(fù)雜度可見此文章 看完這篇，還不清楚時(shí)間復(fù)雜度的，請來懟我）
• 更加節(jié)省內(nèi)存（針對不同長度設(shè)置了不同的數(shù)據(jù)類型 sdshdr5、sdshdr8、sdshdr16等。）
• 杜絕緩沖區(qū)溢出
• 大大減少了修改字符串長度時(shí)所需要的內(nèi)存分配次數(shù)
• 二進(jìn)制安全

2.2 鏈表

鏈表是大家比較熟悉的數(shù)據(jù)結(jié)構(gòu)了，鏈表提供了高效的節(jié)點(diǎn)重排能力，順序訪問，通過增刪節(jié)點(diǎn)調(diào)整長度等特點(diǎn)。Redis List對象的底層實(shí)現(xiàn)之一就是鏈表。

每一個(gè)鏈表節(jié)點(diǎn)使用如下的結(jié)構(gòu)來表示。

/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

而多了listNode可以通過prev 和 next 指針組成一個(gè)雙端隊(duì)列如下圖：

多個(gè)節(jié)點(diǎn)可以組成一個(gè)鏈表，Redis使用了List結(jié)構(gòu)來持有這些節(jié)點(diǎn)，操作更方便。其結(jié)構(gòu)如下：

typedef struct list {
    listNode *head;  //鏈表頭節(jié)點(diǎn)指針
    listNode *tail;  //鏈表尾節(jié)點(diǎn)指針
    void *(*dup)(void *ptr); // 用于復(fù)制鏈表節(jié)點(diǎn)所保存的值
    void (*free)(void *ptr); // 用于釋放鏈表節(jié)點(diǎn)所保存的值
    int (*match)(void *ptr, void *key); //用于對比鏈表節(jié)點(diǎn)所保存的值和另一個(gè)輸入值是否相等
    unsigned long len; // 鏈表所包含的節(jié)點(diǎn)數(shù)量
} list;

簡單結(jié)構(gòu)如下圖：

Redis鏈表具有如下特性：

• 由于是雙端鏈表，有prev和next指針，獲取節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的復(fù)雜度為O(1)
• 頭節(jié)點(diǎn)的prev和尾節(jié)點(diǎn)的next均指向NULL，為無環(huán)鏈表，可以以NULL為鏈表訪問終點(diǎn)
• 鏈表本身提供了指針，可以快速獲取鏈表的表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)
• 自帶鏈表長度計(jì)數(shù)器，可以快速獲取鏈表長度
• 鏈表可以保存各種不同類型的值

2.3 字典

字典是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)。

在字典中，一個(gè)鍵（key）可以和一個(gè)值（value）進(jìn)行關(guān)聯(lián)，稱之為鍵值對。字典中每個(gè)鍵都是獨(dú)一無二的，并且程序都是通過key來操作更新value或者刪除數(shù)據(jù)等。

Redis的字典使用哈希表作為底層實(shí)現(xiàn)的， 一個(gè)哈希表可以包含多個(gè)哈希表節(jié)點(diǎn)，而每個(gè)哈希表節(jié)點(diǎn)就保存了字典中的一個(gè)鍵值對。

下面再講一下哈希表，哈希表節(jié)點(diǎn)，以及字典的實(shí)現(xiàn)。

哈希表及哈希表節(jié)點(diǎn)結(jié)構(gòu)，字典結(jié)構(gòu) 如下：

//字典結(jié)構(gòu)
typedef struct dict {
    dictType *type; // 類型特定的函數(shù)
    void *privdata;  //私有數(shù)據(jù)
    dictht ht[2]; //長度為2的哈希表數(shù)組， 一般情況下字典僅使用 ht[0]哈希表， ht[1]在rehash的時(shí)候會使用到。
    long rehashidx; /* 未進(jìn)行rehash的時(shí)候 rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

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

//哈希節(jié)點(diǎn)
typedef struct dictEntry {
    void *key; //鍵
    union { //value值，包含了多種類型的值，不同類型的值可以使用不同的數(shù)據(jù)結(jié)構(gòu)存儲，節(jié)省內(nèi)存。
        void *val;  //其值可以是一個(gè)指針
        uint64_t u64; //其值也可以是一個(gè)uint64_t 整數(shù)
        int64_t s64; //其值可以是一個(gè)int64_t 整數(shù)
        double d; //其值可以是一個(gè)double 
    } v;
    struct dictEntry *next; //指向像一個(gè)哈希節(jié)點(diǎn)
} dictEntry;

普通狀態(tài)下的字典結(jié)構(gòu)示意圖：

添加新建的機(jī)制是大家比較熟悉的思路啦。

• 使用字典設(shè)置的哈希函數(shù)計(jì)算key的哈希值，
• 哈希值與sizemask 進(jìn)行 & 運(yùn)算，計(jì)算出索引值。然后加入到數(shù)組中。

如果出現(xiàn)哈希沖突，那么會使用鏈地址法解決沖突，使用next指針指向下一個(gè)哈希節(jié)點(diǎn)。

哈希表保存的鍵值逐漸增多或者減少地過程中，程序會對哈希表進(jìn)行擴(kuò)展或者收縮，這個(gè)過程稱之為rehash。

rehash過程中會使用上面的ht[0] ht[1]，具體過程這里就不詳細(xì)說了，會另外專門寫一篇來介紹。

2.4 跳躍表

跳躍表（skiplist ）是一種有序數(shù)據(jù)結(jié)構(gòu)，它在每個(gè)節(jié)點(diǎn)中維護(hù)多個(gè)指向其他節(jié)點(diǎn)的指針，從而可以快速訪問。其支持平均O(logN) 復(fù)雜度的節(jié)點(diǎn)查找。

Zset使用了跳躍表和字典作為其底層實(shí)現(xiàn)。其好處就是可以進(jìn)行高效的范圍查詢，也可以進(jìn)行高效的單點(diǎn)查詢。

在源碼中其結(jié)構(gòu)如下：

typedef struct zskiplistNode { //跳躍表節(jié)點(diǎn)
    sds ele; //成員對象，各個(gè)節(jié)點(diǎn)中成員對象唯一的。
    double score; //分值
    struct zskiplistNode *backward; //后退指針
    struct zskiplistLevel { //層， 最大32層
        struct zskiplistNode *forward; //前進(jìn)指針
        unsigned long span; //跨度
    } level[];
} zskiplistNode;

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

typedef struct zset { // zset的數(shù)據(jù)結(jié)構(gòu)使用了 字典dict 和 zskiplist
    dict *dict;
    zskiplist *zsl;
} zset;

關(guān)于跳躍表節(jié)點(diǎn)的各參數(shù)解釋如下：

• 層 level：跳躍表節(jié)點(diǎn)的level數(shù)組可以包含多個(gè)節(jié)點(diǎn)元素，每個(gè)元素都包含指向其他節(jié)點(diǎn)的指針，程序可以通過這些指針來加快訪問其他節(jié)點(diǎn)的速度，層數(shù)越多訪問效率越高。每創(chuàng)建一個(gè)新的跳躍表節(jié)點(diǎn)，程序會隨機(jī)生成一個(gè)1-32之間層數(shù)的值，作為level數(shù)組的大小。表示節(jié)點(diǎn)的高度。
• 前進(jìn)指針，forward ：每層有一個(gè)指向表尾方向的前進(jìn)指針，可以通過表頭向表尾訪問節(jié)點(diǎn)。
• 跨度 span：記錄兩個(gè)節(jié)點(diǎn)之間的距離。
• 后退指針 backward：節(jié)點(diǎn)的后退指針，用于從表尾向表頭訪問節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只有一個(gè)后退指針，所以每次只能后退一個(gè)節(jié)點(diǎn)。
• 分值 score：分值是一個(gè)浮點(diǎn)數(shù)，跳躍表中的節(jié)點(diǎn)按照分值來排序，
• 成員對象 ele：一個(gè)指針，指向一個(gè)SDS對象。

下面我們畫一個(gè)跳躍表的示意圖：

圖中如果要訪問節(jié)點(diǎn)3，則只需要通過頭節(jié)點(diǎn)第四層的前進(jìn)指針，就可以找到此節(jié)點(diǎn)。

如果需要增加元素的時(shí)候，會先使用高層前進(jìn)指針去遍歷，并對比score值，然后逐步縮小插入元素的位置范圍，然后確定最終的位置。這樣其平均時(shí)間復(fù)雜度為O(logN). 相比于鏈表的O(N)的時(shí)間復(fù)雜度來說，其效率大大提高。只不過其代價(jià)就是需要多一點(diǎn)的內(nèi)存空間。

個(gè)人感覺和MySql的索引有點(diǎn)類似。

2.5壓縮列表 ziplist

壓縮列表是 Redis中l(wèi)ist和 hash 對象的底層實(shí)現(xiàn)之一。壓縮列表是為了節(jié)約內(nèi)存而開發(fā)的，是由一系列連續(xù)編碼的內(nèi)存塊組成。其結(jié)構(gòu)示意如下：

其中各節(jié)點(diǎn)說明如下：

• zlbytes ，4字節(jié)， 記錄壓縮列表占用的內(nèi)存字節(jié)數(shù)，對壓縮列表僅進(jìn)行內(nèi)存重分配，或計(jì)算zlend尾節(jié)點(diǎn)位置時(shí)使用。
• zltail ，4字節(jié)， 記錄壓縮列表尾節(jié)點(diǎn)距離壓縮列表的起始地址有多少個(gè)字節(jié)?？梢钥焖儆?jì)算得到尾節(jié)點(diǎn)的地址
• zlen， 2字節(jié) ，記錄了壓縮列表包含的節(jié)點(diǎn)數(shù)量
• entry X 壓縮列表中的節(jié)點(diǎn)，其長度取決于節(jié)點(diǎn)內(nèi)容
• zlend ， 1字節(jié) ， 特殊值OxFF (255) 標(biāo)記壓縮列表末端

其中每一個(gè)壓縮列表節(jié)點(diǎn)entry由如下部分組成：

• previous_entry_length 記錄了壓縮列表中前一個(gè)節(jié)點(diǎn)的長度，其屬性可以是1或5個(gè)字節(jié)。如果前一個(gè)節(jié)點(diǎn)的長度小于254，那么其長度就是1字節(jié)，表示前一節(jié)點(diǎn)的長度。如果遷移節(jié)點(diǎn)的長度大于254字節(jié)， 那么其屬性長度則為5個(gè)字節(jié)，其中第一個(gè)字節(jié)會設(shè)置為OxFE(254) , 后面的4個(gè)字節(jié)用來表示前一節(jié)點(diǎn)的長度。
• encoding 表示content 屬性保存的數(shù)據(jù)類型以及長度。content保存字節(jié)數(shù)組時(shí)，encoding的值為1，2，5字節(jié)， 最高前兩位分別為00，01，10， 最高前兩位后面的其他位數(shù)則記錄content的長度。content保存整數(shù)編碼時(shí)，最高2位為11， 其余位記錄整數(shù)類型及。
• content 保存節(jié)點(diǎn)的內(nèi)容，可以保存字節(jié)數(shù)組或者整數(shù)。

由于previous_entry_length 記錄了前一個(gè)節(jié)點(diǎn)的長度，而且其可能為1個(gè)字節(jié)或者5個(gè)字節(jié)，如果前一個(gè)節(jié)點(diǎn)的長度從254之下增加到254之上，那么previous_entry_length 的值就要使用5個(gè)字節(jié)類表示。而如果后面的節(jié)點(diǎn)均存在同樣的情況，那么壓縮列表就會出現(xiàn) 連鎖更新 ，導(dǎo)致內(nèi)存空間重新分配，從而導(dǎo)致壓縮列表增加節(jié)點(diǎn)或者刪除節(jié)點(diǎn)的最壞時(shí)間復(fù)雜度位O(N2).

新版本的redis中，引入了 listpack 。其目的是替換ziplist，整體結(jié)構(gòu)類似。

其entry結(jié)構(gòu)如下：

len保存了當(dāng)前節(jié)點(diǎn)encoding及data的長度綜合，從而可以避免連鎖更新

2.6快速列表

快速列表（quicklist）可以看成是雙向鏈表和壓縮列表的一種組合。Redis3.2之后 list對象使用快速列表作為其底層實(shí)現(xiàn)。

快速列表使用了quickListNode節(jié)點(diǎn)組成雙向鏈表，然后在每個(gè)快速列表節(jié)點(diǎn)內(nèi)部使用壓縮列表存儲數(shù)據(jù)，從而可以控制壓縮列表的長度，避免連鎖更新帶來的性能影響。

其中快速列表的源碼結(jié)構(gòu)如下：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quickList 中維護(hù)了一個(gè)quicklistBookmark數(shù)組，并且有執(zhí)行qulickListNode 頭尾的指針。

每一個(gè)quicklistBookmark 中有一個(gè)quickListNode的指針，同時(shí)每一個(gè)quickListNode又有指向前一個(gè)后一個(gè)node的指針。

其結(jié)構(gòu)示意圖如下：

2.7 整數(shù)集合

整數(shù)集合（intset） 是集合鍵底層實(shí)現(xiàn)之一，當(dāng)一個(gè)集合只包含整數(shù)元素的時(shí)候，Redis會使用整數(shù)集合作為集合鍵的實(shí)現(xiàn)。

整數(shù)集合的源碼如下：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

整數(shù)集合底層是一個(gè)數(shù)組，如果每一個(gè)元素都在16位以內(nèi)的整數(shù)類型(-32768 到 32767)，則數(shù)組的每個(gè)元素都為int16_t ， 如果新加的整數(shù)超過這個(gè)范圍，并且在32位以內(nèi)的話， 整個(gè)數(shù)組中的每一個(gè)元素都會升級成int32_t 表示的整數(shù)， 如果新加入的是64 位才能表示的整數(shù)的話，所以的元素又會再一次升級。

但是整數(shù)集合不支持降級，及 整數(shù)集合中如果有一個(gè)64位的整數(shù)，即使移除此元素，整個(gè)集合也不會降級。

這樣做具有一定的靈活性，而且可以節(jié)省內(nèi)存。當(dāng)需要升級的時(shí)候才進(jìn)行升級。

總結(jié)

通過以上 Redis 底層數(shù)據(jù)結(jié)構(gòu)可以看出，其設(shè)計(jì)核心總是在節(jié)約內(nèi)內(nèi)存，提高訪問速度。所以Redis快，這小巧妙的底層設(shè)計(jì)也是功不可沒。同時(shí)我們也可以根據(jù)著些設(shè)計(jì)思想去優(yōu)化我們自己的代碼，優(yōu)秀的設(shè)計(jì)總是值得去學(xué)習(xí)的。