select → poll → epoll：Linux IO 多路复用的三代演进

一句话结论（30s）

三代演进的进化主线是消除「每次调用都全量拷贝 + 全量遍历」——select 用定长位图（1024 上限）且每次 O(n) 拷贝与遍历，poll 用动态数组突破 fd 上限但仍是 O(n)。epoll 的核心创新是把「每次全量传递」变成「一次注册、事件驱动通知」，因为内核用红黑树存所有 fd 状态、用就绪链表存结果、用回调自动驱动就绪，epoll_wait 只拷就绪事件，所以是 O(1) 分发。核心权衡是：epoll 用更复杂的内核数据结构（红黑树 + 就绪链表）换取百万级连接的支撑能力，代价是编程模型从「每次传全量」变成「先 ctl 注册再 wait 取结果」。

核心原理（2min）

select 每次调用都要把整个 fd_set 位图拷进内核，内核遍历所有 fd 检查就绪后写回位图，用户再遍历一遍找出被置位的 fd，三次 O(n) 叠加；poll 改用 pollfd 动态数组突破 1024 上限，但每次仍需全量拷贝与遍历。epoll 把工作拆成三个系统调用：epoll_create 创建 eventpoll 对象（内含红黑树 rbtree 存所有注册 fd、就绪链表 rdllist 存就绪 fd），epoll_ctl 把 fd 加入红黑树并注册回调（fd 就绪时回调将其挂进就绪链表），epoll_wait 直接从 rdllist 取出就绪事件拷贝到用户态。每个 fd 只注册一次，之后 wait 只拷就绪事件而非全量列表——1 万连接中 5 个有数据，就只拷这 5 个就绪事件。

底层深入（5-10min）

select：位图的局限

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

内部实现：

用户将 fd 设置到 fd_set（位图，默认最大 1024 bit = FD_SETSIZE）
select 将整个 fd_set 拷贝到内核空间
内核遍历所有 fd，检查就绪状态，写回 fd_set
用户拿到 fd_set 后，再次遍历所有 fd 找出哪些被置位

每次 select 调用:
  - 内核拷贝整个 fd_set（O(n) 拷贝）
  - 内核遍历所有 fd（O(n) 扫描）
  - 用户遍历所有 fd（O(n) 扫描）

10000 个 fd → 每次 select = 30000 次操作（最少）

思考：select 慢的根源是什么？——不是「一次遍历」，而是「每次调用都全量重来」。即便 10000 个 fd 里只有 1 个就绪，select 也要把这 10000 个 fd 的位图拷进内核、内核遍历一遍、用户再遍历一遍。连接越多，这套「全量拷贝 + 全量遍历」的成本越高，而且是每一次 select 都要付一遍。

poll：突破 fd 上限

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

struct pollfd {
    int fd;         // 文件描述符
    short events;   // 关注的事件
    short revents;  // 返回的就绪事件
};

用动态数组替代定长位图——突破了 1024 的 fd 限制。 但本质仍然是：

将整个 pollfd 数组拷贝到内核
内核遍历所有 fd
返回 revents

fd 数量多时 O(n) 的拷贝和遍历仍然是瓶颈。100 万连接 → 每次 poll 拷贝 100 万 × 8B ≈ 8MB → 循环 100 万次遍历 → 性能急剧恶化。

思考：poll 突破了 1024 上限，为什么还是被 epoll 取代？——因为它只改了「容器」（位图变数组），没改「算法」。每次 poll 依然要把整个 pollfd 数组拷进内核、遍历所有 fd，fd 从 1 万涨到 100 万时，O(n) 拷贝和遍历照样是瓶颈。上限破了，复杂度没变。

epoll：事件驱动的 O(1) 分发

int epoll_create(int size);         // 创建 epoll 对象
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);  // 注册/修改/删除 fd
int epoll_wait(int epfd, struct epoll_event *events, int maxevents, int timeout);  // 等待事件

epoll_create：创建 epoll 对象

内核分配一个 eventpoll 结构，包含：

红黑树（rbtree）：存储所有注册的 fd，增删改 O(log n)
就绪链表（rdllist）：存储就绪的 fd，epoll_wait 直接从链表取

epoll_ctl：注册 / 修改 fd

将 fd 加入红黑树，同时向内核注册一个回调：当该 fd 就绪时，回调函数将其加入就绪链表。

每个 fd 注册一次，不需要每次 epoll_wait 重新传递全量 fd 列表。

epoll_wait：获取就绪事件

直接从就绪链表 (rdllist) 中取出事件 → 拷贝到用户态 events 数组

没有”遍历所有 fd”——只拷贝就绪事件。 1 万个连接中 5 个有数据 → 只拷贝这 5 个就绪事件（40 字节 vs 80000 字节的数组拷贝）。

思考：epoll 的 O(1) 是怎么「白捡」来的？——靠内核替你维护状态。红黑树存了所有 fd 的状态，fd 就绪时回调自动把它挂进就绪链表，epoll_wait 只需要从链表里把就绪的取出来，不用再遍历全体。代价是注册时多一次 epoll_ctl，以及内核要维护更复杂的数据结构——这就是「一次注册，换取后续每次 O(1)」。

三代对比

	select	poll	epoll
fd 存储	bitmap (1024 上限)	动态数组（突破上限）	红黑树（无上限）
内核遍历	O(n)	O(n)	O(1)
内核拷贝	每次全量 fd_set	每次全量 pollfd	仅拷贝就绪 events
注册成本	每次调用都传全量	每次调用都传全量	epoll_ctl 一次注册
适合场景	少量 fd（< 100）	中等 fd（< 10000）	大量 fd（百万级）

总结

epoll 的核心创新：把”每次都要全量传递”变成”一次注册、事件驱动通知”。 红黑树存状态，就绪链表返回结果，回调函数自动驱动就绪事件。三个系统调用分工明确——create 建结构、ctl 管注册、wait 取结果。

章末提问

追问 1：select 和 epoll 的核心区别是什么？

回答思路：结论先行——核心区别是 select 每次调用都「全量拷贝 + 全量遍历」，epoll 是「一次注册、事件驱动」。因为 select 每次都要把整个 fd_set 位图拷进内核并 O(n) 遍历，用户还要再遍历一遍；epoll 用红黑树存状态、就绪链表存结果、回调驱动就绪，epoll_wait 只拷就绪事件，所以是 O(1) 分发。

追问 2：epoll 为什么能支撑百万连接？

回答思路：结论先行——因为 epoll 把「每次全量传递」变成「一次注册 + 只取就绪」。因为 epoll_create 建红黑树（增删 O(log n)），epoll_ctl 一次性注册 fd 并挂回调，epoll_wait 直接从就绪链表拷贝就绪事件；百万连接里只有少量活跃时，每次只拷活跃的那几个，成本不会随连接总数线性增长。

追问 3：poll 相比 select 改进了什么？它解决了 select 的根本问题吗？

回答思路：结论先行——poll 只解决了 fd 数量上限（位图 1024 → 动态数组），没解决 O(n) 复杂度。因为 poll 只是把定长位图换成 pollfd 动态数组，突破了 1024 限制，但每次调用依然全量拷贝 + 全量遍历，fd 上百万时性能照样恶化。根本问题是「每次全量」，这只有 epoll 的「事件驱动」才解决。

select→poll→epoll——Linux IO多路复用的三代演进