通过epoll理解协程

IO多路复用

C10K问题

在互联网的最早期，网络上设备很少，那时每个连接都需要一个进程来处理。一些老的处理方式（如CGI）也沿用了多进程的思路来处理连接。但随着互联网规模快速扩大，一个服务器要同时服务的人越来越多，这也就产生了著名的C10K问题，也就是一个服务器如何处理一万个客户端同时连接。

进程与线程的局限性

进程出现后又出现了线程，相比进程，线程切换的创建与代价更低。也出现了进程池、线程池这样的技术，用于避免频繁创建和销毁的开销，仅保留切换的开销。但这些处理方案都有一个特点：一个进程或线程同时只能处理一个连接，即使连接空闲，线程也不能处理其他连接，这期间线程只能等待。

那么一个线程只能处理一个连接吗？显然不是的，线程和网络并没有什么必然的关联，一个线程既可以同时处理多个网络连接，一个网络连接也可以被多个线程处理。

阻塞与非阻塞

阻塞的概念非常容易理解，在生活中，如果我们看到有什么本该畅通的东西被其他东西堵住了，就可说这里被阻塞了。类似地，如果线程不得不等待某个某些数据到来或某个条件为真后才能继续执行后面的代码，我们就可以说线程被阻塞了。

虽然很多时候，只要耗时较长就可以称之为阻塞了，但严格地说，只有那些可能会导致线程无限等待的操作才被称作阻塞操作，例如等待锁的释放、等待网络连接的数据到达、等待管道内产生新数据等。否则就无法明确区分阻塞与非阻塞了（1us以上算阻塞？还是1ms以上算？）。

在Linux系统上读取磁盘文件时，O_NONBLOCK标志位并不能起有效作用。因为操作系统不会认为磁盘文件的读写有可能导致无限等待。

网络连接的阻塞操作

在看IO多路复用的实现前，我们先看看线程是怎么处理一个网络连接的。线程使用read / write或recv / send系统调用来读/写一个连接，每个连接在操作系统内核中都有一个读写缓冲区。读时如果内核缓冲区中还没有数据，操作系统会让线程阻塞等待，直到缓冲区中有数据后，读操作才能返回数据；写时如果内核缓冲区已满，操作也会被阻塞，直到将全部的数据写入缓冲区。这期间网卡会不断工作，将收到数据送入内核的读缓冲区，并将内核写缓冲区的内容发送出去。

这种机制导致了一个线程难以同时处理两个可能导致阻塞的连接。例如同时存在连接A和连接B，当线程尝试从连接A处收数据时，会阻塞在read调用中。如果此时连接A由于网络波动或其他原因没有数据到达，则线程会一直在此处等待，即使连接B可能已经有很多数据到达需要处理，线程也无法切换。

select, poll 与 epoll

为了让一个线程同时处理多个连接，系统开发者们设计了IO多路复用机制。在Linux上有三类系统调用：select, poll 与 epoll，在UNIX类系统中与epoll对应的则是kqueue。

select 与 poll

了解了上面阻塞操作的原理，再去理解IO多路复用就变成了一个简单的思路转变：当一个连接无法读写时，不要让操作系统等待，而是让操作系统立刻返回并告知因为无数据/数据已满而无法读写，此时线程就可以暂时放弃它而去检查另一个连接是否可读写了。这就是IO多路复用的基石：非阻塞IO。

检查连接是否可读写需要进行一次系统调用，检查很多个连接则需要进行很多次系统调用，而系统调用相比普通函数调用速度稍慢，操作系统的开发者们为了加快这一操作，开发了可以一次性检查多个连接是否可读写的系统调用：selelct和poll。

注意：很多八股文会提到 poll系统调用是传入的参数是链表，但这并不正确。poll传入的是pollfd数组，并有一个参数n指示了有n个该元素。事实上，系统调用很少涉及链表结构和回调函数，这两者在系统调用中难以高效、安全地实现。

poll的签名如下：int poll(struct pollfd *fds, nfds_t nfds, int timeout);

这两个系统调用思路是相同的。使用者将所有需要检查读写的连接全部放入给定的结构中后，发起调用。此时线程会等待，直到这其中有连接可以进行读写、发生异常或达到设定的超时时间。这相当于操作系统在内部帮你遍历检查你提供的连接中有没有连接可以读写。当返回后，用户程序通过遍历检查返回数组中的元素来确认哪个连接可以被读/写了。这种方式将多次系统调用简化成一次，节约了频繁发起系统调用的时间。

但这种方式仍然有可优化的空间。

内核通常不会直接通过指针访问用户程序的内存，而是需要先从用户空间内复制到内核空间。而select和poll每次都必须将所有需要监控的连接提交到内核，导致每次都需要在内核空间和用户空间中复制较多的数据，并且用户程序还需要遍历检查。为了优化这些问题，Linux从 2.5.44版本中提供了epoll系统调用系列。

epoll

从上文select和poll的使用方式可以看出，它们在内核中是无状态的，这意味着每次对它们的调用都是独立的，每次调用都需要提供全部感兴趣的连接。但实践中感兴趣的连接通常不会急剧变化。在维护长连接时，短时间内只有小部分连接需要读写，所以可以从内核中维护状态，程序只需要在需要的时候添加和删除即可（通常是连接accept后添加，close前删除，不过close会自动删除）。

由于需要在内核中维护状态，epoll提供了三个系统调用epoll_cerate, epoll_ctl, epoll_wait。epoll_create用于创建epoll实例，让内核开始维护状态，epoll_ctl可以添加、删除或修改感兴趣的连接和事件，epoll_wait则用于等待事件发生，当有一个或多个连接有感兴趣的事件时，epoll_wait会返回这些事件。由于只返回了实际发生了事件的文件描述符，所以epoll可以尽量减少内核态到用户态的拷贝。

这是当前（2024年）Linux下大多数异步程序使用的方式。

io_uring 与 IOCP

io_uring是解决Linux在磁盘IO场景下的弱势的，在io_uring出现之前，Linux的异步磁盘IO通常是使用其他线程来完成，如tokio、libuv均使用线程池来处理文件的异步操作。只有部分数据库软件才会用那个又难用又复杂的Linux aio（可以说说就是这些数据库软件的开发者为了数据库高效读写磁盘才开发的）。

除了处理异步磁盘IO，io_uring也可以用于高效处理异步网络IO，由于数据拷贝有单独的内核线程来完成，而非read / write系统调用这种由用户线程发起的系统调用来完成，当前（2024年）在单线程场景下，io_uring要比epoll快一些，但多线程场景差距不大。io_uring的相比epoll减少了系统调用的次数，并且可以使用轮询方式彻底避免系统调用带来的开销。

IOCP是Windows NT内核中用于处理异步IO的接口，其原理与io_uring类似，但出现要更早。

什么是协程

在了解协程之前，让我们先区分一下同步与异步。

同步与异步

同步代表只有上一个任务执行完成，才会去执行下一个任务，即使两个任务之间没有任何关系。

而异步则是不等待上一个任务执行完成就去执行下一个任务。需要注意的是，异步只强调不等待上一个任务完成就执行新任务，并不代表上一个任务一定能和新任务同时执行。例如在单核CPU上，使用两个线程并发执行两个任务也是异步，但事实上CPU同时只能执行一个任务。

为什么按顺序执行的反而被称为同步

相信很多人会好奇，同步通常指同时进行，为什么在计算机领域里反而成了每个任务都按顺序执行呢？首先这并非翻译问题，英语中的 synchronous 也指的是 happening or existing at the same time. 所以英语国家的人也会有和我们一样的困惑。

事实上，同步这个术语来自于数字电路领域。数字电路中，有一个核心组件叫时钟电路。为了保证数字电路的执行不混乱，绝大部分元件都会受时钟电路的控制，每当时钟电路动作一次（上升沿或下降沿），它们也就集体动作一次，这样也就保证了所有的动作像流水线一样有先后顺序。所以，所谓的同步是与时钟电路同步。

而异步则是那个无视时钟电路，直接改变电路状态的方法。它通常表现为一个按钮，用户只要按下去电路就立刻切换到指定的状态。

构建在数字电路上的计算机沿用了这个叫法，所以同步就是跟随时钟信号按顺序执行；而异步则是靠信号或者事件插入，不按顺序地执行。

事件驱动编程

有了epoll的帮助，用户态编程就可以更轻松的处理更多同时发生的连接了。

一个线程处理一个连接只需要按照逻辑进行read和write就可以了，执行状态会自然保存在线程的执行栈中。但有多个连接时，就需要分别记录下每个连接的执行状态，为此出现了事件驱动模型。简单地说，事件驱动的控制流不再是顺序的，而是被拆分成了一个个函数，每当一个新事件到来，就会触发这个事件类型对应的函数。下面用简单的C代码来表示。

#define BUF_SIZE 4096
struct socket {
    int fd;
    char *read_buf;
    ssize_t read_size;
    
    char *write_buf;
    ssize_t write_size;
}

void on_read(struct socket *s) {
    // 收到读事件的时候一定能读出点什么东西，不考虑错误
    s->read_size = read(s->fd, s->read_buf, BUF_SIZE);
    process_http(s->read_buf, s->read_size);
    strncpy("HTTP/1.1 200 OK\r\n", s->write_buf, BUF_SIZE);
    on_write(s); // 立刻尝试写，写不下去在再考虑其他问题
}

void on_write(struct socket *s) {
    // 最简化，忽略写不完的情况
    // 读后立刻触发一次写，但可能因为缓冲区满写不进去，那就返回，等之后写event到来再写
    ssize_t w = write(s->fd, s->write_buf, s->write_size);
    if (w < 0 && (errno == EWOULDBLOCK || errno == EAGAIN)) {
    	return;
    }
    close(s->fd);
}

void on_hangup(struct socket *s) { /* ... */ }

void event_loop() {
    while (1) {
	    int num_events = epoll_wait(epoll_fd, events, MAX_EVENTS, -1);
        for (int i = 0; i < num_events; i++) {
            if (events[i].events & EPOLLUP) {
            	on_read(events[i].data.ptr);
            } else if (events[i].events & EPOLLOUT) {
                on_write(events[i].data.ptr);
            } /* ... */
        }
	}
}

这种编程模型通过将状态保存到额外结构中可以有效管理大量连接的状态，但显然也会使开发的控制流变得复杂，阻塞开发模式下，程序员只需要关注当前位置的代码即可。然而事件驱动编程导致程序的控制流会在多个函数间反复变化，这些函数间可能相距很远，并且需要区分函数内的状态和在额外的结构中保存的持久状态，无疑加重了程序员的编码负担。

简化编程步骤

为了让语句尽可能集中在一处而非分散在多处，开发者们在事件驱动编程的基础上又衍生了许多开发方式。

以JavaScript为例，首先是闭包回调，通过闭包将类转换为闭包函数，这种方式不仅将代码位置合并到一起，而且状态也可以直接由闭包捕获，减少了非常多的工作量，但这种方式仍然有较大的缺点。首先是回调地狱，多次非阻塞调用就需要多个回调，而每个回调都会嵌套，导致多个回调中缩进非常复杂，并且由于回调函数仅仅代表将来会执行，接下来函数还是会执行下面的代码，导致控制流仍然不清晰。

setTimeout(function() { //第一层
    console.log('我是第一个执行');
    setTimeout(function() { //第二程
        console.log('我第二个执行');
        setTimeout(function() { //第三层
            console.log('我第三个执行');
        }, 1000);
        console.log('但我在第二个和第三个之间执行');
    }, 2000);
    console.log('而我在第一个和第二个之间执行')
}, 3000)

为此，JavaScript又推出了Promise，这稍微缓解了一些回调地狱引起的问题。但是依然存在异常控制流不清晰，多个闭包间难以共享变量等等情况。

new Promise((resolve)=>{
        console.log('我第一个执行');
    	resolve(0);
    	console.log('我第二个执行')
    })
    .then(() => {
        return new Promise(resolve => setTimeout(resolve, 1000));
    })
    .then(r=>console.log('我第三个执行'))

在经过多年的尝试与改进后，几乎所有主流编程语言都选择了同一个方向：协程。

协程解决了什么问题

通过上面三个例子，我们可以看到事件驱动编程模型的缺点的主要原因：控制流由事件决定，而非逻辑决定，程序员必须照顾随时可能到来的事件，进而导致逻辑难以组织。而传统的同步编程，逻辑就清晰多了。

所以，协程的根本目标就在于：让程序员像编写同步代码一样编写异步代码。我们可以想象一个函数yield，当读写遇到阻塞时，可以将执行权交出去，而当收到可以读写的事件时，又可以回到交出执行权的那个地方。

ssize_t unblocking_read(int fd, void *buf, ssize_t size) {
    while (1) {
        ssize_t ret = read(fd, buf, size);
        if (ret < 0 && (errno == EWOULDBLOCK || errno == EAGAIN)) {
            yield(); // 神奇的函数，能够跳出执行流程，去执行其他等待的函数，当有事件来的时候再从这里恢复
        } else {
            return ret;
        }
    }
}
ssize_t unblockint_write(int fd, void *buf, ssize_t size); // 与写类似

void process_http(int fd) {
    char buf[4096];
    ssize_t size = unblocking_read(fd, buf, sizeof(buf));
    proc_http_header(buf, size);
    unblocking_write(fd, "HTTP/1.1 200 OK\r\n");
    close(fd);
    return 0;
}

这就是协程的核心思想：通过包装让非阻塞调用的行为与阻塞调用类似，让程序员可以重新专注在逻辑维护而非状态维护上。可以看到相比上面的事件驱动模型，这里的核心函数process_http简化了非常多。

如何实现协程

主流的协程实现方式有两种，不需要额外函数调用栈的无栈协程与需要额外调用栈的有栈协程。

有栈协程

通常有栈协程被称为用户线程、虚拟线程、绿色线程、纤程等。从名字上就可以看出，有栈协程使用的思路与操作系统的线程一致，它为每个协程开辟独立的栈空间，但相较于操作系统的调度，有栈协程的调度需要保存的寄存器更少、无需进入内核态，并且调度时机也由程序自身控制，所以切换代价更低。其中Golang的goroutine、Java 21的虚拟线程都属于有栈协程。由于保留了函数的全部调用栈数据，这使得有栈协程的异步代码可以和同步代码没有任何区别，编写时不会增加任何额外的心智负担。这其中最具代表性的就是Golang，Golang从语言和标准库层面封装了常见阻塞操作的非阻塞版本，使用Golang编写代码几乎和使用多线程处理连接几乎完全一致，这使得迁移非常容易。

另外，有栈协程可以完全在运行时实现，而无需编译器的支持，例如C++的libgo库就是通过替换阻塞系统调用和运行时操作来达成和Golang类似的效果的。

我的这个仓库使用C语言实现了一个简单的单线程有栈协程，可以处理网络连接、协程睡眠两种情况，这个程序通过setjmp和很少量汇编编写。所以这个库只能用于X86-64 Linux环境。如果有机会我可以单独开一篇文章写如何实现协程。

无栈协程

无栈协程与有栈协程相对，其不保留函数的调用栈，只保留必要的变量。由于这个限制，产生了无栈协程的最大特点：必须要使用类似async / await的关键字标识协程函数与协程的切换时机。需要注意的是，有栈协程也可以使用类似的关键字，只是并非必须使用。

相比有栈协程，无栈协程需要的内存和额外保留的数据更少，但进行协程切换的时机则被固定在了await时。无栈协程通常使用闭包的思路实现：分析每个可能跨await使用的变量，将它们存放在堆上；同时将每个await块拆分成独立的函数，进行await时相当于返回包含必要局部变量的闭包等待调度。例如JavaScript的协程就是对Promise的一种包装和优化。可以看到，想要使用无栈协程，就必须要编译器提供支持。

大部分使用async / await的语言均为无栈协程实现，例如Python、JavaScript、Rust、C#等。