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

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。