epoll is a scalable I/O event notification mechanism in the Linux kernel, widely used by high-performance systems like Nginx, Redis, and Netty. Its design overcomes fundamental limitations of older approaches such as select and poll, enabling efficient handling of tens or even millions of concurrent file descriptors (FDs).

The Problem with select and poll

Traditional multiplexing APIs suffer from critical inefficiencies under load:

• Linear scanning: Every call requires the kernel to inspect all registered FDs, resulting in $O(n)$ time complexity.
• FD limits: select caps at 1024 FDs by default; poll removes this cap but retains inefficient scanning.
• Redundant copying: The full set of FDs must be copied from user space to kernel space on every call.
• Passive model: Applications must actively poll for readiness—there’s no push-based notification.

epoll addresses these by enabling the kernel to proactively notify only about ready FDs, reducing per-event cost to near $O(1)$.

Core Kernel Data Structures

epoll’s efficiency stems from three internal components:

Structure	Purpose	Implementation	Advantage
Red-black tree	Stores all monitored FDs and their associated events	Balanced BST	$O(\log n)$ insertion/deletion; scales to millions of FDs
Ready list	Holds FDs that have become ready for I/O	Doubly-linked list	Direct access to active events; no scanning needed
Callback hooks	Attached to each FD’s driver; triggered when data arrives	Function pointers	Enables automatic, zero-overhead readiness signaling

The red-black tree acts as a registry, the ready list as a work queue, and callbacks as event triggers.

Execution Workflow

epoll operates through four distinct phases:

1. Initialization (epoll_create)

Creates an epoll instanec in kernel memory and returns a file descriptor (epfd) used for subsequent operations.

int epfd = epoll_create1(0); // Modern variant; ignores size hint
if (epfd == -1) { /* handle error */ }

This epfd behaves like any other FD and is automatically cleaned up on process exit.

2. Registration (epoll_ctl)

Associates an FD with the epoll instance and specifies which events to monitor (e.g., EPOLLIN, EPOLLOUT).

struct epoll_event ev;
ev.events = EPOLLIN | EPOLLET; // Edge-triggered read monitoring
ev.data.fd = sock_fd;
epoll_ctl(epfd, EPOLL_CTL_ADD, sock_fd, &ev);

Crucially, the FD should be set to non-blocking mode to prevent read/write calls from stalling after an event fires.

Under the hood, the kernel inserts the FD into the red-black tree and registers a callback with the underlying device driver (e.g., network stack). When data arrives, the driver invokes this callback, which appends the FD to the ready list.

3. Waiting (epoll_wait)

Blocks until one or more FDs become ready—or until timeout:

struct epoll_event events[MAX_EVENTS];
int n = epoll_wait(epfd, events, MAX_EVENTS, -1); // -1 = indefinite wait

If the ready list is non-empty, the kernel copies only those entries to user space. If empty, the calling thread sleeps on an internal wait queue until woken by a callback.

Unlike select/poll, only ready FDs are copied—dramatically reducing overhead.

4. Event Processing

The application iterates over the returned events and performs I/O:

for (int i = 0; i < n; ++i) {
    if (events[i].data.fd == server_sock) {
        // Accept new connections
        while ((client = accept4(server_sock, NULL, NULL, SOCK_NONBLOCK)) != -1) {
            struct epoll_event cev = {.events = EPOLLIN | EPOLLET, .data.fd = client};
            epoll_ctl(epfd, EPOLL_CTL_ADD, client, &cev);
        }
    } else {
        // Handle client data
        char buf[4096];
        ssize_t bytes = read(events[i].data.fd, buf, sizeof(buf));
        if (bytes <= 0) {
            close(events[i].data.fd);
            epoll_ctl(epfd, EPOLL_CTL_DEL, events[i].data.fd, NULL);
        }
        // Process buf...
    }
}

In edge-triggered (ET) mode (EPOLLET), the application must consume all available data in one go—otherwise, it may miss subsequent notifications. Level-triggered (LT) mode (default) re-notifies until the FD is no longer readable/writable.

Why epoll Scales

Four key optimizations enable massive concurrency:

1. Event-driven architecture: Callbacks eliminate polling; only active FDs are processed.
2. Minimal data copying: FD sets are copied once during registration; epoll_wait returns only ready FDs.
3. Efficient data structures: Red-black tree for registration ($O(\log n)$), linked list for ready evants ($O(1)$ per event).
4. No artificial FD limits: Constrained only by system-wide file descriptor limits (ulimit -n).

Comparison with Legacy APIs

Feature	select	poll	epoll
Max FDs	~1024	Limited by RAM	System limit (~1M+)
Time complexity	$O(n)$	$O(n)$	$O(1)$ per event
Copy overhead	Full set per call	Full set per call	One-time + ready set
Trigger modes	LT only	LT only	LT + ET
Ideal use case	Low concurrancy	Moderate load	High-scale servers

Real-World Usage

epoll underpins modern high-throughput systems:

• Web servers (Nginx)
• In-memory databases (Redis)
• Network frameworks (Netty, libevent)
• Messaging platforms and IoT gateways requiring 100K+ concurrent connections

By offloading event detection to the kernel and minimizing unnecessary work, epoll provides the foundation for efficient, scalable I/O in Linux environments.