---

Epoll 红黑树 + 就绪链表数据结构

---

0. 定位声明

适用版本：Linux Kernel 2.6.17+（epoll 接口稳定版本）；glibc 2.3.2+
前置知识：
  - 了解文件描述符（fd）和 I/O 多路复用基本概念（select/poll）
  - 理解基本数据结构：链表、二叉搜索树
  - 了解 Linux 系统调用基础（syscall、用户态/内核态切换）
  - 理解进程/线程阻塞与唤醒机制
不适用范围：
  - 本文不覆盖 epoll 的用户态 API 全貌（仅聚焦内部数据结构）
  - 不适用于 Windows IOCP、macOS kqueue 等其他平台实现
  - 不涵盖 io_uring（Linux 5.1+ 的新一代异步 I/O 接口）

---

1. 一句话本质

用大白话说：你要同时盯着 10 万扇门，等待任意一扇门敲响。epoll 的做法是：用一棵有序的"花名册"（红黑树）记录所有要监视的门；同时维护一个"今天有动静的门"的排队名单（就绪链表）。每次你只需要看这个名单，而不是挨个检查 10 万扇门。

正式描述：epoll 在内核中用红黑树（rb_tree）管理所有注册监听的文件描述符（O(log n) 增删改），用双向链表（rdllist）收集已就绪的事件，应用程序每次 epoll_wait 只需从链表头部摘取事件，实现 O(1) 的事件获取，彻底解决 select/poll 的 O(n) 线性扫描瓶颈。

---

2. 背景与根本矛盾

历史背景

2001 年前，Linux 服务器处理高并发连接的主要方式是 select 和 poll。它们的致命缺陷：

• select：fd 集合上限 1024，每次调用需将整个集合从用户态拷贝到内核态，内核线性扫描所有 fd
• poll：取消了 1024 限制，但每次调用仍需传入完整 fd 数组，O(n) 扫描

C10K 问题（单机 1 万并发连接）在这两种方案下，随连接数增加性能急剧恶化。2002 年，Davide Libenzi 提出并实现了 epoll，Linux 2.5.44 合入，2.6 内核正式稳定，核心思路：把"哪些 fd 需要监听"从每次调用中剥离出去，持久存储在内核中。

根本矛盾（Trade-off）

对立维度	选择	代价
注册效率 vs 查找效率	红黑树 O(log n) 兼顾二者	实现复杂度高，比哈希表内存开销略大
内核内存开销 vs 用户态拷贝	状态持久化在内核，避免重复拷贝	每个 epoll 实例消耗内核内存
事件通知及时性 vs 惊群效应	就绪链表 + 回调注入	ET 模式不当使用会导致事件丢失
并发安全 vs 性能	链表操作使用 ep->lock（自旋锁）	高并发下锁竞争成为瓶颈

---

3. 核心概念与领域模型

3.1 关键术语表

术语	费曼式定义	正式定义
epoll 实例	你雇的一个"门卫"，他有自己的花名册和待处理事件本	通过 epoll_create 创建的内核对象，包含红黑树和就绪链表
epitem	花名册上的一条记录，存着"这扇门的编号和我关心什么事"	内核结构体 struct epitem，红黑树的节点，同时也是就绪链表的节点
红黑树（rbr）	按 fd 编号排好序的花名册，翻找某扇门很快	struct rb_root，以 (epoll_fd, target_fd) 为 key，O(log n) 增删查
就绪链表（rdllist）	"今天来敲门的客人"排的队，先来先服务	struct list_head rdllist，内核回调直接将就绪 epitem 插入此链表
等待队列（wq）	门卫睡着时等待叫醒的名单	struct wait_queue_head_t wq，epoll_wait 阻塞时挂在此处
LT 模式	只要门还没关好，每次问你都会提醒	Level Triggered：只要 fd 处于就绪状态，每次 epoll_wait 都返回
ET 模式	只在门刚打开那一刻提醒你一次	Edge Triggered：仅在状态变化边沿触发一次，需循环读到 EAGAIN

3.2 领域模型

epoll 实例（eventpoll）
│
├── rbr（红黑树）─── 存储所有监听的 fd
│     ├── epitem(fd=3, events=EPOLLIN)
│     ├── epitem(fd=5, events=EPOLLOUT)
│     └── epitem(fd=7, events=EPOLLIN|EPOLLET)
│
├── rdllist（就绪双向链表）─── 只存储"当前有事件"的 fd
│     ├── → epitem(fd=3)  ← 内核回调注入
│     └── → epitem(fd=7)
│
└── wq（等待队列）─── epoll_wait 阻塞时挂在此处

关键：同一个 epitem 节点同时存在于红黑树（管理）和就绪链表（通知）中！
通过 epitem 内部的两套 list_head 实现"一个节点，两个身份"。

3.3 核心数据结构（简化版内核源码）

// 内核版本：Linux 5.15 (fs/eventpoll.c)

struct eventpoll {
    spinlock_t        lock;       // 保护就绪链表的自旋锁
    struct mutex      mtx;        // 保护红黑树的互斥锁
    wait_queue_head_t wq;         // epoll_wait() 阻塞队列
    struct list_head  rdllist;    // 就绪事件链表 ⭐
    struct rb_root_cached rbr;    // 红黑树根节点 ⭐
    struct epitem     *ovflist;   // 溢出链表（scan 期间的并发缓冲）
    struct file       *file;
};

struct epitem {
    union {
        struct rb_node  rbn;      // 红黑树节点 ⭐
        struct rcu_head rcu;
    };
    struct list_head  rdllink;    // 就绪链表节点 ⭐（同一结构体！）
    struct epoll_filefd ffd;      // 监听目标 {file*, fd}，作为红黑树 key
    struct eventpoll  *ep;        // 反向指针到所属 epoll 实例
    struct epoll_event event;     // 用户注册的感兴趣事件 mask
};

---

4. 对比与选型决策

4.1 同类技术横向对比

特性	select	poll	epoll	kqueue	io_uring
fd 上限	1024	无限制	无限制	无限制	无限制
就绪扫描复杂度	O(n)	O(n)	O(1)	O(1)	O(1)
fd 集合传递	每次全量	每次全量	一次注册持久化	一次注册	零拷贝环形队列
内核触发机制	轮询	轮询	回调注入链表	回调注入	完成队列
10万连接参考延迟	~1ms/次	~0.8ms/次	~10μs/次 ⚠️存疑	相近 epoll	更优
磁盘 I/O 支持	否	否	否	部分	是

⚠️ 存疑：延迟数值受硬件、内核版本、活跃连接比例影响显著，以上为量级参考。

4.2 选型决策树

连接数 < 1000 且需跨平台？
  └─ YES → select/poll
  └─ NO  → Linux 平台？
              └─ YES → 需要磁盘 I/O 异步？
                          └─ YES → io_uring（Kernel 5.10+）
                          └─ NO  → epoll（成熟稳定，生态完善）
              └─ NO  → macOS/BSD → kqueue

---

5. 工作原理与实现机制

5.1 为什么选红黑树 + 链表？

为什么是红黑树而不是哈希表？
epoll_ctl 需要快速按 (epollfd, targetfd) 查找 epitem。哈希表虽然 O(1)，但扩容代价大、内存不连续，对内核内存分配器不友好；红黑树 O(log n) 有界（log₂(100000) ≈ 17次比较），内存局部性好，无需扩容，在典型场景下差距不足 1μs。

为什么就绪通知用链表而不是数组？
同一个 epitem 节点可以同时挂在红黑树和链表上（通过不同的 list_head 成员），无需额外内存分配；链表 O(1) 插入/删除；数组在中断回调上下文中动态扩容是危险操作。

5.2 动态行为：三大系统调用时序

epoll_create — 创建阶段

用户态: epoll_create(1)
    ↓ syscall
内核:
  1. 分配 eventpoll 结构体（kmalloc）
  2. 初始化红黑树根节点 rb_root = RB_ROOT
  3. 初始化就绪链表 INIT_LIST_HEAD(&ep->rdllist)
  4. 初始化等待队列、互斥锁、自旋锁
  5. 创建匿名 file，返回 epfd

epoll_ctl(ADD) — 注册阶段

内核:
  1. 根据 epfd 找到 eventpoll 实例
  2. mutex_lock(&ep->mtx)  // 保护红黑树
  3. ep_find()：红黑树中查找 (epfd, fd) 的 epitem
  4. 若不存在：
     a. 分配 epitem，填充 ffd、event
     b. ep_rbtree_insert()：插入红黑树  ⭐
     c. 调用 target_file->f_op->poll()，将 ep_ptable_queue_proc
        注册为该 fd 的等待队列回调  ⭐（灵魂所在！）
     d. 若此时 fd 已就绪，直接加入 rdllist
  5. mutex_unlock(&ep->mtx)

epoll_wait — 等待与收割阶段

内核:
  1. rdllist 非空？→ 直接收割
     rdllist 为空？→ 进程加入 ep->wq，schedule() 睡眠

  [网卡中断 → 协议栈 → 唤醒 socket 等待队列 → ep_poll_callback 被触发]

  ep_poll_callback（中断上下文）:
  2. spin_lock(&ep->lock)
  3. 将 epitem 加入 ep->rdllist  ⭐
  4. wake_up_locked() 唤醒阻塞进程
  5. spin_unlock(&ep->lock)

  [进程唤醒后] ep_send_events():
  6. spin_lock → 将 rdllist 转移到临时 txlist → spin_unlock
  7. 遍历 txlist，copy_to_user 到用户态 events 数组
  8. LT 模式：fd 仍就绪则重新加回 rdllist
     ET 模式：不重新加回
  9. 返回就绪事件数量 k

5.3 关键设计决策

决策 1：回调注入 vs 轮询
若 epoll_wait 定期遍历红黑树调用每个 fd 的 poll() → O(n) 退化。改为注册回调，fd 状态变化时内核主动推送 → O(1) 获取。代价是注册时有回调安装开销，且回调在中断上下文不能阻塞。

决策 2：ovflist 溢出链表
ep_send_events 遍历 rdllist 期间，新就绪事件先进入 ovflist，遍历完成后合并，避免持锁期间的并发写入冲突。

决策 3：互斥锁 + 自旋锁双锁设计
红黑树操作（用户态 ctl）用可睡眠的互斥锁；就绪链表操作（中断上下文 callback）用不可睡眠的自旋锁。两者操作不同数据结构，各司其职。

---

6. 高可靠性保障

6.1 并发安全机制

操作	保护机制	原因
epoll_ctl（红黑树增删改）	ep->mtx（互斥锁）	用户态 ctl 操作可睡眠
回调写入 rdllist	ep->lock（自旋锁）	中断上下文不能睡眠
epoll_wait 读取 rdllist	ep->lock + txlist 转移	最小化持锁时间

6.2 关键监控指标

指标	获取方式	正常参考值	告警阈值
epoll fd 数量	lsof -p <pid> | grep eventpoll	每进程 1~10 个	>100 需排查泄漏
单次 epoll_wait 返回事件数	应用日志	< maxevents	持续等于 maxevents
系统级 fd 使用率	cat /proc/sys/fs/file-nr	< 80%	> 90% 需扩容
epoll 内核内存（slab）	cat /proc/slabinfo | grep eventpoll	视连接数	eventpoll_epi 条目异常多

---

7. 使用实践与故障手册

7.1 典型使用方式

// 运行环境：Linux 5.15+, glibc 2.34
// 编译：gcc -O2 -o epoll_demo epoll_demo.c

#include <sys/epoll.h>
#include <fcntl.h>
#include <unistd.h>
#include <errno.h>

#define MAX_EVENTS 4096

static int set_nonblocking(int fd) {
    int flags = fcntl(fd, F_GETFL, 0);
    return fcntl(fd, F_SETFL, flags | O_NONBLOCK);
}

int main(void) {
    int listen_fd = 0; /* 已完成 socket/bind/listen */
    char buf[4096];

    // 1. 创建 epoll 实例（size 参数 Linux 2.6.8+ 忽略，但必须 > 0）
    int epfd = epoll_create(1);

    // 2. 注册 listen_fd（使用 LT，accept 场景更安全）
    struct epoll_event ev = { .events = EPOLLIN, .data.fd = listen_fd };
    epoll_ctl(epfd, EPOLL_CTL_ADD, listen_fd, &ev);

    struct epoll_event events[MAX_EVENTS];
    while (1) {
        // 3. 等待事件（-1 = 永久阻塞）
        int nfds = epoll_wait(epfd, events, MAX_EVENTS, -1);
        if (nfds == -1 && errno == EINTR) continue;

        for (int i = 0; i < nfds; i++) {
            int fd = events[i].data.fd;
            if (fd == listen_fd) {
                int conn_fd = accept(listen_fd, NULL, NULL);
                set_nonblocking(conn_fd);  // ET 必须非阻塞

                // ET + EPOLLONESHOT（防多线程竞争）
                ev.events = EPOLLIN | EPOLLET | EPOLLONESHOT;
                ev.data.fd = conn_fd;
                epoll_ctl(epfd, EPOLL_CTL_ADD, conn_fd, &ev);
            } else {
                // ET 模式：必须循环读到 EAGAIN
                while (1) {
                    ssize_t n = read(fd, buf, sizeof(buf));
                    if (n > 0) {
                        /* 处理数据... */
                    } else if (n == -1 && (errno == EAGAIN || errno == EWOULDBLOCK)) {
                        // 读完，重新 ARM
                        ev.events = EPOLLIN | EPOLLET | EPOLLONESHOT;
                        ev.data.fd = fd;
                        epoll_ctl(epfd, EPOLL_CTL_MOD, fd, &ev);
                        break;
                    } else {
                        // 错误或对端关闭
                        epoll_ctl(epfd, EPOLL_CTL_DEL, fd, NULL);
                        close(fd);
                        break;
                    }
                }
            }
        }
    }
    close(epfd);
    return 0;
}

7.2 故障模式手册

【故障 1：ET 模式下事件丢失，连接卡死】
- 现象：客户端发送数据后服务端长时间无响应；strace 显示 epoll_wait 不返回
- 根本原因：未循环读到 EAGAIN，内核不再通知，fd 永久"沉默"
- 预防：ET 下必须 while(read() != EAGAIN)；fd 必须 O_NONBLOCK
- 应急：关闭问题连接重连；检查 EAGAIN 处理逻辑

【故障 2：多进程惊群（thundering herd）】
- 现象：多进程共享 epfd，新连接到来时大量进程唤醒，只有一个 accept 成功
- 根本原因：Linux 4.5 之前全部唤醒
- 预防：Linux 4.5+ 使用 EPOLLEXCLUSIVE；或每进程独立 epfd + SO_REUSEPORT
- 应急：升级内核；使用 accept4() + SOCK_NONBLOCK

【故障 3：fd 泄漏 "too many open files"】
- 现象：EMFILE/ENFILE，新连接无法建立
- 根本原因：close(fd) 前未 EPOLL_CTL_DEL；或 epfd 本身泄漏
- 预防：关闭顺序：epoll_ctl(DEL) → close(fd)
- 应急：lsof -p <pid> 排查；临时 ulimit -n 65535

【故障 4：磁盘文件 fd 加入 epoll 行为异常】
- 现象：epoll_wait 立即返回，不符合预期的"阻塞等待"
- 根本原因：磁盘文件 poll() 总返回就绪，epoll 不适用于普通文件
- 预防：磁盘 I/O 用 io_uring 或线程池

7.3 边界条件与局限性

• 不适用于磁盘文件：poll() 总就绪，epoll 无意义
• dup2 陷阱：红黑树 key 是 (struct file*, fd)，dup 后的 fd 与原 fd 共享 file，DEL 行为需注意
• epoll 嵌套上限：最大 5 层（内核硬编码，防循环）
• 每 fd 内核内存：约 128 字节，10 万连接约 12MB

---

8. 性能调优指南

8.1 调优步骤（按优先级）

① 调整 fd 上限（极高优先级）

# /etc/security/limits.conf
* soft nofile 65535
* hard nofile 65535
# /etc/sysctl.conf
fs.file-max = 1000000
net.core.somaxconn = 65535

② 增大 maxevents（高优先级）
高并发下建议 4096~16384，避免持续等于 maxevents 导致处理积压。

③ LT 换 ET（中优先级，需谨慎）
活跃连接密集时 ET 可减少 30%~50% epoll_wait 调用 ⚠️存疑，但需完整的 EAGAIN 循环处理。

④ 减少 EPOLL_CTL_MOD 频率（低优先级）
用状态机批量合并读写事件切换，避免频繁 ctl 带来的红黑树操作开销。

8.2 调优参数速查表

参数	默认值	推荐生产值	风险
ulimit -n	1024	65535	无明显风险
fs.file-max	~100万	按内存调整	过高消耗内核内存
net.core.somaxconn	128	65535	过高浪费内存
net.ipv4.tcp_max_syn_backlog	128	8192~65535	影响半连接队列
MAX_EVENTS（应用层）	各框架不同	4096~16384	过大占栈空间

---

9. 演进方向与未来趋势

io_uring 的冲击：Linux 5.1 引入，5.10 趋于成熟。核心优势是共享内存环形队列（零拷贝）+ 真正支持磁盘 I/O 异步，IORING_OP_POLL_ADD 可完全替代 epoll。Redis、Nginx 正在评估集成。目标内核 >= 5.10 的新项目可考虑直接使用 liburing。短期内 epoll 仍是生产主流。

EPOLLEXCLUSIVE 持续演进：Linux 4.5 引入，解决多进程惊群，社区持续优化多核锁竞争，关注 kernel.org net-next 树中 eventpoll 相关 patch。

---

10. 面试高频题

【基础理解层】

Q：select、poll、epoll 的主要区别？
A：select fd 上限 1024，每次调用全量拷贝 fd 集合，O(n) 扫描；poll 取消 1024 限制但仍 O(n) 全量扫描；epoll fd 持久化在内核红黑树，只返回就绪的 fd，O(1) 获取事件，O(log n) 注册/注销，适合高并发长连接。
考察意图：验证对 I/O 多路复用发展脉络的理解

Q：epoll 为什么用红黑树而不是哈希表？
A：红黑树无需 rehash，内存行为在内核分配器中更稳定；O(log n) 在 10 万 fd 以内与 O(1) 差距不足 1μs；哈希表扩容在内核实现复杂，最坏情况难以保证。
考察意图：数据结构选型的 trade-off 意识

【原理深挖层】

Q：事件如何从内核"推"到就绪链表？
A：epoll_ctl ADD 时，内核通过 target_file->f_op->poll() 将 ep_poll_callback 注册到目标 fd 的等待队列。fd 状态变化（如网卡数据到来，协议栈处理后唤醒 socket）时，内核在中断上下文调用此回调，回调持自旋锁将 epitem 插入 rdllist，并唤醒 epoll_wait 阻塞的进程。整个过程是内核主动推送，而非 epoll 轮询。
考察意图：内核回调机制和中断上下文的理解深度

Q：LT 和 ET 在就绪链表处理上有何不同？
A：ep_send_events 将事件拷贝给用户态后，LT 模式检查 fd 是否仍就绪，若是则将 epitem 重新加回 rdllist，下次 epoll_wait 仍返回；ET 模式不重新入链，只有 fd 状态再次变化时才通过回调入链。因此 ET 下未读完数据内核不会再通知，必须循环读到 EAGAIN。
考察意图：LT/ET 内核实现差异的精确理解

Q：epoll_ctl 和 ep_poll_callback 并发执行时如何保证安全？
A：两者使用不同锁，操作不同数据结构：epoll_ctl 修改红黑树用 ep->mtx（互斥锁，可睡眠）；ep_poll_callback 修改就绪链表用 ep->lock（自旋锁，中断上下文不可睡眠）。ep_send_events 读取就绪链表时先持自旋锁转移到临时 txlist，最小化持锁时间。
考察意图：互斥锁 vs 自旋锁的使用场景理解

【生产实战层】

Q：ET 模式如何防止事件丢失？
A：（1）fd 必须 O_NONBLOCK；（2）EPOLLIN 后循环 read() 直到 EAGAIN；（3）多线程配合 EPOLLONESHOT，处理完后 EPOLL_CTL_MOD 重新 ARM；（4）注意 EPOLLERR/EPOLLHUP 始终上报；（5）accept 建议用 LT 或 EPOLLEXCLUSIVE 防漏连接。
考察意图：生产 ET 模式的编程规范和常见陷阱

Q：服务出现大量 “too many open files” 如何排查？
A：（1）lsof -p <pid> | wc -l 确认 fd 数量对比 ulimit -n；（2）lsof -p <pid> | sort | uniq -c | sort -rn 找 fd 类型分布；（3）socket 占多数则排查连接未 close 或 TIME_WAIT 过多；（4）短期 ulimit -n 65535；（5）根本修复：确保 epoll_ctl DEL → close 的顺序，排查 epfd 本身是否泄漏。
考察意图：生产问题排查能力

---

11. 文档元信息

验证声明

✅ 与 Linux 内核源码（5.15.x fs/eventpoll.c）一致性核查
✅ 与 Linux man page epoll(7)、epoll_ctl(2)、epoll_wait(2) 核查
⚠️ 以下内容未经本地环境验证，仅基于文档推断：
   - §8.2 ET vs LT 性能提升 30%~50% 的具体数值（场景强相关）
   - §4.1 各方案延迟对比数值（硬件强相关）

参考资料

• 官方文档：https://man7.org/linux/man-pages/man7/epoll.7.html
• 内核源码：https://elixir.bootlin.com/linux/v5.15/source/fs/eventpoll.c
• C10K 问题原文：http://www.kegel.com/c10k.html
• Linux Kernel Development - Robert Love, Chapter 5
• Nginx epoll 模块：src/event/modules/ngx_epoll_module.c
• Redis ae 事件循环：src/ae_epoll.c
• io_uring 论文：https://kernel.dk/io_uring.pdf

---