Why epoll Uses Red-Black Trees for High-Performance Linux Networking

1. What is epoll?

epoll is a Linux kernel I/O multiplexing mechanism for efficiently managing large numbers of file descriptors. It solves the performance bottlenecks of select and poll in high-concurrency scenarios.

1.1 Limitations of select/poll

Linear scan problem : select and poll copy all FDs to kernel and scan linearly, O(n) time, causing performance drop with tens of thousands of FDs.

No state preservation : each call retransmits the whole FD set, increasing user‑kernel interaction overhead.

Hard limits : select limited by FD_SETSIZE (usually 1024); poll has no hard limit but still degrades linearly.

1.2 epoll improvements

Event registration : epoll_ctl registers FDs into a kernel event table, avoiding repeated copying.

Callback notification : kernel actively notifies user‑space of interested events, eliminating active polling.

Efficient data structure : uses a red‑black tree for O(log n) insert and lookup.

2. Red‑Black Tree characteristics and advantages

Red‑black tree is a self‑balancing binary search tree with key properties:

Insertion, deletion, lookup run in O(log n).

Balance maintained via color marks and rotations, keeping height at log n.

Ordered traversal supports fast search and dynamic updates.

2.1 Why choose a red‑black tree?

In epoll, the red‑black tree manages registered FDs and their events, offering:

2.2.1 Efficient FD registration and management

Insertion: epoll_ctl(EPOLL_CTL_ADD, fd, event) inserts fd into the tree with O(log n) cost.

Memory efficiency: no need to pre‑allocate large memory, suitable for dynamic FD sets.

2.2.2 Fast event query and trigger

When an FD changes state, the kernel quickly locates the node in the tree and adds the event to the ready list.

Ready‑list separation: the tree stores all registered FDs, while the ready list holds only active ones; epoll_wait traverses the ready list in near O(1) time.

2.2.3 Kernel implementation details

struct eventpoll

: represents an epoll instance, containing the red‑black tree root and the ready list. struct epitem: red‑black tree node storing FD and event information.

Key code fragment (simplified):

struct eventpoll {
    struct rb_root rbr; // red‑black tree root
    struct list_head rdllist; // ready list
    ...
};

struct epitem {
    struct rb_node rbn; // red‑black tree node
    struct list_head rdllink; // ready list node
    struct epoll_filefd ffd; // file descriptor
    struct eventpoll *ep; // owning epoll instance
    ...
};

3. epoll workflow and red‑black tree usage

3.1 Core components

epoll instance created by epoll_create, containing a red‑black tree and a ready list.

Red‑black tree stores all registered FDs and their event info.

Ready list holds FDs that are currently ready; epoll_wait returns them.

Illustration:

+-----------------------------+
| epoll instance (kernel)     |
| 1. Red‑black tree (rbtree)  |
|    - stores all registered FD|
|    - O(log n) insert/delete |
| 2. Ready list               |
|    - stores ready FD       |
|    - epoll_wait scans it   |
+-----------------------------+

3.2 Workflow diagram

+-------------------+       +---------------------+
| User program      |       | Kernel (epoll)      |
| epoll_create()    | ----> | creates tree & list |
| epoll_ctl(ADD)    | ----> | inserts FD into tree|
| epoll_wait()      | <---- | returns ready list  |
+-------------------+       +---------------------+

3.3 Key operations

epoll_create : creates an epoll instance, allocates a red‑black tree and a ready list, returns an epoll file descriptor.

epoll_ctl(ADD/MOD/DEL) : adds, modifies, or removes an FD in the red‑black tree; operations run in O(log n).

Event trigger : when an FD becomes ready, the kernel moves it from the tree to the ready list.

epoll_wait : user‑space calls to retrieve events; only the ready list is traversed, achieving near O(1) time.

3.4 Trigger modes

Edge Triggered (ET) : notifies only on state change, suitable for non‑blocking I/O.

Level Triggered (LT) : notifies as long as the FD remains ready; default mode with broader compatibility.

4. Performance comparison: select vs poll vs epoll

epoll removes the hard FD limit, provides O(1) event notification, copies FD set only during registration, and uses a callback‑driven model, making it ideal for high‑concurrency (>10 000) workloads, whereas select and poll suffer O(n) complexity and lower scalability.

5. Summary

epoll chooses a red‑black tree because it efficiently manages massive numbers of file descriptors with O(log n) operations, solving the performance bottlenecks of select and poll. In high‑concurrency scenarios, epoll is the preferred Linux networking solution, and the red‑black tree is the key to its performance.