前言

我們都知道憎账，redis最基本的數(shù)據(jù)結(jié)構(gòu)有5種，分別是字符串卡辰、列表胞皱、哈希表、集合和有序集合九妈。其實準(zhǔn)確來說反砌，這種表述容易造成誤會，給人誤解允蚣。從redis的源碼來看于颖，這5種其實是redis封裝的對象，而底層對象的實現(xiàn)才應(yīng)該成為數(shù)據(jù)結(jié)構(gòu)嚷兔。redis最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)包括以下幾種：簡單動態(tài)字符串森渐、鏈表、字典冒晰、跳躍表同衣、整數(shù)集合、壓縮列表壶运。而redis對象(也就是一開始提到的5種)其實底層都是基于這些數(shù)據(jù)結(jié)構(gòu)的耐齐，這樣的好處是，同一種對象根據(jù)實際場景的不同底層可以使用不同的數(shù)據(jù)機構(gòu)來優(yōu)化使用效率蒋情。redis的對象還基于引用計數(shù)實現(xiàn)了內(nèi)存回收機制和對象共享機制埠况，這里就不展開了。本文參考《Redis 設(shè)計與實現(xiàn)》主要介紹一下redis的6種底層數(shù)據(jù)結(jié)構(gòu)棵癣。

簡單動態(tài)字符串

定義

Redis 沒有直接使用 C 語言傳統(tǒng)的字符串表示（以空字符結(jié)尾的字符數(shù)組辕翰，以下簡稱 C 字符串）， 而是自己構(gòu)建了一種名為簡單動態(tài)字符串（simple dynamic string狈谊，SDS）的抽象類型喜命， 并將 SDS 用作 Redis 的默認(rèn)字符串表示沟沙。
如果 Redis 需要一個可以改變的字符串對象的時候，底層就會使用 SDS 來實現(xiàn)壁榕，SDS 結(jié)構(gòu)的源碼實現(xiàn)如下：

/*
 * 保存字符串對象的結(jié)構(gòu)
 */
struct sdshdr {
    
    // buf 中已占用空間的長度
    int len;

    // buf 中剩余可用空間的長度
    int free;

    // 數(shù)據(jù)空間
    char buf[];
};

buf作為字節(jié)數(shù)組矛紫，底層保留了C語言以空字符('\0')結(jié)尾的特性以便重用部分C的函數(shù)，空字符不計算長度牌里。

與C語言字符串的區(qū)別

Redis 不直接使用 C 的字符串肯定是因為有自己的考慮颊咬，就是因為 SDS 這種實現(xiàn)相比原生的 C 字符串有很多優(yōu)點。

• 常數(shù)復(fù)雜度獲取字符串長度

由 SDS 的源碼可以看到牡辽，獲取長度直接返回len即可贪染，而 C 的字符串需要遍歷，時間復(fù)雜度為O(N)催享。

• 杜絕緩沖區(qū)溢出

C 語言進行字符串拼接時需要人工考慮內(nèi)存的分配，否則可能導(dǎo)致內(nèi)存溢出從而覆蓋已有的數(shù)據(jù)哟绊。而 SDS 在拼接時直接查詢 free 字段即可知道空間是否足夠因妙，不夠會自動進行擴展。

• 減少修改字符串時帶來的內(nèi)存重分配次數(shù)

C 字符串以空字符結(jié)尾票髓，長度固定為 (有效字符數(shù) + 1)攀涵，每次進行字符串拼接或者截斷操作都需要進行內(nèi)存重分配，否則會造成內(nèi)存溢出和內(nèi)存泄露洽沟。SDS 通過空間預(yù)分配和惰性空間釋放來解決這個問題以故，free 字段記錄了有效字符空間與實際數(shù)組空間的差值，SDS 擴展時會分配額外空間裆操，這稱為空間預(yù)分配怒详；SDS 縮短時不會立即進行空間釋放(除非手動調(diào)用API進行空間釋放)，會用free字段記錄釋放的空間踪区，這稱為惰性空間釋放昆烁。

• 二進制安全

C 的字符串不能保存含有空字符的數(shù)據(jù)，因為空字符是用來判斷字符串結(jié)尾的缎岗，所以不能用于保存二進制數(shù)據(jù)静尼。SDS 用len判斷字符串長度可以保存任意二進制數(shù)據(jù)。

• SDS 可以兼容部分 C 字符串函數(shù)

因為buf作為字符數(shù)組也是用空字符結(jié)尾的传泊，所以部分 C 語言的函數(shù)是可以直接使用的

鏈表

實現(xiàn)

Redis 實現(xiàn)的鏈表是一個雙向鏈表华临，每個節(jié)點有特定實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)芯杀，而整個鏈表的表示則使用了另一個代表整體的結(jié)構(gòu)，源碼如下：

/*
 * 雙端鏈表節(jié)點
 */
typedef struct listNode {

    // 前置節(jié)點
    struct listNode *prev;

    // 后置節(jié)點
    struct listNode *next;

    // 節(jié)點的值
    void *value;

} listNode;

/*
 * 雙端鏈表結(jié)構(gòu)
 */
typedef struct list {

    // 表頭節(jié)點
    listNode *head;

    // 表尾節(jié)點
    listNode *tail;

    // 節(jié)點值復(fù)制函數(shù)
    void *(*dup)(void *ptr);

    // 節(jié)點值釋放函數(shù)
    void (*free)(void *ptr);

    // 節(jié)點值對比函數(shù)
    int (*match)(void *ptr, void *key);

    // 鏈表所包含的節(jié)點數(shù)量
    unsigned long len;

} list;

鏈表的特性：

1. 雙端
2. 無環(huán)
3. 帶表頭指針和表尾指針
4. 帶鏈表長度計數(shù)器
5. 多態(tài)雅潭，可以保存不同的值

Redis 用鏈表來實現(xiàn)列表建揭厚、發(fā)布與訂閱、慢查詢扶供、監(jiān)視器等功能筛圆。

字典

Redis 數(shù)據(jù)庫以及哈希鍵的底層實現(xiàn)用的都是字典。

實現(xiàn)

哈希表

/*
 * 哈希表
 *
 * 每個字典都使用兩個哈希表椿浓，從而實現(xiàn)漸進式 rehash 太援。
 */
typedef struct dictht {
    
    // 哈希表數(shù)組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩碼，用于計算索引值
    // 總是等于 size - 1
    unsigned long sizemask;

    // 該哈希表已有節(jié)點的數(shù)量
    unsigned long used;

} dictht;

哈希表節(jié)點

/*
 * 哈希表節(jié)點
 */
typedef struct dictEntry {
    
    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個哈希表節(jié)點扳碍，形成鏈表
    struct dictEntry *next;

} dictEntry;

next指針用于解決哈希沖突提岔，跟Java中的HashMap實現(xiàn)是相同的。

字典

/*
 * 字典
 */
typedef struct dict {

    // 類型特定函數(shù)
    dictType *type;

    // 私有數(shù)據(jù)
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 當(dāng) rehash 不在進行時笋敞，值為 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在運行的安全迭代器的數(shù)量
    int iterators; /* number of iterators currently running */

} dict;

ht 屬性是一個包含兩個項的數(shù)組碱蒙， 數(shù)組中的每個項都是一個 dictht 哈希表， 一般情況下夯巷， 字典只使用 ht[0] 哈希表赛惩， ht[1] 哈希表只會在對 ht[0] 哈希表進行 rehash 時使用。

除了 ht[1] 之外趁餐， 另一個和 rehash 有關(guān)的屬性就是 rehashidx ： 它記錄了 rehash 目前的進度坊秸， 如果目前沒有在進行 rehash ， 那么它的值為 -1 澎怒。

image

哈希算法

當(dāng)字典被用作數(shù)據(jù)庫的底層實現(xiàn)褒搔， 或者哈希鍵的底層實現(xiàn)時， Redis 使用 MurmurHash2 算法來計算鍵的哈希值喷面。

解決鍵沖突

鏈地址法解決哈希沖突星瘾，類似于java中的HashMap。dictEntry組成的鏈表是一個單向鏈表惧辈，沒有指向表尾的指針琳状，多以后加入的節(jié)點如果產(chǎn)生了哈希沖突則會放到鏈表的表頭。

rehash

所有的哈希表隨著鍵值對的增多和減少都需要進行擴展或者收縮操作盒齿，不然就會造成哈希沖突過多或者內(nèi)存浪費念逞。Redis 的哈希表重新散列的步驟如下：

1. 為字典的 ht[1] 哈希表分配空間困食， 這個哈希表的空間大小取決于要執(zhí)行的操作， 以及 ht[0] 當(dāng)前包含的鍵值對數(shù)量 （也即是 ht[0].used 屬性的值）：
   如果執(zhí)行的是擴展操作翎承， 那么 ht[1] 的大小為第一個大于等于 ht[0].used * 2 的 2^n （2 的 n 次方冪）硕盹；
   如果執(zhí)行的是收縮操作， 那么 ht[1] 的大小為第一個大于等于 ht[0].used 的 2^n 叨咖。
2. 將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面： rehash 指的是重新計算鍵的哈希值和索引值瘩例， 然后將鍵值對放置到 ht[1] 哈希表的指定位置上。
3. 當(dāng) ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后 （ht[0] 變?yōu)榭毡恚?釋放 ht[0] 甸各， 將 ht[1] 設(shè)置為 ht[0] 垛贤， 并在 ht[1] 新創(chuàng)建一個空白哈希表， 為下一次 rehash 做準(zhǔn)備趣倾。

rehash的觸發(fā)條件：

1. 服務(wù)器目前沒有在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令聘惦， 并且哈希表的負(fù)載因子大于等于 1 ；
2. 服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令儒恋， 并且哈希表的負(fù)載因子大于等于 5 部凑；
3. 當(dāng)哈希表的負(fù)載因子小于 0.1 時， 程序自動開始對哈希表執(zhí)行收縮操作碧浊。

# 負(fù)載因子 = 哈希表已保存節(jié)點數(shù)量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

漸進式rehash

主要防止哈希表過大導(dǎo)致rehash時間過長，主要步驟如下：

1. 為 ht[1] 分配空間瘟仿， 讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表箱锐。
2. 在字典中維持一個索引計數(shù)器變量 rehashidx ， 并將它的值設(shè)置為 0 劳较， 表示 rehash 工作正式開始驹止。
3. 在 rehash 進行期間， 每次對字典執(zhí)行添加观蜗、刪除臊恋、查找或者更新操作時， 程序除了執(zhí)行指定的操作以外墓捻， 還會順帶將 ht[0] 哈希表在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] 抖仅， 當(dāng) rehash 工作完成之后， 程序?qū)?rehashidx 屬性的值增一砖第。
4. 隨著字典操作的不斷執(zhí)行撤卢， 最終在某個時間點上， ht[0] 的所有鍵值對都會被 rehash 至 ht[1] 梧兼， 這時程序?qū)?rehashidx 屬性的值設(shè)為 -1 放吩， 表示 rehash 操作已完成。

漸進式rehash期間羽杰，查詢會先插ht[0]再查ht[1]渡紫，增加則只會增加到ht[1]到推。

跳躍表

Redis在有序集合的實現(xiàn)以及集群節(jié)點內(nèi)部數(shù)據(jù)機構(gòu)用到了跳躍表。

實現(xiàn)

image

/*
 * 跳躍表節(jié)點
 */
typedef struct zskiplistNode {

    // 成員對象
    robj *obj;

    // 分值
    double score;

    // 后退指針
    struct zskiplistNode *backward;

    // 層
    struct zskiplistLevel {

        // 前進指針
        struct zskiplistNode *forward;

        // 跨度
        unsigned int span;

    } level[];

} zskiplistNode;

/*
 * 跳躍表
 */
typedef struct zskiplist {

    // 表頭節(jié)點和表尾節(jié)點
    struct zskiplistNode *header, *tail;

    // 表中節(jié)點的數(shù)量
    unsigned long length;

    // 表中層數(shù)最大的節(jié)點的層數(shù)
    int level;

} zskiplist;

• 每個跳躍表節(jié)點的層高都是 1 至 32 之間的隨機數(shù)惕澎。
• 在同一個跳躍表中莉测， 多個節(jié)點可以包含相同的分值， 但每個節(jié)點的成員對象必須是唯一的集灌。
• 跳躍表中的節(jié)點按照分值大小進行排序悔雹， 當(dāng)分值相同時， 節(jié)點按照成員對象的大小進行排序欣喧。

整數(shù)集合

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

實現(xiàn)

typedef struct intset {
    
    // 編碼方式
    uint32_t encoding;

    // 集合包含的元素數(shù)量
    uint32_t length;

    // 保存元素的數(shù)組
    int8_t contents[];

} intset;

雖然 intset 結(jié)構(gòu)將 contents 屬性聲明為 int8_t 類型的數(shù)組， 但實際上 contents 數(shù)組并不保存任何 int8_t 類型的值 —— contents 數(shù)組的真正類型取決于 encoding 屬性的值：

1. 如果 encoding 屬性的值為 INTSET_ENC_INT16 唆阿， 那么 contents 就是一個 int16_t 類型的數(shù)組益涧， 數(shù)組里的每個項都是一個 int16_t 類型的整數(shù)值 （最小值為 -32,768 ，最大值為 32,767 ）驯鳖。
2. 如果 encoding 屬性的值為 INTSET_ENC_INT32 闲询， 那么 contents 就是一個 int32_t 類型的數(shù)組， 數(shù)組里的每個項都是一個 int32_t 類型的整數(shù)值 （最小值為 -2,147,483,648 浅辙，最大值為 2,147,483,647 ）扭弧。
3. 如果 encoding 屬性的值為 INTSET_ENC_INT64 ， 那么 contents 就是一個 int64_t 類型的數(shù)組记舆， 數(shù)組里的每個項都是一個 int64_t 類型的整數(shù)值 （最小值為 -9,223,372,036,854,775,808 鸽捻，最大值為 9,223,372,036,854,775,807 ）。

升級

每當(dāng)我們要將一個新元素添加到整數(shù)集合里面泽腮， 并且新元素的類型比整數(shù)集合現(xiàn)有所有元素的類型都要長時御蒲， 整數(shù)集合需要先進行升級（upgrade）， 然后才能將新元素添加到整數(shù)集合里面诊赊。

升級整數(shù)集合并添加新元素共分為三步進行：

1. 根據(jù)新元素的類型厚满， 擴展整數(shù)集合底層數(shù)組的空間大小， 并為新元素分配空間碧磅。
2. 將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成與新元素相同的類型碘箍， 并將類型轉(zhuǎn)換后的元素放置到正確的位上， 而且在放置元素的過程中鲸郊， 需要繼續(xù)維持底層數(shù)組的有序性質(zhì)不變敲街。
3. 將新元素添加到底層數(shù)組里面。

整數(shù)集合的升級操作提升了靈活性严望，節(jié)約了內(nèi)存多艇，并且整數(shù)集合不支持降級操作削解。

壓縮列表

壓縮列表是列表鍵和哈希鍵的底層實現(xiàn)之一醉者，主要目的就是為了節(jié)約內(nèi)存罪帖。

構(gòu)成

壓縮列表是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)晃琳。一個壓縮列表可以包含任意多個節(jié)點（entry），每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值姆涩。具體組成部分和說明如下：

壓縮列表節(jié)點構(gòu)成

每個壓縮列表節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值脐往， 其中， 字節(jié)數(shù)組可以是以下三種長度的其中一種：

• 長度小于等于 63 （2^{6}-1）字節(jié)的字節(jié)數(shù)組扳埂；
• 長度小于等于 16383 （2^{14}-1） 字節(jié)的字節(jié)數(shù)組业簿；
• 長度小于等于 4294967295 （2^{32}-1）字節(jié)的字節(jié)數(shù)組；

而整數(shù)值則可以是以下六種長度的其中一種：

• 4 位長阳懂，介于 0 至 12 之間的無符號整數(shù)梅尤；
• 1 字節(jié)長的有符號整數(shù)；
• 3 字節(jié)長的有符號整數(shù)希太；
• int16_t 類型整數(shù)；
• int32_t 類型整數(shù)酝蜒；
• int64_t 類型整數(shù)誊辉。

previous_entry_length

以字節(jié)為單位， 壓縮列表中前一個節(jié)點的長度亡脑。

previous_entry_length 屬性的長度可以是 1 字節(jié)或者 5 字節(jié)：

• 如果前一節(jié)點的長度小于 254 字節(jié)堕澄， 那么 previous_entry_length 屬性的長度為 1 字節(jié)： 前一節(jié)點的長度就保存在這一個字節(jié)里面。
• 如果前一節(jié)點的長度大于等于 254 字節(jié)霉咨， 那么 previous_entry_length 屬性的長度為 5 字節(jié)： 其中屬性的第一字節(jié)會被設(shè)置為 0xFE （十進制值 254）蛙紫， 而之后的四個字節(jié)則用于保存前一節(jié)點的長度。

previous_entry_length可以用于壓縮列表從尾部到頭部的遍歷途戒。

encoding

值的最高位為 00 坑傅、 01 或者 10 的是字節(jié)數(shù)組編碼，值的最高位以 11 開頭的是整數(shù)編碼喷斋。

content

節(jié)點的 content 屬性負(fù)責(zé)保存節(jié)點的值唁毒， 節(jié)點值可以是一個字節(jié)數(shù)組或者整數(shù)蒜茴， 值的類型和長度由節(jié)點的 encoding 屬性決定。

連鎖更新

previous_entry_length占用的空間是1字節(jié)或者5字節(jié)浆西，取決于上一節(jié)點的長度粉私，如果壓縮列表中連續(xù)多個節(jié)點處于臨界值，而此時改變某個節(jié)點的長度近零，就有可能觸發(fā)連鎖更新诺核，最壞的時間復(fù)雜度到達O(N)。
因為出現(xiàn)條件比較苛刻久信，出現(xiàn)幾率比較小窖杀，所以Redis沒有避免這種情況，我們也可以大膽使用入篮。