美团二面：epoll性能那么高，为什么？

朴灿烈づ我的快乐病毒、 2024-03-22 19:53 71阅读 0赞

### 说在前面 ###

在40岁老架构师 尼恩的**读者交流群**(50+)中，最近有小伙伴拿到了一线互联网企业如美团、拼多多、极兔、有赞、希音的面试资格，遇到一几个很重要的面试题：

*  说说epoll的数据结构
 *  说说epoll的实现原理
 *  协议栈如何与epoll通信？
 *  epoll线程安全如何加锁？
 *  说说ET与LT的实现
 *  ……

这里尼恩给大家做一下系统化、体系化的梳理，使得大家可以充分展示一下大家雄厚的 “技术肌肉”，**让面试官爱到 “不能自已、口水直流”**。

也一并把这个题目以及参考答案，收入咱们的 《[尼恩Java面试宝典][Java]》V88版本，供后面的小伙伴参考，提升大家的 3高 架构、设计、开发水平。

> 最新《尼恩 架构笔记》《尼恩高并发三部曲 》《尼恩Java面试宝典》 的PDF文件，请到公号【技术自由圈】获取

#### 文章目录 ####

*   *  说在前面
     *  epoll的数据结构
     *   *  多种数据结构进行决策
     *  红黑树和就绪队列的关系
     *  epoll的工作环境
     *  协议栈触发回调通知epoll的时机
     *   *  通知的时机总结
     *  从回调机制看epoll 与 select/poll的区别
     *  epoll线程安全如何加锁
     *   *  3个api做什么事情
     *  分析加锁
     *  ET与LT如何实现
     *  说在最后
     *  推荐相关阅读

### epoll的数据结构 ###

#### 多种数据结构进行决策 ####

epoll至少需要两个集合

*  所有fd的总集
 *  就绪fd的集合

那么这个总集选用什么数据结构存储呢？

我们知道，一个fd，其底层对应一个TCB。那么也就是说key=fd,val=TCB,是一个典型的kv型数据结构，对于kv型数据结构我们可以使用以下三种进行存储。

1.  hash
2.  红黑树
3.  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。

struct epitem{
        
        RB_ENTRY(epitem) rbn;
        LIST_ENTRY(epitem) rdlink;
        int rdy; //exist in list
        
        int sockfd;
        struct epoll_event event;
    };
    struct eventpoll {
        
        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]

协议栈如何与epoll模块通信

### epoll的工作环境 ###

应用程序只能通过三个api接口来操作epoll。当一个io准备就绪的时候，epoll是怎么知道io准备就绪了呢？是由协议栈将数据解析出来触发回调通知epoll的。也就是说可以把epoll的工作环境看出三部分，左边应用程序的api，中间的epoll，右边是协议栈的回调(协议栈当然不能直接操作epoll，中间的vfs在此不是重点，就直接省略vfs这一层了)。

![fe3a42ffedf44835ba8cd4048c8b042b.png][]

### 协议栈触发回调通知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和具体事件这两个参数，然后做下面两个操作

1.  通过fd找到对应的结点
2.  把结点加入到就绪队列

1、协议栈中，在三次握手完成之后，会往全连接队列中添加一个TCB结点，然后触发一个回调函数，通知到epoll里面有个EPOLLIN事件

![2575fa51d12343b0826279e406b08a0b.png][]

2、客户端发送一个数据包，协议栈接收后回复ACK，之后触发一个回调函数，通知到epoll里面有个EPOLLIN事件

![fd347f0d73e148218b2e3188b4f29ec7.png][]

3、每个连接的TCB里面都有一个sendbuf，在对端接收到数据并返回ACK以后，sendbuf就可以将这部分确认接收的数据清空，此时sendbuf里面就有剩余空间，此时触发一个回调函数，通知到epoll里面有个EPOLLOUT事件

![f1157a07ec8c4a8084f4b0a12488e130.png][]

4、当对端发送close，在接收到fin后回复ACK，此时会调用回调函数，通知到epoll有个EPOLLIN事件

![ed55bb82050d44e9ab95edbc79bb843f.png][]

5、当接收到rst标志位的时候，回复ack之后也会触发回调函数，通知epoll有一个EPOLLERR事件

![ef11bb0cf33b48968775ce77a88d84f4.png][]

#### 通知的时机总结 ####

一个有5个通知的地方

1.  三次握手完成之后，
2.  接收数据回复ACK之后，
3.  发送数据收到ACK之后，
4.  接收FIN回复ACK之后，
5.  接收RST回复ACK之后

### 从回调机制看epoll 与 select/poll的区别 ###

由于select和poll没有本质的区别，所以下面统一称为poll。

//  poll跟select类似, 其实poll就是把select三个文件描述符集合变成一个集合了。
    
    int select(int nfds, fd_set * readfds, fd_set *writefds, fd_set *exceptfds, struct timeval *timeout);
    
    int poll(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函数很像

![a1ac62df78354f2bbb823e6c03bb8224.png][]

### 分析加锁 ###

如果有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了。

![b4973161a1531340bd1869e4ee312d3b.png][]

![5993e277c70e42df82669aac3d61bb18.png][]

（真实实现代码参看：linux-2.6.24/fs/eventpoll.c文件中的**ep\_send\_events**函数）

### 说在最后 ###

Linux相关面试题，是非常常见的面试题。

以上的内容，如果大家能对答如流，如数家珍，基本上 面试官会被你 震惊到、吸引到。

最终，**让面试官爱到 “不能自已、口水直流”**。offer， 也就来了。

学习过程中，如果有啥问题，大家可以来 找 40岁老架构师尼恩交流。

### 推荐相关阅读 ###

《[滴滴太狠：分布式ID，如何达到1000Wqps？][ID_1000Wqps]》

《[腾讯太狠：40亿QQ号，给1G内存，怎么去重？][40_QQ_1G]》

《[从0开始，手写Redis][0_Redis]》

《[从0开始，手写MySQL事务管理器TM][0_MySQL_TM]》

《[从0开始，手写MySQL数据管理器DM][0_MySQL_DM]》

> 《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》PDF，请到下面公号【技术自由圈】取↓↓↓

[Java]: https://blog.csdn.net/crazymakercircle/article/details/124790425
[epoll]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/61209db2b4174dfaa78185309e087f88.png
[fe3a42ffedf44835ba8cd4048c8b042b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/6fff86e5cb154c9d8bce40aeb37a7fe2.png
[2575fa51d12343b0826279e406b08a0b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/57f89a74026d486aa827172928fc76e1.png
[fd347f0d73e148218b2e3188b4f29ec7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/dfcd71e92d26418799a7814199460e5f.png
[f1157a07ec8c4a8084f4b0a12488e130.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/618763833d914e65be765255a54ada22.png
[ed55bb82050d44e9ab95edbc79bb843f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/230ea5f2c97c4f39a7e1783e2daec96a.png
[ef11bb0cf33b48968775ce77a88d84f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/e4fa1f51ba9e4b49ba8b9cc407eb0ec3.png
[a1ac62df78354f2bbb823e6c03bb8224.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/38651f7970bd4c4e910794f496d36c44.png
[b4973161a1531340bd1869e4ee312d3b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/856babc15bdf43cd94f013ecc90c6fe4.png
[5993e277c70e42df82669aac3d61bb18.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/983b4ee68db247a2985072f37b10f07e.png
[ID_1000Wqps]: https://blog.csdn.net/crazymakercircle/article/details/131869666
[40_QQ_1G]: https://blog.csdn.net/crazymakercircle/article/details/131256900
[0_Redis]: https://blog.csdn.net/crazymakercircle/article/details/131576101
[0_MySQL_TM]: https://blog.csdn.net/crazymakercircle/article/details/131297906
[0_MySQL_DM]: https://blog.csdn.net/crazymakercircle/article/details/131531774