前言

1. 學(xué)習(xí)視頻： 黑馬程序員Redis入門到實(shí)戰(zhàn)教程，深度透析redis底層原理+redis分布式鎖+企業(yè)解決方案+黑馬點(diǎn)評(píng)實(shí)戰(zhàn)項(xiàng)目

2. 中間件系列 - Redis入門到實(shí)戰(zhàn)

3. 本內(nèi)容僅用于個(gè)人學(xué)習(xí)筆記，如有侵?jǐn)_，聯(lián)系刪除

4. 學(xué)習(xí)目標(biāo)

   • Redis數(shù)據(jù)結(jié)構(gòu)
   • Redis網(wǎng)絡(luò)模型
   • Redis通信協(xié)議-RESP協(xié)議

1 Redis數(shù)據(jù)結(jié)構(gòu)

1.1 動(dòng)態(tài)字符串

我們都知道Redis中保存的Key是字符串，value往往是字符串或者字符串的集合?？梢娮址荝edis中最常用的一種數(shù)據(jù)結(jié)構(gòu)。

不過(guò)Redis沒有直接使用C語(yǔ)言中的字符串，因?yàn)镃語(yǔ)言字符串存在很多問(wèn)題：

• 獲取字符串長(zhǎng)度的需要通過(guò)運(yùn)算
• 非二進(jìn)制安全
• 不可修改

Redis構(gòu)建了一種新的字符串結(jié)構(gòu)，稱為簡(jiǎn)單動(dòng)態(tài)字符串（Simple Dynamic String），簡(jiǎn)稱SDS。

例如，我們執(zhí)行命令：

那么Redis將在底層創(chuàng)建兩個(gè)SDS，其中一個(gè)是包含“name”的SDS，另一個(gè)是包含“虎哥”的SDS。

Redis是C語(yǔ)言實(shí)現(xiàn)的，其中SDS是一個(gè)結(jié)構(gòu)體，源碼如下：

例如，一個(gè)包含字符串“name”的sds結(jié)構(gòu)如下：

SDS之所以叫做動(dòng)態(tài)字符串，是因?yàn)樗邆鋭?dòng)態(tài)擴(kuò)容的能力，例如一個(gè)內(nèi)容為“hi”的SDS：

假如我們要給SDS追加一段字符串“,Amy”，這里首先會(huì)申請(qǐng)新內(nèi)存空間：

如果新字符串小于1M，則新空間為擴(kuò)展后字符串長(zhǎng)度的兩倍+1；

如果新字符串大于1M，則新空間為擴(kuò)展后字符串長(zhǎng)度+1M+1。稱為內(nèi)存預(yù)分配。

1.2 intset

IntSet是Redis中set集合的一種實(shí)現(xiàn)方式，基于整數(shù)數(shù)組來(lái)實(shí)現(xiàn)，并且具備長(zhǎng)度可變、有序等特征。
結(jié)構(gòu)如下：

其中的encoding包含三種模式，表示存儲(chǔ)的整數(shù)大小不同：

現(xiàn)在，數(shù)組中每個(gè)數(shù)字都在int16_t的范圍內(nèi)，因此采用的編碼方式是INTSET_ENC_INT16，每部分占用的字節(jié)大小為：
encoding：4字節(jié)
length：4字節(jié)
contents：2字節(jié) * 3 = 6字節(jié)

我們向該其中添加一個(gè)數(shù)字：50000，這個(gè)數(shù)字超出了int16_t的范圍，intset會(huì)自動(dòng)升級(jí)編碼方式到合適的大小。
以當(dāng)前案例來(lái)說(shuō)流程如下：

• 升級(jí)編碼為INTSET_ENC_INT32, 每個(gè)整數(shù)占4字節(jié)，并按照新的編碼方式及元素個(gè)數(shù)擴(kuò)容數(shù)組
• 倒序依次將數(shù)組中的元素拷貝到擴(kuò)容后的正確位置
• 將待添加的元素放入數(shù)組末尾
• 最后，將inset的encoding屬性改為INTSET_ENC_INT32，將length屬性改為4
  

源碼如下：

小總結(jié)：

Intset可以看做是特殊的整數(shù)數(shù)組，具備一些特點(diǎn)：

• Redis會(huì)確保Intset中的元素唯一、有序
• 具備類型升級(jí)機(jī)制，可以節(jié)省內(nèi)存空間
• 底層采用二分查找方式來(lái)查詢

1.3 Dict

我們知道Redis是一個(gè)鍵值型（Key-Value Pair）的數(shù)據(jù)庫(kù)，我們可以根據(jù)鍵實(shí)現(xiàn)快速的增刪改查。而鍵與值的映射關(guān)系正是通過(guò)Dict來(lái)實(shí)現(xiàn)的。

Dict由三部分組成，分別是：哈希表（DictHashTable）、哈希節(jié)點(diǎn)（DictEntry）、字典（Dict）

當(dāng)我們向Dict添加鍵值對(duì)時(shí)，Redis首先根據(jù)key計(jì)算出hash值（h），然后利用 h & sizemask來(lái)計(jì)算元素應(yīng)該存儲(chǔ)到數(shù)組中的哪個(gè)索引位置。我們存儲(chǔ)k1=v1，假設(shè)k1的哈希值h =1，則1&3 =1，因此k1=v1要存儲(chǔ)到數(shù)組角標(biāo)1位置。

Dict由三部分組成，分別是：哈希表（DictHashTable）、哈希節(jié)點(diǎn)（DictEntry）、字典（Dict）

Dict的擴(kuò)容

Dict中的HashTable就是數(shù)組結(jié)合單向鏈表的實(shí)現(xiàn)，當(dāng)集合中元素較多時(shí)，必然導(dǎo)致哈希沖突增多，鏈表過(guò)長(zhǎng)，則查詢效率會(huì)大大降低。
Dict在每次新增鍵值對(duì)時(shí)都會(huì)檢查負(fù)載因子（LoadFactor = used/size） ，滿足以下兩種情況時(shí)會(huì)觸發(fā)哈希表擴(kuò)容：
哈希表的 LoadFactor >= 1，并且服務(wù)器沒有執(zhí)行 BGSAVE 或者 BGREWRITEAOF 等后臺(tái)進(jìn)程；
哈希表的 LoadFactor > 5 ；

Dict的rehash

不管是擴(kuò)容還是收縮，必定會(huì)創(chuàng)建新的哈希表，導(dǎo)致哈希表的size和sizemask變化，而key的查詢與sizemask有關(guān)。因此必須對(duì)哈希表中的每一個(gè)key重新計(jì)算索引，插入新的哈希表，這個(gè)過(guò)程稱為rehash。過(guò)程是這樣的：

• 計(jì)算新hash表的realeSize，值取決于當(dāng)前要做的是擴(kuò)容還是收縮：

  • 如果是擴(kuò)容，則新size為第一個(gè)大于等于dict.ht[0].used + 1的2^n
  • 如果是收縮，則新size為第一個(gè)大于等于dict.ht[0].used的2^n （不得小于4）

• 按照新的realeSize申請(qǐng)內(nèi)存空間，創(chuàng)建dictht，并賦值給dict.ht[1]

• 設(shè)置dict.rehashidx = 0，標(biāo)示開始rehash

• 將dict.ht[0]中的每一個(gè)dictEntry都rehash到dict.ht[1]

• 將dict.ht[1]賦值給dict.ht[0]，給dict.ht[1]初始化為空哈希表，釋放原來(lái)的dict.ht[0]的內(nèi)存

• 將rehashidx賦值為-1，代表rehash結(jié)束

• 在rehash過(guò)程中，新增操作，則直接寫入ht[1]，查詢、修改和刪除則會(huì)在dict.ht[0]和dict.ht[1]依次查找并執(zhí)行。這樣可以確保ht[0]的數(shù)據(jù)只減不增，隨著rehash最終為空

整個(gè)過(guò)程可以描述成：

小總結(jié)：

Dict的結(jié)構(gòu)：

• 類似java的HashTable，底層是數(shù)組加鏈表來(lái)解決哈希沖突
• Dict包含兩個(gè)哈希表，ht[0]平常用，ht[1]用來(lái)rehash

Dict的伸縮：

• 當(dāng)LoadFactor大于5或者LoadFactor大于1并且沒有子進(jìn)程任務(wù)時(shí)，Dict擴(kuò)容
• 當(dāng)LoadFactor小于0.1時(shí)，Dict收縮
• 擴(kuò)容大小為第一個(gè)大于等于used + 1的2^n
• 收縮大小為第一個(gè)大于等于used 的2^n
• Dict采用漸進(jìn)式rehash，每次訪問(wèn)Dict時(shí)執(zhí)行一次rehash
• rehash時(shí)ht[0]只減不增，新增操作只在ht[1]執(zhí)行，其它操作在兩個(gè)哈希表

1.4 ZipList

ZipList 是一種特殊的“雙端鏈表” ，由一系列特殊編碼的連續(xù)內(nèi)存塊組成?？梢栽谌我庖欢诉M(jìn)行壓入/彈出操作, 并且該操作的時(shí)間復(fù)雜度為 O(1)。

ZipListEntry

ZipList 中的Entry并不像普通鏈表那樣記錄前后節(jié)點(diǎn)的指針，因?yàn)橛涗泝蓚€(gè)指針要占用16個(gè)字節(jié)，浪費(fèi)內(nèi)存。而是采用了下面的結(jié)構(gòu)：

• previous_entry_length：前一節(jié)點(diǎn)的長(zhǎng)度，占1個(gè)或5個(gè)字節(jié)。

  • 如果前一節(jié)點(diǎn)的長(zhǎng)度小于254字節(jié)，則采用1個(gè)字節(jié)來(lái)保存這個(gè)長(zhǎng)度值
  • 如果前一節(jié)點(diǎn)的長(zhǎng)度大于254字節(jié)，則采用5個(gè)字節(jié)來(lái)保存這個(gè)長(zhǎng)度值，第一個(gè)字節(jié)為0xfe，后四個(gè)字節(jié)才是真實(shí)長(zhǎng)度數(shù)據(jù)

• encoding：編碼屬性，記錄content的數(shù)據(jù)類型（字符串還是整數(shù)）以及長(zhǎng)度，占用1個(gè)、2個(gè)或5個(gè)字節(jié)

• contents：負(fù)責(zé)保存節(jié)點(diǎn)的數(shù)據(jù)，可以是字符串或整數(shù)

ZipList中所有存儲(chǔ)長(zhǎng)度的數(shù)值均采用小端字節(jié)序，即低位字節(jié)在前，高位字節(jié)在后。例如：數(shù)值0x1234，采用小端字節(jié)序后實(shí)際存儲(chǔ)值為：0x3412

Encoding編碼

ZipListEntry中的encoding編碼分為字符串和整數(shù)兩種：
字符串：如果encoding是以“00”、“01”或者“10”開頭，則證明content是字符串

例如，我們要保存字符串：“ab”和 “bc”

ZipListEntry中的encoding編碼分為字符串和整數(shù)兩種：

• 整數(shù)：如果encoding是以“11”開始，則證明content是整數(shù)，且encoding固定只占用1個(gè)字節(jié)

1.5 ZipList的連鎖更新問(wèn)題

ZipList的每個(gè)Entry都包含previous_entry_length來(lái)記錄上一個(gè)節(jié)點(diǎn)的大小，長(zhǎng)度是1個(gè)或5個(gè)字節(jié)：
如果前一節(jié)點(diǎn)的長(zhǎng)度小于254字節(jié)，則采用1個(gè)字節(jié)來(lái)保存這個(gè)長(zhǎng)度值
如果前一節(jié)點(diǎn)的長(zhǎng)度大于等于254字節(jié)，則采用5個(gè)字節(jié)來(lái)保存這個(gè)長(zhǎng)度值，第一個(gè)字節(jié)為0xfe，后四個(gè)字節(jié)才是真實(shí)長(zhǎng)度數(shù)據(jù)
現(xiàn)在，假設(shè)我們有N個(gè)連續(xù)的、長(zhǎng)度為250~253字節(jié)之間的entry，因此entry的previous_entry_length屬性用1個(gè)字節(jié)即可表示，如圖所示：

ZipList這種特殊情況下產(chǎn)生的連續(xù)多次空間擴(kuò)展操作稱之為連鎖更新（Cascade Update）。新增、刪除都可能導(dǎo)致連鎖更新的發(fā)生。

小總結(jié)：

ZipList特性：

• 壓縮列表的可以看做一種連續(xù)內(nèi)存空間的"雙向鏈表"
• 列表的節(jié)點(diǎn)之間不是通過(guò)指針連接，而是記錄上一節(jié)點(diǎn)和本節(jié)點(diǎn)長(zhǎng)度來(lái)尋址，內(nèi)存占用較低
• 如果列表數(shù)據(jù)過(guò)多，導(dǎo)致鏈表過(guò)長(zhǎng)，可能影響查詢性能
• 增或刪較大數(shù)據(jù)時(shí)有可能發(fā)生連續(xù)更新問(wèn)題

1.6 QuickList

問(wèn)題1：ZipList雖然節(jié)省內(nèi)存，但申請(qǐng)內(nèi)存必須是連續(xù)空間，如果內(nèi)存占用較多，申請(qǐng)內(nèi)存效率很低。怎么辦？

? 答：為了緩解這個(gè)問(wèn)題，我們必須限制ZipList的長(zhǎng)度和entry大小。

問(wèn)題2：但是我們要存儲(chǔ)大量數(shù)據(jù)，超出了ZipList最佳的上限該怎么辦？

? 答：我們可以創(chuàng)建多個(gè)ZipList來(lái)分片存儲(chǔ)數(shù)據(jù)。

問(wèn)題3：數(shù)據(jù)拆分后比較分散，不方便管理和查找，這多個(gè)ZipList如何建立聯(lián)系？

? 答：Redis在3.2版本引入了新的數(shù)據(jù)結(jié)構(gòu)QuickList，它是一個(gè)雙端鏈表，只不過(guò)鏈表中的每個(gè)節(jié)點(diǎn)都是一個(gè)ZipList。

為了避免QuickList中的每個(gè)ZipList中entry過(guò)多，Redis提供了一個(gè)配置項(xiàng)：list-max-ziplist-size來(lái)限制。
如果值為正，則代表ZipList的允許的entry個(gè)數(shù)的最大值
如果值為負(fù)，則代表ZipList的最大內(nèi)存大小，分5種情況：

• -1：每個(gè)ZipList的內(nèi)存占用不能超過(guò)4kb
• -2：每個(gè)ZipList的內(nèi)存占用不能超過(guò)8kb
• -3：每個(gè)ZipList的內(nèi)存占用不能超過(guò)16kb
• -4：每個(gè)ZipList的內(nèi)存占用不能超過(guò)32kb
• -5：每個(gè)ZipList的內(nèi)存占用不能超過(guò)64kb

其默認(rèn)值為 -2：

以下是QuickList的和QuickListNode的結(jié)構(gòu)源碼：

我們接下來(lái)用一段流程圖來(lái)描述當(dāng)前的這個(gè)結(jié)構(gòu)

總結(jié)：

QuickList的特點(diǎn)：

• 是一個(gè)節(jié)點(diǎn)為ZipList的雙端鏈表
• 節(jié)點(diǎn)采用ZipList，解決了傳統(tǒng)鏈表的內(nèi)存占用問(wèn)題
• 控制了ZipList大小，解決連續(xù)內(nèi)存空間申請(qǐng)效率問(wèn)題
• 中間節(jié)點(diǎn)可以壓縮，進(jìn)一步節(jié)省了內(nèi)存

1.7 SkipList

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點(diǎn)差異：
元素按照升序排列存儲(chǔ)
節(jié)點(diǎn)可能包含多個(gè)指針，指針跨度不同。

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點(diǎn)差異：
元素按照升序排列存儲(chǔ)
節(jié)點(diǎn)可能包含多個(gè)指針，指針跨度不同。

SkipList（跳表）首先是鏈表，但與傳統(tǒng)鏈表相比有幾點(diǎn)差異：
元素按照升序排列存儲(chǔ)
節(jié)點(diǎn)可能包含多個(gè)指針，指針跨度不同。

小總結(jié)：

SkipList的特點(diǎn)：

• 跳躍表是一個(gè)雙向鏈表，每個(gè)節(jié)點(diǎn)都包含score和ele值
• 節(jié)點(diǎn)按照score值排序，score值一樣則按照ele字典排序
• 每個(gè)節(jié)點(diǎn)都可以包含多層指針，層數(shù)是1到32之間的隨機(jī)數(shù)
• 不同層指針到下一個(gè)節(jié)點(diǎn)的跨度不同，層級(jí)越高，跨度越大
• 增刪改查效率與紅黑樹基本一致，實(shí)現(xiàn)卻更簡(jiǎn)單

1.8 RedisObject

Redis中的任意數(shù)據(jù)類型的鍵和值都會(huì)被封裝為一個(gè)RedisObject，也叫做Redis對(duì)象，源碼如下：

1、什么是redisObject：
從Redis的使用者的角度來(lái)看，?個(gè)Redis節(jié)點(diǎn)包含多個(gè)database（非cluster模式下默認(rèn)是16個(gè)，cluster模式下只能是1個(gè)），而一個(gè)database維護(hù)了從key space到object space的映射關(guān)系。這個(gè)映射關(guān)系的key是string類型，?value可以是多種數(shù)據(jù)類型，比如：
string, list, hash、set、sorted set等。我們可以看到，key的類型固定是string，而value可能的類型是多個(gè)。
?從Redis內(nèi)部實(shí)現(xiàn)的?度來(lái)看，database內(nèi)的這個(gè)映射關(guān)系是用?個(gè)dict來(lái)維護(hù)的。dict的key固定用?種數(shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)就夠了，這就是動(dòng)態(tài)字符串sds。而value則比較復(fù)雜，為了在同?個(gè)dict內(nèi)能夠存儲(chǔ)不同類型的value，這就需要?個(gè)通?的數(shù)據(jù)結(jié)構(gòu)，這個(gè)通用的數(shù)據(jù)結(jié)構(gòu)就是robj，全名是redisObject。

Redis的編碼方式

Redis中會(huì)根據(jù)存儲(chǔ)的數(shù)據(jù)類型不同，選擇不同的編碼方式，共包含11種不同類型：

五種數(shù)據(jù)結(jié)構(gòu)

Redis中會(huì)根據(jù)存儲(chǔ)的數(shù)據(jù)類型不同，選擇不同的編碼方式。每種數(shù)據(jù)類型的使用的編碼方式如下：

1.9 String

String是Redis中最常見的數(shù)據(jù)存儲(chǔ)類型：

其基本編碼方式是RAW，基于簡(jiǎn)單動(dòng)態(tài)字符串（SDS）實(shí)現(xiàn)，存儲(chǔ)上限為512mb。

如果存儲(chǔ)的SDS長(zhǎng)度小于44字節(jié)，則會(huì)采用EMBSTR編碼，此時(shí)object head與SDS是一段連續(xù)空間。申請(qǐng)內(nèi)存時(shí)

只需要調(diào)用一次內(nèi)存分配函數(shù)，效率更高。

（1）底層實(shí)現(xiàn)?式：動(dòng)態(tài)字符串sds 或者 long
String的內(nèi)部存儲(chǔ)結(jié)構(gòu)?般是sds（Simple Dynamic String，可以動(dòng)態(tài)擴(kuò)展內(nèi)存），但是如果?個(gè)String類型的value的值是數(shù)字，那么Redis內(nèi)部會(huì)把它轉(zhuǎn)成long類型來(lái)存儲(chǔ)，從?減少內(nèi)存的使用。

如果存儲(chǔ)的字符串是整數(shù)值，并且大小在LONG_MAX范圍內(nèi)，則會(huì)采用INT編碼：直接將數(shù)據(jù)保存在RedisObject的ptr指針位置（剛好8字節(jié)），不再需要SDS了。

確切地說(shuō)，String在Redis中是??個(gè)robj來(lái)表示的。

用來(lái)表示String的robj可能編碼成3種內(nèi)部表?：OBJ_ENCODING_RAW，OBJ_ENCODING_EMBSTR，OBJ_ENCODING_INT。
其中前兩種編碼使?的是sds來(lái)存儲(chǔ)，最后?種OBJ_ENCODING_INT編碼直接把string存成了long型。
在對(duì)string進(jìn)行incr, decr等操作的時(shí)候，如果它內(nèi)部是OBJ_ENCODING_INT編碼，那么可以直接行加減操作；如果它內(nèi)部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR編碼，那么Redis會(huì)先試圖把sds存儲(chǔ)的字符串轉(zhuǎn)成long型，如果能轉(zhuǎn)成功，再進(jìn)行加減操作。對(duì)?個(gè)內(nèi)部表示成long型的string執(zhí)行append, setbit, getrange這些命令，針對(duì)的仍然是string的值（即?進(jìn)制表示的字符串），而不是針對(duì)內(nèi)部表?的long型進(jìn)?操作。比如字符串”32”，如果按照字符數(shù)組來(lái)解釋，它包含兩個(gè)字符，它們的ASCII碼分別是0x33和0x32。當(dāng)我們執(zhí)行命令setbit key 7 0的時(shí)候，相當(dāng)于把字符0x33變成了0x32，這樣字符串的值就變成了”22”。?如果將字符串”32”按照內(nèi)部的64位long型來(lái)解釋，那么它是0x0000000000000020，在這個(gè)基礎(chǔ)上執(zhí)?setbit位操作，結(jié)果就完全不對(duì)了。因此，在這些命令的實(shí)現(xiàn)中，會(huì)把long型先轉(zhuǎn)成字符串再進(jìn)行相應(yīng)的操作。

2.0 List

Redis的List類型可以從首、尾操作列表中的元素：

哪一個(gè)數(shù)據(jù)結(jié)構(gòu)能滿足上述特征？

• LinkedList ：普通鏈表，可以從雙端訪問(wèn)，內(nèi)存占用較高，內(nèi)存碎片較多
• ZipList ：壓縮列表，可以從雙端訪問(wèn)，內(nèi)存占用低，存儲(chǔ)上限低
• QuickList：LinkedList + ZipList，可以從雙端訪問(wèn)，內(nèi)存占用較低，包含多個(gè)ZipList，存儲(chǔ)上限高

Redis的List結(jié)構(gòu)類似一個(gè)雙端鏈表，可以從首、尾操作列表中的元素：

在3.2版本之前，Redis采用ZipList和LinkedList來(lái)實(shí)現(xiàn)List，當(dāng)元素?cái)?shù)量小于512并且元素大小小于64字節(jié)時(shí)采用ZipList編碼，超過(guò)則采用LinkedList編碼。

在3.2版本之后，Redis統(tǒng)一采用QuickList來(lái)實(shí)現(xiàn)List：

2.1 Set

Set是Redis中的單列集合，滿足下列特點(diǎn)：

• 不保證有序性
• 保證元素唯一
• 求交集、并集、差集
  

可以看出，Set對(duì)查詢?cè)氐男室蠓浅８?，思考一下，什么樣的?shù)據(jù)結(jié)構(gòu)可以滿足？
HashTable，也就是Redis中的Dict，不過(guò)Dict是雙列集合（可以存鍵、值對(duì)）

Set是Redis中的集合，不一定確保元素有序，可以滿足元素唯一、查詢效率要求極高。
為了查詢效率和唯一性，set采用HT編碼（Dict）。Dict中的key用來(lái)存儲(chǔ)元素，value統(tǒng)一為null。
當(dāng)存儲(chǔ)的所有數(shù)據(jù)都是整數(shù)，并且元素?cái)?shù)量不超過(guò)set-max-intset-entries時(shí)，Set會(huì)采用IntSet編碼，以節(jié)省內(nèi)存

結(jié)構(gòu)如下：

2.2 ZSET

ZSet也就是SortedSet，其中每一個(gè)元素都需要指定一個(gè)score值和member值：

• 可以根據(jù)score值排序后
• member必須唯一
• 可以根據(jù)member查詢分?jǐn)?shù)

因此，zset底層數(shù)據(jù)結(jié)構(gòu)必須滿足鍵值存儲(chǔ)、鍵必須唯一、可排序這幾個(gè)需求。之前學(xué)習(xí)的哪種編碼結(jié)構(gòu)可以滿足？

• SkipList：可以排序，并且可以同時(shí)存儲(chǔ)score和ele值（member）
• HT（Dict）：可以鍵值存儲(chǔ)，并且可以根據(jù)key找value

當(dāng)元素?cái)?shù)量不多時(shí)，HT和SkipList的優(yōu)勢(shì)不明顯，而且更耗內(nèi)存。因此zset還會(huì)采用ZipList結(jié)構(gòu)來(lái)節(jié)省內(nèi)存，不過(guò)需要同時(shí)滿足兩個(gè)條件：

• 元素?cái)?shù)量小于zset_max_ziplist_entries，默認(rèn)值128
• 每個(gè)元素都小于zset_max_ziplist_value字節(jié)，默認(rèn)值64

ziplist本身沒有排序功能，而且沒有鍵值對(duì)的概念，因此需要有zset通過(guò)編碼實(shí)現(xiàn)：

• ZipList是連續(xù)內(nèi)存，因此score和element是緊挨在一起的兩個(gè)entry， element在前，score在后
• score越小越接近隊(duì)首，score越大越接近隊(duì)尾，按照score值升序排列
  
  

2.3 Hash

Hash結(jié)構(gòu)與Redis中的Zset非常類似：

• 都是鍵值存儲(chǔ)
• 都需求根據(jù)鍵獲取值
• 鍵必須唯一

區(qū)別如下：

• zset的鍵是member，值是score；hash的鍵和值都是任意值
• zset要根據(jù)score排序；hash則無(wú)需排序

（1）底層實(shí)現(xiàn)方式：壓縮列表ziplist 或者 字典dict
當(dāng)Hash中數(shù)據(jù)項(xiàng)比較少的情況下，Hash底層才?壓縮列表ziplist進(jìn)?存儲(chǔ)數(shù)據(jù)，隨著數(shù)據(jù)的增加，底層的ziplist就可能會(huì)轉(zhuǎn)成dict，具體配置如下：

hash-max-ziplist-entries 512

hash-max-ziplist-value 64

當(dāng)滿足上面兩個(gè)條件其中之?的時(shí)候，Redis就使?dict字典來(lái)實(shí)現(xiàn)hash。
Redis的hash之所以這樣設(shè)計(jì)，是因?yàn)楫?dāng)ziplist變得很?的時(shí)候，它有如下幾個(gè)缺點(diǎn)：

• 每次插?或修改引發(fā)的realloc操作會(huì)有更?的概率造成內(nèi)存拷貝，從而降低性能。
• ?旦發(fā)生內(nèi)存拷貝，內(nèi)存拷貝的成本也相應(yīng)增加，因?yàn)橐截惛?的?塊數(shù)據(jù)。
• 當(dāng)ziplist數(shù)據(jù)項(xiàng)過(guò)多的時(shí)候，在它上?查找指定的數(shù)據(jù)項(xiàng)就會(huì)性能變得很低，因?yàn)閦iplist上的查找需要進(jìn)行遍歷。

總之，ziplist本來(lái)就設(shè)計(jì)為各個(gè)數(shù)據(jù)項(xiàng)挨在?起組成連續(xù)的內(nèi)存空間，這種結(jié)構(gòu)并不擅長(zhǎng)做修改操作。?旦數(shù)據(jù)發(fā)?改動(dòng)，就會(huì)引發(fā)內(nèi)存realloc，可能導(dǎo)致內(nèi)存拷貝。

hash結(jié)構(gòu)如下：

zset集合如下：

因此，Hash底層采用的編碼與Zset也基本一致，只需要把排序有關(guān)的SkipList去掉即可：

Hash結(jié)構(gòu)默認(rèn)采用ZipList編碼，用以節(jié)省內(nèi)存。 ZipList中相鄰的兩個(gè)entry 分別保存field和value

當(dāng)數(shù)據(jù)量較大時(shí)，Hash結(jié)構(gòu)會(huì)轉(zhuǎn)為HT編碼，也就是Dict，觸發(fā)條件有兩個(gè)：

• ZipList中的元素?cái)?shù)量超過(guò)了hash-max-ziplist-entries（默認(rèn)512）
• ZipList中的任意entry大小超過(guò)了hash-max-ziplist-value（默認(rèn)64字節(jié)）
  

2 Redis網(wǎng)絡(luò)模型

2.1 用戶空間和內(nèi)核態(tài)空間

服務(wù)器大多都采用Linux系統(tǒng)，這里我們以Linux為例來(lái)講解:

ubuntu和Centos 都是Linux的發(fā)行版，發(fā)行版可以看成對(duì)linux包了一層殼，任何Linux發(fā)行版，其系統(tǒng)內(nèi)核都是Linux。我們的應(yīng)用都需要通過(guò)Linux內(nèi)核與硬件交互

用戶的應(yīng)用，比如redis，mysql等其實(shí)是沒有辦法去執(zhí)行訪問(wèn)我們操作系統(tǒng)的硬件的，所以我們可以通過(guò)發(fā)行版的這個(gè)殼子去訪問(wèn)內(nèi)核，再通過(guò)內(nèi)核去訪問(wèn)計(jì)算機(jī)硬件

計(jì)算機(jī)硬件包括，如cpu，內(nèi)存，網(wǎng)卡等等，內(nèi)核（通過(guò)尋址空間）可以操作硬件的，但是內(nèi)核需要不同設(shè)備的驅(qū)動(dòng)，有了這些驅(qū)動(dòng)之后，內(nèi)核就可以去對(duì)計(jì)算機(jī)硬件去進(jìn)行 內(nèi)存管理，文件系統(tǒng)的管理，進(jìn)程的管理等等

我們想要用戶的應(yīng)用來(lái)訪問(wèn)，計(jì)算機(jī)就必須要通過(guò)對(duì)外暴露的一些接口，才能訪問(wèn)到，從而簡(jiǎn)介的實(shí)現(xiàn)對(duì)內(nèi)核的操控，但是內(nèi)核本身上來(lái)說(shuō)也是一個(gè)應(yīng)用，所以他本身也需要一些內(nèi)存，cpu等設(shè)備資源，用戶應(yīng)用本身也在消耗這些資源，如果不加任何限制，用戶去操作隨意的去操作我們的資源，就有可能導(dǎo)致一些沖突，甚至有可能導(dǎo)致我們的系統(tǒng)出現(xiàn)無(wú)法運(yùn)行的問(wèn)題，因此我們需要把用戶和內(nèi)核隔離開

• 進(jìn)程的尋址空間劃分成兩部分：內(nèi)核空間、用戶空間
• 用戶空間只能執(zhí)行受限的命令 (Ring3)，而且不能直接調(diào)用系統(tǒng)資源，必須通過(guò)內(nèi)核提供的接口來(lái)訪問(wèn)
• 內(nèi)核空間可以執(zhí)行特權(quán)命令 (Ring0)，調(diào)用一切系統(tǒng)資源

什么是尋址空間呢？我們的應(yīng)用程序也好，還是內(nèi)核空間也好，都是沒有辦法直接去物理內(nèi)存的，而是通過(guò)分配一些虛擬內(nèi)存映射到物理內(nèi)存中，我們的內(nèi)核和應(yīng)用程序去訪問(wèn)虛擬內(nèi)存的時(shí)候，就需要一個(gè)虛擬地址，這個(gè)地址是一個(gè)無(wú)符號(hào)的整數(shù)，比如一個(gè)32位的操作系統(tǒng)，他的帶寬就是32，他的虛擬地址就是2的32次方，也就是說(shuō)他尋址的范圍就是0~2的32次方， 這片尋址空間對(duì)應(yīng)的就是2的32個(gè)字節(jié)，就是4GB，這個(gè)4GB，會(huì)有3個(gè)GB分給用戶空間，會(huì)有1GB給內(nèi)核系統(tǒng)

在linux中，他們權(quán)限分成兩個(gè)等級(jí)，0和3，用戶空間只能執(zhí)行受限的命令（Ring3），而且不能直接調(diào)用系統(tǒng)資源，必須通過(guò)內(nèi)核提供的接口來(lái)訪問(wèn)內(nèi)核空間可以執(zhí)行特權(quán)命令（Ring0），調(diào)用一切系統(tǒng)資源，所以一般情況下，用戶的操作是運(yùn)行在用戶空間，而內(nèi)核運(yùn)行的數(shù)據(jù)是在內(nèi)核空間的，而有的情況下，一個(gè)應(yīng)用程序需要去調(diào)用一些特權(quán)資源，去調(diào)用一些內(nèi)核空間的操作，所以此時(shí)他倆需要在用戶態(tài)和內(nèi)核態(tài)之間進(jìn)行切換。

比如：

Linux系統(tǒng)為了提高IO效率，會(huì)在用戶空間和內(nèi)核空間都加入緩沖區(qū)：

• 寫數(shù)據(jù)時(shí)，要把用戶緩沖數(shù)據(jù)拷貝到內(nèi)核緩沖區(qū)，然后寫入設(shè)備

• 讀數(shù)據(jù)時(shí)，要從設(shè)備讀取數(shù)據(jù)到內(nèi)核緩沖區(qū)，然后拷貝到用戶緩沖區(qū)

針對(duì)這個(gè)操作：我們的用戶在寫讀數(shù)據(jù)時(shí)，會(huì)去向內(nèi)核態(tài)申請(qǐng)，想要讀取內(nèi)核的數(shù)據(jù)，而內(nèi)核數(shù)據(jù)要去等待驅(qū)動(dòng)程序從硬件上讀取數(shù)據(jù)，當(dāng)從磁盤上加載到數(shù)據(jù)之后，內(nèi)核會(huì)將數(shù)據(jù)寫入到內(nèi)核的緩沖區(qū)中，然后再將數(shù)據(jù)拷貝到用戶態(tài)的buffer中，然后再返回給應(yīng)用程序，整體而言，速度慢，就是這個(gè)原因，為了加速，我們希望read也好，還是wait for data也最好都不要等待，或者時(shí)間盡量的短。

2.2 阻塞IO

在《UNIX網(wǎng)絡(luò)編程》一書中，總結(jié)歸納了5種IO模型：

• 阻塞IO（Blocking IO）
• 非阻塞IO（Nonblocking IO）
• IO多路復(fù)用（IO Multiplexing）
• 信號(hào)驅(qū)動(dòng)IO（Signal Driven IO）
• 異步IO（Asynchronous IO）

應(yīng)用程序想要去讀取數(shù)據(jù)，他是無(wú)法直接去讀取磁盤數(shù)據(jù)的，他需要先到內(nèi)核里邊去等待內(nèi)核操作硬件拿到數(shù)據(jù)，這個(gè)過(guò)程就是1，是需要等待的，等到內(nèi)核從磁盤上把數(shù)據(jù)加載出來(lái)之后，再把這個(gè)數(shù)據(jù)寫給用戶的緩存區(qū)，這個(gè)過(guò)程是2，如果是阻塞IO，那么整個(gè)過(guò)程中，用戶從發(fā)起讀請(qǐng)求開始，一直到讀取到數(shù)據(jù)，都是一個(gè)阻塞狀態(tài)。

具體流程如下圖：

用戶去讀取數(shù)據(jù)時(shí)，會(huì)去先發(fā)起recvform一個(gè)命令，去嘗試從內(nèi)核上加載數(shù)據(jù)，如果內(nèi)核沒有數(shù)據(jù)，那么用戶就會(huì)等待，此時(shí)內(nèi)核會(huì)去從硬件上讀取數(shù)據(jù)，內(nèi)核讀取數(shù)據(jù)之后，會(huì)把數(shù)據(jù)拷貝到用戶態(tài)，并且返回ok，整個(gè)過(guò)程，都是阻塞等待的，這就是阻塞IO

總結(jié)如下：

顧名思義，阻塞IO就是兩個(gè)階段都必須阻塞等待：

階段一：

• 用戶進(jìn)程嘗試讀取數(shù)據(jù)（比如網(wǎng)卡數(shù)據(jù)）
• 此時(shí)數(shù)據(jù)尚未到達(dá)，內(nèi)核需要等待數(shù)據(jù)
• 此時(shí)用戶進(jìn)程也處于阻塞狀態(tài)

階段二：

• 數(shù)據(jù)到達(dá)并拷貝到內(nèi)核緩沖區(qū)，代表已就緒
• 將內(nèi)核數(shù)據(jù)拷貝到用戶緩沖區(qū)
• 拷貝過(guò)程中，用戶進(jìn)程依然阻塞等待
• 拷貝完成，用戶進(jìn)程解除阻塞，處理數(shù)據(jù)

可以看到，阻塞IO模型中，用戶進(jìn)程在兩個(gè)階段都是阻塞狀態(tài)。

2.3 非阻塞IO

顧名思義，非阻塞IO的recvfrom操作會(huì)立即返回結(jié)果而不是阻塞用戶進(jìn)程。

階段一：

• 用戶進(jìn)程嘗試讀取數(shù)據(jù)（比如網(wǎng)卡數(shù)據(jù)）
• 此時(shí)數(shù)據(jù)尚未到達(dá)，內(nèi)核需要等待數(shù)據(jù)
• 返回異常給用戶進(jìn)程
• 用戶進(jìn)程拿到error后，再次嘗試讀取
• 循環(huán)往復(fù)，直到數(shù)據(jù)就緒

階段二：

• 將內(nèi)核數(shù)據(jù)拷貝到用戶緩沖區(qū)
• 拷貝過(guò)程中，用戶進(jìn)程依然阻塞等待
• 拷貝完成，用戶進(jìn)程解除阻塞，處理數(shù)據(jù)
• 可以看到，非阻塞IO模型中，用戶進(jìn)程在第一個(gè)階段是非阻塞，第二個(gè)階段是阻塞狀態(tài)。雖然是非阻塞，但性能并沒有得到提高。而且忙等機(jī)制會(huì)導(dǎo)致CPU空轉(zhuǎn)，CPU使用率暴增。
  

2.4 IO多路復(fù)用

無(wú)論是阻塞IO還是非阻塞IO，用戶應(yīng)用在一階段都需要調(diào)用recvfrom來(lái)獲取數(shù)據(jù)，差別在于無(wú)數(shù)據(jù)時(shí)的處理方案：

• 如果調(diào)用recvfrom時(shí)，恰好沒有數(shù)據(jù)，阻塞IO會(huì)使CPU阻塞，非阻塞IO使CPU空轉(zhuǎn)，都不能充分發(fā)揮CPU的作用。
• 如果調(diào)用recvfrom時(shí)，恰好有數(shù)據(jù)，則用戶進(jìn)程可以直接進(jìn)入第二階段，讀取并處理數(shù)據(jù)

所以怎么看起來(lái)以上兩種方式性能都不好

比如服務(wù)端處理客戶端Socket請(qǐng)求時(shí)，在單線程情況下，只能依次處理每一個(gè)socket，如果正在處理的socket恰好未就緒(數(shù)據(jù)不可讀或不可寫)，線程就會(huì)被阻塞，所有其它客戶端socket都必須等待，性能自然會(huì)很差。

就比如服務(wù)員給顧客點(diǎn)餐，分兩步：

• 顧客思考要吃什么（等待數(shù)據(jù)就緒）
• 顧客想好了，開始點(diǎn)餐（讀取數(shù)據(jù)）

要提高效率有幾種辦法？

• 方案一：增加更多服務(wù)員（多線程）
• 方案二：不排隊(duì)，誰(shuí)想好了吃什么（數(shù)據(jù)就緒了），服務(wù)員就給誰(shuí)點(diǎn)餐（用戶應(yīng)用就去讀取數(shù)據(jù)）

那么問(wèn)題來(lái)了：用戶進(jìn)程如何知道內(nèi)核中數(shù)據(jù)是否就緒呢？

所以接下來(lái)就需要詳細(xì)的來(lái)解決多路復(fù)用模型是如何知道到底怎么知道內(nèi)核數(shù)據(jù)是否就緒的問(wèn)題了

這個(gè)問(wèn)題的解決依賴于提出的

文件描述符（File Descriptor）：簡(jiǎn)稱FD，是一個(gè)從0 開始的無(wú)符號(hào)整數(shù)，用來(lái)關(guān)聯(lián)Linux中的一個(gè)文件。在Linux中，一切皆文件，例如常規(guī)文件、視頻、硬件設(shè)備等，當(dāng)然也包括網(wǎng)絡(luò)套接字（Socket）。

IO多路復(fù)用：是利用單個(gè)線程來(lái)同時(shí)監(jiān)聽多個(gè)FD，并在某個(gè)FD可讀、可寫時(shí)得到通知，從而避免無(wú)效的等待，充分利用CPU資源。

階段一：

• 用戶進(jìn)程調(diào)用select，指定要監(jiān)聽的FD集合
• 核監(jiān)聽FD對(duì)應(yīng)的多個(gè)socket
• 任意一個(gè)或多個(gè)socket數(shù)據(jù)就緒則返回readable
• 此過(guò)程中用戶進(jìn)程阻塞

階段二：

• 用戶進(jìn)程找到就緒的socket
• 依次調(diào)用recvfrom讀取數(shù)據(jù)
• 內(nèi)核將數(shù)據(jù)拷貝到用戶空間
• 用戶進(jìn)程處理數(shù)據(jù)

當(dāng)用戶去讀取數(shù)據(jù)的時(shí)候，不再去直接調(diào)用recvfrom了，而是調(diào)用select的函數(shù)，select函數(shù)會(huì)將需要監(jiān)聽的數(shù)據(jù)交給內(nèi)核，由內(nèi)核去檢查這些數(shù)據(jù)是否就緒了，如果說(shuō)這個(gè)數(shù)據(jù)就緒了，就會(huì)通知應(yīng)用程序數(shù)據(jù)就緒，然后來(lái)讀取數(shù)據(jù)，再?gòu)膬?nèi)核中把數(shù)據(jù)拷貝給用戶態(tài)，完成數(shù)據(jù)處理，如果N多個(gè)FD一個(gè)都沒處理完，此時(shí)就進(jìn)行等待。

用IO復(fù)用模式，可以確保去讀數(shù)據(jù)的時(shí)候，數(shù)據(jù)是一定存在的，他的效率比原來(lái)的阻塞IO和非阻塞IO性能都要高

IO多路復(fù)用：是利用單個(gè)線程來(lái)同時(shí)監(jiān)聽多個(gè)FD，并在某個(gè)FD可讀、可寫時(shí)得到通知，從而避免無(wú)效的等待，充分利用CPU資源。不過(guò)監(jiān)聽FD的方式、通知的方式又有多種實(shí)現(xiàn)，常見的有：

• select
• poll
• epoll
  

其中select和pool相當(dāng)于是當(dāng)被監(jiān)聽的數(shù)據(jù)準(zhǔn)備好之后，他會(huì)把你監(jiān)聽的FD整個(gè)數(shù)據(jù)都發(fā)給你，你需要到整個(gè)FD中去找，哪些是處理好了的，需要通過(guò)遍歷的方式，所以性能也并不是那么好

而epoll，則相當(dāng)于內(nèi)核準(zhǔn)備好了之后，他會(huì)把準(zhǔn)備好的數(shù)據(jù)，直接發(fā)給你，咱們就省去了遍歷的動(dòng)作。

2.4.1 select方式

select是Linux最早是由的I/O多路復(fù)用技術(shù)：

簡(jiǎn)單說(shuō)，就是我們把需要處理的數(shù)據(jù)封裝成FD，然后在用戶態(tài)時(shí)創(chuàng)建一個(gè)fd的集合（這個(gè)集合的大小是要監(jiān)聽的那個(gè)FD的最大值+1，但是大小整體是有限制的 ），這個(gè)集合的長(zhǎng)度大小是有限制的，同時(shí)在這個(gè)集合中，標(biāo)明出來(lái)我們要控制哪些數(shù)據(jù)，

比如要監(jiān)聽的數(shù)據(jù)，是1,2,5三個(gè)數(shù)據(jù)，此時(shí)會(huì)執(zhí)行select函數(shù)，然后將整個(gè)fd發(fā)給內(nèi)核態(tài)，內(nèi)核態(tài)會(huì)去遍歷用戶態(tài)傳遞過(guò)來(lái)的數(shù)據(jù)，如果發(fā)現(xiàn)這里邊都數(shù)據(jù)都沒有就緒，就休眠，直到有數(shù)據(jù)準(zhǔn)備好時(shí)，就會(huì)被喚醒，喚醒之后，再次遍歷一遍，看看誰(shuí)準(zhǔn)備好了，然后再將處理掉沒有準(zhǔn)備好的數(shù)據(jù)，最后再將這個(gè)FD集合寫回到用戶態(tài)中去，此時(shí)用戶態(tài)就知道了，奧，有人準(zhǔn)備好了，但是對(duì)于用戶態(tài)而言，并不知道誰(shuí)處理好了，所以用戶態(tài)也需要去進(jìn)行遍歷，然后找到對(duì)應(yīng)準(zhǔn)備好數(shù)據(jù)的節(jié)點(diǎn)，再去發(fā)起讀請(qǐng)求，我們會(huì)發(fā)現(xiàn)，這種模式下他雖然比阻塞IO和非阻塞IO好，但是依然有些麻煩的事情， 比如說(shuō)頻繁的傳遞fd集合，頻繁的去遍歷FD等問(wèn)題

2.4.2 poll模式

poll模式對(duì)select模式做了簡(jiǎn)單改進(jìn)，但性能提升不明顯，部分關(guān)鍵代碼如下：

IO流程：

• 創(chuàng)建pollfd數(shù)組，向其中添加關(guān)注的fd信息，數(shù)組大小自定義
• 調(diào)用poll函數(shù)，將pollfd數(shù)組拷貝到內(nèi)核空間，轉(zhuǎn)鏈表存儲(chǔ)，無(wú)上限
• 內(nèi)核遍歷fd，判斷是否就緒
• 數(shù)據(jù)就緒或超時(shí)后，拷貝pollfd數(shù)組到用戶空間，返回就緒fd數(shù)量n
• 用戶進(jìn)程判斷n是否大于0,大于0則遍歷pollfd數(shù)組，找到就緒的fd

與select對(duì)比：

• select模式中的fd_set大小固定為1024，而pollfd在內(nèi)核中采用鏈表，理論上無(wú)上限
• 監(jiān)聽FD越多，每次遍歷消耗時(shí)間也越久，性能反而會(huì)下降

2.4.3 epoll函數(shù)

epoll模式是對(duì)select和poll的改進(jìn)，它提供了三個(gè)函數(shù)：

第一個(gè)是：eventpoll的函數(shù)，他內(nèi)部包含兩個(gè)東西

一個(gè)是：

1、紅黑樹 -> 記錄的事要監(jiān)聽的FD

另一個(gè)是：

2、鏈表 -> 一個(gè)鏈表，記錄的是就緒的FD

緊接著調(diào)用epoll_ctl操作，將要監(jiān)聽的數(shù)據(jù)添加到紅黑樹上去，并且給每個(gè)fd設(shè)置一個(gè)監(jiān)聽函數(shù)，這個(gè)函數(shù)會(huì)在fd數(shù)據(jù)就緒時(shí)觸發(fā)，就是準(zhǔn)備好了，現(xiàn)在就把fd把數(shù)據(jù)添加到list_head中去

3、調(diào)用epoll_wait函數(shù)

就去等待，在用戶態(tài)創(chuàng)建一個(gè)空的events數(shù)組，當(dāng)就緒之后，我們的回調(diào)函數(shù)會(huì)把數(shù)據(jù)添加到list_head中去，當(dāng)調(diào)用這個(gè)函數(shù)的時(shí)候，會(huì)去檢查list_head，當(dāng)然這個(gè)過(guò)程需要參考配置的等待時(shí)間，可以等一定時(shí)間，也可以一直等， 如果在此過(guò)程中，檢查到了list_head中有數(shù)據(jù)會(huì)將數(shù)據(jù)添加到鏈表中，此時(shí)將數(shù)據(jù)放入到events數(shù)組中，并且返回對(duì)應(yīng)的操作的數(shù)量，用戶態(tài)的此時(shí)收到響應(yīng)后，從events中拿到對(duì)應(yīng)準(zhǔn)備好的數(shù)據(jù)的節(jié)點(diǎn)，再去調(diào)用方法去拿數(shù)據(jù)。

小總結(jié)：

select模式存在的三個(gè)問(wèn)題：

• 能監(jiān)聽的FD最大不超過(guò)1024
• 每次select都需要把所有要監(jiān)聽的FD都拷貝到內(nèi)核空間
• 每次都要遍歷所有FD來(lái)判斷就緒狀態(tài)

poll模式的問(wèn)題：

• poll利用鏈表解決了select中監(jiān)聽FD上限的問(wèn)題，但依然要遍歷所有FD，如果監(jiān)聽較多，性能會(huì)下降

epoll模式中如何解決這些問(wèn)題的？

• 基于epoll實(shí)例中的紅黑樹保存要監(jiān)聽的FD，理論上無(wú)上限，而且增刪改查效率都非常高
• 每個(gè)FD只需要執(zhí)行一次epoll_ctl添加到紅黑樹，以后每次epol_wait無(wú)需傳遞任何參數(shù)，無(wú)需重復(fù)拷貝FD到內(nèi)核空間
• 利用ep_poll_callback機(jī)制來(lái)監(jiān)聽FD狀態(tài)，無(wú)需遍歷所有FD，因此性能不會(huì)隨監(jiān)聽的FD數(shù)量增多而下降

2.4.4 事件通知機(jī)制

當(dāng)FD有數(shù)據(jù)可讀時(shí)，我們調(diào)用epoll_wait（或者select、poll）可以得到通知。但是事件通知的模式有兩種：

• LevelTriggered：簡(jiǎn)稱LT，也叫做水平觸發(fā)。只要某個(gè)FD中有數(shù)據(jù)可讀，每次調(diào)用epoll_wait都會(huì)得到通知。
• EdgeTriggered：簡(jiǎn)稱ET，也叫做邊沿觸發(fā)。只有在某個(gè)FD有狀態(tài)變化時(shí)，調(diào)用epoll_wait才會(huì)被通知。

舉個(gè)栗子：

• 假設(shè)一個(gè)客戶端socket對(duì)應(yīng)的FD已經(jīng)注冊(cè)到了epoll實(shí)例中
• 客戶端socket發(fā)送了2kb的數(shù)據(jù)
• 服務(wù)端調(diào)用epoll_wait，得到通知說(shuō)FD就緒
• 服務(wù)端從FD讀取了1kb數(shù)據(jù)回到步驟3（再次調(diào)用epoll_wait，形成循環(huán)）

結(jié)論：

如果我們采用LT模式，因?yàn)镕D中仍有1kb數(shù)據(jù)，則第⑤步依然會(huì)返回結(jié)果，并且得到通知

如果我們采用ET模式，因?yàn)榈冖鄄揭呀?jīng)消費(fèi)了FD可讀事件，第⑤步FD狀態(tài)沒有變化，因此epoll_wait不會(huì)返回，數(shù)據(jù)無(wú)法讀取，客戶端響應(yīng)超時(shí)。

2.4.5 基于epoll的服務(wù)器端流程

我們來(lái)梳理一下這張圖

服務(wù)器啟動(dòng)以后，服務(wù)端會(huì)去調(diào)用epoll_create，創(chuàng)建一個(gè)epoll實(shí)例，epoll實(shí)例中包含兩個(gè)數(shù)據(jù)

1、紅黑樹（為空）：rb_root 用來(lái)去記錄需要被監(jiān)聽的FD

2、鏈表（為空）：list_head，用來(lái)存放已經(jīng)就緒的FD

創(chuàng)建好了之后，會(huì)去調(diào)用epoll_ctl函數(shù)，此函數(shù)會(huì)會(huì)將需要監(jiān)聽的數(shù)據(jù)添加到rb_root中去，并且對(duì)當(dāng)前這些存在于紅黑樹的節(jié)點(diǎn)設(shè)置回調(diào)函數(shù)，當(dāng)這些被監(jiān)聽的數(shù)據(jù)一旦準(zhǔn)備完成，就會(huì)被調(diào)用，而調(diào)用的結(jié)果就是將紅黑樹的fd添加到list_head中去(但是此時(shí)并沒有完成)

3、當(dāng)?shù)诙酵瓿珊?，就?huì)調(diào)用epoll_wait函數(shù)，這個(gè)函數(shù)會(huì)去校驗(yàn)是否有數(shù)據(jù)準(zhǔn)備完畢（因?yàn)閿?shù)據(jù)一旦準(zhǔn)備就緒，就會(huì)被回調(diào)函數(shù)添加到list_head中），在等待了一段時(shí)間后(可以進(jìn)行配置)，如果等夠了超時(shí)時(shí)間，則返回沒有數(shù)據(jù)，如果有，則進(jìn)一步判斷當(dāng)前是什么事件，如果是建立連接時(shí)間，則調(diào)用accept() 接受客戶端socket，拿到建立連接的socket，然后建立起來(lái)連接，如果是其他事件，則把數(shù)據(jù)進(jìn)行寫出

2.5 信號(hào)驅(qū)動(dòng)

信號(hào)驅(qū)動(dòng)IO是與內(nèi)核建立SIGIO的信號(hào)關(guān)聯(lián)并設(shè)置回調(diào)，當(dāng)內(nèi)核有FD就緒時(shí)，會(huì)發(fā)出SIGIO信號(hào)通知用戶，期間用戶應(yīng)用可以執(zhí)行其它業(yè)務(wù)，無(wú)需阻塞等待。

階段一：

• 用戶進(jìn)程調(diào)用sigaction，注冊(cè)信號(hào)處理函數(shù)
• 內(nèi)核返回成功，開始監(jiān)聽FD
• 用戶進(jìn)程不阻塞等待，可以執(zhí)行其它業(yè)務(wù)
• 當(dāng)內(nèi)核數(shù)據(jù)就緒后，回調(diào)用戶進(jìn)程的SIGIO處理函數(shù)

階段二：

• 收到SIGIO回調(diào)信號(hào)
• 調(diào)用recvfrom，讀取
• 內(nèi)核將數(shù)據(jù)拷貝到用戶空間
• 用戶進(jìn)程處理數(shù)據(jù)
  

缺點(diǎn)：

• 當(dāng)有大量IO操作時(shí)，信號(hào)較多，SIGIO處理函數(shù)不能及時(shí)處理可能導(dǎo)致信號(hào)隊(duì)列溢出
• 而且內(nèi)核空間與用戶空間的頻繁信號(hào)交互性能也較低。

2.6 異步IO

異步IO的整個(gè)過(guò)程都是非阻塞的，用戶進(jìn)程調(diào)用完異步API后就可以去做其它事情，內(nèi)核等待數(shù)據(jù)就緒并拷貝到用戶空間后才會(huì)遞交信號(hào)，通知用戶進(jìn)程。

這種方式，不僅僅是用戶態(tài)在試圖讀取數(shù)據(jù)后，不阻塞，而且當(dāng)內(nèi)核的數(shù)據(jù)準(zhǔn)備完成后，也不會(huì)阻塞
他會(huì)由內(nèi)核將所有數(shù)據(jù)處理完成后，由內(nèi)核將數(shù)據(jù)寫入到用戶態(tài)中，然后才算完成，所以性能極高，不會(huì)有任何阻塞，全部都由內(nèi)核完成，可以看到，異步IO模型中，用戶進(jìn)程在兩個(gè)階段都是非阻塞狀態(tài)。

同步和異步對(duì)比

最后用一幅圖，來(lái)說(shuō)明他們之間的區(qū)別：

IO操作是同步還是異步，關(guān)鍵看數(shù)據(jù)在內(nèi)核空間與用戶空間的拷貝過(guò)程(數(shù)據(jù)讀寫的IO操作)
也就是階段二是同步還是異步:

2.7 Redis網(wǎng)絡(luò)模型

2.7.1 Redis是單線程的嗎？為什么使用單線程

Redis到底是單線程還是多線程？

• 如果僅僅聊Redis的核心業(yè)務(wù)部分（命令處理），答案是單線程
• 如果是聊整個(gè)Redis，那么答案就是多線程

在Redis版本迭代過(guò)程中，在兩個(gè)重要的時(shí)間節(jié)點(diǎn)上引入了多線程的支持：

• Redis v4.0：引入多線程異步處理一些耗時(shí)較舊的任務(wù)，例如異步刪除命令unlink
• Redis v6.0：在核心網(wǎng)絡(luò)模型中引入 多線程，進(jìn)一步提高對(duì)于多核CPU的利用率

因此，對(duì)于Redis的核心網(wǎng)絡(luò)模型，在Redis 6.0之前確實(shí)都是單線程。是利用epoll（Linux系統(tǒng)）這樣的IO多路復(fù)用技術(shù)在事件循環(huán)中不斷處理客戶端情況。

為什么Redis要選擇單線程？

• 拋開持久化不談，Redis是純 內(nèi)存操作，執(zhí)行速度非?？欤男阅芷款i是網(wǎng)絡(luò)延遲而不是執(zhí)行速度，因此多線程并不會(huì)帶來(lái)巨大的性能提升。
• 多線程會(huì)導(dǎo)致過(guò)多的上下文切換，帶來(lái)不必要的開銷
• 引入多線程會(huì)面臨線程安全問(wèn)題，必然要引入線程鎖這樣的安全手段，實(shí)現(xiàn)復(fù)雜度增高，而且性能也會(huì)大打折扣

2.7.2 Redis的單線程模型-Redis單線程和多線程網(wǎng)絡(luò)模型變更

Redis通過(guò)IO多路復(fù)用來(lái)提高網(wǎng)絡(luò)性能，并且支持各種不同的多路復(fù)用實(shí)現(xiàn)，并且將這些實(shí)現(xiàn)進(jìn)行封裝，提供了統(tǒng)一的高性能事件庫(kù)API庫(kù)AE:

當(dāng)我們的客戶端想要去連接我們服務(wù)器，會(huì)去先到IO多路復(fù)用模型去進(jìn)行排隊(duì)，會(huì)有一個(gè)連接應(yīng)答處理器，他會(huì)去接受讀請(qǐng)求，然后又把讀請(qǐng)求注冊(cè)到具體模型中去，此時(shí)這些建立起來(lái)的連接，如果是客戶端請(qǐng)求處理器去進(jìn)行執(zhí)行命令時(shí)，他會(huì)去把數(shù)據(jù)讀取出來(lái)，然后把數(shù)據(jù)放入到client中， clinet去解析當(dāng)前的命令轉(zhuǎn)化為redis認(rèn)識(shí)的命令，接下來(lái)就開始處理這些命令，從redis中的command中找到這些命令，然后就真正的去操作對(duì)應(yīng)的數(shù)據(jù)了，當(dāng)數(shù)據(jù)操作完成后，會(huì)去找到命令回復(fù)處理器，再由他將數(shù)據(jù)寫出。

3 Redis通信協(xié)議-RESP協(xié)議

Redis是一個(gè)CS架構(gòu)的軟件，通信一般分兩步（不包括pipeline和PubSub）：

• 客戶端（client）向服務(wù)端（server）發(fā)送一條命令

• 服務(wù)端解析并執(zhí)行命令，返回響應(yīng)結(jié)果給客戶端

因此客戶端發(fā)送命令的格式、服務(wù)端響應(yīng)結(jié)果的格式必須有一個(gè)規(guī)范，這個(gè)規(guī)范就是通信協(xié)議。

而在Redis中采用的是RESP（Redis Serialization Protocol）協(xié)議：

Redis 1.2版本引入了RESP協(xié)議

Redis 2.0版本中成為與Redis服務(wù)端通信的標(biāo)準(zhǔn)，稱為RESP2

Redis 6.0版本中，從RESP2升級(jí)到了RESP3協(xié)議，增加了更多數(shù)據(jù)類型并且支持6.0的新特性–客戶端緩存

但目前，默認(rèn)使用的依然是RESP2協(xié)議，也是我們要學(xué)習(xí)的協(xié)議版本（以下簡(jiǎn)稱RESP）。

在RESP中，通過(guò)首字節(jié)的字符來(lái)區(qū)分不同數(shù)據(jù)類型，常用的數(shù)據(jù)類型包括5種：

• 單行字符串：首字節(jié)是 ‘+’ ，后面跟上單行字符串，以CRLF（ “\r\n” ）結(jié)尾。例如返回"OK"： “+OK\r\n”

• 錯(cuò)誤（Errors）：首字節(jié)是 ‘-’ ，與單行字符串格式一樣，只是字符串是異常信息，例如：“-Error message\r\n”

• 數(shù)值：首字節(jié)是 ‘:’ ，后面跟上數(shù)字格式的字符串，以CRLF結(jié)尾。例如：“:10\r\n”

• 多行字符串：首字節(jié)是 ‘$’ ，表示二進(jìn)制安全的字符串，最大支持512MB：

  如果大小為0，則代表空字符串：“$0\r\n\r\n”

  如果大小為-1，則代表不存在：“$-1\r\n”

• 數(shù)組：首字節(jié)是 ‘*’，后面跟上數(shù)組元素個(gè)數(shù)，再跟上元素，元素?cái)?shù)據(jù)類型不限:
  

3.1 基于Socket自定義Redis的客戶端

Redis支持TCP通信，因此我們可以使用Socket來(lái)模擬客戶端，與Redis服務(wù)端建立連接：

public class Main {

    static Socket s;
    static PrintWriter writer;
    static BufferedReader reader;

    public static void main(String[] args) {
        try {
            // 1.建立連接
            String host = "192.168.150.101";
            int port = 6379;
            s = new Socket(host, port);
            // 2.獲取輸出流、輸入流
            writer = new PrintWriter(new OutputStreamWriter(s.getOutputStream(), StandardCharsets.UTF_8));
            reader = new BufferedReader(new InputStreamReader(s.getInputStream(), StandardCharsets.UTF_8));

            // 3.發(fā)出請(qǐng)求
            // 3.1.獲取授權(quán) auth 123321
            sendRequest("auth", "123321");
            Object obj = handleResponse();
            System.out.println("obj = " + obj);

            // 3.2.set name 虎哥
            sendRequest("set", "name", "虎哥");
            // 4.解析響應(yīng)
            obj = handleResponse();
            System.out.println("obj = " + obj);

            // 3.2.set name 虎哥
            sendRequest("get", "name");
            // 4.解析響應(yīng)
            obj = handleResponse();
            System.out.println("obj = " + obj);

            // 3.2.set name 虎哥
            sendRequest("mget", "name", "num", "msg");
            // 4.解析響應(yīng)
            obj = handleResponse();
            System.out.println("obj = " + obj);
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            // 5.釋放連接
            try {
                if (reader != null) reader.close();
                if (writer != null) writer.close();
                if (s != null) s.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    private static Object handleResponse() throws IOException {
        // 讀取首字節(jié)
        int prefix = reader.read();
        // 判斷數(shù)據(jù)類型標(biāo)示
        switch (prefix) {
            case '+': // 單行字符串，直接讀一行
                return reader.readLine();
            case '-': // 異常，也讀一行
                throw new RuntimeException(reader.readLine());
            case ':': // 數(shù)字
                return Long.parseLong(reader.readLine());
            case '$': // 多行字符串
                // 先讀長(zhǎng)度
                int len = Integer.parseInt(reader.readLine());
                if (len == -1) {
                    return null;
                }
                if (len == 0) {
                    return "";
                }
                // 再讀數(shù)據(jù),讀len個(gè)字節(jié)。我們假設(shè)沒有特殊字符，所以讀一行（簡(jiǎn)化）
                return reader.readLine();
            case '*':
                return readBulkString();
            default:
                throw new RuntimeException("錯(cuò)誤的數(shù)據(jù)格式！");
        }
    }

    private static Object readBulkString() throws IOException {
        // 獲取數(shù)組大小
        int len = Integer.parseInt(reader.readLine());
        if (len <= 0) {
            return null;
        }
        // 定義集合，接收多個(gè)元素
        List<Object> list = new ArrayList<>(len);
        // 遍歷，依次讀取每個(gè)元素
        for (int i = 0; i < len; i++) {
            list.add(handleResponse());
        }
        return list;
    }

    // set name 虎哥
    private static void sendRequest(String ... args) {
        writer.println("*" + args.length);
        for (String arg : args) {
            writer.println("$" + arg.getBytes(StandardCharsets.UTF_8).length);
            writer.println(arg);
        }
        writer.flush();
    }
}

3.2 Redis內(nèi)存回收

Redis之所以性能強(qiáng)，最主要的原因就是基于內(nèi)存存儲(chǔ)。然而單節(jié)點(diǎn)的Redis其內(nèi)存大小不宜過(guò)大，會(huì)影響持久化或主從同步性能。

我們可以通過(guò)修改配置文件來(lái)設(shè)置Redis的最大內(nèi)存：

當(dāng)內(nèi)存使用達(dá)到上限時(shí)，就無(wú)法存儲(chǔ)更多數(shù)據(jù)了。為了解決這個(gè)問(wèn)題，Redis提供了一些策略實(shí)現(xiàn)內(nèi)存回收：

3.2.1 內(nèi)存過(guò)期策略

在學(xué)習(xí)Redis緩存的時(shí)候我們說(shuō)過(guò)，可以通過(guò)expire命令給Redis的key設(shè)置TTL（存活時(shí)間）：

可以發(fā)現(xiàn)，當(dāng)key的TTL到期以后，再次訪問(wèn)name返回的是nil，說(shuō)明這個(gè)key已經(jīng)不存在了，對(duì)應(yīng)的內(nèi)存也得到釋放。從而起到內(nèi)存回收的目的。

Redis本身是一個(gè)典型的key-value內(nèi)存存儲(chǔ)數(shù)據(jù)庫(kù)，因此所有的key、value都保存在之前學(xué)習(xí)過(guò)的Dict結(jié)構(gòu)中。不過(guò)在其database結(jié)構(gòu)體中，有兩個(gè)Dict：一個(gè)用來(lái)記錄key-value；另一個(gè)用來(lái)記錄key-TTL。

這里有兩個(gè)問(wèn)題需要我們思考：

1. Redis是如何知道一個(gè)key是否過(guò)期呢？

   • 利用兩個(gè)Dict分別記錄key-value對(duì)及key-ttl對(duì)

2. 是不是TTL到期就立即刪除了呢？

惰性刪除

惰性刪除：顧明思議并不是在TTL到期后就立刻刪除，而是在訪問(wèn)一個(gè)key的時(shí)候，檢查該key的存活時(shí)間，如果已經(jīng)過(guò)期才執(zhí)行刪除。

周期刪除

周期刪除：顧明思議是通過(guò)一個(gè)定時(shí)任務(wù)，周期性的抽樣部分過(guò)期的key，然后執(zhí)行刪除。執(zhí)行周期有兩種：

• Redis服務(wù)初始化函數(shù)initServer()中設(shè)置定時(shí)任務(wù)，按照server.hz的頻率來(lái)執(zhí)行過(guò)期key清理，模式為SLOW
• Redis的每個(gè)事件循環(huán)前會(huì)調(diào)用beforeSleep()函數(shù)，執(zhí)行過(guò)期key清理，模式為FAST

SLOW模式規(guī)則：

• 執(zhí)行頻率受server.hz影響，默認(rèn)為10，即每秒執(zhí)行10次，每個(gè)執(zhí)行周期100ms。
• 執(zhí)行清理耗時(shí)不超過(guò)一次執(zhí)行周期的25%.默認(rèn)slow模式耗時(shí)不超過(guò)25ms
• 逐個(gè)遍歷db，逐個(gè)遍歷db中的bucket，抽取20個(gè)key判斷是否過(guò)期
• 如果沒達(dá)到時(shí)間上限（25ms）并且過(guò)期key比例大于10%，再進(jìn)行一次抽樣，否則結(jié)束
• FAST模式規(guī)則（過(guò)期key比例小于10%不執(zhí)行 ）：
• 執(zhí)行頻率受beforeSleep()調(diào)用頻率影響，但兩次FAST模式間隔不低于2ms
• 執(zhí)行清理耗時(shí)不超過(guò)1ms
• 逐個(gè)遍歷db，逐個(gè)遍歷db中的bucket，抽取20個(gè)key判斷是否過(guò)期
  如果沒達(dá)到時(shí)間上限（1ms）并且過(guò)期key比例大于10%，再進(jìn)行一次抽樣，否則結(jié)束

小總結(jié)：

RedisKey的TTL記錄方式：

• 在RedisDB中通過(guò)一個(gè)Dict記錄每個(gè)Key的TTL時(shí)間

過(guò)期key的刪除策略：

• 惰性清理：每次查找key時(shí)判斷是否過(guò)期，如果過(guò)期則刪除

• 定期清理：定期抽樣部分key，判斷是否過(guò)期，如果過(guò)期則刪除。

定期清理的兩種模式：

• SLOW模式執(zhí)行頻率默認(rèn)為10，每次不超過(guò)25ms

• FAST模式執(zhí)行頻率不固定，但兩次間隔不低于2ms，每次耗時(shí)不超過(guò)1ms

3.2.2 內(nèi)存淘汰策略

內(nèi)存淘汰：就是當(dāng)Redis內(nèi)存使用達(dá)到設(shè)置的上限時(shí)，主動(dòng)挑選部分key刪除以釋放更多內(nèi)存的流程。Redis會(huì)在處理客戶端命令的方法processCommand()中嘗試做內(nèi)存淘汰：

淘汰策略

Redis支持8種不同策略來(lái)選擇要?jiǎng)h除的key：

• noeviction： 不淘汰任何key，但是內(nèi)存滿時(shí)不允許寫入新數(shù)據(jù)，默認(rèn)就是這種策略。

• volatile-ttl： 對(duì)設(shè)置了TTL的key，比較key的剩余TTL值，TTL越小越先被淘汰

• allkeys-random：對(duì)全體key ，隨機(jī)進(jìn)行淘汰。也就是直接從db->dict中隨機(jī)挑選

• volatile-random：對(duì)設(shè)置了TTL的key ，隨機(jī)進(jìn)行淘汰。也就是從db->expires中隨機(jī)挑選。

• allkeys-lru： 對(duì)全體key，基于LRU算法進(jìn)行淘汰

• volatile-lru： 對(duì)設(shè)置了TTL的key，基于LRU算法進(jìn)行淘汰

• allkeys-lfu： 對(duì)全體key，基于LFU算法進(jìn)行淘汰

• volatile-lfu： 對(duì)設(shè)置了TTL的key，基于LFI算法進(jìn)行淘汰

  比較容易混淆的有兩個(gè)：

  • LRU（Least Recently Used），最少最近使用。用當(dāng)前時(shí)間減去最后一次訪問(wèn)時(shí)間，這個(gè)值越大則淘汰優(yōu)先級(jí)越高。
  • LFU（Least Frequently Used），最少頻率使用。會(huì)統(tǒng)計(jì)每個(gè)key的訪問(wèn)頻率，值越小淘汰優(yōu)先級(jí)越高。

Redis的數(shù)據(jù)都會(huì)被封裝為RedisObject結(jié)構(gòu)：

LFU的訪問(wèn)次數(shù)之所以叫做邏輯訪問(wèn)次數(shù)，是因?yàn)椴⒉皇敲看蝛ey被訪問(wèn)都計(jì)數(shù)，而是通過(guò)運(yùn)算：

• 生成0~1之間的隨機(jī)數(shù)R
• 計(jì)算 (舊次數(shù) * lfu_log_factor + 1)，記錄為P
• 如果 R < P ，則計(jì)數(shù)器 + 1，且最大不超過(guò)255
• 訪問(wèn)次數(shù)會(huì)隨時(shí)間衰減，距離上一次訪問(wèn)時(shí)間每隔 lfu_decay_time 分鐘，計(jì)數(shù)器 -1

最后用一副圖來(lái)描述當(dāng)前的這個(gè)流程吧
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-770981.html

到了這里，關(guān)于中間件系列 - Redis入門到實(shí)戰(zhàn)(原理篇)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！