基础概念

Socket

套接字。对网络中不同主机上的应用程序之间进行双向通信的端点的抽象。
例子：客户端将数据通过网线发送到服务端，客户端发送数据需要一个出口，服务端接收数据需要一个入口，这两个"口子"就是Socket

FD：file descriptor

文件描述符，非负整数。“一切皆文件”，linux中的一切资源都可以通过文件的方式访问和管理。而FD就类似文件的索引（符号），指向某个资源，内核（kernel）利用FD来访问和管理资源。

什么是IO多路复用

  • IO多路复用是一种同步IO模型，实现一个线程可以监视多个文件句柄；
  • 一旦某个文件句柄就绪，就能够通知应用程序进行相应的读写操作；
  • 没有文件句柄就绪就会阻塞应用程序，交出CPU；

多路指网络连接，复用指的是同一个线程。

为什么有IO多路复用机制

没有IO多路复用机制时，有BIO、NIO两种实现方式，但它们都有一些问题

同步阻塞（BIO）

1、服务端采用单线程，当 accept 一个请求后，在 recv 或 send 调用阻塞时，将无法 accept 其他请求（必须等上一个请求处理 recv 或 send 完 ）（无法处理并发）

// 伪代码描述
while (true) {
	// accept阻塞
    client_fd = accept(listen_fd);
    fds.append(client_fd);
    for (fd in fds) {
    	// recv阻塞（会影响上面的accept）
        if (recv(fd)) {
        	// logic
        }
    }
}

2、服务端采用多线程，当 accept 一个请求后，开启线程进行 recv，可以完成并发处理，但随着请求数增加需要增加系统线程，大量的线程占用很大的内存空间，并且线程切换会带来很大的开销，10000个线程真正发生读写实际的线程数不会超过20%，每次accept都开一个线程也是一种资源浪费。

// 伪代码描述
while(true) {
  // accept阻塞
  client_fd = accept(listen_fd)
  // 开启线程read数据（fd增多导致线程数增多）
  new Thread func() {
    // recv阻塞（多线程不影响上面的accept）
    if (recv(fd)) {
      // logic
    }
  }  
}

同步非阻塞（NIO）

服务器端当 accept 一个请求后，加入 fds 集合，每次轮询一遍 fds 集合 recv (非阻塞)数据，没有数据则立即返回错误，每次轮询所有 fd （包括没有发生读写实际的 fd）会很浪费 CPU。

// 伪代码描述
while(true) {
  // accept非阻塞（cpu一直忙轮询）
  client_fd = accept(listen_fd)
  if (client_fd != null) {
    // 有人连接
    fds.append(client_fd)
  } else {
    // 无人连接
  }  
  for (fd in fds) {
    // recv非阻塞
    setNonblocking(client_fd)
    // recv 为非阻塞命令
    if (len = recv(fd) && len > 0) {
      // 有读写数据
      // logic
    } else {
       无读写数据
    }
  }  
}

IO多路复用

服务器端采用单线程通过 select/poll/epoll 等系统调用获取 fd 列表，遍历有事件的 fd 进行accept/recv/send ，使其能支持更多的并发连接请求。

// 伪代码描述
while(true) {
  // 通过内核获取有读写事件发生的fd，只要有一个则返回，无则阻塞
  // 整个过程只在调用select、poll、epoll这些调用的时候才会阻塞，accept/recv是不会阻塞
  for (fd in select(fds)) {
    if (fd == listen_fd) {
        client_fd = accept(listen_fd)
        fds.append(client_fd)
    } elseif (len = recv(fd) && len != -1) { 
      // logic
    }
  }  
}

IO多路复用的三种实现

select

基本概念

将socket是否就绪检查逻辑下沉到操作系统层面，避免大量的系统调用。告诉你有事件就绪了，但是没告诉你具体是哪个FD。所以select具有O(n)的无差别轮训复杂度。

调用过程

image-1663074040421

  1. 使用copy_from_user从用户空间拷贝fd_set到内核空间
  2. 注册回调函数__pollwait
  3. 遍历所有fd，调用其对应的poll方法（对于socket，这个poll方法是sock_poll，sock_poll根据情况会调用到tcp_poll,udp_poll或者datagram_poll）
  4. 以tcp_poll为例，其核心实现就是__pollwait，也就是上面注册的回调函数。
  5. __pollwait的主要工作就是把current（当前进程）挂到设备的等待队列中，不同的设备有不同的等待队列，对于tcp_poll来说，其等待队列是sk->sk_sleep（注意把进程挂到等待队列中并不代表进程已经睡眠了）。在设备收到一条消息（网络设备）或填写完文件数据（磁盘设备）后，会唤醒设备等待队列上睡眠的进程，这时current便被唤醒了。
  6. poll方法返回时会返回一个描述读写操作是否就绪的mask掩码，根据这个mask掩码给fd_set赋值。
  7. 如果遍历完所有的fd，还没有返回一个可读写的mask掩码，则会调用schedule_timeout是调用select的进程（也就是current）进入睡眠。当设备驱动发生自身资源可读写后，会唤醒其等待队列上睡眠的进程。如果超过一定的超时时间（schedule_timeout指定），还是没人唤醒，则调用select的进程会重新被唤醒获得CPU，进而重新遍历fd，判断有没有就绪的fd。
  8. 把fd_set从内核空间拷贝到用户空间。

select函数接口

#include <sys/select.h>
#include <sys/time.h>

#define FD_SETSIZE 1024
#define NFDBITS (8 * sizeof(unsigned long))
#define __FDSET_LONGS (FD_SETSIZE/NFDBITS)

// 数据结构 (bitmap)
typedef struct {
    unsigned long fds_bits[__FDSET_LONGS];
} fd_set;

// API
int select(
    int max_fd, 
    fd_set *readset, 
    fd_set *writeset, 
    fd_set *exceptset, 
    struct timeval *timeout
)                              // 返回值就绪描述符的数目

FD_ZERO(int fd, fd_set* fds)   // 清空集合
FD_SET(int fd, fd_set* fds)    // 将给定的描述符加入集合
FD_ISSET(int fd, fd_set* fds)  // 判断指定描述符是否在集合中 
FD_CLR(int fd, fd_set* fds)    // 将给定的描述符从文件中删除

使用示例

int main() {
  /*
   * 这里进行一些初始化的设置，
   * 包括socket建立，地址的设置等,
   */

  fd_set read_fs, write_fs;
  struct timeval timeout;
  int max = 0;  // 用于记录最大的fd，在轮询中时刻更新即可

  // 初始化比特位
  FD_ZERO(&read_fs);
  FD_ZERO(&write_fs);

  int nfds = 0; // 记录就绪的事件，可以减少遍历的次数
  while (1) {
    // 阻塞获取
    // 每次需要把fd从用户态拷贝到内核态
    nfds = select(max + 1, &read_fd, &write_fd, NULL, &timeout);
    // 每次需要遍历所有fd，判断有无读写事件发生
    for (int i = 0; i <= max && nfds; ++i) {
      if (i == listenfd) {
         --nfds;
         // 这里处理accept事件
         FD_SET(i, &read_fd);//将客户端socket加入到集合中
      }
      if (FD_ISSET(i, &read_fd)) {
        --nfds;
        // 这里处理read事件
      }
      if (FD_ISSET(i, &write_fd)) {
         --nfds;
        // 这里处理write事件
      }
    }
  }

select的优点

不需要每个FD都进行一次系统调用，解决频繁的用户态和内核态切换的问题

select的缺点

  1. 每个进程所打开的FD是有限制的，通过FD_SETSIZE设置，默认为1024；
  2. 每次调用select都需要把FD集合从用户态拷贝到内核态，这个开销在FD很多时会很大；

需要维护一个用来存放大量FD的数据结构，这样会使得用户空间和内核空间在传递该结构时复制开销大

  1. 不知道具体是哪个文件描述符就绪，需要遍历全部的文件描述符；

当套接字比较多的时候，每次select()都要通过遍历FD_SETSIZE个socket来完成调度，不管哪个socket是活跃的，都遍历一遍。这会浪费很多CPU时间。如果能给套接字注册某个回调函数，当他们活跃的时候，自动完成相关操作，那就避免了轮训，这正是epoll和kqueue做的。

  1. 入参的3个FD_SET集合每次调用都需要重置；

poll

基本概念

poll本质上和select没有区别，它将用户传入的数组拷贝到内核空间，然后查询每个FD对应的设备状态，但是它没有最大连接数的限制，原因是它是基于链表来存储的。

poll函数接口

#include <poll.h>
// 数据结构
struct pollfd {
    int fd;                         // 需要监视的文件描述符
    short events;                   // 需要内核监视的事件
    short revents;                  // 实际发生的事件
};

// API
int poll(struct pollfd fds[], nfds_t nfds, int timeout);

poll使用示例

// 先宏定义长度
#define MAX_POLLFD_LEN 4096  

int main() {
  /*
   * 在这里进行一些初始化的操作，
   * 比如初始化数据和socket等。
   */

  int nfds = 0;
  pollfd fds[MAX_POLLFD_LEN];
  memset(fds, 0, sizeof(fds));
  fds[0].fd = listenfd;
  fds[0].events = POLLRDNORM;
  int max  = 0;  // 队列的实际长度，是一个随时更新的，也可以自定义其他的
  int timeout = 0;

  int current_size = max;
  while (1) {
    // 阻塞获取
    // 每次需要把fd从用户态拷贝到内核态
    nfds = poll(fds, max+1, timeout);
    if (fds[0].revents & POLLRDNORM) {
        // 这里处理accept事件
        connfd = accept(listenfd);
        //将新的描述符添加到读描述符集合中
    }
    // 每次需要遍历所有fd，判断有无读写事件发生
    for (int i = 1; i < max; ++i) {     
      if (fds[i].revents & POLLRDNORM) { 
         sockfd = fds[i].fd
         if ((n = read(sockfd, buf, MAXLINE)) <= 0) {
            // 这里处理read事件
            if (n == 0) {
                close(sockfd);
                fds[i].fd = -1;
            }
         } else {
             // 这里处理write事件     
         }
         if (--nfds <= 0) {
            break;       
         }   
      }
    }
  }

poll的优点

不需要每个FD都进行一次系统调用，解决频繁的用户态和内核态切换的问题。

poll的缺点

  1. 每次调用都需要将FD从用户态拷贝到内核态；
  2. 不知道具体是哪个文件描述符就绪，需要遍历全部的文件描述符；

优化的点

  1. 单进程监听的FD去除了1024的限制；
  2. 优化了数据结构，采用了链表去存储文件描述符，不需要每次都去重置FD_SET文件描述符的集合；

epoll

基本概念

epoll可以理解为event poll，不同于忙轮训和无差别轮训，epoll会把哪个流发生了怎样的IO事件通知我们。所以我们说epoll实际上是事件驱动（每个事件关联上fd）的，此时我们对这些流的操作都是有意义的。（复杂度降低到了O(1)）

epoll函数接口

当某一进程调用epoll_create方法时，Linux内核会创建一个eventpoll结构体，这个结构体中有两个成员与epoll的使用方式密切相关。eventpoll结构体如下所示：

#include <sys/epoll.h>

// 数据结构
// 每一个epoll对象都有一个独立的eventpoll结构体
// 用于存放通过epoll_ctl方法向epoll对象中添加进来的事件
// epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可
struct eventpoll {
    /*红黑树的根节点，这颗树中存储着所有添加到epoll中的需要监控的事件*/
    struct rb_root  rbr;
    /*双链表中则存放着将要通过epoll_wait返回给用户的满足条件的事件*/
    struct list_head rdlist;
};

// API
int epoll_create(int size); // 内核中间加一个 ep 对象，把所有需要监听的 socket 都放到 ep 对象中
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event); // epoll_ctl 负责把 socket 增加、删除到内核红黑树
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);// epoll_wait 负责检测可读队列，没有可读 socket 则阻塞进程

每一个epoll对象都有一个独立的eventpoll结构体，用于存放通过epoll_ctl方法向epoll对象中添加进来的事件。这些事件都会挂载在红黑树中，如此，重复添加的事件就可以通过红黑树而高效的识别出来(红黑树的插入时间效率是lgn，其中n为红黑树元素个数)。
而所有添加到epoll中的事件都会与设备(网卡)驱动程序建立回调关系，也就是说，当相应的事件发生时会调用这个回调方法。这个回调方法在内核中叫ep_poll_callback,它会将发生的事件添加到rdlist双链表中。
在epoll中，对于每一个事件，都会建立一个epitem结构体，如下所示：

struct epitem{
    struct rb_node  rbn;//红黑树节点
    struct list_head    rdllink;//双向链表节点
    struct epoll_filefd  ffd;  //事件句柄信息
    struct eventpoll *ep;    //指向其所属的eventpoll对象
    struct epoll_event event; //期待发生的事件类型
}

当调用epoll_wait检查是否有事件发生时，只需要检查eventpoll对象中的rdlist双链表中是否有epitem元素即可。如果rdlist不为空，则把发生的事件复制到用户态，同时将事件数量返回给用户。
epoll.png
从上面的讲解可知：通过红黑树和双链表数据结构，并结合回调机制，造就了epoll的高效。 讲解完了Epoll的机理，我们便能很容易掌握epoll的用法了。一句话描述就是：三步曲。

  • 第一步：epoll_create()系统调用。此调用返回一个句柄，之后所有的使用都依靠这个句柄来标识。
  • 第二步：epoll_ctl()系统调用。通过此调用向epoll对象中添加、删除、修改感兴趣的事件，返回0标识成功，返回-1表示失败。
  • 第三部：epoll_wait()系统调用。通过此调用收集收集在epoll监控中已经发生的事件。

epoll使用示例

int main(int argc, char* argv[])
{
   /*
   * 在这里进行一些初始化的操作，
   * 比如初始化数据和socket等。
   */

    // 内核中创建ep对象
    epfd=epoll_create(256);
    // 需要监听的socket放到ep中
    epoll_ctl(epfd,EPOLL_CTL_ADD,listenfd,&ev);
 
    while(1) {
      // 阻塞获取
      nfds = epoll_wait(epfd,events,20,0);
      for(i=0;i<nfds;++i) {
          if(events[i].data.fd==listenfd) {
              // 这里处理accept事件
              connfd = accept(listenfd);
              // 接收新连接写到内核对象中
              epoll_ctl(epfd,EPOLL_CTL_ADD,connfd,&ev);
          } else if (events[i].events&EPOLLIN) {
              // 这里处理read事件
              read(sockfd, BUF, MAXLINE);
              //读完后准备写
              epoll_ctl(epfd,EPOLL_CTL_MOD,sockfd,&ev);
          } else if(events[i].events&EPOLLOUT) {
              // 这里处理write事件
              write(sockfd, BUF, n);
              //写完后准备读
              epoll_ctl(epfd,EPOLL_CTL_MOD,sockfd,&ev);
          }
      }
    }
    return 0;
}

epoll的优点

  1. 没有最大并发连接的限制，能打开的FD的上限远大于1024（1G的内存上能监听约10万个端口）；
  2. epoll在内核态维护了红黑树，将文件描述符维护在内核态里面，不需要每次将想要监听的FD从用户态拷贝到内核态，直接通过epoll_ctl将文件描述符添加到内核态，后续就一直去维护这个epoll对象；
  3. 通过一个就绪链表，可以知道哪些文件描述符是就绪的，不需要用户空间每次去遍历所有的文件描述符，找出就绪的文件描述符；

epoll的缺点

  1. 跨平台性不好，只支持Linux，macOS等操作系统不支持；
  2. 相较于epoll，select更轻量可移植性更强；
  3. 在监听连接数和事件较少的场景下，select可能更优；

epoll LT（水平触发） 与 ET（边缘触发） 模式的区别

  • LT模式下，只要这个FD还有数据刻度，每次epoll_wait就会返回它的事件，提醒用户程序去操作；
  • ET模式下，它只会提示一次，直到下次在有数据流入之前都不会在提示了，无论FD中是否还有数据可读。所以在ET模式下，read一个FD的时候一定要把它的buffer读完，或者遇到EAGIN错误。

epoll使用“事件”的就绪通知方式，通过epoll_ctl注册FD，一旦该FD就绪，内核就会采用类似callback的回调机制来激活FD，epoll_wait便可以收到通知。

select/poll/epoll之间的区别

select、poll、epoll都是IO多路复用的机制。IO多路复用就通过一种机制，可以监视多个描述符，一旦某个文件描述符就绪（一般是读就绪或者写就绪），能够通知程序进行响应的读写操作。但select、poll、epoll本质上都是同步IO，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的， 而异步IO则无需自己负责进行读写，异步IO的实现会负责把数据从内核拷贝到用户空间。
epoll跟select都能提供IO多路复用的解决方案。在现在的Linux内核里面都能支持，其中epoll是Linux锁特有的，而select则应该是POSIX所规定的，一般操作系统均有实现

select poll epoll
操作方式 遍历 遍历 回调
数据结构 bitmap 数组 红黑树
最大连接数 1024（x86）或2048（x64） 无上限 无上限
最大支持文件描述符 一般有最大值限制 65535 65535
FD拷贝 每次调用select，都需要把FD集合从用户态拷贝到内核态 每次调用poll，都需要把FD集合从用户态拷贝到内核态 FD首次调用epoll_ctl拷贝，每次调用epoll_wait不拷贝
工作模式 LT LT 支持ET高效模式
工作效率 每次调用都进行线性遍历，时间复杂度为O(n) 每次调用都进行线性遍历，时间复杂度为O(n) 事件通知方式，每当FD就绪，系统注册的回调函数就会被调用，将就绪的FD放到readList里面，时间复杂度为O(1)

epoll是Linux目前大规模网络并发程序开发的首选模型。在绝大多数情况下性能远超select和poll。目前流行的高性能web服务器Nginx正式依赖于epoll提供的高效网络套接字轮询服务。但是，在并发连接不高的情况下，多线程+阻塞I/O方式可能性能更好。

支持一个进程所能打开的最大连接数

  • select：单个进程所能打开的最大连接数有FD_SETSIZE宏定义，其大小是32个整数的大小（在32位的机器上，大小就是32_32，同理64位机器上FD_SETSIZE为32_64），当然我们可以对进行修改，然后重新编译内核，但是性能可能会受到影响，这需要进一步的测试。
  • poll：poll本质上和select没有区别，但是它没有最大连接数的限制，原因是它是基于链表来存储的。
  • epoll：虽然连接数有上限，但是很大，1G内存的机器上可以打开10万左右的连接，2G内存的机器可以打开20万左右的连接。

FD剧增后带来的IO效率问题

  • select：因为每次调用时都会对连接进行线性遍历，所以随着FD的增加会造成遍历速度慢的“线性下降性能问题”。
  • poll：因为每次调用时都会对连接进行线性遍历，所以随着FD的增加会造成遍历速度慢的“线性下降性能问题”。
  • epoll：因为epoll内核中实现是根据每个fd上的callback函数来实现的，只有活跃的socket才会主动调用callback，所以在活跃socket较少的情况下，使用epoll没有前面两者的线性下降的性能问题，但是所有socket都很活跃的情况下，可能会有性能问题。

消息传递方式

  • select：内核需要将消息传递到用户空间，都需要内核拷贝动作
  • poll：内核需要将消息传递到用户空间，都需要内核拷贝动作
  • epoll：epoll通过内核和用户空间共享一块内存来实现的。

总结

select，poll实现需要自己不断轮询所有fd集合，直到设备就绪，期间可能要睡眠和唤醒多次交替。而epoll其实也需要调用epoll_wait不断轮询就绪链表，期间也可能多次睡眠和唤醒交替，但是它是设备就绪时，调用回调函数，把就绪fd放入就绪链表中，并唤醒在epoll_wait中进入睡眠的进程。虽然都要睡眠和交替，但是select和poll在“醒着”的时候要遍历整个fd集合，而epoll在“醒着”的时候只要判断一下就绪链表是否为空就行了，这节省了大量的CPU时间。这就是回调机制带来的性能提升。
select，poll每次调用都要把fd集合从用户态往内核态拷贝一次，并且要把current往设备等待队列中挂一次，而epoll只要一次拷贝，而且把current往等待队列上挂也只挂一次（在epoll_wait的开始，注意这里的等待队列并不是设备等待队列，只是一个epoll内部定义的等待队列）。这也能节省不少的开销。

参考

https://juejin.cn/post/6882984260672847879#heading-6
https://www.bilibili.com/video/BV1r54y1f7bU?spm_id_from=333.337.search-card.all.click
https://xiaolincoding.com/os/8_network_system/selete_poll_epoll.html#%E6%9C%80%E5%9F%BA%E6%9C%AC%E7%9A%84-socket-%E6%A8%A1%E5%9E%8B
https://mp.weixin.qq.com/s/Qpa0qXxuIM8jrBqDaXmVNA