Redis系列（二）: 連集合底層實(shí)現(xiàn)原理都不知道，你敢說(shuō)Redis用的很溜？
★?一枚用心堅(jiān)持寫原創(chuàng)的“無(wú)趣”程序猿，在自身受益的同時(shí)也讓朋友們?cè)诩夹g(shù)上有所提升。
目錄
SDS 的設(shè)計(jì)到底有多牛逼。 List、Set、Sorted Set、Hash 底層實(shí)現(xiàn)原理
SDS 的設(shè)計(jì)到底有多牛逼
Redis 使用 C 語(yǔ)言編寫，但是并沒(méi)有直接使用 C 語(yǔ)言自帶的字符串，而是使用了 SDS 來(lái)管理字符串。接下來(lái)就來(lái)探討下為什么 Redis 使用了 SDS 來(lái)管理字符串。
SDS 全稱 Simple Dynamic String，即簡(jiǎn)單動(dòng)態(tài)字符串。SDS 組成部分如下：
free：表示 buf 中的空閑的空間大小，圖左空閑空間為 0，圖右空閑空間為 3 len：表示 buf 中的內(nèi)容長(zhǎng)度，注意 len 的長(zhǎng)度不包括 ' \0 '（字符串以\0 結(jié)尾是為了使用 C 語(yǔ)言中現(xiàn)成的庫(kù)函數(shù)，而不需要重新造輪子） buf：一個(gè) char 類型的數(shù)組，用于存儲(chǔ)實(shí)際字符串的內(nèi)容。
SDS 的優(yōu)勢(shì)
獲取字符串長(zhǎng)度的復(fù)雜度為 O(1)；直接可通過(guò) len 屬性獲得字符串的長(zhǎng)度。 防止 buf 存儲(chǔ)內(nèi)容溢出的問(wèn)題；每次增加字符串的長(zhǎng)度的時(shí)候先檢查 free 屬性是否能存下要增加的字符串的長(zhǎng)度，如果不夠，則先對(duì) buf 數(shù)組擴(kuò)容，然后在將內(nèi)容存入 buf 數(shù)組中。 空間預(yù)分配&空間惰性釋放；SDS 會(huì)預(yù)先分配一部分空閑空間，當(dāng)字符串內(nèi)容添加時(shí)不需要做空間申請(qǐng)的工作，當(dāng)字符串從 buf 數(shù)組中移除時(shí)，空閑出來(lái)的空間不會(huì)立馬被內(nèi)存回收，防止新增字符串的內(nèi)容寫入時(shí)空間不夠而臨時(shí)申請(qǐng)空間。
二級(jí)制安全性；由于字符串是存儲(chǔ)在 char 類型的數(shù)組中，即內(nèi)容是以二進(jìn)制的形式存儲(chǔ)的，所以 SDS 可以存儲(chǔ)任何類型的二進(jìn)制數(shù)據(jù)，同時(shí)也不需要擔(dān)心數(shù)據(jù)格式轉(zhuǎn)換的問(wèn)題。
List 的實(shí)現(xiàn)原理
在 Redis3.2 之前，List 底層采用了 ZipList 和 LinkedList 實(shí)現(xiàn)的，在 3.2 之后，List 底層采用了 QuickList。
Redis3.2 之前，初始化的 List 使用的 ZipList，List 滿足以下兩個(gè)條件時(shí)則一直使用 ZipList 作為底層實(shí)現(xiàn)，當(dāng)以下兩個(gè)條件任一一個(gè)不滿足時(shí)，則會(huì)被轉(zhuǎn)換成 LinkedList。
List 中存儲(chǔ)的每個(gè)元素的長(zhǎng)度小于 64byte 元素個(gè)數(shù)小于 512
ZipList方式?的實(shí)現(xiàn)原理
ZipList 是由一塊連續(xù)的存儲(chǔ)空間組成，從圖中可以看出 ZipList 沒(méi)有前后指針。
各部分作用說(shuō)明：
zlbytes：表示當(dāng)前 list 的存儲(chǔ)元素的總長(zhǎng)度。
zllen：表示當(dāng)前 list 存儲(chǔ)的元素的個(gè)數(shù)。
zltail：表示當(dāng)前 list 的頭結(jié)點(diǎn)的地址，通過(guò) zltail 就是可以實(shí)現(xiàn) list 的遍歷。
zlend：表示當(dāng)前 list 的結(jié)束標(biāo)識(shí)。
entry：表示存儲(chǔ)實(shí)際數(shù)據(jù)的節(jié)點(diǎn)，每個(gè) entry 代表一個(gè)元素。
previours_entry_length: 表示當(dāng)前節(jié)點(diǎn)元素的長(zhǎng)度，通過(guò)其長(zhǎng)度可以計(jì)算出下一個(gè)元素的位置。 encoding：表示元素的編碼格式。 content：表示實(shí)際存儲(chǔ)的元素內(nèi)容。
ZipList 的優(yōu)缺點(diǎn)比較
優(yōu)點(diǎn)：內(nèi)存地址連續(xù)，省去了每個(gè)元素的頭尾節(jié)點(diǎn)指針占用的內(nèi)存。 缺點(diǎn)：對(duì)于刪除和插入操作比較可能會(huì)觸發(fā)連鎖更新反應(yīng)，比如在 list 中間插入刪除一個(gè)元素時(shí)，在插入或刪除位置后面的元素可能都需要發(fā)生相應(yīng)的移動(dòng)操作。
LinkedList方式 的實(shí)現(xiàn)原理
LinkedList 都比較熟悉了，是由一系列不連續(xù)的內(nèi)存塊通過(guò)指針連接起來(lái)的雙向鏈表。
各部分作用說(shuō)明：
head：表示 List 的頭結(jié)點(diǎn)；通過(guò)其可以找到 List 的頭節(jié)點(diǎn)。 tail：表示 List 的尾節(jié)點(diǎn)；通過(guò)其可以找到 List 的尾節(jié)點(diǎn)。 len：表示 List 存儲(chǔ)的元素個(gè)數(shù)。 dup：表示用于復(fù)制元素的函數(shù)。 free：表示用于釋放元素的函數(shù)。 match：表示用于對(duì)比元素的函數(shù)。
QuickList方式 的實(shí)現(xiàn)原理
在 Redis3.2 版本之后，Redis 集合采用了 QuickList 作為 List 的底層實(shí)現(xiàn)，QuickList 其實(shí)就是結(jié)合了 ZipList 和 LinkedList 的優(yōu)點(diǎn)設(shè)計(jì)出來(lái)的。
各部分作用說(shuō)明：
每個(gè) listNode 存儲(chǔ)一個(gè)指向 ZipList 的指針，ZipList 用來(lái)真正存儲(chǔ)元素的數(shù)據(jù)。 ZipList 中存儲(chǔ)的元素?cái)?shù)據(jù)總大小超過(guò) 8kb（默認(rèn)大小，通過(guò) list-max-ziplist-size 參數(shù)可以進(jìn)行配置）的時(shí)候，就會(huì)重新創(chuàng)建出來(lái)一個(gè) ListNode 和 ZipList，然后將其通過(guò)指針關(guān)聯(lián)起來(lái)。
Set 的實(shí)現(xiàn)原理
Set 集合采用了整數(shù)集合和字典兩種方式來(lái)實(shí)現(xiàn)的，當(dāng)滿足如下兩個(gè)條件的時(shí)候，采用整數(shù)集合實(shí)現(xiàn)；一旦有一個(gè)條件不滿足時(shí)則采用字典來(lái)實(shí)現(xiàn)。
Set 集合中的所有元素都為整數(shù) Set 集合中的元素個(gè)數(shù)不大于 512（默認(rèn) 512，可以通過(guò)修改 set-max-intset-entries 配置調(diào)整集合大?。?/section>
Zset 的實(shí)現(xiàn)原理
Zset 底層同樣采用了兩種方式來(lái)實(shí)現(xiàn)，分別是 ZipList 和 SkipList。當(dāng)同時(shí)滿足以下兩個(gè)條件時(shí)，采用 ZipList 實(shí)現(xiàn)；反之采用 SkipList 實(shí)現(xiàn)。
Zset 中保存的元素個(gè)數(shù)小于 128。（通過(guò)修改 zset-max-ziplist-entries 配置來(lái)修改） Zset 中保存的所有元素長(zhǎng)度小于 64byte。（通過(guò)修改 zset-max-ziplist-values 配置來(lái)修改）
采用 ZipList 的實(shí)現(xiàn)原理
和 List 的底層實(shí)現(xiàn)有些相似，對(duì)于 Zset 不同的是，其存儲(chǔ)是以鍵值對(duì)的方式依次排列，鍵存儲(chǔ)的是實(shí)際 value，值存儲(chǔ)的是 value 對(duì)應(yīng)的分值。
采用 SkipList 的實(shí)現(xiàn)原理
SkipList 分為兩部分，dict 部分是由字典實(shí)現(xiàn)，Zset 部分使用跳躍表實(shí)現(xiàn)，從圖中可以看出，dict 和跳躍表都存儲(chǔ)的數(shù)據(jù)，實(shí)際上 dict 和跳躍表最終使用指針都指向了同一份數(shù)據(jù)，即數(shù)據(jù)是被兩部分共享的，為了方便表達(dá)將同一份數(shù)據(jù)展示在兩個(gè)地方。
關(guān)于跳躍表和字典的具體實(shí)現(xiàn)，此處不詳細(xì)介紹，想深入了解的朋友自行上網(wǎng)查閱。
Hash 的實(shí)現(xiàn)原理。
Hash 底層實(shí)現(xiàn)采用了 ZipList 和 HashTable 兩種實(shí)現(xiàn)方式，相信看到這里大家都比較輕車熟路了，下面來(lái)看看。Hash 結(jié)構(gòu)當(dāng)同時(shí)滿足如下兩個(gè)條件時(shí)底層采用了 ZipList 實(shí)現(xiàn)，一旦有一個(gè)條件不滿足時(shí)，就會(huì)被轉(zhuǎn)碼為 HashTable 進(jìn)行存儲(chǔ)。
Hash 中存儲(chǔ)的所有元素的 key 和 value 的長(zhǎng)度都小于 64byte。（通過(guò)修改 hash-max-ziplist-value 配置調(diào)節(jié)大?。?/section> Hash 中存儲(chǔ)的元素個(gè)數(shù)小于 512。（通過(guò)修改 hash-max-ziplist-entries 配置調(diào)節(jié)大?。?/section>
ZipList方式 的實(shí)現(xiàn)原理
從圖上看是不是很熟悉，其實(shí)和 Zset 的 ZipList 的實(shí)現(xiàn)邏輯幾乎相同，就不多介紹了。
HashTable方式 的實(shí)現(xiàn)原理
HashTable 實(shí)現(xiàn)底層采用了字段的方式實(shí)現(xiàn)，其中鍵存儲(chǔ)的內(nèi)容為 field，值存儲(chǔ)的是 value 值。
總結(jié)
本文主要介紹了 5 種基礎(chǔ)常用集合的底層實(shí)現(xiàn)原理，相信大家看完之后，在業(yè)務(wù)開(kāi)發(fā)時(shí)對(duì)集合選用，同時(shí)結(jié)合業(yè)務(wù)使用的命令更加有自己的理解。
下篇文章我們來(lái)介紹 Redis 數(shù)據(jù)過(guò)期策略、AOF 及 RDB 文件等內(nèi)容，盡情期待。