3妹

2哥：3妹，前些天我們學(xué)習(xí)了1.Redis概述，還記得嗎？
3妹：記得啊，我課后還有復(fù)習(xí)呢，主要講了redis的作用、五大數(shù)據(jù)類型和使用場景。
2哥：沒錯，今天我們再來學(xué)習(xí)一下五大數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)。
3妹：好啊好啊，稍等下，我搬個小板凳，拿個筆記本好好學(xué)習(xí)。
2哥：哈哈，3妹的學(xué)習(xí)熱情還很高嘛。

講課

1、演示數(shù)據(jù)類型的實現(xiàn)

OBJECT ENCODING key 

該命令是用來顯示那五大數(shù)據(jù)類型的底層數(shù)據(jù)結(jié)構(gòu)。

比如對于 string 數(shù)據(jù)類型：

image.png

我們可以看到實現(xiàn)string數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)有 embstr 以及 int。

再比如 list 數(shù)據(jù)類型：

image.png

可以看到，list的數(shù)據(jù)類型是鏈表

2、六種數(shù)據(jù)結(jié)構(gòu)

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

Redis 是用 C 語言寫的，但是對于Redis的字符串，卻不是 C 語言中的字符串（即以空字符’\0’結(jié)尾的字符數(shù)組），它是自己構(gòu)建了一種名為 簡單動態(tài)字符串（simple dynamic string,SDS）的抽象類型，并將 SDS 作為 Redis的默認(rèn)字符串表示。

SDS 定義如下：

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

假設(shè)用SDS保存字符串 “Redis”， 具體的存儲結(jié)構(gòu)如下圖：

image.png

我們看上面對于 SDS 數(shù)據(jù)類型的定義：
1、len 保存了SDS保存字符串的長度
2、buf[] 數(shù)組用來保存字符串的每個元素
3、free j記錄了 buf 數(shù)組中未使用的字節(jié)數(shù)量

上面的定義相對于 C 語言對于字符串的定義，多出了 len 屬性以及 free 屬性。為什么不使用C語言字符串實現(xiàn)，而是使用 SDS呢？這樣實現(xiàn)有什么好處？
好處：
①、常數(shù)復(fù)雜度獲取字符串長度
由于 len 屬性的存在，我們獲取 SDS 字符串的長度只需要讀取 len 屬性，時間復(fù)雜度為 O(1)。而對于 C 語言，獲取字符串的長度通常是經(jīng)過遍歷計數(shù)來實現(xiàn)的，時間復(fù)雜度為 O(n)。通過 strlen key 命令可以獲取 key 的字符串長度。

②、杜絕緩沖區(qū)溢出
我們知道在 C 語言中使用 strcat 函數(shù)來進(jìn)行兩個字符串的拼接，一旦沒有分配足夠長度的內(nèi)存空間，就會造成緩沖區(qū)溢出。而對于 SDS 數(shù)據(jù)類型，在進(jìn)行字符修改的時候，會首先根據(jù)記錄的 len 屬性 檢查內(nèi)存空間是否滿足需求，如果不滿足，會進(jìn)行相應(yīng)的空間擴(kuò)展，然后在進(jìn)行修改操作，所以不會出現(xiàn)緩沖區(qū)溢出。

③、減少修改字符串的內(nèi)存重新分配次數(shù)
C語言由于不記錄字符串的長度，所以如果要修改字符串，必須要重新分配內(nèi)存（先釋放再申請），因為如果沒有重新分配，字符串長度增大時會造成內(nèi)存緩沖區(qū)溢出，字符串長度減小時會造成內(nèi)存泄露。

而對于SDS，由于len屬性和free屬性的存在，對于修改字符串SDS實現(xiàn)了空間預(yù)分配和惰性空間釋放兩種策略：

• 空間預(yù)分配：對字符串進(jìn)行空間擴(kuò)展的時候，擴(kuò)展的內(nèi)存比實際需要的多，這樣可以減少連續(xù)執(zhí)行字符串增長操作所需的內(nèi)存重分配次數(shù)。
• 惰性空間釋放：對字符串進(jìn)行縮短操作時，程序不立即使用內(nèi)存重新分配來回收縮短后多余的字節(jié)，而是使用 free 屬性 將這些字節(jié)的數(shù)量記錄下來，等待后續(xù)使用。（當(dāng)然SDS也提供了相應(yīng)的API，當(dāng)我們有需要時，也可以手動釋放這些未使用的空間。）

④、二進(jìn)制安全
因為C字符串 以空字符作為字符串結(jié)束的標(biāo)識，而對于一些二進(jìn)制文件（如圖片等），內(nèi)容可能包括空字符串，因此C字符串無法正確存取；而所有 SDS 的API 都是以處理二進(jìn)制的方式來處理 buf 里面的元素，并且 SDS 不是以空字符串來判斷是否結(jié)束，而是以 len 屬性表示的長度來判斷字符串是否結(jié)束。

⑤、兼容部分 C 字符串函數(shù)
雖然 SDS 是二進(jìn)制安全的，但是一樣遵從每個字符串都是以空字符串結(jié)尾的慣例，這樣可以重用 C 語言庫<string.h> 中的一部分函數(shù)。

⑥、總結(jié)
一般來說，SDS 除了保存數(shù)據(jù)庫中的字符串值以外，SDS 還可以作為緩沖區(qū)（buffer）：包括 AOF 模塊中的AOF緩沖區(qū)以及客戶端狀態(tài)中的 輸入緩沖區(qū)。后面在介紹Redis的持久化時會進(jìn)行介紹。

2.2 鏈表

鏈表是一種常用的數(shù)據(jù)結(jié)構(gòu)，C 語言內(nèi)部是沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，所以Redis自己構(gòu)建了鏈表的實現(xiàn)。
鏈表定義如下：

typedef  struct listNode{
       //前置節(jié)點
       struct listNode *prev;
       //后置節(jié)點
       struct listNode *next;
       //節(jié)點的值
       void *value;  
}listNode

通過多個 listNode 結(jié)構(gòu)就可以組成鏈表，這是一個雙端鏈表，Redis還提供了操作鏈表的數(shù)據(jù)結(jié)構(gòu)：

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

image.png

Redis鏈表特性：

①、雙端：鏈表具有前置節(jié)點和后置節(jié)點的引用，獲取這兩個節(jié)點時間復(fù)雜度都為O(1)。
②、無環(huán)：表頭節(jié)點的 prev 指針和表尾節(jié)點的 next 指針都指向 NULL,對鏈表的訪問都是以 NULL 結(jié)束。
③、帶鏈表長度計數(shù)器：通過 len 屬性 獲取鏈表長度的時間復(fù)雜度為 O(1)。
④、多態(tài)：鏈表節(jié)點使用 void* 指針來保存節(jié)點值，可以保存各種不同類型的值。

2.3 字典

字典又稱為符號表或者關(guān)聯(lián)數(shù)組、或映射（map），是一種用于保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)。字典中的每一個鍵 key 都是唯一的，通過 key 可以對值來進(jìn)行查找或修改。C 語言中沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)，所以字典依然是 Redis自己構(gòu)建的。

Redis 的字典使用 哈希表 作為底層實現(xiàn)。

哈希表結(jié)構(gòu)定義：

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

}dictht

哈希表是由數(shù)組 table 組成，table 中每個元素都是指向 dict.h/dictEntry 結(jié)構(gòu)，dictEntry 結(jié)構(gòu)定義如下：

typedef struct dictEntry{
     //鍵
     void *key;
     //值
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     }v;

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

key 用來保存鍵，val 屬性用來保存值，值可以是一個指針，也可以是uint64_t整數(shù)，也可以是int64_t整數(shù)。

注意這里還有一個指向下一個哈希表節(jié)點的指針，我們知道哈希表最大的問題是存在哈希沖突，如何解決哈希沖突，有開放地址法和鏈地址法。這里采用的便是鏈地址法，通過next這個指針可以將 多個哈希值相同的 鍵值對 連接在一起，用來解決哈希沖突。

image.png

①、哈希算法：Redis計算哈希值和索引值方法如下：

#1、使用字典設(shè)置的哈希函數(shù)，計算鍵 key 的哈希值
hash = dict->type->hashFunction(key);
#2、使用哈希表的sizemask屬性和第一步得到的哈希值，計算索引值
index = hash & dict->ht[x].sizemask;

②、解決哈希沖突：這個問題上面我們介紹了，方法是鏈地址法。通過字典里面的 *next 指針指向下一個具有相同索引值的哈希表節(jié)點。

③、擴(kuò)容和收縮：當(dāng)哈希表保存的鍵值對太多或者太少時，就要通過 rehash(重新散列）來對哈希表進(jìn)行相應(yīng)的擴(kuò)展或者收縮。具體步驟：

• 1、若是擴(kuò)展操作，那么ht[1]的大小為>=ht[0].used*2的2^n
  若是收縮操作，那么ht[1]的大小為>=ht[0].used的2^n
• 2、重新利用上面的哈希算法，計算索引值，然后將鍵值對放到新的哈希表位置上。
• 3、所有鍵值對都遷徙完畢后，釋放原哈希表的內(nèi)存空間。

④、觸發(fā)擴(kuò)容的條件

• 1、服務(wù)器目前沒有執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且負(fù)載因子大于等于1。
• 2、服務(wù)器目前正在執(zhí)行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且負(fù)載因子大于等于5。

ps：負(fù)載因子 = 哈希表已保存節(jié)點數(shù)量 / 哈希表大小。

⑤、漸近式 rehash

什么叫漸進(jìn)式 rehash？也就是說擴(kuò)容和收縮操作不是一次性、集中式完成的，而是分多次、漸進(jìn)式完成的。如果保存在Redis中的鍵值對只有幾個幾十個，那么 rehash 操作可以瞬間完成，但是如果鍵值對有幾百萬，幾千萬甚至幾億，那么要一次性的進(jìn)行 rehash，勢必會造成Redis一段時間內(nèi)不能進(jìn)行別的操作。所以Redis采用漸進(jìn)式 rehash，這樣在進(jìn)行漸進(jìn)式rehash期間，字典的刪除查找更新等操作可能會在兩個哈希表上進(jìn)行，第一個哈希表沒有找到，就會去第二個哈希表上進(jìn)行查找。但是進(jìn)行 增加操作，一定是在新的哈希表上進(jìn)行的。

2.4 跳躍表

關(guān)于跳躍表的趣味介紹：http://blog.jobbole.com/111731/

跳躍表（skiplist）是一種有序數(shù)據(jù)結(jié)構(gòu)，它通過在每個節(jié)點中維持多個指向其它節(jié)點的指針，從而達(dá)到快速訪問節(jié)點的目的。具有如下性質(zhì)：

1、由很多層結(jié)構(gòu)組成；

2、每一層都是一個有序的鏈表，排列順序為由高層到底層，都至少包含兩個鏈表節(jié)點，分別是前面的head節(jié)點和后面的nil節(jié)點；

3、最底層的鏈表包含了所有的元素；

4、如果一個元素出現(xiàn)在某一層的鏈表中，那么在該層之下的鏈表也全都會出現(xiàn)（上一層的元素是當(dāng)前層的元素的子集）；

5、鏈表中的每個節(jié)點都包含兩個指針，一個指向同一層的下一個鏈表節(jié)點，另一個指向下一層的同一個鏈表節(jié)點；

image.png

Redis中跳躍表節(jié)點定義如下：

typedef struct zskiplistNode {
     //層
     struct zskiplistLevel{
           //前進(jìn)指針
           struct zskiplistNode *forward;
           //跨度
           unsigned int span;
     }level[];

     //后退指針
     struct zskiplistNode *backward;
     //分值 用于排序的
     double score;
     //成員對象
     robj *obj;

} zskiplistNode

多個跳躍表節(jié)點構(gòu)成一個跳躍表：

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

}zskiplist;

image.png

• ①、搜索：從最高層的鏈表節(jié)點開始，如果比當(dāng)前節(jié)點要大和比當(dāng)前層的下一個節(jié)點要小，那么則往下找，也就是和當(dāng)前層的下一層的節(jié)點的下一個節(jié)點進(jìn)行比較，以此類推，一直找到最底層的最后一個節(jié)點，如果找到則返回，反之則返回空。
• ②、插入：首先確定插入的層數(shù)，有一種方法是假設(shè)拋一枚硬幣，如果是正面就累加，直到遇見反面為止，最后記錄正面的次數(shù)作為插入的層數(shù)。當(dāng)確定插入的層數(shù)k后，則需要將新元素插入到從底層到k層。
• ③、刪除：在各個層中找到包含指定值的節(jié)點，然后將節(jié)點從鏈表中刪除即可，如果刪除以后，只剩下頭尾兩個節(jié)點，則刪除這一層。

2.5 整數(shù)集合

整數(shù)集合（intset）是Redis用于保存整數(shù)值的集合抽象數(shù)據(jù)類型，它可以保存類型為int16_t、int32_t 或者int64_t 的整數(shù)值，并且保證集合中不會出現(xiàn)重復(fù)元素。定義如下：

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

}intset;

整數(shù)集合的每個元素 都是 contents 數(shù)組 的一個數(shù)據(jù)項，它們按照從小到大的順序排列，并且不包含任何重復(fù)項。

length 屬性記錄了 contents 數(shù)組的大小。

需要注意的是雖然 contents 數(shù)組聲明為 int8_t 類型，但是實際上contents 數(shù)組并不保存任何 int8_t 類型的值，其真正類型有 encoding 來決定。

①、升級： 能極大地節(jié)省內(nèi)存。

當(dāng)我們新增的元素類型 比原集合元素類型的長度要大時，需要對整數(shù)集合進(jìn)行升級，才能將新元素放入整數(shù)集合中。具體步驟：

• 1、根據(jù)新元素類型，擴(kuò)展 整數(shù)集合底層數(shù)組的 大小，并為新元素分配空間。
• 2、將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)成與新元素相同類型的元素，并將轉(zhuǎn)換后的元素放到正確的位置，放置過程中，維持整個元素順序都是有序的。
• 3、將新元素添加到整數(shù)集合中（保證有序）。

②、降級

整數(shù)集合不支持降級操作，一旦對數(shù)組進(jìn)行了升級，編碼就會一直保持升級后的狀態(tài)。

2.6 壓縮列表

壓縮列表（ziplist）是Redis為了節(jié)省內(nèi)存而開發(fā)的，是由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型數(shù)據(jù)結(jié)構(gòu)，一個壓縮列表可以包含任意多個節(jié)點（entry），每個節(jié)點可以保存一個字節(jié)數(shù)組或者一個整數(shù)值。

壓縮列表的原理： 壓縮列表并不是對數(shù)據(jù)利用某種算法進(jìn)行壓縮，而是將數(shù)據(jù)按照一定規(guī)則編碼在一塊連續(xù)的內(nèi)存區(qū)域，目的是節(jié)省內(nèi)存。

image.png

壓縮列表的每個節(jié)點構(gòu)成如下：

image.png

①、previous_entry_length：記錄壓縮列表 前一個字節(jié) 的長度。previous_entry_length的長度可能是1個字節(jié)或者是5個字節(jié)，如果上一個節(jié)點的長度小于254，則該節(jié)點只需要一個字節(jié)就可以表示前一個節(jié)點的長度了，如果前一個節(jié)點的長度大于等于254，則previous length的第一個字節(jié)為254，后面用四個字節(jié)表示當(dāng)前節(jié)點前一個節(jié)點的長度。利用此原理，即當(dāng)前節(jié)點位置 減去 上一個節(jié)點的長度即得到上一個節(jié)點的起始位置，壓縮列表 可以 從尾部向頭部 遍歷。這么做很有效地 減少了 內(nèi)存的浪費(fèi)。

②、encoding：節(jié)點的encoding保存的是節(jié)點的content的內(nèi)容類型以及長度，encoding類型有兩種，一種字節(jié)數(shù)組，一種是整數(shù)，encoding區(qū)域長度為1字節(jié)、2字節(jié)或者5字節(jié)長。

③、content：content區(qū)域用于保存 節(jié)點的內(nèi)容，節(jié)點內(nèi)容類型和長度，由encoding決定。

3、總結(jié)

大多數(shù)情況下，Redis使用簡單字符串SDS作為字符串的表示，相對于C語言字符串，SDS具有常數(shù)復(fù)雜度 獲取字符串長度，杜絕了緩存區(qū)的溢出，減少了修改字符串長度時，所需的內(nèi)存重分配次數(shù)，以及二進(jìn)制安全，能存儲各種類型的文件，并且還兼容部分C函數(shù)。

通過為鏈表設(shè)置不同類型的特定函數(shù)，Redis鏈表可以 保存各種不同類型的值，除了用作列表鍵，還在發(fā)布與訂閱、慢查詢、監(jiān)視器等方面發(fā)揮作用（后面會介紹）。

Redis的字典 底層 使用 哈希表實現(xiàn)，每個字典通常有兩個哈希表，一個平時使用，另一個用于rehash時使用，使用鏈地址法解決哈希沖突。

跳躍表通常是有序集合 的底層實現(xiàn)之一，表中的節(jié)點按照分值大小進(jìn)行排序。

整數(shù)集合是集合 的底層實現(xiàn)之一，底層由數(shù)組構(gòu)成，升級特性能盡可能的節(jié)省內(nèi)存。

壓縮列表是Redis為節(jié)省內(nèi)存而開發(fā)的順序型數(shù)據(jù)結(jié)構(gòu)，通常作為列表鍵和哈希鍵的底層實現(xiàn)之一。

以上介紹的簡單字符串、鏈表、字典、跳躍表、整數(shù)集合、壓縮列表等數(shù)據(jù)結(jié)構(gòu)就是Redis底層的一些數(shù)據(jù)結(jié)構(gòu)。