IO多路複用：Redis中經典的Reactor設計模式
Redis Server跑在單進程單線程中，接收到的命令操作都是按照順序線性執行的，即便如此，它的讀寫性能依然能達到10W+的QPS，不得不說：Redis的設計十分優秀。
爲什麼Redis的讀寫性能這麼高呢？原因有許多，我們列舉主要的三個：
1、Redis基於內存操作：
絕大部分的請求爲純粹的內存操作，而且使用hash結構存儲數據，查找和操作的時間複雜度均爲O(1)。
2、Redis數據結構簡單：
redis對數據的操作還是比較簡單的，而且redis的數據結構是專門設計的。
3、單線程-IO多路複用模型：
單線程的設計省去了很多的麻煩：比如上下文切換、資源競爭、CPU切換消耗以及各種鎖操作等等問題，而IO多路複用模型的使用更讓Redis提升了效率。
今天，我們就來聊一聊：IO多路複用模型。
IO即爲網絡I/O，多路即爲多個TCP連接，複用即爲共用一個線程或者進程，模型最大的優勢是系統開銷小，不必創建也不必維護過多的線程或進程。
IO多路複用是經典的Reactor設計模式，有時也稱爲異步阻塞IO（異步指socket爲non-blocking，堵塞指select堵塞），爲常見的四種IO模型之一，其他三種分別是：同步堵塞IO、同步非堵塞IO、異步（非堵塞）IO。
IO多路複用的核心是可以同時處理多個連接請求，爲此使用了兩個系統調用，分別是：
1.select/poll/epoll--模型機制：可以監視多個描述符（fd），一旦某個描述符就緒（讀/寫/異常）就能通知程序進行相應的讀寫操作。讀寫操作都是自己負責的，也即是阻塞的，所以本質上都是同步（堵塞）IO。Redis支持這三種機制，默認使用epoll機制。2.recvfrom--接收數據。而blocking IO只調用了recvfrom，所以在連接數不高的情況下，blocking IO的性能不一定比IO多路複用差。
補充：異步IO無需自己負責讀寫操作。
1、select機制：
select原理：
當client連接到server後，server會創建一個該連接的描述符fd，fd有三種狀態，分別是讀、寫、異常，存放在三個fd_set（其實就是三個long型數組）中。
#include <sys/select.h>
//select接口，調用時會堵塞
int select(int nfds, fd_set *readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
而select()的本質就是通過設置和檢查fd的三個fd_set來進行下一步處理。
select大體執行步驟：
1) 使用copy_from_user從用戶空間拷貝fd_set到內核空間
2) 內核遍歷[0,nfds)範圍內的每個fd，調用fd所對應的設備的驅動poll函數，poll函數可以檢測fd的可用流（讀流、寫流、異常流）。
3) 檢查是否有流發生，如果有發生，把流設置對應的類別，並執行4，如果沒有流發生，執行5。或者timeout=0，執行4。
4) select返回。
5）select阻塞進程，等待被流對應的設備喚醒時執行2，或timeout到期，執行4。
select的侷限性：
- 維護一個存放大量描述符的數組：每次調用select()都需要將fd_set從用戶態拷貝到內核態，然後由內核遍歷fd_set，如果fd_set很大，那麼拷貝和遍歷的開銷會很大，爲了減少性能損壞，內核對fd_set的大小做了限制，並通過宏定義控制，無法改變（1024）。
- 單進程監聽的描述符數量有限制：單進程能打開的最大連接數。
- 輪詢遍歷數組，效率低下：select機制只知道有IO發生，但是不知道是哪幾個描述符，每次喚醒，都需要遍歷一次，複雜度爲O(n);
2、poll機制：
poll原理：
poll的實現和select非常相似，輪詢+遍歷+根據描述符的狀態處理，只是fd_set換成了pollfd，而且去掉了最大描述符數量限制，其他的侷限性同樣存在。
#include <poll.h>
int poll ( struct pollfd * fds, unsigned int nfds, int timeout);
struct pollfd {
int fd; /* 文件描述符 */
short events; /* 等待的事件 */
short revents; /* 實際發生了的事件 */
} ;
3、epoll機制：epoll對select和poll進行了改進，避免了上述三個侷限性。
epoll原理：
與select和poll只提供一個接口函數不同的是，epoll提供了三個接口函數及一些結構體：
/*建一個epoll句柄*/
int epoll_create(int size);
/*向epoll句柄中添加需要監聽的fd和時間event*/
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
/*返回發生事件的隊列*/
int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout);
struct eventpoll
{
...
/*紅黑樹的根節點，這棵樹中存儲着所有添加到epoll中的事件，也就是這個epoll_ctl監控的事件*/
struct rb_root rbr;
/*雙向鏈表rdllist保存着將要通過epoll_wait返回給用戶的、滿足條件的事件*/
struct list_head rdllist;
1.調用epoll_create：linux內核會在epoll文件系統創建一個file節點，同時創建一個eventpoll結構體，結構體中有兩個重要的成員：rbr是一棵紅黑樹，用於存放epoll_ctl註冊的socket和事件；rdllist是一條雙向鏈表，用於存放準備就緒的事件供epoll_wait調用。
2.調用epoll_ctl：會檢測rbr中是否已經存在節點，有就返回，沒有則新增，同時會向內核註冊回調函數ep_poll_callback，當有事件中斷來臨時，調用回調函數向rdllist中插入數據，epoll_ctl也可以增刪改事件。
3.調用epoll_wait：返回或者判斷rdllist中的數據即可。
epoll兩種工作模式：LT--水平觸發 ET--邊緣觸發
LT：只要文件描述符還有數據可讀，每次 epoll_wait都會返回它的事件，提醒用戶程序去操作。
ET：檢測到有IO事件時，通過epoll_wait調用會得到有事件通知的文件描述符，對於每一個被通知的文件描述符，必須將該文件描述符一直讀到空，讓errno返回EAGAIN爲止，否則下次的epoll_wait不會返回餘下的數據，會丟掉事件。
ET比LT更加高效，因爲ET只通知一次，而LT會通知多次，LT可能會充斥大量不關心的就緒文件描述符。
epoll總結：
- 使用紅黑樹而不是數組存放描述符和事件，增刪改查非常高效，輕易可處理大量併發連接。
- 紅黑樹及雙向鏈表都在內核cache中，避免拷貝開銷。
- 採用回調機制，事件的發生只需關注rdllist雙向鏈表即可。