SDS

• 無(wú)論是 Redis 的 Key 還是 Value，其基礎(chǔ)數(shù)據(jù)類型都是字符串。
• 雖然 Redis是使用標(biāo)準(zhǔn) C 語(yǔ)言開(kāi)發(fā)的，但并沒(méi)有直接使用 C 語(yǔ)言中傳統(tǒng)的字符串表示，而是自定義了一 種字符串。這種字符串本身的結(jié)構(gòu)比較簡(jiǎn)單，但功能卻非常強(qiáng)大，稱為簡(jiǎn)單動(dòng)態(tài)字符串，Simple Dynamic String，簡(jiǎn)稱 SDS。

SDS 結(jié)構(gòu)

SDS 不同于 C 字符串。C 字符串本身是一個(gè)以雙引號(hào)括起來(lái)，以空字符’\0’結(jié)尾的字符序 列。但 SDS 是一個(gè)結(jié)構(gòu)體，定義在 Redis 安裝目錄下的 src/sds.h 中：

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

通過(guò)以上結(jié)構(gòu)可以看出，SDS 的 buf 值實(shí)際是一個(gè) C 字符串，包含空字符’\0’共占 6 個(gè)字 節(jié)。**但 SDS 的 len 是不包含空字符’\0’的。
**

SDS 的優(yōu)勢(shì)

• 對(duì)于 C 字符串，若要獲取其長(zhǎng)度，則必須要通過(guò)遍歷整個(gè)字符串才可獲取到的。對(duì)于超 長(zhǎng)字符串的遍歷，會(huì)成為系統(tǒng)的性能瓶頸。 SDS 結(jié)構(gòu)體中直接就存放著字符串的長(zhǎng)度數(shù)據(jù)

• SDS 采用了空間預(yù)分配策略與惰性空間釋放策略來(lái)避免內(nèi)存再分配問(wèn)題。

• 空間預(yù)分配策略是指，每次 SDS 進(jìn)行空間擴(kuò)展時(shí)，程序不但為其分配所需的空間，還會(huì) 為其分配**額外的未使用空間，以減少內(nèi)存再分配次數(shù)。**而額外分配的未使用空間大小取決于 空間擴(kuò)展后 SDS 的 len 屬性值。

  • 如果 len 屬性值**小于 1M，**那么分配的未使用空間 free 的大小與 len 屬性值相同。
  • 如果 len 屬性值大于等于 1M ，那么分配的未使用空間 free 的大小固定是 1M。

• SDS 對(duì)于空間釋放采用的是惰性空間釋放策略。

  • 該策略是指，SDS 字符串長(zhǎng)度如果縮短， 那么多出的未使用空間將暫時(shí)不釋放，而是增加到 free 中。以使后期擴(kuò)展 SDS 時(shí)減少內(nèi)存 再分配次數(shù)。 如果要釋放 SDS 的未使用空間，則可通過(guò) sdsRemoveFreeSpace()函數(shù)來(lái)釋放。

集合的底層實(shí)現(xiàn)原理

• Redis 中對(duì)于 Set 類型的底層實(shí)現(xiàn)，直接采用了 hashTable。hashtable就是普通的哈希表（key為set的值，value為null）。
• 但對(duì)于 Hash、ZSet、List 集 合的底層實(shí)現(xiàn)進(jìn)行了特殊的設(shè)計(jì)，使其保證了 Redis 的高性能。

1 兩種實(shí)現(xiàn)的選擇

• 對(duì)于Hash與ZSet集合，其底層的實(shí)現(xiàn)實(shí)際有兩種：壓縮列表zipList，與跳躍列表skipList。
• 這兩種實(shí)現(xiàn)對(duì)于用戶來(lái)說(shuō)是透明的，但用戶寫(xiě)入不同的數(shù)據(jù)，系統(tǒng)會(huì)自動(dòng)使用不同的實(shí)現(xiàn)。 只有同時(shí)滿足以配置文件 redis.conf 中相關(guān)集合元素?cái)?shù)量閾值與元素大小閾值兩個(gè)條件****，使用的就是壓縮列表 zipList，只要有一個(gè)條件不滿足使用的就是跳躍列表 skipList。、
• 例如，對(duì)于ZSet 集合中這兩個(gè)條件如下：
  • 集合元素個(gè)數(shù)小于 redis.conf 中 zset-max-ziplist-entries 屬性的值，其默認(rèn)值為 128
  • 每個(gè)集合元素大小都小于 redis.conf 中 zset-max-ziplist-value 屬性的值，其默認(rèn)值為 64字節(jié)

2什么是 zipList

zipList，通常稱為壓縮列表，是一個(gè)經(jīng)過(guò)特殊編碼的用于存儲(chǔ)字符串或整數(shù)的雙向鏈表。 其底層數(shù)據(jù)結(jié)構(gòu)由三部分構(gòu)成：**head、entries 與 end。**這三部分在內(nèi)存上是連續(xù)存放的。

• prevlength：該部分用于記錄上一個(gè) entry 的長(zhǎng)度，以實(shí)現(xiàn)逆序遍歷。
• encoding：該部分用于標(biāo)志后面的 data 的具體類型。如果 data 為整數(shù)類型，encoding固定長(zhǎng)度為 1 字節(jié)。如果 data 為字符串類型，則 encoding 長(zhǎng)度可能會(huì)是 1 字節(jié)、2 字 節(jié)或 5 字節(jié)。data 字符串不同的長(zhǎng)度，對(duì)應(yīng)著不同的 encoding 長(zhǎng)度。（壓縮的體現(xiàn)）。

什么是** skipList

skipList，跳躍列表，簡(jiǎn)稱跳表，是一種**隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表，**實(shí)現(xiàn)簡(jiǎn)單， 查找效率較高。簡(jiǎn)單來(lái)說(shuō)跳表也是鏈表的一種，只不過(guò)它在鏈表的基礎(chǔ)上增加了跳躍功能。 也正是這個(gè)跳躍功能，使得在查找元素時(shí)，能夠提供較高的效率。

skipList 原理

假設(shè)有一個(gè)帶頭尾結(jié)點(diǎn)的有序鏈表。

為了提升查找效率，在偶數(shù)結(jié)點(diǎn)上增加一個(gè)指針，讓其指向下一個(gè)偶數(shù)結(jié)點(diǎn)。

這樣所有偶數(shù)結(jié)點(diǎn)就連成了一個(gè)新的鏈表（簡(jiǎn)稱高層鏈表），當(dāng)然，高層鏈表包含的節(jié) 點(diǎn)個(gè)數(shù)只是原來(lái)鏈表的一半。此時(shí)再想查找某個(gè)數(shù)據(jù)時(shí)，先沿著高層鏈表進(jìn)行查找。當(dāng)遇到 第一個(gè)比待查數(shù)據(jù)大的節(jié)點(diǎn)時(shí)，立即從該大節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)回到原鏈表中進(jìn)行查找。

問(wèn)題：這種對(duì)鏈表分層級(jí)的方式從原理上看確實(shí)提升了查找效率，但在實(shí)際操作時(shí)就出現(xiàn)了問(wèn) 題：由于固定序號(hào)的元素?fù)碛泄潭▽蛹?jí)，所以列表元素出現(xiàn)增加或刪除的情況下，會(huì)導(dǎo)致列表整體元素層級(jí)大調(diào)整，但這樣勢(shì)必會(huì)大大降低系統(tǒng)性能。

優(yōu)化

為了避免前面的問(wèn)題，skipList 采用了隨機(jī)分配層級(jí)方式。即在確定了總層級(jí)后，每添 加一個(gè)新的元素時(shí)會(huì)自動(dòng)為其隨機(jī)分配一個(gè)層級(jí)。這種隨機(jī)性就解決了節(jié)點(diǎn)序號(hào)與層級(jí)間的 固定關(guān)系問(wèn)題。

• 上圖演示了列表在生成過(guò)程中為每個(gè)元素隨機(jī)分配層級(jí)的過(guò)程。從這個(gè) skiplist 的創(chuàng)建 和插入過(guò)程可以看出，每一個(gè)節(jié)點(diǎn)的層級(jí)數(shù)都是隨機(jī)分配的，而且新插入一個(gè)節(jié)點(diǎn)不會(huì)影響 到其它節(jié)點(diǎn)的層級(jí)數(shù)。
• 只需要**修改插入節(jié)點(diǎn)前后的指針，**而不需對(duì)很多節(jié)點(diǎn)都進(jìn)行調(diào)整。這 就降低了插入操作的復(fù)雜度。

什么是 quickList

• List的底層實(shí)現(xiàn)： quickList，快速列表，quickList 本身是一個(gè)雙向無(wú)循環(huán)鏈表，它的每一個(gè)節(jié)點(diǎn)都是一個(gè)zipList。

• quickList 本質(zhì)上是 zipList 和 linkedList 的混合體。其將 linkedList 按段切分，每一段使用 zipList 來(lái)緊湊存儲(chǔ)若干真正的數(shù)據(jù)元素，多個(gè) zipList 之間使用雙向指針串接起來(lái)。當(dāng)然， 對(duì)于每個(gè) zipList 中最多可存放多大容量的數(shù)據(jù)元素，在配置文件中通過(guò) list-max-ziplist-size屬性可以指定。