Redis從入門到實戰

一、數據結構

1. 動態字符串SDS

我們都知道Redis中保存的key是字符串，value往往是字符串或者字符串的集合。可見字符串是Redis中最常用的一種數據結構。

不過Redis沒有直接使用C語言中的字符串，因為C語言字符串存在很多問題：

獲取字符串長度需要通過運算
非二進制安全
不可修改

// C語言，聲明字符串
char* s = "hello"
// 本質是字符數組：{'h', 'e', 'l', 'l', 'o', '\0'}

Redis構建了一種新的字符串結構，稱為簡單動態字符串（Simple Dynamin String），簡稱SDS。

例如，我們執行命令：

那么Redis將在底層創建兩個SDS，其中一個是包含“name”的SDS，另一個是包含“虎哥”的SDS。

Redis是C語言實現的，其中SDS是一個結構體，源碼如下：

例如，一個包含字符串“name”的sds結構如下：

SDS之所以叫作動態字符串，是因為它具備動態擴容的能力，例如一個內容為“hi”的SDS：

假如我們要給SDS追加一段字符串，",Amy"，這里首先會申請新內存空間：

如果新字符串小于1M，則新空間為擴展后字符串長度的兩倍 + 1;
如果新字符串大于1M，則新空間為擴展后字符串長度+ 1M + 1。稱為內存預分配。

優點：

獲取字符串長度的時間復雜度為O(1)
支持動態擴容
減少內存分配次數
二進制安全

2. IntSet

InSet是Redis中set集合的一種實現方式，基于整數數組來實現，并且具備長度可變、有序等特征。結構如下：

其中的encoding包含三種模式，表示存儲的整數大小不同：

為了方便查找，Redis會將inset中所有的整數按照升序依次保存在contents數組中，結構如圖：

現在，數組中每個數字都在int16_t的范圍內，因此采用的編碼方式是INTSET_ENC_INT16，每部分占用的字節大小為：

encoding：4字節
length：4字節
contents：2字節 * 3 = 6字節

尋址公式：startPtr + (sizeof(int16) * index)

IntSet升級

現在，假設有一個intset，元素為{5, 10, 20}，采用的編碼是INTSET_ENC_INT16，則每個整數占2字節：

我們向該intset中添加一個數字：50000，這個數字超出了int16_t的范圍，intset會自動升級編碼方式到合適的大小

以當前案例來說，流程如下：

①升級編碼為INTSET_ENC_INT32，每個整數占4字節，并按照新的編碼方式及元素個數擴容數組

②倒序依次將數組中的元素拷貝到擴容后的正確位置

③將待添加的元素放入數組末尾

④最后，將intset的encoding屬性改為INTSET_ENC_INT32，將length屬性改為4

總結

IntSet可以看做是特殊的整數數組，具備一些特點：

Redis會確保IntSet中的元素唯一、有序
具備類型升級機制，可以節省內存空間
底層采用二分查找方式來查詢

3. Dict

Redis是一個鍵值型（Key-Value pair）的數據庫，我們可以根據鍵實現快速的增刪改查。而鍵與值的映射關系正是通過Dict來實現的。

Dict由三部分組成，分別是：哈希表（DictHashTable）、哈希節點（DictEntry）、字典（Dict）

當我們向Dict添加鍵值對時，Redis首先根據key計算出hash值（h），然后利用 h & sizemask 來計算元素應該存儲到數組中的哪個索引位置。

假如，我們存儲k1 = v1，假設k1的哈希值h = 1，則1 & 3 = 1，因此k1 = v1要存儲到數組角標1位置：

現在又來了一個鍵值對k2 = v2，剛好計算得到的角標也是1，則把新來的鍵值對放到鏈表的頭部（頭插法）

結構：

Dict的擴容

Dict中的HashTable就是數組結合單向鏈表的實現，當集合中元素較多時，必然導致哈希沖突增多，鏈表過長，則查詢效率會大大降低。

Dict在每次新增鍵值對時都會檢查負載因子（LoadFactor = used/size），滿足以下兩種情況時會觸發哈希表擴容：

哈希表的LoadFactor?>= 1，并且服務器沒有執行BGSAVE或者BGREWRITE等后臺進程；
哈希表的LoadFactor > 5;

Dict的收縮

Dict除了擴容之外，每次刪除元素時，也會對負載因子做檢查，當LoadFactor < 0.1時，會做哈希表收縮：

Dict的rehash

不管是擴容還是收縮，必定會創建新的哈希表，導致哈希表的size和sizemask變化，而key的查詢與sizemask有關。因此必須對哈希表中是每一個key重新計算索引，插入新的哈希表，這個過程稱為rehash。過程是這樣的：

①計算新hash表的realeSize，值取決于當前要做的是擴容還是收縮：

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

②按照新的realeSize申請內存空間，創建dictht，并賦值給dict.ht[1]

③設置dict.rehashidx = 0，標示開始rehash

~~④將dict.ht[0]中的每一個dictEntry都rehash到dict.ht[1]~~

④每次執行新增、查詢、修改、刪除操作時，都檢查一下dict.rehashidx是否大于-1，如果是則將dict.ht[0].table[rehashidx]的entry鏈表rehash到dict.ht[1]，并且將rehashidx++。直至dict.ht[0]的所有數據都rehash到dict.ht[1]

⑤將dict.ht[1]賦值給dict.ht[0]，給dict.ht[1]初始化為空哈希表，釋放原來的dict.ht[0]的內存

總結

Dict的結構：

類似Java的HashTable，底層是數組加鏈表來解決哈希沖突
Dict包含兩個哈希表，ht[0]平常用，ht[1]用來rehash

Dict的伸縮：

當LoadFactor大于5或者LoadFactor大于1并且沒有子進程任務時，Dict擴容
當LoadFactor小于0.1時，Dict收縮
擴容大小為第一個大于等于used + 1的2^n
收縮大小為第一個大于等于used的2^n
Dict采用漸進式rehash，每次訪問Dict時執行一次rehash
rehash時ht[0]只減不增，新增操作只在ht[1]執行，其它操作在兩個哈希表

4. ZipList

ZipList是一種特殊的“雙端鏈表”，由一系列特殊編碼的連續內存塊組成。可以在任意一端進行壓入/彈出操作，并且該操作的時間復雜度為O(1)。

屬性	類型	長度	用途
zlbytes	uint32_t	4字節	記錄整個壓縮列表占用的內存字節數
zltail	uint32_t	4字節	記錄壓縮列表表尾節點距離壓縮列表的起始地址有多少字節，通過這個偏移量，可以確定表尾節點的地址
zllen	unit16_t	2字節	記錄了壓縮列表包含的節點數量。最大值為UINT16_MAX（65534），如果超過這個值，此處會記錄為65535，但節點的真實數量需要遍歷整個壓縮列表才能計算得出
entry	列表節點	不定	壓縮列表包含的各個節點，節點的長度由節點保存的內存決定
zlend	uint8_t	1字節	特殊值0xFF（十進制255），用于標記壓縮列表的末端

ZipListEntry

ZipList中的Entry并不像普通鏈表那樣記錄前后節點的指針，因為記錄兩個指針要占用16個字節，浪費內存。而是采用了下面的結構：

previous_entry_length：前一節點的長度，占1個或5個字節
- 如果前一節點的長度小于254字節，則采用1個字節來保存這個長度值
- 如果前一節點的長度大于254字節，則采用5個字節來保存這個長度值，第一個字節為0xfe，后四個字節才是真實長度數據
encoding：編碼屬性，記錄content的數據類型（字符串還是整數）以及長度，占用1個、2個或5個字節
content：負責保存節點的數據，可以是字符串或整數

注意：ZipList中所有存儲長度的數值均采用小端字節序，即低位字節在前，高位字節在后。例如：數值0x1234，采用小端字節序后實際存儲值為：0x3412

Encoding編碼

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

字符串：如果encoding是以“00”、“01”或者“10”開頭，證明content是字符串

編碼	編碼長度	字符串大小
\|00pppppp\|	1 bytes	<= 63 bytes
\|01pppppp\|qqqqqqqq\|	2 bytes	<= 16383 bytes
\| 10000000 \| qqqqqqqq \| rrrrrrrr \| ssssssss \| tttttttt \|	5 bytes	<= 4294967295 bytes

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

鏈表結構：

整數：如果encoding是以“11”開始，則證明content是整數，且encoding固定只占用1個字節

編碼	編碼長度	整數類型
11000000	1	int16_t（2 bytes）
11010000	1	int32_t（4 bytes）
11100000	1	int64_t（8 bytes)
11110000	1	24位有符整數（3 bytes）
11111110	1	8位有符整數（1 bytes）
1111xxxx	1	直接在xxxx位置保存數值，范圍從0001~1101，減1后結果為實際值

例如，一個ZipList中包含兩個整數值：“2”和“5”

ZipList結構：

ZipList的連鎖更新問題

ZipList的每個Entry都包含previos_entry_length來記錄上一個節點的大小，長度是1個或5個字節：

如果前一節點的長度小于254字節，則采用1個字節來保存這個長度值
如果前一節點的長度大于等于254字節，則采用5個字節來保存這個長度值，第一個字節為0xfe，后四個字節才是真實長度數據

現在，假設我們有N個連續的、長度為250~253字節之間的entry，因此previous_entry_length屬性用1個字節即可表示，如圖所示：

插入一個254bytes的節點：

ZipList這種特殊情況下產生的連續多次空間擴展操作稱之為連鎖更新（Cascade Update）。新增、刪除都可能導致連鎖更新的產生。

總結

ZipList特性：

①壓縮列表可以看做一種連續內存空間的“雙向鏈表”

②列表的節點之間不是通過指針連接，而是記錄上一節點和本節點長度來尋址，內存占用較低

③如果列表數據過多，導致鏈表過長，可能影響查詢性能

④增或刪較大數據時有可能發生連鎖更新問題

5. QuickList

問題1：ZipList雖然節省內存，但申請內存必須是連續空間，如果內存占用較多，申請內存效率較低。怎么辦？

答：為了緩解這個問題，我們必須限制ZipList的長度和entry大小。

問題2：但是我們要存儲大量數據，超出了ZipList最佳的上限該怎么辦？

答：我們可以創建多個ZipList來分片存儲數據。

問題3：數據拆分后比較分散，不方便管理和查找，這多個ZipList如何建立聯系？

答：Redis在3.2版本引入了新的數據結構QuickList，它是一個雙端鏈表，只不過鏈表中的每個節點都是一個ZipList。

為了避免QuickList中每個ZipList中entry過多，Redis提供了一個配置項：list-max-ziplist-size來限制。

如果值為正，則代表ZipList的允許的entry個數的最大值
如果值為負，則代表ZipList的最大內存大小，分為5種情況：
- -1：每個ZipList的內存占用不能超過4kb
- -2：每個ZipList的內存占用不能超過8kb
- -3：每個ZipList的內存占用不能超過16kb
- -4：每個ZipList的內存占用不能超過32kb
- -5：每個ZipList的內存占用不能超過64kb

其默認值為 -2：

除了控制ZipList的大小，QuickList還可以對節點的ZipList做壓縮。通過配置項 list-compress-depth來控制。因為鏈表一般都是從首尾訪問較多，所以首尾是不壓縮的。這個參數是控制首尾不壓縮的節點個數：

0：特殊值，代表不壓縮
1：標示QuickList的首尾各有1個節點不壓縮，中間節點壓縮
2：標示QuickList的首尾各有2個節點不壓縮，中間節點壓縮
以此類推

默認值：

以下是QuickList和QuickListNode的結構源碼：

總結

QuickList的特點：

是一個節點為ZipList的雙端鏈表
節點采用ZipList，解決了傳統鏈表的內存占用問題
控制了ZipList大小，解決連續內存空間申請效率問題
中間節點可以壓縮，進一步節省了內存

6. SkipList

SkipList（跳表）首先是鏈表，但與傳統鏈表相比有幾點差異：

元素按照升序排列存儲

節點可能包含多個指針，指針跨度不同

總結

SkipList的特點：

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

7. RedisObject

Redis中的任意數據類型的鍵和值都會被封裝為一個RedisObject，也叫做Redis對象，源碼如下：

Redis中會根據存儲的數據類型不同，選擇不同的編碼方式，共包含11中不同類型：

編號	編碼方式	說明
0	OBJ_ENCODING_RAW	raw編碼動態字符串
1	OBJ_ENCODING_INT	long類型的整數的字符串
2	OBJ_ENCODING_HT	hash表（字典dict）
3	OBJ_ENCODING_ZIPMAP	已廢棄
4	OBJ_ENCODING_LINKEDLIST	雙端鏈表
5	OBJ_ENCODING_ZIPLIST	壓縮列表
6	OBJ_ENCODING_INTSET	整數集合
7	OBJ_ENCODING_SKIPLIST	跳表
8	OBJ_ENCODING_EMBSTR	embstr的動態字符串
9	OBJ_ENCODING_QUICKLIST	快速列表
10	OBJ_ENCODING_STREAM	Stream流

8. 五種數據結構

Redis中會根據存儲的數據類型不同，選擇不同的編碼方式。每種數據類型的使用的編碼方式如下：

數據類型	編碼方式
OBJ_STRING	int、embstr、raw
OBJ_LIST	LinkedList和ZipList(3.2以前)、QuickList(3.2以后)
OBJ_SET	intset、HT
OBJ_ZSET	ZipList、HT、SkipList
OBJ_HASH	ZipList、HT

8.1 String

String是Redis中最常見的數據存儲類型：

其基本編碼方式是RAW，基于簡單動態字符串（SDS）實現，存儲上限為512mb；

如果存儲的SDS長度小于44字節，則會采用EMBSTR編碼，此時object head與SDS是一段連續空間。申請內存時只需要調用一次內存分配函數，效率更高；
如果存儲的字符串是整數值，并且大小在LONG_MAX范圍內，則會采用INT編碼：直接將數據保存在RedisObject的ptr指針位置（剛好8個字節），不再需要SDS了。

示例：

8.2 List

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

哪一個數據結構能滿足上述特征？

LinkedList：普通鏈表，可以從雙端訪問，但內存占用較高，內存碎片較多
ZipList：壓縮列表，可以從雙端訪問，內存占用低，存儲上限低
QuickList：LinkedList + ZipList，可以從雙端訪問，內存占用較低，包含多個ZipList，存儲上限高

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

在3.2版本之前，Redis采用ZipList和LinkedList來實現List，當元素數量小于512并且元素大小小于64字節時采用ZipList編碼，超過則采用LinkedList編碼
在3.2版本之后，Redis統一采用QuickList來實現List

8.3 Set

Set是Redis中的單列集合，滿足下列特點：

不保證有序性
保證元素唯一（可以判斷元素是否存在）
求交集、并集、差集

可以看出，Set對查詢元素的效率要求非常高，思考一下，什么樣的數據結構可以滿足要求？

答：HashTable，也就是Redis中的Dict，不過Dict是雙列集合（可以存鍵、值對）

Set是Redis中的集合，不一定確保元素有序，可以滿足元素唯一、查詢效率要求極高

為了查詢效率和唯一性，set采用HT編碼（Dict）。Dict中的key用來存儲元素，value統一為null；
當存儲的所有數據都是整數，并且元素數量不超過 set-max-intset-entries（默認是512）時，Set會采用IntSet編碼，以節省內存；

8.4 ZSet

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

可以根據score值排序
member必須唯一
可以根據member查詢分數

因此，ZSet底層數據結構必須滿足鍵值存儲、鍵必須唯一、可排序這幾個需求。

~~SkipLis~~t：可以排序，并且可以同時存儲score和ele值（member）（鍵不一定唯一）
~~HT（Dict）~~：可以鍵值存儲，并且可以根據key找value（不可排序）
HT + SkipList

當元素數量不多時，HT和SkipList的優勢不明顯，而且更耗內存。因此ZSet還會采用ZipList結構來節省內存，不過需要同時滿足兩個條件：

①元素數量小于zset_max_ziplist_entries，默認值128

②每個元素都小于zset_max_ziplist_value字節，默認值64

ZipList本身沒有排序功能，而且沒有鍵值對的概念，因此需要有zset通過編碼實現：

ZipList是連續內存，因此score和element是緊挨在一起的兩個entry，element在前，score在后
score越小越接近隊首，score越大越接近隊尾，按照score值升序排列

ZipList轉HT + SkipList：

8.5 Hash

Hash結構與Redis中的ZSet非常類似：

都是鍵值存儲
都需求根據鍵獲取值
鍵必須唯一

區別如下：

zset的鍵是member，值是score；hash的鍵和值都是任意值
zset要根據score排序；hash則無需排序

因此，Hash底層采用的編碼也與ZSet基本一致，只需要把排序有關的Skiplist去掉即可：

Hash結構默認采用ZipList編碼，用以節省內存。ZipList中相鄰的兩個entry分別保存field和value
當數據量較大時，Hash結構會轉為HT編碼，也就是Dict，觸發條件有兩個：
- ZipList中的元素數量超過了hash-max-ziplist-entries（默認512）
- ZipList中的任意entry大小超過了hash-max-ziplist-value（默認64字節）

二、網絡模型

1. 用戶空間和內核空間

服務器大多采用Linux系統，這里我們以Linux為例來講解：

任何Linux發行版，其系統內核都是Linux，我們的應用都需要通過Linux內核與硬件交互。

為了避免用戶應用導致沖突甚至內核崩潰，用戶應用于內核是分離的：

進程的尋址空間會劃分為兩部分：內核空間、用戶空間
用戶空間只能執行受限的命令（Ring3），而且不能直接調用系統資源，必須通過內核提供的接口來訪問
內核空間可以執行特權命令（Ring0），調用一切系統資源

2. 阻塞IO

在《UNIX網絡編程》一書中，總結歸納了5種IO模型：

阻塞IO（Blocking IO）
非阻塞IO（NonBlocking IO）
IO多路復用（IO Multiplexing）
信號驅動IO（Signal Driven IO）
異步IO（Asynchronous IO)

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

階段一：

用戶進程嘗試讀取數據（比如網卡數據）
此時數據尚未到達，內核需要等待數據
此時用戶進程也處于阻塞狀態

階段二：

數據到達并拷貝到內核緩沖區，代表已就緒
將內核數據拷貝到用戶緩沖區
拷貝過程中，用戶進程依然阻塞等待
拷貝完成，用戶進程解除阻塞，處理數據

3. 非阻塞IO

顧名思義，非阻塞IO的recvfrom操作會立即返回結果而不是阻塞用戶進程。

階段一：

用戶進程嘗試讀取數據（比如網卡數據）
此時數據尚未到達，內核需要等待數據
返回異常給用戶進程
用戶進程拿到error后，再次嘗試讀取
循環往復，直到數據就緒

階段二：

將內核數據拷貝到用戶緩沖區
拷貝過程中，用戶進程依然阻塞等待
拷貝完成，用戶進程解除阻塞，處理數據

可以看到，非阻塞IO模型中，用戶進程在第一個階段是非阻塞，第二個階段是阻塞狀態。雖然是非阻塞，但性能并沒有得到提高。而且忙等機制會導致CPU空轉，CPU使用率暴增。

4. IO多路復用

無論是阻塞IO還是非阻塞IO，用戶應用在一階段都需要調用recvfrom來獲取數據，差別在于無數據時的處理方案：

如果調用recvfrom時，恰好沒有數據，阻塞IO會使進程阻塞，非阻塞IO使CPU空轉，都不能充分發揮CPU的作用；
如果調用recvfrom時，恰好有數據，則用戶進程可以直接進入第二階段，讀取并處理數據

比如服務端處理客戶端Socket請求時，在單線程情況下，只能依次處理每一個socket，如果正在處理的socket恰好未就緒（數據不可讀或不可寫），線程就會被阻塞，所有其它客戶端socket都必須等待，性能自然會很差。

這就像服務員給顧客點餐，分兩步：

①顧客思考要吃什么（等待數據就緒）

②顧客想好了，開始點餐（讀取數據）

要提高效率有幾種方法？

方案一：增加更多服務員（多線程）
方案二：不排隊，誰想好了吃什么（數據就緒了），服務員就給誰點餐（用戶應用就去讀取數據）

問題：用戶進程如何知道內核中數據是否就緒呢？

文件描述符（File Descriptor）：簡稱FD，是一個從0開始遞增的無符號整數，用來關聯Linux中的一個文件。在Linux中，一切皆文件，例如常規文件、視頻、硬件設備等，當然也包括網絡套接字（Socket）。

IO多路復用：是利用單個線程來同時監聽多個FD，并在某個FD可讀時、可寫時得到通知，從而避免無效的等待，充分利用CPU資源。

不過監聽FD的方式、通知的方式又有多種實現，常見的有：

select
poll
epoll

差異：

select和poll只會通知用戶進程有FD就緒，但不確定具體是哪個FD，需要用戶進程逐個遍歷FD來確認
epoll則會在通知用戶進程FD就緒的同時，把已就緒的FD寫入用戶空間

4.1 IO多路復用 - select

select是Linux中最早的I/O多路復用實現方案：

IO流程：

①初始化fd_set集合

使用FD_ZERO清空集合；
使用FD_SET將需要監控的FD加入readfds（可讀）、writefds（可寫）或exceptfds（異常）集合；

②調用select阻塞等待：

select會阻塞，直到至少一個FD就緒，或者超時（如果設置了timeout）
內核會輪詢所有被監控的FD，檢查它們是否就緒（如socket可讀、可寫或發生異常）；

③select返回：

返回值 > 0：表示就緒的FD數量；
返回值 = 0：表示超時，沒有FD就緒；
返回值 = -1：表示出錯（如被信號中斷）；

④遍歷fd_set檢查就緒的FD：

使用FD_ISSET檢查哪些FD已經就緒；
處理就緒的FD（如讀取數據、發送數據等）；

⑤循環調用select：

由于select會修改fd_set，每次調用前需要重新設置FD集合。

select模式存在的問題：

需要將整個fd_set從用戶空間拷貝到內核空間，select結束還要再次拷貝回用戶空間
select無法得知具體是哪個fd就緒，需要遍歷整個fd_set
fd_set監聽的fd數量不能超過1024

4.2?IO多路復用 - poll

poll模式對select模式做了簡單改進，但性能提升不明顯，部分關鍵代碼如下：

IO流程：

①創建pollfd數組，向其中添加關注的fd信息，數組大小自定義

②調用poll函數，將pollfd數組拷貝到內核空間，轉鏈表存儲，無上限

③內核遍歷fd，判斷是否就緒

④數據就緒或超時后，拷貝pollfd數組到用戶空間，返回就緒fd數量n

⑤用戶進程判斷n是否大于0

⑥大于0則遍歷pollfd數組，找到就緒的fd

與select對比：

select模式中的fd_set大小固定為1024，而pollfd在內核中采用鏈表，理論上無上限
監聽FD越多，每次遍歷消耗時間也越久，性能反而會下降

4.3?IO多路復用 - epoll

epoll模式是對select和poll的改進，它提供了三個函數：

IO流程：

①創建epoll實例：

內核會創建一個epoll實例，返回對應的句柄epoll_fd；
底層數據結構：紅黑樹（存儲待監聽的FD）+ 就緒鏈表（存儲就緒的FD）。

②注冊/修改/刪除 FD事件

epoll_ctl操作類型：EPOLL_CTL_ADD、EPOLL_CTL_MOD、EPOLL_CTL_DEL
事件類型：EPOLLIN（FD可讀）、EPOLLOUT（FD可寫）、EPOLLET（邊緣觸發模式，默認是水平觸發LT）、EPOLLRDHUP（對端關閉連接 - TCP半關閉）

③等待事件就緒：

epoll_wait返回就緒的FD數量，并將就緒事件填充到events數組；
兩種觸發模式：
- 水平觸發（LT，默認）：只有FD 可讀/可寫，就會一直通知。
- 邊緣觸發（ET）：僅在FD狀態變化時通知一次（必須一次性處理完數據）

④處理就緒事件：

遍歷events數組，處理所有就緒的FD（如讀取數據、發送數據等）。

總結：

1. select模式存在的三個問題：

能監聽的FD最大不超過1024；
每次select都需要把所有要監聽的FD都拷貝到內核空間
每次都要遍歷所有FD來判斷就緒狀態

2. poll模式的問題：

poll利用鏈表解決了select中監聽FD上限的問題，但依然要遍歷所有FD，如果監聽較多，性能會下降

3. epoll模式中如何解決這些問題的？

基于epoll實例中的紅黑樹保存要監聽的FD，理論上無上限，而且增刪改查效率都非常高，性能不會隨監聽的FD數量增多而下降
每個FD只需要執行一次epoll_ctl添加到紅黑樹，以后每次epoll_wait無需傳遞任何參數，無需重復拷貝FD到內核空間；
內核會將就緒的FD直接拷貝到用戶空間的指定位置，用戶進程無需遍歷所有FD就能知道就緒的FD是誰。

特性	`select`	`poll`	`epoll`?(Linux)
FD 數量限制	1024（固定）	無限制（基于鏈表）	無限制（基于紅黑樹）
效率	O(n) 遍歷所有 FD	O(n) 遍歷所有 FD	O(1) 僅返回就緒 FD
事件通知	僅返回就緒 FD	僅返回就緒 FD	可返回具體事件類型
內存拷貝	每次調用都要拷貝 FD 集合	每次調用都要拷貝 FD 數組	使用 mmap 減少拷貝
適用場景	跨平臺、少量連接	比?`select`?稍好	高并發（如 10萬+ 連接）

4.3.1 IO多路復用 - 事件通知機制

當FD有數據可讀時，我們調用epoll_wait就可以得到通知。但是事件通知的模式有兩種：

LevelTriggered：簡稱LT。當FD有數據可讀時，會重復通知多次，直至數據處理完成。是Epoll的默認模式。
EdgeTriggered：簡稱ET。當FD有數據可讀時，只會被通知一次，不管數據是否處理完成。

舉個例子：

①假設一個客戶端socket對應的FD已經注冊到了epoll實例中

②客戶端socket發送了2kb的數據

③服務端調用epoll_wait，得到通知說FD就緒

④服務端從FD讀取了1kb數據

⑤回到步驟3（再次調用epoll_wait，形成循環）

結論

如果我們采用LT模式，因為FD中仍有1kb數據，則第⑤步依然會返回結果，并且得到通知；
如果我們采用ET模式，因為第③步已經消費了FD可讀事件，第⑤步FD狀態沒有變化，因此epoll_wait不會返回，數據無法讀取客戶端響應超時。
ET模式避免了LT模式可能出現的驚群現象
ET模式最好結合非阻塞IO讀取FD數據，相比LT會復雜一些

4.3.2 IO多路復用 - 基于epoll的服務器端流程

基于epoll模式的web服務器的基本流程如圖：

我們來梳理一下這張圖：

①服務器啟動以后，服務端會去調用epoll_create，創建一個epoll實例，epoll實例中包含兩個數據：

紅黑樹（為空）：rb_root用來記錄需要被監聽的FD
鏈表（為空）：list_head，用來存放已經就緒的FD

②創建好了之后，會去調用epoll_ctl函數，此函數會將需要監聽的數據添加到rb_root中去，并且對當前這些存在于紅黑樹的節點設置回調函數，當這些被監聽的數據一旦準備完成，就會被調用，而調用的結果就是將紅黑樹的fd添加到list_head中去（但是此時并沒有完成）；

③當第二步完成以后，就會調用epoll_wait函數，這個函數會去校驗是否有數據準備完畢（因為數據一旦準備就緒，就會被回調函數添加到list_head中），在等待了一段時間后（可以進行配置），如果等夠了超時時間，則返回沒有數據；如果有，則進一步判斷當前是什么事件，如果是建立連接事件，則調用accept()接受客戶端socket，拿到建立連接的socket，然后建立起來連接，如果是其它事件，則把數據進行寫出。

5. 信號驅動IO

信號驅動IO是與內核建立SIGIO的信號關聯并設置回調，當內核有FD就緒時，會發出SIGIO信號通知用戶，期間用戶應用可以執行其它業務，無需阻塞等待。

階段一：

用戶進程調用sigaction，注冊信號處理函數
內核返回成功，開始監聽FD
用戶進程不阻塞等待，可以執行其它業務
當內核數據就緒后，回調用戶進程的SIGIO處理函數

階段二：

收到SIGIO回調信號
調用recvfrom，讀取
內核將數據拷貝到用戶空間
用戶進程處理數據

當有大量IO操作時，信號較多，SIGIO處理函數不能及時處理可能導致信號隊列溢出，而且內核空間與用戶空間的頻繁信號交互性能也較低。

6. 異步IO

異步IO的整個過程都是非阻塞的，用戶進程調用完異步API后就可以去做其它事情，內核等待數據就緒并拷貝到用戶空間后才會遞交信號，通知用戶進程。

同步和異步

IO操作是同步還是異步，關鍵看數據在內核空間與用戶空間的拷貝過程（數據讀寫的IO操作），也就是階段二是同步還是異步：

7. Redis網絡模型

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

如果僅僅聊Redis的核心業務部分（命令處理），答案是單線程；
如果是聊整個Redis，那么答案就是多線程。

在Redis版本迭代過程中，在兩個重要的時間節點上引入了多線程的支持：

Redis v4.0：引入多線程異步處理一些耗時比較長的任務，例如異步刪除命令unlink
Redis v6.0：在核心網絡模型中引入多線程，進一步提高對于多核CPU的利用率

2. 為什么Redis要選擇單線程？

拋開持久化不談，Redis是純內存操作，執行速度非常快，它的性能瓶頸是網絡延遲而不是執行速度，因此多線程并不會帶來巨大的性能提升。
多線程會導致過多的上下文切換，帶來不必要的開銷
引入多線程會面臨線程安全問題，比如要引入線程鎖這樣的安全手段，實現復雜度增高，而且性能也會大打折扣。

Redis通過IO多路復用來提高網絡性能，并且支持各種不同的多路復用實現，并且將這些實現進行封裝，提供了統一的高性能事件庫API庫 AE：

來看下Redis單線程網絡模型的整個流程：

Redis 6.0版本中引入了多線程，目的是為了提高IO讀寫效率。因此在解析客戶端命令、寫響應結果時采用了多線程。核心的命令執行、IO多路復用模塊依然是由主線程執行。

三、通信協議

1. RESP協議

Redis是一個C/S架構的軟件，通信一般分兩步（不包括pipeline和PubSub）：

①客戶端（client）向服務端（server）發送一條命令；

②服務端解析并執行命令，返回響應結果給客戶端。

因此，客戶端發送命令的格式、服務端響應結果的格式必須有一個規范，這個規范就是通信協議。

而在Redis中采用的是RESP（Redis Serialization Protocol）協議:

Redis 1.2版本引入了RESP協議
Redis 2.0版本中稱為與Redis服務端通信的標準，稱為RESP2
Redis 6.0版本中，從RESP2升級到了RESP3協議，增加了更多數據類型并且支持6.0的新特性 - 客戶端緩存。

但目前，默認使用的依然是RESP2協議，也是我們要學習的協議版本（以下簡稱RESP）。

在RESP中，通過首字節的字符來區分不同數據類型，常用的數據類型包括5種：

單行字符串：首字節是'+'，后面跟上單行字符串，以CRLF（"\r\n"）結尾。例如返回"OK": "+OK\r\n"
錯誤（Errors）：首字節是'-'，與單行字符串格式一樣，只是字符串是異常信息，例如："-Error message\r\n"
數值：首字節是':'，后面跟上數字格式的字符串，以CRLF結尾。例如：":10\r\n"
多行字符串：首字節是'$'，表示二進制安全的字符串，最大支持512MB：
- 如果大小為0，則代表空字符串："$0\r\n\r\n"
- 如果大小為-1，則代表不存在："$-1\r\n"
數組：首字節是'*'，后面跟上數組元素個數，再跟上元素，元素數據類型不限：

2. 模擬Redis客戶端

package com.company;import java.io.*;
import java.net.Socket;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;public class Main {static Socket s;static PrintWriter writer;  // 按行輸出static BufferedReader reader;public static void main(String[] args) {try {// 1.建立連接String host = "192.168.200.130";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.發出請求// 3.1.獲取授權 auth leadnewssendRequest("auth", "leadnews");Object obj = handleResponse();System.out.println("obj = " + obj);// 3.2.set name 虎哥sendRequest("set", "name", "虎哥");// 4.解析響應obj = handleResponse();System.out.println("obj = " + obj);// 3.2.get namesendRequest("get", "name");// 4.解析響應obj = handleResponse();System.out.println("obj = " + obj);// 3.2.set name 虎哥sendRequest("mget", "name", "num", "msg");// 4.解析響應obj = handleResponse();System.out.println("obj = " + obj);} catch (IOException e) {e.printStackTrace();} finally {// 5.釋放連接try {if (reader != null) reader.close();} catch (IOException e) {e.printStackTrace();}if (writer != null) writer.close();try {if (s != null) s.close();} catch (IOException e) {e.printStackTrace();}}}private static Object handleResponse() throws IOException {// 讀取首字節int prefix = reader.read();// 判斷數據類型標示switch (prefix) {case '+': // 單行字符串，直接讀一行return reader.readLine();case '-': // 異常，也讀一行throw new RuntimeException(reader.readLine());case ':': // 數字return Long.parseLong(reader.readLine());case '$': // 多行字符串// 先讀長度int len = Integer.parseInt(reader.readLine());if (len == -1) {return null;}if (len == 0) {return "";}// 再讀數據,讀len個字節。我們假設沒有特殊字符，所以讀一行（簡化）return reader.readLine();case '*':return readBulkString();default:throw new RuntimeException("錯誤的數據格式！");}}private static Object readBulkString() throws IOException {// 獲取數組大小int len = Integer.parseInt(reader.readLine());if (len <= 0) {return null;}// 定義集合，接收多個元素List<Object> list = new ArrayList<>(len);// 遍歷，依次讀取每個元素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();}
}