epoll 是 Linux 下的一种 I/O 事件通知机制1——这样写的话，总让人感觉不知所云。写这个主要是因为今年的 OSH 课程有一个写高性能静态页面的网页服务器的实验。epoll 作为一种提高性能的方式被不少人拿去用，虽然理解与写 epoll 代码并不是什么容易的事情，而且最后还是会有各种各样的问题。

在介绍 epoll 之前，不如让我们来看看，epoll 到底是怎么出现的。

网页服务器与 C10K 问题

C10K 问题指同时处理一万个并发连接时的优化问题2。

起初……

最开始的时候，网页服务器处理连接的做法非常简单：accept() 阻塞在那，接收到连接之后就处理、返回数据。但这样简单的做法在多用户的情况下效果是很差的：如果我在下载一个超大的文件，其他用户的连接就根本无法被处理，这显然是无法接受的。

既然要同时处理多个连接，那 fork() 总可以吧——接收到连接后先 fork() 一下，新进程去处理当前请求，父进程继续 accept()，或者我 pthread_create() 创建新线程也行。这样确实部分解决了上一段的问题，但是创建新的进程/线程是有比较大的开销的。

既然开销大，那么我能不能在最开始的时候就先创建一些进程/线程呢？这种做法最后就变成了进程/线程池（Apache prefork 就是这样做的）。看起来，我们很好地解决了这个问题，但是……

一万个并发连接 = 一万个进程/线程？

很遗憾的事情是，我们没有一万个 CPU 核心可以来并行运行这些进程/线程。让一万个进程/线程同时保持高性能处理连接是不切实际的。

所以，我们能否让一个进程/线程同时处理多个连接？答案当然是可以的：这就是 I/O 复用。

select()

我们可以注意到，在处理 socket 文件描述符的时候，有一些操作是阻塞的：这包括了读取 (read)、写入 (write) 以及接受连接 (accept) 等等。如果我们有一种方法，能够让我们的进程知道某个文件描述符已经准备好某个操作的话，每次只要把准备好的描述符拿出来做处理就可以了，在执行这些阻塞操作的时候也就不会一直卡在那儿了。这样我们的处理流程就是：

首先由某个函数来告诉我们文件描述符准备好读/写，然后我们对那个文件描述符做短小快速的处理，最后回到那个函数，不停循环。我们不用太担心这样对性能会不会带来比较大的影响，因为网络的 I/O 相比 CPU 来讲慢得多。这样的话我们的单个进程/线程也可以处理好多个连接了。

select()3 就可以做到「通知」的作用。它使用的 fd_set 结构体（其实是一个定长的 buffer）中存储了多个描述符。描述符分成了三类——准备好读取、准备好写入、发生错误。函数原型如下。

int select(int nfds, fd_set *readfds, fd_set *writefds,
           fd_set *exceptfds, struct timeval *timeout);

看起来很好，但是 select() 仍有一些问题。

  • 描述符数量有限制。POSIX 标准允许实现自己来定义数量上限，Linux 内核也没有硬性限制，但是 glibc 有——它把 FD_SETSIZE 直接定义为了 1024。
  • 第二个问题在于 nfds 这个参数：select() 会检查 0 到 nfds - 1 在内的所有文件描述符的情况——这很 O(n)。在大量连接的情况下，我们当然希望轮询的时间复杂度越低越好。
  • select() 会改变 fd_set 结构体的内容，每次调用都要重新初始化。

poll()

poll() 是另一种 I/O 复用的函数。它和 select() 类似。

int poll(struct pollfd *fds, nfds_t nfds, int timeout);

struct pollfd {
  	int   fd;         /* file descriptor */
  	short events;     /* requested events */
  	short revents;    /* returned events */
};

这里，poll() 解决了 select() 的描述符数量和重新初始化的问题，但是 O(n) 的性能问题还是没能得到解决，所以在 Linux 中就出现了 epoll()。

epoll() 简介

epoll() 能够用 O(1) 的时间复杂度去监控文件描述符，解决了 poll() 的问题。与 select() 和 poll() 不同，它不是一个「跨 (POSIX) 平台」的解决方案，例如在 FreeBSD 中，与 epoll 相似的是 kqueue。

相比于前两者来说，epoll 也更加复杂了。它有三个系列函数：

  • epoll_create(): 创建 epoll 实例。
  • epoll_ctl(): 向 epoll 实例注册文件描述符，可以设置添加、修改、删除目标文件描述符。
  • epoll_wait(): 等待 I/O 事件。

水平触发 (LT) 与边缘触发 (ET)

这个术语总有种数电的感觉。

A bad example of level trigger

呆唯逗梓喵——一个水平触发的非典型示例

简单地说，水平触发时，只要某个文件描述符处在准备好了的状态，epoll 就会一直告诉你；边缘触发时，某个文件描述符准备好后，epoll 只会告诉你一次，或者说 epoll 只会在描述符状态变化的时候告诉你。边缘触发是 epoll 新带来的特性。

文档中举了一个例子：

  1. 某个文件描述符的读端 rfd 在 epoll 实例中注册。
  2. 有一个 pipe writer 在管道写端写入了 2 kB 数据。
  3. epoll_wait() 函数返回 rfd，标记它已经准备好读取了。
  4. Pipe reader 在管道读端读取了 1 kB 数据。（之后回到 epoll_wait()）
  5. 如果是水平触发，那么 epoll_wait() 不会阻塞（因为还能读），你可以继续愉快地读取数据；但边缘触发时就会阻塞住，因为文件描述符的状态没有发生变化。

如果使用边缘触发，那么就要将文件描述符设置为非阻塞的。因为由上一个例子可以看到，在边缘触发状态下，如果数据没有读/写完就 epoll_wait() 的话（read() 和 write() 不能保证一定能把你所指定数量字节的信息都读/写完），那么你就永远不会再知道你还可以读/写这个文件描述符了。因此为了完成读写的任务，就不得不循环 read() 或者 write()，直到最后一次确认没有东西可以再读/写了。如果文件描述符是阻塞的话，最后一次执行读写函数的时候就会卡在那里4。

文档对使用边缘触发给出的建议是：

  1. 使用非阻塞的文件描述符。
  2. 直到 read() 或者 write() 返回 EAGAIN，再等待 I/O 事件。

一般来说，边缘触发的性能更好，但是编写也更费劲一些。

epoll_event 结构中可用的事件类型

以下根据 epoll_ctl() 的文档整理，可能会有错误，所以我尽量附上了参考的链接。

  • EPOLLIN: 输入 (read) 事件。
  • EPOLLOUT: 输出 (write) 事件。
  • EPOLLRDHUP: 对方关闭连接，或者 shutdown 了写入端的事件。
    • 「在边缘触发的情况下判断对方 shutdown 连接的时候很有用」。这可以使代码更简单，否则就需要识别到 EPOLLIN 之后跑一次 read()，返回 0 后判断对方已经 shutdown 了写入端5。
  • EPOLLPRI: 文件描述符异常（接收紧急数据6）。
  • EPOLLERR: 文件描述符错误。读取端被关闭后写入端也会报这个事件。不需要特殊指定。
  • EPOLLHUP: 文件描述符被「挂断」，对方 shutdown 或关闭了连接7。
  • EPOLLET: 边缘触发。
  • EPOLLONESHOT: 当文件描述符从 epoll_wait() 中被拿出来后，就不会再被其他对 epoll_wait() 的调用中拿出来了。例如，多个线程使用同一个 epoll 实例的时候，当某个线程拿出某个文件描述符的时候，即使这个文件描述符在处理的过程中发生了事件，其他线程也不会接收到，避免了线程之间的竞争的问题。
  • EPOLLWAKEUP: 保证事件在等待/处理的时候，系统不会进入休眠状态。
  • EPOLLEXCLUSIVE: 保证一个事件发生的时候，只有一个进程/线程会被唤醒。用 EPOLLONESHOT 也能达到类似的效果，只是每次都额外多出了一个 epoll_ctl() 系统调用8。

实现网页服务器的思路与一些问题

这里没有完整的实现代码，因为我写得并不好，完美实现需要的功能是一件很困难的事情。

有限状态机

假设我们的服务器功能很简单：从用户读取一些信息（比如说 HTTP 头），经过处理后向用户返回一些信息。如果要做到快速、安全、可靠的话，我们就不得不考虑以下的问题：

  • 每一阶段的时间不能太长，否则用户的延迟会大大提升。
  • 网络并不可靠：用户可能不会一次性把数据发送过来，我们有时也没有办法一次性给用户发送所有需要的数据。如果单纯在一个状态中处理完所有的输入或输出，那么当数据很大，或者丢包率很高的情况下，单个进程/线程会花大量的时间在一个连接上，无法为其他用户提供服务了。

这样的话，我们就不得不在每次切回 epoll_wait() 时维护每个连接已有的状态（比如说接收到了哪些数据、发送了哪些数据），编程的复杂度也大大提高了。

惊群 (thundering herd)

理论上，假设我们的 CPU 有 n 个核心，我们的网页服务器在启用 n 个进程/线程的时候性能是最好的。但我们服务器的 socket 只有一个，那么很自然的想法就是把这个 socket 分享给所有进程/线程。

这没什么问题，但是比如说我们把服务器的 socket 放在了 epoll 实例中，在 accept() 的时候，一个连接可能会唤起多个进程，但是最后只有一个进程会成功，其他被唤醒的进程徒劳无功。这就是惊群现象。

以上提到的 EPOLLONESHOT 和 EPOLLEXCLUSIVE 可以部分解决这样的惊群问题，除此之外，使用 SO_REUSEPORT 设置监听的 socket，使多个 socket 共享同一个端口，也可以缓解这种问题。但是：

The best and the only scalable approach is to use recent Kernel 4.5+ and use level-triggered events with EPOLLEXCLUSIVE flag. This will ensure only one thread is woken for an event, avoid “thundering herd” issue and scale properly across multiple CPU’s.8

或许真的拿 epoll 来实现一个正确、高效的服务器，真的不是什么容易的事情啊……

这篇是当初写完网页服务器的实验之后想写的，当初写实验的时候就花了好几天查 epoll 的资料，迷迷糊糊的；这几天又查了一些资料，实话讲比原来清楚了一些，但我还是无法保证这里的每句话都是正确的。

就这样吧……

  1. https://en.wikipedia.org/wiki/Epoll ↩

  2. https://en.wikipedia.org/wiki/C10k_problem ↩

  3. 参考了 CSAPP 的 13.2 节。 ↩

  4. https://stackoverflow.com/questions/14643249/why-having-to-use-non-blocking-fd-in-a-edge-triggered-epoll-function ↩

  5. The Linux Programming Interface: A Linux and UNIX System Programming Handbook ↩

  6. https://stackoverflow.com/questions/10681624/epollpri-when-does-this-case-happen ↩

  7. https://stackoverflow.com/questions/52976152/tcp-when-is-epollhup-generated ↩

  8. https://idea.popcount.org/2017-02-20-epoll-is-fundamentally-broken-12/ ↩ ↩2