实现多路复用：select、poll 与 epoll

I/O

JDK1.5 在受支持的 OS 上启用了 epoll 以替代传统的 select/poll，极大的提升了 NIO 的性能。

select()

简介

select() 调用使内核等待多个事件中的任何一个发生，并且在至少一个事件发生或者超时时返回。

int select (int __nfds, fd_set *__restrict __readfds,
		   fd_set *__restrict __writefds,
		   fd_set *__restrict __exceptfds,
		   struct timeval *__restrict __timeout);

可以看到，我们需要提供一个文件描述符数量和三个 interest sets，这三个集合分别是“读就绪”、“写就绪”和“异常”的文件描述符集合。

/* The fd_set member is required to be an array of longs.  */
typedef long int __fd_mask;

/* Some versions of <linux/posix_types.h> define this macros.  */
#undef	__NFDBITS
/* It's easier to assume 8-bit bytes than to get CHAR_BIT.  */
#define __NFDBITS	(8 * (int) sizeof (__fd_mask))
#define	__FD_ELT(d)	((d) / __NFDBITS)
#define	__FD_MASK(d)	((__fd_mask) (1UL << ((d) % __NFDBITS)))

/* fd_set for select and pselect.  */
typedef struct
  {
    /* XPG4.2 requires this member name.  Otherwise avoid the name
       from the global namespace.  */
#ifdef __USE_XOPEN
    __fd_mask fds_bits[__FD_SETSIZE / __NFDBITS];
# define __FDS_BITS(set) ((set)->fds_bits)
#else
    __fd_mask __fds_bits[__FD_SETSIZE / __NFDBITS];
# define __FDS_BITS(set) ((set)->__fds_bits)
#endif
  } fd_set;

fd_set 就是个 long 数组，总共能管理的 fd 数量大小通过 __FD_SETSIZE 限制，Linux 下是 1024，即 select 可以管 1024 个 socket 连接。使用时通过 FD_SET() 将 fd 与一个 bit 对应，即一个 bit 管一个 fd，形成一个 fd bitmap。而一个 long int 是（8 * long int 的字节大小）位 bit，所以数组大小是 1024 除以这个值，64 位系统下，数组大小就是 1024/(8*8)=16。

指针 timeout 为空则永远等待下去直到条件满足，秒数均为 0 时不等待立即返回（即 polling 轮询），其它则正常代表超时：

struct timeval
{
  __time_t tv_sec;		/* Seconds.  */
  __suseconds_t tv_usec;	/* Microseconds.  */
};

问题

select() 存在的问题：

  1. 连接数大小是固定的，通常为 1024，虽然有一些方法可以解决此限制；
  2. 由于 interest sets 会被内核修改，我们的进程需要在每次调用 select() 前都通过 FD_ZERO() 手动 reset 一下它们；
  3. 每次事件到达，内核都要遍历这三个 sets 找到那些文件描述符，效率很低；
  4. 返回后，应用程序还要遍历来确定哪些发生了事件；
  5. 内核每次都遍历所有文件描述符来检查状态。

poll()

简介

typedef unsigned long int nfds_t;

int poll (struct pollfd *__fds, nfds_t __nfds, int __timeout);

struct pollfd
{
  int fd;
  short int events;
  short int revents;
};

poll() 底层不是 bitmap 而是如上结构体的文件描述符数组。

解决的以及剩余的问题

它解决了 select() 的一部分问题：第一点，由于使用数组，这个问题已解决，第二点也解决了，关于第三点，如果 poll() 是将数组分成 result 数组和 interest 数组，则 本可以 解决一部分，比如像这样：

typedef struct 
  {
    int fd;
    short int events;
    short int revents;
  }pollfd;

extern pollfd * poll (pollfd *__fds, nfds_t __nfds, int __timeout);

就可以使应用程序少扫描一些 fd。

但是实际上，poll() 使用了结构体属性 events 和 revents 进行区分，分别表示 poller 感兴趣的和实际发生的事件，应用程序还是得扫描所有成员才能得到结果。

第四点未解决，而第五点无法避免，因为在内核来说，无论 select() 还是 poll() 都是无状态的，返回了下次就重新来过。

poll 还有其它优点：

  1. poll() 所能表示的“感兴趣事件”（short int 2 字节可以表示 16 种）比 select() 的（read、write 和 exception set 共 3 种）多。
  2. poll 数组仅紧凑地表示了感兴趣的文件描述符，并且不会破坏入参。

但是相比 select()，poll() 也有缺点，每个文件描述符 select() 只需要复制 3 个 bit，而 poll() 则是 64 bit（32+16+16），而且 poll() 本身还是有性能不可控问题，扫描工作量与 fd 数目成正比。

select() 和 poll() 存在的意义仅仅为了兼容大多数操作系统而作为 POSIX 的标准存在着。

C10K 问题

如果服务设计的连接数和连接并发不高，比如 100qps，那 select() 或 poll 足以支撑，甚至你不用考虑使用事件驱动的方式进行编程，坚持使用多线程的方式编程即可。但是如果你首先考虑的是性能，且你的服务是网络 I/O 密集型的，继续使用 select() 或 poll 的话，会极大浪费 CPU，因为同一时刻，只有很少的连接处于某种“就绪”状态，剩下的大部分文件描述符的扫描和复制都是无用功。而产生这种情况的根本原因还是上面提到的，内核在进行这两个系统调用时是无状态的，假设有 10000 个并发连接，通常，只有少数可读，但对于每次 select() / poll()，其余的 9990 个文件描述符都会被复制和扫描。

试想如果你的 interest sets 是带状态的，内核自己持有它们并增量更新 interest sets，上层的用户应用程序从内核拿到新事件即可，效率将会大大提升。

正因此，有了 Solaris 中的 /dev/poll、Linux 中的 epoll 和 FreeBSD 的 kqueue，通常服务器使用 Linux 操作系统，所以我们来研究一下 epoll。

epoll()

简介

Linux 自 2.5.44 开始提供 epoll API，epoll 可以提供高度可扩展的事件通知特性。三个 epoll 相关的系统调用如下：

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);

  • epoll_create() 创建一个 epoll 结构，该操作会在内核创建一个存储 socket fd 的数据结构（红黑树，并且有缓存），__size 预设大小，但不会影响最终的容量。

  • epoll_ctl() 可以操作 epoll 结构，具体操作 op 可以是增（EPOLL_CTL_ADD）、删（EPOLL_CTL_DEL）、改（EPOLL_CTL_MOD）一个 socket fd，event 是包含对该 fd 感兴趣的事件和用户自定义数据的 epoll_event：

    typedef union epoll_data
{
  void *ptr;
  int fd;
  uint32_t u32;
  uint64_t u64;
} epoll_data_t;

struct epoll_event
{
  uint32_t events;
  epoll_data_t data;
} __EPOLL_PACKED;

  • epoll_wait() 观察就绪 fd 链表里有没有数据，有就立即返回事件数，没有就阻塞等待。

我们可以看到，epoll 实际上是有状态的，不像 select() / poll() 那样“傻傻的”每次都要重新传入所要监听的 fd，epoll 会在内核创建一个数据结构存储 fd 供每次 select 使用，这解决了上文提到的第 5 点问题。

但其实 epoll 也有监听 fd 数量限制，默认数量比较大而已，并且可以通过 sysctl 设置 fs.epoll.max_user_watches。

工作模式

epoll 有两种工作模式（在 epollctl() 的 events 设置 EPOLLET）：

  • Level-Triggered：意味着 socket 只要一直是某种状态，无论什么时候进行 epoll_wait() 都会返回该 socket，但试想如果我某个 socket 的 I/O 时间比较长，这样在还未完成 I/O 的情况下，多次进行 epoll_wait() 都会拿到这个 fd；

  • Edge-Triggered：边缘触发，只有某个 socket 从 unreadable 变为 readable 或从 unwritable 变为 writable 时，epoll_wait 才会返回该 socket，比 Level-Triggered 更精准，但是编程需要注意不要 错过 处理数据的机会。

Java NIO 在 1.5 版本后使用 epoll() 取代了 select() / poll()，而其和 Redis 一样使用的是 epoll() 默认的 Level-Triggered 模式，Netty、Nginx 则使用的是 Linux 2.6 之后推荐的 Edge-Triggered。

image-20191212114302000

epoll 空轮询 bug

epoll 在性能方面也有缺陷， 它不支持在单个系统调用中对 interest sets 进行多次更新，比如 100 个 fd 更新状态，就必须进行 100 次 epoll_ctl() 调用，更严重的问题是，epoll 可能出现 CPU 空轮询的 bug。

所谓 epoll 空轮询就是 select() 函数被意外 wakeup，在无就绪事件时异常返回，而且不断地从 select() 的阻塞中被 wakeup，导致循环体空转：

while (true) {
    // count = 0
    int count = selector.select();
    if (count != 0) {
        // ...
    }
}

实际上，这是 Linux 系统下 poll() / epoll() 实现导致的 bug，但 Java NIO 并未完善处理它。该问题最早在 JDK 1.6 发现，随后很多版本声称解决了该问题，但实际上只是降低了该 bug 的出现频率。

具体可以查看这两个 bug：

Netty 通过调用带参 select(timeout) 方法并通过记录实际耗时来判断是否进入了空轮询，然后在判定 bug 触发后重建 Selector，即重新调用 epoll_create 创建新的 epoll 结构来解决 epoll bug。