大家好，我是後端架構師。

最近有小夥伴拿到了一線互聯網企業如美團、拼多多、極兔、有贊、希音的面試資格，遇到一幾個很重要的面試題：

說說epoll的數據結構

說說epoll的實作原理

協定棧如何與epoll通訊？

epoll執行緒安全如何加鎖？

說說ET與LT的實作

……

這裏給大家做一下系統化、體系化的梳理，使得大家可以充分展示一下大家雄厚的「技術肌肉」， 讓面試官愛到「不能自已、口水直流」 。

epoll的數據結構

多種數據結構進行決策

epoll至少需要兩個集合

所有fd的總集

就緒fd的集合

那麽這個總集選用什麽數據結構儲存呢？

我們知道，一個fd，其底層對應一個TCB。那麽也就是說key=fd,val=TCB,是一個典型的kv型數據結構，對於kv型數據結構我們可以使用以下三種進行儲存。

hash
紅黑樹
b/b+tree

如果使用hash進行儲存，其優點是查詢速度很快，O(1)。

但是在我們呼叫epoll_create()的時候，hash底層的陣列建立多大合適呢？

如果我們有百萬的fd，那麽這個陣列越大越好，如果我們僅僅十幾個fd需要管理，在建立陣列的時候，太大的空間就很浪費。而這個fd我們又不能預先知道有多少，所以hash是不合適的。

b/b+tree是多叉樹，一個結點可以存多個key，主要是用於降低層高，用於磁盤索引的，所以在我們這個記憶體場景下也是不適合的。

在記憶體索引的場景下我們一般使用紅黑樹來作為首選的數據結構，首先紅黑樹的尋找速度很快,O(log(N))。其次在呼叫epoll_create()的時候，只需要建立一個紅黑樹樹根即可，無需浪費額外的空間。

那麽就緒集合用什麽數據結構呢，首先就緒集合不是以尋找為主的，就緒集合的作用是將裏面的元素拷貝給使用者進行處理，所以集合裏的元素沒有優先級，那麽就可以采用線性的數據結構，使用佇列來儲存，先進先出，先就緒的先處理。

所有fd的總集 -----> 紅黑樹

就緒fd的集合 -----> 佇列

紅黑樹和就緒佇列的關系

紅黑樹的結點和就緒佇列的結點的同一個節點，所謂的加入就緒佇列，就是將結點的前後指標聯系到一起。所以就緒了不是將紅黑樹結點delete掉然後加入佇列。他們是同一個結點，不需要delete。

structepitem{ RB_ENTRY(epitem) rbn; LIST_ENTRY(epitem) rdlink; int rdy; //exist in list int sockfd; structepoll_eventevent; }; structeventpoll { ep_rb_tree rbr; int rbcnt; LIST_HEAD( ,epitem) rdlist; int rdnum; int waiting; pthread_mutex_t mtx; //rbtree update pthread_spinlock_t lock; //rdlist update pthread_cond_t cond; //block for event pthread_mutex_t cdmtx; //mutex for cond };

協定棧如何與epoll模組通訊

epoll的工作環境

應用程式只能透過三個 api介面來操作epoll。當一個io準備就緒的時候，epoll是怎麽知道io準備就緒了呢？是由協定棧將數據解析出來觸發回呼通知epoll的。也就是說可以把epoll的工作環境看出三部份，左邊應用程式的api，中間的epoll，右邊是協定棧的回呼(協定棧當然不能直接操作epoll，中間的vfs在此不是重點，就直接省略vfs這一層了)。

協定棧觸發回呼通知epoll的時機

socket有兩類，一類是監聽listenfd，一類是客戶端clientfd。對於sockfd而言，我們一般比較關註EPOLLIN和EPOLLOUT這兩個事件，所以如果是listenfd，我們通常的做法就是accept。對於clientfd來說，如果可讀我們就recv，如果可寫我們就send。

協定棧將數據解析出來觸發回呼通知epoll。epoll是怎麽知道哪個io就緒了呢？我們從ip頭可以解析出源ip，目的ip和協定，從tcp頭可以解析出源埠和目的埠，此時五元組就湊齊了。socket fd --- < 源IP地址 , 源埠 , 目的IP地址 , 目的埠 , 協定 > 一個fd就是一個五元組，知道了fd，我們就能從紅黑樹中找到對應的結點。

那麽這個回呼函式做什麽事情呢？我們傳入fd和具體事件這兩個參數，然後做下面兩個操作

透過fd找到對應的結點
把結點加入到就緒佇列

1、協定棧中，在三次握手完成之後，會往全連線佇列中添加一個TCB結點，然後觸發一個回呼函式，通知到epoll裏面有個 EPOLL IN事件

2、客戶端發送一個封包，協定棧接收後回復ACK，之後觸發一個回呼函式，通知到epoll裏面有個EPOLLIN事件

3、每個連線的TCB裏面都有一個sendbuf，在對端接收到數據並返回ACK以後，sendbuf就可以將這部份確認接收的數據清空，此時sendbuf裏面就有剩余空間，此時觸發一個回呼函式，通知到epoll裏面有個EPOLLOUT事件

4、當對端發送close，在接收到fin後回復ACK，此時會呼叫回呼函式，通知到epoll有個EPOLLIN事件

5、當接收到rst標誌位的時候，回復ack之後也會觸發回呼函式，通知epoll有一個EPOLLERR事件

通知的時機總結

一個有5個通知的地方

三次握手完成之後
接收數據回復ACK之後
發送數據收到ACK之後
接收FIN回復ACK之後
接收RST回復ACK之後

從回呼機制看epoll 與 select/poll的區別

由於select和poll沒有本質的區別，所以下面統一稱為poll。

// poll跟select類似, 其實poll就是把select三個檔描述符集合變成一個集合了。 intselect(int nfds, fd_set * readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout); intpoll(struct pollfd *fds, nfds_t nfds, int timeout);

我們看到每次呼叫poll，都需要把總集fds拷貝到內核態，檢測完之後，再有內核態拷貝的使用者態，這就是poll。而epoll不是這樣，epoll只要有新的io就呼叫epoll_ctl()加入到紅黑樹裏面，一旦有觸發就用epoll_wait()將有事件的結點帶出來，可以看到他們的第一個區別：poll總是拷貝總集，如果有100w個fd，只有兩三個就緒呢？這會造成大量資源浪費；而epoll總是將需要拷貝的東西進行拷貝，沒有浪費。

第二個區別：我們從上面知道了epoll的事件都是由協定棧進行回呼然後加入到就緒佇列的，而poll呢？內核如何檢測poll的io是否就緒？只能透過遍歷的方法判斷，所以poll檢測io透過遍歷的方法也是比較慢的。

所以兩者的區別：

select/poll需要把總集copy到內核，而epoll不用

實作原理上面，select/poll 需要迴圈遍歷總集是否有就緒，而epoll是那個結點就緒了就加入就緒佇列裏面。

註意：poll不一定就比epoll慢，在io量小的情況下，poll是比epoll快的，而在大io量下，epoll絕對是有主導地位的。至於有多少個io才算多，其實也很難說，一般認為500或者1024為分界點。

epoll執行緒安全如何加鎖

3個api做什麽事情

epoll_create() ===】建立紅黑樹的根節點

epoll_ctl() ===】add,del,mod 增加、刪除、修改結點

epoll_wait() ===】把就緒佇列的結點copy到使用者態放到events裏面，跟recv函式很像

分析加鎖

如果有3個執行緒同時操作epoll，有哪些地方需要加鎖？我們使用者層面一共就只有3個api可以使用：

如果同時呼叫 epoll_create() ，那就是建立三顆紅黑樹，沒有涉及到資源競爭，沒有關系。

如果同時呼叫 epoll_ctl() ，對同一顆紅黑樹進行，增刪改，這就涉及到資源競爭需要加鎖了，此時我們對整棵樹進行加鎖。

如果同時呼叫epoll_wait() ，其操作的是就緒佇列，所以需要對就緒佇列進行加鎖。

我們要扣住epoll的工作環境，在應用程式呼叫 epoll_ctl() ，協定棧會不會有回呼操作紅黑樹結點？呼叫epoll_wait() copy出來的時候，協定棧會不會操作操作紅黑樹結點加入就緒佇列？綜上所述：

epoll_ctl() 對紅黑樹加鎖 epoll_wait()對就緒佇列加鎖回呼函式() 對紅黑樹加鎖,對就緒佇列加鎖

那麽紅黑樹加什麽鎖，就緒佇列加什麽鎖呢？

對於紅黑樹這種節點比較多的時候，采用互斥鎖來加鎖。

就緒佇列就跟生產者消費者一樣，結點是從協定棧回呼函式來生產的，消費是epoll_wait()來消費。那麽對於佇列而言，用自旋鎖（對於佇列而言，插入刪除比較簡單，cpu自旋等待比讓出的成本更低，所以用自旋鎖）。

ET與LT如何實作

ET邊沿觸發，只觸發一次

LT水平觸發，如果沒有讀完就一直觸發

程式碼如何實作ET和LT的效果呢？水平觸發和邊沿觸發不是故意設計出來的，這是自然而然，水到渠成的功能。水平觸發和邊沿觸發程式碼只需要改一點點就能實作。從協定棧檢測到接收數據，就呼叫一次回呼，這就是ET，接收到數據，呼叫一次回呼。而LT水平觸發，檢測到recvbuf裏面有數據就呼叫回呼。所以ET和LT就是在使用回呼的次數上面的差異。

那麽具體如何實作呢？協定棧流程裏面觸發回呼，是天然的符合ET只觸發一次的。那麽如果是LT，在recv之後，如果緩沖區還有數據那麽加入到就緒佇列。那麽如果是LT，在send之後，如果緩沖區還有空間那麽加入到就緒佇列。那麽這樣就能實作LT了。