1. 写在前面
又到周六了, 不过这周有点忙新文章还没有写, 为了不跳票, 就想着把早期还不错的文章, 重新排版修改发一下, 因为当时读者很少, 现在而言完全可以当作一篇新文章( 有种狡辩的意思 )...
今天一起来学习一下高并发实现的的重要基础: I/O 复用技术 & epoll 原理 .
通过本文你将了解到以下内容:
IO 复用的概念
epoll 出现之前的 IO 复用工具
epoll 三级火箭
epoll 底层实现
ET 模式 & LT 模式
一道腾讯面试题
epoll 惊群问题
温馨提示: 技术文章涉及很多细节都会比较晦涩, 反复琢磨才能掌握.
2. 初识复用技术和 IO 复用
在了解 epoll 之前, 我们先看下复用技术的概念和 IO 复用到底在说什么?
2.1 复用概念和资源特性
2.1.1 复用的概念
复用技术 multiplexing 并不是新技术而是一种设计思想, 在通信和硬件设计中存在 频分复用, 时分复用, 波分复用, 码分复用 等, 在日常生活中复用的场景也非常多, 因此不要被专业术语所迷惑.
从本质上来说, 复用就是为了解决 有限资源和过多使用者的不平衡问题 , 从而实现最大的利用率, 处理更多的问题.
2.1.2 资源的可释放
举个例子: 不可释放场景 :ICU 病房的呼吸机作为有限资源, 病人一旦占用且在未脱离危险之前是无法放弃占用的, 因此不可能几个情况一样的病人轮流使用.
可释放场景 : 对于一些其他资源比如医护人员就可以实现对多个病人的同时监护, 理论上不存在一个病人占用医护人员资源不释放的场景.
所以我们可以想一下, 多个 IO 共用的资源 (处理线程) 是否具备可释放性?
2.1.3 理解 IO 复用
I/O 的含义: 在计算机领域常说的 IO 包括 磁盘 IO 和网络 IO , 我们所说的 IO 复用主要是指网络 IO , 在 Linux 中一切皆文件, 因此网络 IO 也经常用文件描述符 FD 来表示.
复用的含义: 那么这些文件描述符 FD 要复用什么呢? 在网络场景中复用的就是任务处理线程, 所以简单理解就是 多个 IO 共用 1 个处理线程 .
IO 复用的可行性: IO 请求的基本操作包括 read 和 write, 由于网络交互的本质性, 必然存在等待, 换言之就是整个网络连接中 FD 的读写是交替出现的, 时而可读可写, 时而空闲, 所以 IO 复用是可用实现的.
综上认为: IO 复用技术就是协调多个可释放资源的 FD 交替共享任务处理线程完成通信任务, 实现多个 fd 对应 1 个任务处理线程的复用场景 .
现实生活中 IO 复用就像一只边牧管理几百只绵羊一样:
图片来自网络: 多只绵羊共享 1 只边牧的管理
2.1.4 IO 复用的出现背景
业务需求是推动技术演进的源动力.
在网络并发量非常小的原始时期, 即使 per req per process 地处理网络请求也可以满足要求, 但是随着网络并发量的提高, 原始方式必将阻碍进步, 所以就刺激了 IO 复用机制的实现和推广.
高效 IO 复用机制要满足: 协调者消耗最少的系统资源, 最小化 FD 的等待时间, 最大化 FD 的数量, 任务处理线程最少的空闲, 多快好省完成任务等.
画外音 : 上面的一段话可能读起来有些绕, 朴素的说法就是让任务处理线程以更小的资源消耗来协调更多的网络请求连接, IO 复用工具也是逐渐演进的, 经过前后对比就可以发现这个原则一直贯穿其中.
理解了 IO 复用技术的基本概念, 我们接着来看 Linux 系统中先后出现的各种 IO 复用工具以及各自的特点, 加深理解.
3. Linux 的 IO 复用工具概览
在 Linux 中先后出现了 select,poll,epoll 等, FreeBSD 的 kqueue 也是非常优秀的 IO 复用工具, kqueue 的原理和 epoll 很类似, 本文以 Linux 环境为例, 并且不讨论过多 select 和 poll 的实现机制和细节.
3.1 先驱者 select
select 是 2000 年左右出现的, 对外的接口定义:
- /* 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 官方提示
作为第一个 IO 复用系统调用, select 使用一个宏定义函数按照 bitmap 原理填充 fd, 默认大小是 1024 个, 因此对于 fd 的数值大于 1024 都可能出现问题, 看下官方预警:
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.
简单解释一下这段话的含义:
当 fd 的 绝对数值大于 1024 时将不可控 , 因为底层的位数组的原因, 官方不建议超过 1024, 但是我们也无法控制 fd 的绝对数值大小, 之前针对这个问题做过一些调研, 结论是系统对于 fd 的分配有自己的策略, 会大概率分配到 1024 以内, 对此我并没有充分理解, 只是提及一下这个坑.
3.1.2 存在的问题和客观评价
由于底层实现方式的局限性, select 存在一些问题, 主要包括:
可协调 fd 数量和数值都不超过 1024 无法实现高并发
使用 O(n)复杂度遍历 fd 数组查看 fd 的可读写性 效率低
涉及大量 kernel 和用户态拷贝 消耗大
每次完成监控需要再次重新传入并且分事件传入 操作冗余
select 以朴素的方式实现了 IO 复用, 将并发量提高的最大 K 级, 但是对于完成这个任务的代价和灵活性都有待提高.
无论怎么样 select 作为先驱对 IO 复用有巨大的推动 , 并且指明了后续的优化方向, 不要无知地指责 select.
3.2 继承者 epoll
在 epoll 出现之前, poll 对 select 进行了改进, 但是本质上并没有太大变化, 因此我们跳过 poll 直接看 epoll.
epoll 最初在 2.5.44 内核版本出现, 后续在 2.6.x 版本中对代码进行了优化使其更加简洁, 先后面对外界的质疑在后续增加了一些设置来解决隐藏的问题, 所以 epoll 也已经有十几年的历史了.
在《Unix 网络编程》第三版 (2003 年) 还没有介绍 epoll, 因为那个时代 epoll 还没有出现, 书中只介绍了 select 和 poll,epoll 对 select 中存在的问题都逐一解决, epoll 的优势包括:
对 fd 数量没有限制(当然这个在 poll 也被解决了)
抛弃了 bitmap 数组实现了新的结构来存储多种事件类型
无需重复拷贝 fd 随用随加 随弃随删
采用事件驱动避免轮询查看可读写事件
epoll 的应用现状
:
epoll 出现之后大大提高了并发量对于 C10K 问题轻松应对, 即使后续出现了真正的异步 IO, 也并没有 (暂时没有) 撼动 epoll 的江湖地位.
因为 epoll 可以解决数万数十万的并发量, 已经可以解决现在大部分的场景了, 异步 IO 固然优异, 但是编程难度比 epoll 更大, 权衡之下 epoll 仍然富有生命力.
4. 初识 epoll
epoll 继承了 select 的风格, 留给用户的接口非常简洁, 可以说是简约而不简单, 我们一起来感受一下.
4.1 epoll 的基础 API 和数据结构
epoll 主要包括 epoll_data,epoll_event, 三个 API, 如下所示:
- // 用户数据载体
- typedef union epoll_data {
- void *ptr;
- int fd;
- uint32_t u32;
- uint64_t u64;
- } epoll_data_t;
- //fd 装载入内核的载体
- 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 三级火箭的科班理解
epoll_create
该接口是在内核区创建一个 epoll 相关的一些列结构, 并且将一个句柄 fd 返回给用户态, 后续的操作都是基于此 fd 的, 参数 size 是告诉内核这个结构的元素的大小, 类似于 stl 的 vector 动态数组, 如果 size 不合适会涉及复制扩容, 不过貌似 4.1.2 内核之后 size 已经没有太大用途了;
epoll_ctl
该接口是将 fd 添加 / 删除于 epoll_create 返回的 epfd 中, 其中 epoll_event 是用户态和内核态交互的结构, 定义了用户态关心的事件类型和触发时数据的载体 epoll_data;
epoll_wait
该接口是阻塞等待内核返回的可读写事件, epfd 还是 epoll_create 的返回值, events 是个结构体数组指针存储 epoll_event, 也就是将内核返回的待处理 epoll_event 结构都存储下来, maxevents 告诉内核本次返回的最大 fd 数量, 这个和 events 指向的数组是相关的;
其中三个 API 中贯穿了一个数据结构: epoll_event, 它可以说是用户态需监控 fd 的代言人, 后续用户程序对 fd 的操作都是基于此结构的;
4.3 epoll 三级火箭的通俗解释
可能上面的描述有些抽象, 举个现实中的例子, 来帮助大家理解:
epoll_create 场景
大学开学第一周, 你作为班长需要帮全班同学领取相关物品, 你在学生处告诉工作人员, 我是 xx 学院 xx 专业 xx 班的班长, 这时工作人员确定你的身份并且给了你凭证, 后面办的事情都需要用到(
也就是调用 epoll_create 向内核申请了 epfd 结构, 内核返回了 epfd 句柄给你使用
);
epoll_ctl 场景
你拿着凭证在办事大厅开始办事, 分拣办公室工作人员说班长你把所有需要办理事情的同学的学生册和需要办理的事情都记录下来吧, 于是班长开始在每个学生手册单独写对应需要办的事情: 李明需要开实验室权限, 孙大熊需要办游泳卡...... 就这样班长一股脑写完并交给了工作人员(
也就是告诉内核哪些 fd 需要做哪些操作
);
epoll_wait 场景
你拿着凭证在领取办公室门前等着, 这时候广播喊 xx 班长你们班孙大熊的游泳卡办好了速来领取, 李明实验室权限卡办好了速来取.... 还有同学的事情没办好, 所以班长只能继续(
也就是调用 epoll_wait 等待内核反馈的可读写事件发生并处理
);
4.4 epoll 官方 demo
通过 man epoll 可以看到官方的 demo, 虽然只有 50 行, 但是 干货满满 , 如下:
- #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) {
- // 主监听 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);
- }
- }
- }
特别注意 : 在 epoll_wait 时需要区分是主监听线程 fd 的新连接事件还是已连接事件的读写请求, 进而单独处理.
5. epoll 的底层细节
epoll 底层实现最重要的两个数据结构: epitem 和 eventpoll.
可以简单的认为 epitem 是和每个用户态监控 IO 的 fd 对应的, eventpoll 是用户态创建的管理所有被监控 fd 的结构, 我们从局部到整体, 从内到外看一下 epoll 相关的数据结构.
5.1 底层数据结构
红黑树节点定义:
- #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; // 红黑树根节点
- struct epitem *ovflist;
- }
5.2 底层调用过程
epoll_create 会创建一个类型为 struct eventpoll 的对象, 并返回一个与之对应文件描述符, 之后应用程序在用户态使用 epoll 的时候都将依靠这个文件描述符, 而在 epoll 内部也是通过该文件描述符进一步获取到 eventpoll 类型对象, 再进行对应的操作, 完成了用户态和内核态的贯穿.
epoll_ctl 底层调用 epoll_insert 实现:
创建并初始化一个 strut epitem 类型的对象, 完成该对象和被监控事件以及 epoll 对象 eventpoll 的关联;
将 struct epitem 类型的对象加入到 epoll 对象 eventpoll 的红黑树中管理起来;
将 struct epitem 类型的对象加入到被监控事件对应的目标文件的等待列表中, 并注册事件就绪时会调用的回调函数, 在 epoll 中该回调函数就是 ep_poll_callback();
ovflist 主要是暂态处理, 调用 ep_poll_callback()回调函数的时候发现 eventpoll 的 ovflist 成员不等于 EP_UNACTIVE_PTR, 说明正在扫描 rdllist 链表, 这时将就绪事件对应的 epitem 加入到 ovflist 链表暂存起来, 等 rdllist 链表扫描完再将 ovflist 链表中的元素移动到 rdllist 链表;
如图展示了红黑树, 双链表, epitem 之间的关系:
5.3 易混淆的数据拷贝
一种广泛流传的错误观点:
epoll_wait 返回时, 对于就绪的事件, epoll 使用的是共享内存的方式, 即用户态和内核态都指向了就绪链表, 所以就避免了内存拷贝消耗
共享内存? 不存在的!
关于 epoll_wait 使用共享内存的方式来加速用户态和内核态的数据交互, 避免内存拷贝的观点, 并没有得到 2.6 内核版本代码的证实, 并且关于这次拷贝的实现是这样的:
- 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 标记的处理
- else if (!(epi->event.events & EPOLLET)) {
- list_add_tail(&epi->rdllink, &ep->rdllist);//LT 模式处理
- ep_pm_stay_awake(epi);
- }
- }
6.LT 模式和 ET 模式
epoll 的两种模式是留给用户的发挥空间, 也是个重点问题.
6.1 LT/ET 的简单理解
默认采用 LT 模式, LT 支持阻塞和非阻塞套, ET 模式只支持非阻塞套接字, 其效率要高于 LT 模式, 并且 LT 模式更加安全.
LT 和 ET 模式下都可以通过 epoll_wait 方法来获取事件, LT 模式下将事件拷贝给用户程序之后, 如果没有被处理或者未处理完, 那么在下次调用时还会反馈给用户程序, 可以认为数据不会丢失会反复提醒;
ET 模式下如果没有被处理或者未处理完, 那么下次将不再通知到用户程序, 因此避免了反复被提醒, 却加强了对用户程序读写的要求;
6.2 LT/ET 的深入理解
上面的解释在网上随便找一篇都会讲到, 但是 LT 和 ET 真正使用起来, 还是存在难度的.
6.2.1 LT 的读写操作
LT 对于 read 操作比较简单, 有 read 事件就读, 读多读少都没有问题, 但是 write 就不那么容易了, 一般来说 socket 在空闲状态时发送缓冲区一定是不满的, 假如 fd 一直在监控中, 那么会一直通知写事件, 不胜其烦.
所以必须保证没有数据要发送的时候, 要把 fd 的写事件监控从 epoll 列表中删除, 需要的时候再加入回去, 如此反复.
天下没有免费的午餐, 总是无代价地提醒是不可能的, 对应 write 的过度提醒, 需要使用者随用随加, 否则将一直被提醒可写事件.
6.2.2 ET 的读写操作
fd 可读则返回可读事件, 若开发者没有把所有数据读取完毕, epoll 不会再次通知 read 事件, 也就是说如果没有全部读取所有数据, 那么导致 epoll 不会再通知该 socket 的 read 事件, 事实上一直读完很容易做到.
若发送缓冲区未满, epoll 通知 write 事件, 直到开发者填满发送缓冲区, epoll 才会在下次发送缓冲区由满变成未满时通知 write 事件.
ET 模式下只有 socket 的状态发生变化时才会通知, 也就是读取缓冲区由无数据到有数据时通知 read 事件, 发送缓冲区由满变成未满通知 write 事件.
6.2.3 一道腾讯面试题
仿佛有点蒙圈, 那来一道面试题看看:
使用 Linux epoll 模型的 LT 水平触发模式, 当 socket 可写时, 会不停的触发 socket 可写的事件, 如何处理?
确实是一道很好的问题啊! 我们来分析领略一下其中深意.
这道题目对 LT 和 ET 考察比较深入, 验证了前文说的 LT 模式 write 问题.
普通做法:
当需要向 socket 写数据时, 将该 socket 加入到 epoll 等待可写事件. 接收到 socket 可写事件后, 调用 write 或 send 发送数据, 当数据全部写完后, 将 socket 描述符移出 epoll 列表, 这种做法需要反复添加和删除.
改进做法:
向 socket 写数据时直接调用 send 发送, 当 send 返回错误码 EAGAIN, 才将 socket 加入到 epoll, 等待可写事件后再发送数据, 全部数据发送完毕, 再移出 epoll 模型, 改进的做法相当于认为 socket 在大部分时候是可写的, 不能写了再让 epoll 帮忙监控.
上面两种做法是对 LT 模式下 write 事件频繁通知的修复, 本质上 ET 模式就可以直接搞定, 并不需要用户层程序的补丁操作.
6.2.4 ET 模式的线程饥饿问题
如果某个 socket 源源不断地收到非常多的数据, 在试图读取完所有数据的过程中, 有可能会造成其他的 socket 得不到处理, 从而造成饥饿问题.
解决办法: 为每个已经准备好的描述符维护一个队列, 这样程序就可以知道哪些描述符已经准备好了但是并没有被读取完, 然后程序定时或定量的读取, 如果读完则移除, 直到队列为空, 这样就保证了每个 fd 都被读到并且不会丢失数据.
流程如图:
6.2.5 EPOLLONESHOT 设置
A 线程读完某 socket 上数据后开始处理这些数据, 此时该 socket 上又有新数据可读, B 线程被唤醒读新的数据, 造成 2 个线程同时操作一个 socket 的局面 ,EPOLLONESHOT 保证一个 socket 连接在任一时刻只被一个线程处理.
6.2.6 LT 和 ET 的选择
通过前面的对比可以看到 LT 模式比较安全并且代码编写也更清晰, 但是 ET 模式属于高速模式, 在处理大高并发场景使用得当效果更好, 具体选择什么根据自己实际需要和团队代码能力来选择.
在知乎上有关于 ET 和 LT 选择的对比, 有很多大牛在其中发表观点, 感兴趣可以前往查阅.
7.epoll 的惊群问题
如果你不知道什么是惊群效应, 想象一下:
你在广场喂鸽子, 你只投喂了一份食物, 却引来一群鸽子争抢, 最终还是只有一只鸽子抢到了食物, 对于其他鸽子来说是徒劳的.
这种想象在网络编程中同样存在.
在 2.6.18 内核中 accept 的惊群问题已经被解决了, 但是在 epoll 中仍然存在惊群问题, 表现起来就是当多个进程 / 线程调用 epoll_wait 时会阻塞等待, 当内核触发可读写事件, 所有进程 / 线程都会进行响应, 但是实际上只有一个进程 / 线程真实处理这些事件.
在 epoll 官方没有正式修复这个问题之前, Nginx 作为知名使用者采用全局锁来限制每次可监听 fd 的进程数量, 每次只有 1 个可监听的进程, 后来在 Linux 3.9 内核中增加了 SO_REUSEPORT 选项实现了内核级的负载均衡, Nginx1.9.1 版本支持了 reuseport 这个新特性, 从而解决惊群问题.
EPOLLEXCLUSIVE 是在 2016 年 Linux 4.5 内核新添加的一个 epoll 的标识, Ngnix 在 1.11.3 之后添加了 NGX_EXCLUSIVE_EVENT 选项对该特性进行支持. EPOLLEXCLUSIVE 标识会保证一个事件发生时候只有一个线程会被唤醒, 以避免多侦听下的惊群问题.
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/
来源: http://www.tuicool.com/articles/mmqmUvb