不管是從事前端開發人員還是後端開發人員，他們在部署服務時，第一個想到的就是用Nginx做代理和靜态資源緩存，因為Nginx經過千錘百煉，足以應對百萬并發。
但是對于Nginx這種高效web服務，它底層到底有什麼神秘武器支援大流量并發呢？答案就在epoll裡面。
1. epoll 資料結構 + 算法
epoll 的核心資料結構是：1個紅黑樹和1個雙向連結清單。還有3個核心API。如上圖所示。
2. 監視socket索引-紅黑樹
為什麼采用紅黑樹呢？因為和epoll的工作機制有關。epoll在添加一個socket或者删除一個socket或者修改一個socket的時候，它需要查詢速度更快，操作效率最高，是以需要一個更加優秀的資料結構能夠管理這些socket。
我們想到的比如連結清單，數組，二叉搜尋樹，B+樹等都無法滿足要求，
- 因為連結清單在查詢，删除的時候毫無疑問時間複雜度是O(n)；
- 數組查詢很快，但是删除和新增時間複雜度是O(n)；
- 二叉搜尋樹雖然查詢效率是lgn，但是如果不是平衡的，那麼就會退化為線性查找，複雜度直接來到O(n)；
- B+樹是平衡多路查找樹，主要是通過降低樹的高度來存儲上億級别的資料，但是它的應用場景是記憶體放不下的時候能夠用最少的IO通路次數從磁盤擷取資料。比如資料庫聚簇索引，成百上千萬的資料記憶體無法滿足查找就需要到記憶體查找，而因為B+樹層高很低，隻需要幾次磁盤IO就能擷取資料到記憶體，是以在這種磁盤到記憶體通路上B+樹更适合。
因為我們處理上萬級的fd，它們本身的存儲空間并不會很大，是以傾向于在記憶體中去實作管理，而紅黑樹是一種非常優秀的平衡樹，它完全是在記憶體中操作，而且查找，删除和新增時間複雜度都是lgn，效率非常高，是以選擇用紅黑樹實作epoll是最佳的選擇。
當然不選擇用AVL樹是因為紅黑樹是不符合AVL樹的平衡條件的，紅黑是用非嚴格的平衡來換取增删節點時候旋轉次數的降低，任何不平衡都會在三次旋轉之内解決；而AVL樹是嚴格平衡樹，在增加或者删除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多。是以紅黑樹的插入效率更高。
3. 就緒socket清單-雙向連結清單
就緒清單存儲的是就緒的socket，是以它應能夠快速的插入資料。
程式可能随時調用epoll_ctl添加監視socket，也可能随時删除。當删除時，若該socket已經存放在就緒清單中，它也應該被移除。（事實上，每個epoll_item既是紅黑樹節點，也是連結清單節點，删除紅黑樹節點，自然删除了連結清單節點）
是以就緒清單應是一種能夠快速插入和删除的資料結構。雙向連結清單就是這樣一種資料結構，epoll使用雙向連結清單來實作就緒隊列（rdllist）
4. 三個API
4.1 int epoll_create(int size)
功能：
核心會産生一個epoll 執行個體資料結構并傳回一個檔案描述符epfd，這個特殊的描述符就是epoll執行個體的句柄，後面的兩個接口都以它為中心。同時也會建立紅黑樹和就緒清單，紅黑樹來管理注冊fd，就緒清單來收集所有就緒fd。size參數表示所要監視檔案描述符的最大值，不過在後來的Linux版本中已經被棄用（同時，size不要傳0，會報invalid argument錯誤）
4.2 int epoll_ctl(int epfd， int op， int fd， struct epoll_event *event)
功能：
将被監聽的socket檔案描述符添加到紅黑樹或從紅黑樹中删除或者對監聽事件進行修改；同時向核心中斷處理程式注冊一個回調函數，核心在檢測到某檔案描述符可讀/可寫時會調用回調函數，該回調函數将檔案描述符放在就緒連結清單中。
4.3 int epoll_wait(int epfd， struct epoll_event *events， int maxevents， int timeout);
功能：
阻塞等待注冊的事件發生，傳回事件的數目，并将觸發的事件寫入events數組中。
events: 用來記錄被觸發的events，其大小應該和maxevents一緻
maxevents: 傳回的events的最大個數處于ready狀态的那些檔案描述符會被複制進ready list中，epoll_wait用于向使用者程序傳回ready list(就緒清單)。
events和maxevents兩個參數描述一個由使用者配置設定的struct epoll event數組，調用傳回時，核心将就緒清單(雙向連結清單)複制到這個數組中，并将實際複制的個數作為傳回值。
注意，如果就緒清單比maxevents長，則隻能複制前maxevents個成員；反之，則能夠完全複制就緒清單。
另外，struct epoll event結構中的events域在這裡的解釋是：在被監測的檔案描述符上實際發生的事件。
4.4 小結
調用epoll_create時，在核心cache裡建了個紅黑樹用于存儲以後epoll_ctl傳來的socket外，還會再建立一個list連結清單，用于存儲準備就緒的事件。
當epoll_wait調用時，僅僅觀察這個雙向連結清單裡有沒有資料即可。有資料就傳回，沒有資料就sleep，等到timeout時間到後即使連結清單沒資料也傳回。是以，epoll_wait非常高效。而且，通常情況下即使我們要監控百萬計的句柄，大多一次也隻傳回很少量的準備就緒句柄而已，是以，epoll_wait僅需要從核心态copy少量的句柄到使用者态而已。
相關視訊推薦
6種epoll的做法，從redis，memcached到nginx的網絡模型實作
5種紅黑樹的場景，從Linux核心談到Nginx源碼，聽完醍醐灌頂
學習位址：c/c++ linux伺服器開發/背景架構師
【文章福利】需要C/C++ Linux伺服器架構師學習資料加群812855908（資料包括C/C++，Linux，golang技術，核心，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg，大廠面試題 等）
5. 實作細節
linux采用eventpoll資料結構來管理epoll，紅黑樹每個節點用epitime資料結構來管理，具體請參考linux3.16：eventpoll.c 和 eventpoll.h 主要位于fs/eventpoll.c 和 include/linux/eventpool.h。
有了這兩個核心資料結構之後，那麼在處理事件和就緒隊列的時候就會高效的多。
6. 整個Nginx epoll流程
我們知道worker程序是最終處理請求的，是以事件循環在worker裡面進行。核心主流程就是多個worker程序去競争鎖，拿到鎖的worker程序注冊檔案描述符fd到epoll的紅黑樹中，然後worker程序在等待就緒fd的時候将自己挂起。等核心擷取到中斷信号之後會發起回調，将已經就緒的fd寫入到雙向連結清單，然後核心周遊連結清單将fd拷貝到使用者口空間的event_list中，這樣被挂起的worker程序就會被喚醒(之前阻塞在這裡是因為沒有fd就緒，現在數組有fd了，會換新程序)，通過周遊event_list執行fd相應事件的回調，這樣請求就從worker進來，經過epoll處理之後将我們關心的fd事件通過回調的方式通知到Nginx，Nginx可以做進一步處理，最後也釋放了鎖。如下圖：
周遊就緒事件的核心處理邏輯是：ngx_epoll_process_events
7. epoll更高效的原因
有人說epoll使用了mmap，我找了源碼半天沒有找到，真的想打人。根據以上分析，epoll_ctl注冊fd到紅黑樹拷貝一次，然後從就緒隊列拷貝少量的fd到數組中又是一次拷貝，整體而言拷貝比較少(因為活躍的比較少，遇到大量活躍的可能性能就比較差了)。再加上少量輪循就可以處理就緒fd，是以效率非常高。
8. 總結