1. 前言

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

下面我們來了解一下其底層數據結構的精妙之處。

2. Redis底層數據結構

2.1 SDS

Redis自定義了一種簡單動態字符串（simple dynamic string），將其作為Redis的默認字符串表示。

其主要結構如下：

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

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

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具有以下優點。

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

2.2 鏈表

鏈表是大家比較熟悉的數據結構了，鏈表提供了高效的節點重排能力，順序訪問，通過增刪節點調整長度等特點。Redis List對象的底層實現之一就是鏈表。

每一個鏈表節點使用如下的結構來表示。

/* 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 指針組成一個雙端隊列如下圖：

多個節點可以組成一個鏈表，Redis使用了List結構來持有這些節點，操作更方便。其結構如下：

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

簡單結構如下圖：

Redis鏈表具有如下特性：

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

2.3 字典

字典是一種用于保存鍵值對的抽象數據結構。

在字典中，一個鍵（key）可以和一個值（value）進行關聯，稱之為鍵值對。字典中每個鍵都是獨一無二的，并且程序都是通過key來操作更新value或者刪除數據等。

Redis的字典使用哈希表作為底層實現的， 一個哈希表可以包含多個哈希表節點，而每個哈希表節點就保存了字典中的一個鍵值對。

下面再講一下哈希表，哈希表節點，以及字典的實現。

哈希表及哈希表節點結構，字典結構 如下：

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

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

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

普通狀態下的字典結構示意圖：

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

• 使用字典設置的哈希函數計算key的哈希值，
• 哈希值與sizemask 進行 & 運算，計算出索引值。然后加入到數組中。

如果出現哈希沖突，那么會使用鏈地址法解決沖突，使用next指針指向下一個哈希節點。

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

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

2.4 跳躍表

跳躍表（skiplist ）是一種有序數據結構，它在每個節點中維護多個指向其他節點的指針，從而可以快速訪問。其支持平均O(logN) 復雜度的節點查找。

Zset使用了跳躍表和字典作為其底層實現。其好處就是可以進行高效的范圍查詢，也可以進行高效的單點查詢。

在源碼中其結構如下：

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

typedef struct zskiplist { //跳躍表
    struct zskiplistNode *header, *tail;//指向 跳躍表頭 和表尾節點
    unsigned long length; // 節點數量
    int level; //跳躍表中層數最大的節點層數量
} zskiplist;

typedef struct zset { // zset的數據結構使用了 字典dict 和 zskiplist
    dict *dict;
    zskiplist *zsl;
} zset;

關于跳躍表節點的各參數解釋如下：

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

下面我們畫一個跳躍表的示意圖：

圖中如果要訪問節點3，則只需要通過頭節點第四層的前進指針，就可以找到此節點。

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

個人感覺和MySql的索引有點類似。

2.5壓縮列表 ziplist

壓縮列表是 Redis中list和 hash 對象的底層實現之一。壓縮列表是為了節約內存而開發的，是由一系列連續編碼的內存塊組成。其結構示意如下：

其中各節點說明如下：

• zlbytes ，4字節， 記錄壓縮列表占用的內存字節數，對壓縮列表僅進行內存重分配，或計算zlend尾節點位置時使用。
• zltail ，4字節， 記錄壓縮列表尾節點距離壓縮列表的起始地址有多少個字節。可以快速計算得到尾節點的地址
• zlen， 2字節 ，記錄了壓縮列表包含的節點數量
• entry X 壓縮列表中的節點，其長度取決于節點內容
• zlend ， 1字節 ， 特殊值OxFF (255) 標記壓縮列表末端

其中每一個壓縮列表節點entry由如下部分組成：

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

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

新版本的redis中，引入了 listpack 。其目的是替換ziplist，整體結構類似。

其entry結構如下：

len保存了當前節點encoding及data的長度綜合，從而可以避免連鎖更新

2.6快速列表

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

快速列表使用了quickListNode節點組成雙向鏈表，然后在每個快速列表節點內部使用壓縮列表存儲數據，從而可以控制壓縮列表的長度，避免連鎖更新帶來的性能影響。

其中快速列表的源碼結構如下：

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 中維護了一個quicklistBookmark數組，并且有執行qulickListNode 頭尾的指針。

每一個quicklistBookmark 中有一個quickListNode的指針，同時每一個quickListNode又有指向前一個后一個node的指針。

其結構示意圖如下：

2.7 整數集合

整數集合（intset） 是集合鍵底層實現之一，當一個集合只包含整數元素的時候，Redis會使用整數集合作為集合鍵的實現。

整數集合的源碼如下：

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

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

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

這樣做具有一定的靈活性，而且可以節省內存。當需要升級的時候才進行升級。

總結

通過以上 Redis 底層數據結構可以看出，其設計核心總是在節約內內存，提高訪問速度。所以Redis快，這小巧妙的底層設計也是功不可沒。同時我們也可以根據著些設計思想去優化我們自己的代碼，優秀的設計總是值得去學習的。