高并發(fā)基石|深入理解IO復(fù)用技術(shù)之epoll
1.寫在前面
-
IO復(fù)用的概念 -
epoll出現(xiàn)之前的IO復(fù)用工具 -
epoll三級(jí)火箭 -
epoll底層實(shí)現(xiàn) -
ET模式<模式 -
一道騰訊面試題 -
epoll驚群?jiǎn)栴}
2.初識(shí)復(fù)用技術(shù)和IO復(fù)用
在了解epoll之前，我們先看下復(fù)用技術(shù)的概念和IO復(fù)用到底在說什么？
2.1 復(fù)用概念和資源特性
2.1.1 復(fù)用的概念
復(fù)用技術(shù) multiplexing 并不是新技術(shù)而是一種設(shè)計(jì)思想，在通信和硬件設(shè)計(jì)中存在頻分復(fù)用、時(shí)分復(fù)用、波分復(fù)用、碼分復(fù)用等，在日常生活中復(fù)用的場(chǎng)景也非常多，因此不要被專業(yè)術(shù)語所迷惑。
從本質(zhì)上來說，復(fù)用就是為了解決有限資源和過多使用者的不平衡問題，從而實(shí)現(xiàn)最大的利用率，處理更多的問題。
2.1.2 資源的可釋放
舉個(gè)例子：
不可釋放場(chǎng)景：ICU 病房的呼吸機(jī)作為有限資源，病人一旦占用且在未脫離危險(xiǎn)之前是無法放棄占用的，因此不可能幾個(gè)情況一樣的病人輪流使用。
可釋放場(chǎng)景：對(duì)于一些其他資源比如醫(yī)護(hù)人員就可以實(shí)現(xiàn)對(duì)多個(gè)病人的同時(shí)監(jiān)護(hù)，理論上不存在一個(gè)病人占用醫(yī)護(hù)人員資源不釋放的場(chǎng)景。
所以我們可以想一下，多個(gè) IO 共用的資源(處理線程)是否具備可釋放性？
2.1.3 理解IO復(fù)用
I/O的含義：在計(jì)算機(jī)領(lǐng)域常說的IO包括磁盤 IO 和網(wǎng)絡(luò) IO，我們所說的IO復(fù)用主要是指網(wǎng)絡(luò) IO ，在Linux中一切皆文件，因此網(wǎng)絡(luò)IO也經(jīng)常用文件描述符 FD 來表示。
復(fù)用的含義：那么這些文件描述符 FD 要復(fù)用什么呢？在網(wǎng)絡(luò)場(chǎng)景中復(fù)用的就是任務(wù)處理線程，所以簡(jiǎn)單理解就是多個(gè)IO共用1個(gè)處理線程。
IO復(fù)用的可行性：IO請(qǐng)求的基本操作包括read和write，由于網(wǎng)絡(luò)交互的本質(zhì)性，必然存在等待，換言之就是整個(gè)網(wǎng)絡(luò)連接中FD的讀寫是交替出現(xiàn)的，時(shí)而可讀可寫，時(shí)而空閑，所以IO復(fù)用是可用實(shí)現(xiàn)的。
綜上認(rèn)為：IO復(fù)用技術(shù)就是協(xié)調(diào)多個(gè)可釋放資源的FD交替共享任務(wù)處理線程完成通信任務(wù)，實(shí)現(xiàn)多個(gè)fd對(duì)應(yīng)1個(gè)任務(wù)處理線程的復(fù)用場(chǎng)景。
現(xiàn)實(shí)生活中IO復(fù)用就像一只邊牧管理幾百只綿羊一樣：
2.1.4 IO復(fù)用的出現(xiàn)背景
畫外音：上面的一段話可能讀起來有些繞，樸素的說法就是讓任務(wù)處理線程以更小的資源消耗來協(xié)調(diào)更多的網(wǎng)絡(luò)請(qǐng)求連接，IO復(fù)用工具也是逐漸演進(jìn)的，經(jīng)過前后對(duì)比就可以發(fā)現(xiàn)這個(gè)原則一直貫穿其中。
3. Linux的IO復(fù)用工具概覽
3.1 先驅(qū)者select
/* According to POSIX.1-2001 */
#include <sys/select.h>
/* According to earlier standards */
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
int select(int nfds, fd_set *readfds, fd_set *writefds,
fd_set *exceptfds, struct timeval *timeout);
void FD_CLR(int fd, fd_set *set);
int FD_ISSET(int fd, fd_set *set);
void FD_SET(int fd, fd_set *set);
void FD_ZERO(fd_set *set);
3.1.1 官方提示
Macro: int FD_SETSIZE
The value of this macro is the maximum number of file descriptors that a fd_set object can hold information about. On systems with a fixed maximum number, FD_SETSIZE is at least that number. On some systems, including GNU, there is no absolute limit on the number of descriptors open, but this macro still has a constant value which controls the number of bits in an fd_set; if you get a file descriptor with a value as high as FD_SETSIZE, you cannot put that descriptor into an fd_set.
3.1.2 存在的問題和客觀評(píng)價(jià)
-
可協(xié)調(diào)fd數(shù)量和數(shù)值都不超過1024 無法實(shí)現(xiàn)高并發(fā) -
使用O(n)復(fù)雜度遍歷fd數(shù)組查看fd的可讀寫性 效率低 -
涉及大量kernel和用戶態(tài)拷貝 消耗大 -
每次完成監(jiān)控需要再次重新傳入并且分事件傳入 操作冗余
3.2 繼承者epoll
-
對(duì)fd數(shù)量沒有限制(當(dāng)然這個(gè)在poll也被解決了) -
拋棄了bitmap數(shù)組實(shí)現(xiàn)了新的結(jié)構(gòu)來存儲(chǔ)多種事件類型 -
無需重復(fù)拷貝fd 隨用隨加 隨棄隨刪 -
采用事件驅(qū)動(dòng)避免輪詢查看可讀寫事件
epoll出現(xiàn)之后大大提高了并發(fā)量對(duì)于C10K問題輕松應(yīng)對(duì)，即使后續(xù)出現(xiàn)了真正的異步IO，也并沒有(暫時(shí)沒有)撼動(dòng)epoll的江湖地位。
4. 初識(shí)epoll
4.1 epoll的基礎(chǔ)API和數(shù)據(jù)結(jié)構(gòu)
//用戶數(shù)據(jù)載體
typedef union epoll_data {
void *ptr;
int fd;
uint32_t u32;
uint64_t u64;
} epoll_data_t;
//fd裝載入內(nèi)核的載體
struct epoll_event {
uint32_t events; /* Epoll events */
epoll_data_t data; /* User data variable */
};
//三板斧api
int epoll_create(int size);
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);4.2 epoll三級(jí)火箭的科班理解
-
epoll_create
該接口是在內(nèi)核區(qū)創(chuàng)建一個(gè)epoll相關(guān)的一些列結(jié)構(gòu)，并且將一個(gè)句柄fd返回給用戶態(tài)，后續(xù)的操作都是基于此fd的，參數(shù)size是告訴內(nèi)核這個(gè)結(jié)構(gòu)的元素的大小，類似于stl的vector動(dòng)態(tài)數(shù)組，如果size不合適會(huì)涉及復(fù)制擴(kuò)容，不過貌似4.1.2內(nèi)核之后size已經(jīng)沒有太大用途了； -
epoll_ctl
該接口是將fd添加/刪除于epoll_create返回的epfd中，其中epoll_event是用戶態(tài)和內(nèi)核態(tài)交互的結(jié)構(gòu)，定義了用戶態(tài)關(guān)心的事件類型和觸發(fā)時(shí)數(shù)據(jù)的載體epoll_data； -
epoll_wait
該接口是阻塞等待內(nèi)核返回的可讀寫事件，epfd還是epoll_create的返回值，events是個(gè)結(jié)構(gòu)體數(shù)組指針存儲(chǔ)epoll_event，也就是將內(nèi)核返回的待處理epoll_event結(jié)構(gòu)都存儲(chǔ)下來，maxevents告訴內(nèi)核本次返回的最大fd數(shù)量，這個(gè)和events指向的數(shù)組是相關(guān)的；
4.3 epoll三級(jí)火箭的通俗解釋
-
epoll_create場(chǎng)景
大學(xué)開學(xué)第一周，你作為班長需要幫全班同學(xué)領(lǐng)取相關(guān)物品，你在學(xué)生處告訴工作人員，我是xx學(xué)院xx專業(yè)xx班的班長，這時(shí)工作人員確定你的身份并且給了你憑證，后面辦的事情都需要用到( 也就是調(diào)用epoll_create向內(nèi)核申請(qǐng)了epfd結(jié)構(gòu)，內(nèi)核返回了epfd句柄給你使用)； -
epoll_ctl場(chǎng)景
你拿著憑證在辦事大廳開始辦事，分揀辦公室工作人員說班長你把所有需要辦理事情的同學(xué)的學(xué)生冊(cè)和需要辦理的事情都記錄下來吧，于是班長開始在每個(gè)學(xué)生手冊(cè)單獨(dú)寫對(duì)應(yīng)需要辦的事情：李明需要開實(shí)驗(yàn)室權(quán)限、孫大熊需要辦游泳卡......就這樣班長一股腦寫完并交給了工作人員( 也就是告訴內(nèi)核哪些fd需要做哪些操作)； -
epoll_wait場(chǎng)景
你拿著憑證在領(lǐng)取辦公室門前等著，這時(shí)候廣播喊xx班長你們班孫大熊的游泳卡辦好了速來領(lǐng)取、李明實(shí)驗(yàn)室權(quán)限卡辦好了速來取....還有同學(xué)的事情沒辦好，所以班長只能繼續(xù)( 也就是調(diào)用epoll_wait等待內(nèi)核反饋的可讀寫事件發(fā)生并處理)；
4.4 epoll官方demo
#define MAX_EVENTS 10
struct epoll_event ev, events[MAX_EVENTS];
int listen_sock, conn_sock, nfds, epollfd;
/* Set up listening socket, 'listen_sock' (socket(),
bind(), listen()) */
epollfd = epoll_create(10);
if(epollfd == -1) {
perror("epoll_create");
exit(EXIT_FAILURE);
}
ev.events = EPOLLIN;
ev.data.fd = listen_sock;
if(epoll_ctl(epollfd, EPOLL_CTL_ADD, listen_sock, &ev) == -1) {
perror("epoll_ctl: listen_sock");
exit(EXIT_FAILURE);
}
for(;;) {
nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
if (nfds == -1) {
perror("epoll_pwait");
exit(EXIT_FAILURE);
}
for (n = 0; n < nfds; ++n) {
if (events[n].data.fd == listen_sock) {
//主監(jiān)聽socket有新連接
conn_sock = accept(listen_sock,
(struct sockaddr *) &local, &addrlen);
if (conn_sock == -1) {
perror("accept");
exit(EXIT_FAILURE);
}
setnonblocking(conn_sock);
ev.events = EPOLLIN | EPOLLET;
ev.data.fd = conn_sock;
if (epoll_ctl(epollfd, EPOLL_CTL_ADD, conn_sock,
&ev) == -1) {
perror("epoll_ctl: conn_sock");
exit(EXIT_FAILURE);
}
} else {
//已建立連接的可讀寫句柄
do_use_fd(events[n].data.fd);
}
}
}
5. epoll的底層細(xì)節(jié)
5.1 底層數(shù)據(jù)結(jié)構(gòu)
紅黑樹節(jié)點(diǎn)定義：
#ifndef _LINUX_RBTREE_H
#define _LINUX_RBTREE_H
#include <linux/kernel.h>
#include <linux/stddef.h>
#include <linux/rcupdate.h>
struct rb_node {
unsigned long __rb_parent_color;
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */
struct rb_root {
struct rb_node *rb_node;
};
epitem定義：
struct epitem {
struct rb_node rbn;
struct list_head rdllink;
struct epitem *next;
struct epoll_filefd ffd;
int nwait;
struct list_head pwqlist;
struct eventpoll *ep;
struct list_head fllink;
struct epoll_event event;
}
eventpoll定義：
struct eventpoll {
spin_lock_t lock;
struct mutex mtx;
wait_queue_head_t wq;
wait_queue_head_t poll_wait;
struct list_head rdllist; //就緒鏈表
struct rb_root rbr; //紅黑樹根節(jié)點(diǎn)
struct epitem *ovflist;
}
5.2 底層調(diào)用過程
-
創(chuàng)建并初始化一個(gè)strut epitem類型的對(duì)象，完成該對(duì)象和被監(jiān)控事件以及epoll對(duì)象eventpoll的關(guān)聯(lián);
-
將struct epitem類型的對(duì)象加入到epoll對(duì)象eventpoll的紅黑樹中管理起來;
-
將struct epitem類型的對(duì)象加入到被監(jiān)控事件對(duì)應(yīng)的目標(biāo)文件的等待列表中，并注冊(cè)事件就緒時(shí)會(huì)調(diào)用的回調(diào)函數(shù)，在epoll中該回調(diào)函數(shù)就是ep_poll_callback();
-
ovflist主要是暫態(tài)處理，調(diào)用ep_poll_callback()回調(diào)函數(shù)的時(shí)候發(fā)現(xiàn)eventpoll的ovflist成員不等于EP_UNACTIVE_PTR，說明正在掃描rdllist鏈表，這時(shí)將就緒事件對(duì)應(yīng)的epitem加入到ovflist鏈表暫存起來，等rdllist鏈表掃描完再將ovflist鏈表中的元素移動(dòng)到rdllist鏈表；
5.3 易混淆的數(shù)據(jù)拷貝
一種廣泛流傳的錯(cuò)誤觀點(diǎn)：
epoll_wait返回時(shí)，對(duì)于就緒的事件，epoll使用的是共享內(nèi)存的方式，即用戶態(tài)和內(nèi)核態(tài)都指向了就緒鏈表，所以就避免了內(nèi)存拷貝消耗
revents = ep_item_poll(epi, &pt);//獲取就緒事件
if (revents) {
if (__put_user(revents, &uevent->events) ||
__put_user(epi->event.data, &uevent->data)) {
list_add(&epi->rdllink, head);//處理失敗則重新加入鏈表
ep_pm_stay_awake(epi);
return eventcnt ? eventcnt : -EFAULT;
}
eventcnt++;
uevent++;
if (epi->event.events & EPOLLONESHOT)
epi->event.events &= EP_PRIVATE_BITS;//EPOLLONESHOT標(biāo)記的處理
else if (!(epi->event.events & EPOLLET)) {
list_add_tail(&epi->rdllink, &ep->rdllist);//LT模式處理
ep_pm_stay_awake(epi);
}
}6.LT模式和ET模式
6.1 LT/ET的簡(jiǎn)單理解
6.2 LT/ET的深入理解
6.2.1 LT的讀寫操作
6.2.2 ET的讀寫操作
6.2.3 一道騰訊面試題
使用Linux epoll模型的LT水平觸發(fā)模式，當(dāng)socket可寫時(shí)，會(huì)不停的觸發(fā)socket可寫的事件，如何處理？
當(dāng)需要向socket寫數(shù)據(jù)時(shí)，將該socket加入到epoll等待可寫事件。接收到socket可寫事件后，調(diào)用write或send發(fā)送數(shù)據(jù)，當(dāng)數(shù)據(jù)全部寫完后， 將socket描述符移出epoll列表，這種做法需要反復(fù)添加和刪除。
向socket寫數(shù)據(jù)時(shí)直接調(diào)用send發(fā)送，當(dāng)send返回錯(cuò)誤碼EAGAIN，才將socket加入到epoll，等待可寫事件后再發(fā)送數(shù)據(jù)，全部數(shù)據(jù)發(fā)送完畢，再移出epoll模型，改進(jìn)的做法相當(dāng)于認(rèn)為socket在大部分時(shí)候是可寫的，不能寫了再讓epoll幫忙監(jiān)控。
6.2.4 ET模式的線程饑餓問題
為每個(gè)已經(jīng)準(zhǔn)備好的描述符維護(hù)一個(gè)隊(duì)列，這樣程序就可以知道哪些描述符已經(jīng)準(zhǔn)備好了但是并沒有被讀取完，然后程序定時(shí)或定量的讀取，如果讀完則移除，直到隊(duì)列為空，這樣就保證了每個(gè)fd都被讀到并且不會(huì)丟失數(shù)據(jù)。
6.2.5 EPOLLONESHOT設(shè)置
6.2.6 LT和ET的選擇
7.epoll的驚群?jiǎn)栴}
你在廣場(chǎng)喂鴿子，你只投喂了一份食物，卻引來一群鴿子爭(zhēng)搶，最終還是只有一只鴿子搶到了食物，對(duì)于其他鴿子來說是徒勞的。
8.巨人的肩膀
-
http://harlon.org/2018/04/11/networksocket5/ -
https://devarea.com/linux-io-multiplexing-select-vs-poll-vs-epoll/#.Xa0sDqqFOUk -
https://jvns.ca/blog/2017/06/03/async-io-on-linux--select--poll--and-epoll/ -
https://zhuanlan.zhihu.com/p/78510741 -
http://www.cnhalo.net/2016/07/13/linux-epoll/ -
https://www.ichenfu.com/2017/05/03/proxy-epoll-thundering-herd/ -
https://github.com/torvalds/linux/commit/df0108c5da561c66c333bb46bfe3c1fc65905898 -
https://simpleyyt.com/2017/06/25/how-ngnix-solve-thundering-herd/
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
