web服务的高并发性能指标可以通过QPS（Query per second）来衡量，QPS指每秒处理请求数，可用（并发数/一般响应时间）来计算

网络I/O过程涉及到应用进程以及linux内核两个对象，分为两个阶段

数据准备：通常涉及等待数据从网络中到达。当所等待分组到达时，它被复制到内核中的某个缓冲区
数据拷贝：把数据从内核缓冲区复制到应用进程缓冲区

五种IO模型分类：

	阻塞	非阻塞
同步	阻塞IO	非阻塞IO，IO多路复用，信号驱动IO
异步IO		异步IO

五种IO模型

阻塞式I/O

进程调用recvfrom，直到数据包到达且被复制到应用程序的缓冲区或发生错误才返回。最常见的错误是系统调用信号被中断。我们称进程在从调用recvfrom开始到返回的整段时间内是阻塞的。

BIO，通过多线程提高并发能力,解决串行问题。

当一个read操作发生时，它会经历两个阶段： 1 等待数据准备 (Waiting for the data to be ready) 2 将数据从内核拷贝到进程中 (Copying the data from the kernel to the process)

非阻塞式I/O

进程轮询数据准备的状态，如果没准备好，则立即返回错误，如果准备好并且拷贝完成，则返回成功

NIO，轮询占用CPU效率,一般很少直接使用这种模型，而是在其他I/O模型中使用非阻塞I/O这一特性

多路复用I/O

select/poll/epoll模型，进程调用select/poll，阻塞等待套接字变为可读。当select返回套接字可读这一条件时，进程调用recvfrom把所读数据复制到应用进程缓冲区。

IO多路复用，使用select函数进行I/O请求和同步阻塞模型没有太大的区别，甚至还多了添加监视socket，以及调用select函数的额外操作，效率更差。但是使用select以后最大的优势是用户可以在一个线程内同时处理多个socket的I/O请求。用户可以注册多个socket，然后不断地调用select读取被激活的socket，即可达到在同一个线程内同时处理多个I/O请求的目的。而在同步阻塞模型中，必须通过多线程的方式才能达到这个目的。

调用select/poll该方法由一个用户态线程负责轮询多个socket,直到某个阶段1的数据就绪,再通知实际的用户线程执行阶段2的拷贝。通过一个专职的用户态线程执行非阻塞I/O轮询,模拟实现了阶段一的异步化。

信号驱动式I/O

进程向系统注册感兴趣的信号，并立即返回，当数据准备完成的信号触发时，系统通知进程，进程调用recvfrom把所读数据复制到应用程序缓冲区。

信号驱动，在一个tcp连接的生命周期内，有大量的信号需要监听，并且信号目的难以区分，使得对于socket几乎无用，在udp服务程序中可用。

异步I/O

进程调用系统函数，并告诉内核当整个操作完成时如何通知进程。该系统调用立即返回，而且在等待I/O完成期间，进程不被阻塞。当数据准备好，并且复制到应用进程缓冲区后，内核才会产生这个通知。

AIO，需要底层操作系统支持，而linux系统并不完全支持异步，windows提供了IOCP的接口支持异步。

blocking IO，non-blocking IO，IO multiplexing都属于synchronous IO。有人可能会说，non-blocking IO并没有被block啊。这里有个非常“狡猾”的地方，定义中所指的”IO operation”是指真实的IO操作，就是例子中的recvfrom这个system call。non-blocking IO在执行recvfrom这个system call的时候，如果kernel的数据没有准备好，这时候不会block进程。但是，当kernel中数据准备好的时候，recvfrom会将数据从kernel拷贝到用户内存中，这个时候进程是被block了，在这段时间内，进程是被block的。而asynchronous IO则不一样，当进程发起IO 操作之后，就直接返回再也不理睬了，直到kernel发送一个信号，告诉进程说IO完成。在这整个过程中，进程完全没有被block。

可以看到，尽管阻塞式I/O、非阻塞式I/O、多路复用I/O、信号驱动式I/O在第一阶段的处理不同，但在数据拷贝阶段都处于同步阻塞等待状态，因此可以看作是同步I/O的一种，这里的同步指的是recvfrom这个系统调用。

对比select poll epoll

	最大连接数最大文件描述符限制	时间复杂度	处理机制	性能问题
select	32bit 为 1024 , 64bit 为 2048	O(n) 仅知道有I/O事件发生，却不知哪几个流，只会无差异轮询所有流，找出能读/写数据的流进行操作。同时处理的流越多，无差别轮询时间越长	轮询	FD的增加会造成遍历速度慢的线性下降性能问题
poll	没有基于链表来存储	O(n) poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个fd对应的设备状态	轮询
epoll	没有	O(1)	I/O通知机制	根据每个fd上的callback函数来实现的，只有活跃的socket才会主动调用callback，所以在活跃socket较少的情况下，使用epoll没有前面两者的线性下降的性能问题，但是所有socket都很活跃的情况下，可能会有性能问题

共同点：

select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。

select和poll缺点：

对socket进行扫描时是线性扫描，即采用轮询的方法，效率较低，经历了多次无谓的遍历。
需要维护一个用来存放大量fd的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大

select和poll不同

对于select有最大连接数限制，poll基于链表
poll还有一个特点是：如果报告了fd后，没有被处理，那么下次poll时会再次报告该fd。
poll使用pollfd结构而非select的fd_set结构。
1
2
3
4
5
struct pollfd { int fd; short events; short revents; };
管理多个描述符也是进行轮询，根据描述符的状态进行处理，但poll无最大文件描述符数量的限制

epoll

解决三个问题

epoll提供了三个函数

epoll_create是创建一个epoll句柄；
epoll_ctl是注册要监听的事件类型
1. 遍历内核事件表，看该描述符是否在内核事件表中。
2. 判断所要做的操作：插入、删除或是修改
3. 根据操作做相应处理
每次注册新的事件到epoll句柄中时（在epoll_ctl中指定EPOLL_CTL_ADD），会把所有的fd拷贝进内核，而不是在epoll_wait的时候重复拷贝。epoll保证了每个fd在整个过程中只会拷贝一次。

在插入的时候，对相应的描述符注册了回调函数，即当该描述符上有数据就绪时，自动调用回调函数将该描述符加入就绪队列，不需要轮询，解决上面select/poll需要轮询的问题
epoll_wait则是等待事件的产生。

一个进程调用 epoll_wait()后，如果当前还没有任何事件发生，需要让当前进程挂起等待放到wq(等待队列)，当 epoll 实例监视的文件上有事件发生后，需要唤醒 wq上的进程去继续执行用户态的业务逻辑。之所以要用一个等待队列来维护关注这个 epoll 的进程，是因为有时候调用 epoll_wait()的不只一个进程，当多个进程都在关注同一个 epoll 实例时，休眠的进程们通过这个等待队列就可以逐个被唤醒了。

不断查看就绪队列（rdllist 红黑树链表）中有没有fd，如果没有就一直检查、直到超时。如果有就绪fd，就将就绪fd通知给用户。

epoll其支持fd上限是最大可以打开文件的数目，一般远大于2048。1GB内存机器大约10万左右，具体数目可查看 cat /proc/sys/fs/file-max，这数目和系统内存关系很大。

对比水平触发 ( level trigger )，边缘触发 ( edge trigger )

水平触发(LT)和边缘触发(ET)是 epoll_wait 的 2 种工作模式

ET模式是高效模式，当有读事件到来变化才触发, 当缓冲区可写才触发。

就绪描述符只通知用户一次，如果用户没做处理内核将不再进行通知；当为ET模式时，上边我们提到就绪描述符是用链表组织的，因此只需将就绪部分断链发给用户
LT模式比较稳定，只要可读 (读缓冲区有数据) ,可写 (写缓冲区未满) 就一直可以拿到事件，轮询

如果用户没有处理就绪的描述符，内核会不断通知。在LT模式下，用户没有处理就绪描述符时，内核会再次将未处理的就绪描述符加入到就绪队列中重复提醒用户空间。

怎样才会被epoll 监视

只有底层驱动实现了 file_operations 中 poll 函数的文件类型才可以被 epoll 监视！socket 类型的文件驱动是实现了 poll 函数的，因此才可以被 epoll 监视。struct file_operations 声明位置是在 include/linux/fs.h 中。

惊群

多个进程等待在 wq 上，事件触发后所有进程都被唤醒，但只有其中 1 个进程能够成功继续执行的现象。其他被白白唤起的进程等于做了无用功，无故上下文切换，可能会造成系统负载过高的问题。

为了解决 epoll 惊群，内核后续的高版本又提供了 EPOLLEXCLUSIVE 选项和 SO_REUSEPORT 选项，

EPOLLEXCLUSIVE 是在唤起进程阶段起作用，只唤起排在队列最前面的 1 个进程，不够均衡
SO_REUSEPORT 是在分配连接时起作用，相当于每个进程自己都有一个独立的 epoll 实例，内核来决策把连接分配给哪个 epoll

什么是 epitem

epitem 是 epoll 中很重要的一种数据结构，是红黑树和 rdllist 的基本组成元素。需要监听的文件和事件信息，都被包装在 epitem 结构里。

struct epitem {
    struct rb_node rbn;  // 用于加入红黑树
    struct list_head rdllink; // 用于加入rdllist
    struct epoll_filefd ffd; // 包含被监视文件的文件指针和fd信息
    struct list_head pwqlist; // poll等待队列
    struct eventpoll *ep; // 所属的epoll实例
    struct epoll_event event;  // 关注的事件
    /* 其他成员省略 */
};

使用红黑树的目的

用来维护一个 epoll 实例中所有的 epitem。

用户态调用 epoll_ctl()来操作 epoll 的监视文件时，需要增、删、改、查等动作有着比较高的效率。尤其是当 epoll 监视的文件数量达到百万级的时候，选用不同的数据结构带来的效率差异可能非常大。

ep->poll_wait 的作用

ep->poll_wait 是 epoll 实例中另一个等待队列。当被监视的文件是一个 epoll 类型时，需要用这个等待队列来处理递归唤醒。

epoll 也是一种文件类型，其底层驱动也实现了 file_operations 中的 poll 函数，因此一个 epoll 类型的 fd 可以被其他 epoll 实例监视。而 epoll 类型的 fd 只会有“读就绪”的事件。当 epoll 所监视的非 epoll 类型文件有“读就绪”事件时，当前 epoll 也会进入“读就绪”状态。

因此如果一个 epoll 实例监视了另一个 epoll 就会出现递归。

epollfd1 监视了 2 个“非 epoll”类型的 fd
epollfd2 监视了 epollfd1 和 2 个“非 epoll”类型的 fd

如果 epollfd1 所监视的 2 个 fd 中有可读事件触发，fd 的 ep_poll_callback 回调函数会触发将 fd 放到 epollfd1 的 rdllist 中。此时 epollfd1 本身的可读事件也会触发，就需要从 epollfd1 的 poll_wait 等待队列中找到 epollfd2，调用 epollfd1 的 ep_poll_callback(将 epollfd1 放到 epollfd2 的 rdllist 中)。因此 ep->poll_wait 是用来处理 epoll 间嵌套监视的情况的。

ep->rdllist 的作用是什么

epoll 实例中包含就绪事件的 fd 组成的链表。

通过扫描 ep->rdllist 链表，内核可以轻松获取当前有事件触发的 fd。而不是像 select()/poll() 那样全量扫描所有被监视的 fd，再从中找出有事件就绪的。因此可以说这一点决定了 epoll 的性能是远高于 select/poll 的。

为什么 epoll 中事件就绪的 fd 会“主动”跑到 rdllist 中去，而不用全量扫描就能找到它们呢？ 这是因为每当调用 epoll_ctl 新增一个被监视的 fd 时，都会注册一下这个 fd 的回调函数 ep_poll_callback， 当网卡收到数据包会触发一个中断，中断处理函数再回调 ep_poll_callback 将这个 fd 所属的epitem添加至 epoll 实例中的 rdllist 中。

ep->ovflist 的作用是什么

在rdllist 被占用时，用来在不持有 ep->lock 的情况下收集有就绪事件的 fd

当 epoll 上已经有了一些就绪事件的时候，内核需要扫描 rdllist 将就绪的 fd 返回给用户态。这一步通过 ep_scan_ready_list 函数来实现。其中 sproc 是一个回调函数(也就是 ep_send_events_proc 函数)，来处理数据从内核态到用户态的复制。

/**
 * ep_scan_ready_list - Scans the ready list in a way that makes possible for the scan code, to call f_op->poll(). Also allows for O(NumReady) performance.
 * @ep: Pointer to the epoll private data structure.
 * @sproc: Pointer to the scan callback.
 * @priv: Private opaque data passed to the @sproc callback.
 * Returns: The same integer error code returned by the @sproc callback.
 */
static int ep_scan_ready_list(struct eventpoll *ep,
                  int (*sproc)(struct eventpoll *,
                       struct list_head *, void *),
                  void *priv)

dllist 链表业务非常繁忙（epoll 增加监视文件、修改监视文件、有事件触发…等情况都需要操作 rdllist)，所以在复制数据到用户空间时，加了一个 ep->mtx 互斥锁来保护 epoll 自身数据结构线程安全，此时其他执行流程里有争抢 ep->mtx 的操作都会因命中 ep->mtx 进入休眠。

但加锁期间很可能有新事件源源不断地产生，进而调用 ep_poll_callback(ep_poll_callback 不用争抢 ep->mtx 所以不会休眠)，新触发的事件需要一个地方来收集，不然就丢事件了。这个用来临时收集新事件的链表就是 ovflist

还有个 txlist 链表，这个链表用来最后向用户态复制数据，rdllist 要先把自己的数据全部转移到 txlist，然后 rdllist 自己被清空。

ep_send_events_proc 遍历 txlist 处理向用户空间复制，复制成功后如果是水平触发(LT)还要把这个事件还回 rdllist，等待下一次 epoll_wait 来获取它。ovflist 上的 fd 会合入 rdllist 上等待下一次扫描；如果 txlist 上的 fd 没有处理完，最后也会合入 rdllist。

epitem->pwqlist 队列的作用是什么

保存epitem 的 poll 等待队列，pwdlist 就是跟 ep_poll_callback 注册相关的。

当调用 epoll_ctl()新增一个监视文件后，内核会为这个 epitem 创建一个 eppoll_entry 对象，通过 eppoll_entry->wait_queue_t->wait_queue_func_t 来设置 ep_poll_callback。

pwqlist、epitem、fd、epoll_entry、ep_poll_callback 间的关系是这样：

pwdlist 为什么要做成一个队列呢，直接设置成 eppoll_entry 对象不就行了吗？实际上不同文件类型实现 file_operations->poll 用到等待队列数量可能不同。虽然大多数都是 1 个，但也有例外。比如“scullpipe”类型的文件就用到了 2 个等待队列。

epmutex、ep->mtx、ep->lock 3 把锁的区别是

epmutex 是一个全局互斥锁，epoll 中一共只有 3 个地方用到这把锁。分别是 ep_free() 销毁一个 epoll 实例时、eventpoll_release_file() 清理从 epoll 中已经关闭的文件时、epoll_ctl() 时避免 epoll 间嵌套调用时形成死锁。我的理解是 epmutex 的锁粒度最大，用来处理跨 epoll 实例级别的同步操作。
ep->mtx 是一个 epoll 内部的互斥锁，在 ep_scan_ready_list() 扫描就绪列表、eventpoll_release_file() 中执行 ep_remove()删除一个被监视文件、ep_loop_check_proc()检查 epoll 是否有循环嵌套或过深嵌套、还有 epoll_ctl() 操作被监视文件增删改等处有使用。可以看出上述的函数里都会涉及对 epoll 实例中 rdllist 或红黑树的访问，因此我的理解是 ep->mtx 是一个 epoll 实例内的互斥锁，用来保护 epoll 实例内部的数据结构的线程安全。
ep->lock 是一个 epoll 实例内部的自旋锁，用来保护 ep->rdllist 的线程安全。自旋锁的特点是得不到锁时不会引起进程休眠，所以在 ep_poll_callback 中只能使用 ep->lock，否则就会丢事件。

高并发I/O