Linux Epoll Uses Red-Black Trees and Ready Lists to Bypass Linear File Descriptor Scans

For an event notification system to actually scale, the vast majority of monitored connections must be doing absolutely nothing. If every connected client sends data at the exact same millisecond, the operating system still has to process every single file descriptor.[4]

Under those saturated conditions, advanced data structures offer no mathematical advantage over a simple list. But modern internet traffic is overwhelmingly idle, providing the exact environment required for event-driven architectures to thrive.[4]

A standard web server might hold open tens of thousands of connections, while only a few dozen are actively transmitting packets at any given moment. This reality is the binding constraint that makes scalable polling mechanisms possible.[1]

Before the turn of the millennium, operating systems struggled to handle this ratio. In 1999, software engineer Dan Kegel coined the C10K problem, challenging the industry to build servers capable of handling 10,000 concurrent connections.[1]

The primary bottleneck was not hardware, but the Linux kernel's software architecture. At the time, applications relied on the legacy select and poll system calls to monitor network sockets, which operate on a fundamentally linear premise.[1][3]

Shifting the computational burden

When an application wants to know if data has arrived, it hands the kernel a complete array of every file descriptor it cares about. The kernel must then iterate through that entire array, checking the status of each socket one by one.[3]

If a server is monitoring 10,000 connections, the kernel performs 10,000 checks, even if only three sockets actually have data ready to read. This linear time complexity meant that as traffic grew, the CPU spent most of its time checking empty connections.[1][3]

"The problem with poll is that it requires the kernel to scan the entire list of file descriptors," researchers Gaurav Banga, Peter Druschel, and Jeffrey Mogul noted in their foundational 1999 paper on scalable multiplexing.[5]

They proposed that the operating system should maintain the state of interest across multiple system calls, rather than forcing the application to declare it every time. To break the linear scaling trap, the Linux kernel needed a mechanism that decoupled monitoring from readiness checks.[5]

In 2002, developer Davide Libenzi merged the epoll subsystem into Linux kernel version 2.5.44. It fundamentally redesigned how the operating system tracks network events by splitting the process into distinct setup and execution phases.

The hardware interrupt advantage

Instead of passing an array of sockets on every loop iteration, an application opens a dedicated file descriptor that represents the event queue itself. Applications then register, modify, or remove individual network sockets from this persistent monitoring list.[3]

Because the kernel now remembers which connections the application cares about, the computational cost is shifted entirely to the initial setup phase. To manage this persistent state efficiently, the kernel stores the monitored file descriptors in a red-black tree.[3]

This self-balancing binary search tree ensures that inserting a new connection, or finding an existing one to remove it, always occurs in logarithmic time. Even with millions of open sockets, the tree remains shallow and fast to navigate.

Storing the sockets efficiently is only half the solution. The true performance breakthrough lies in how the subsystem detects when data actually arrives, relying directly on the hardware interrupts generated by the network interface card.[3]

When a packet arrives over the network, the hardware interrupts the CPU, and the kernel's network stack processes the data. If the data belongs to a monitored socket, the kernel executes a specific callback function named ep_poll_callback.

Edge-triggered execution

This callback function takes the active file descriptor and appends it to a separate data structure known as the ready list. The ready list is a simple doubly linked list that contains only the sockets that currently have pending events.

The vast majority of idle sockets in the red-black tree are completely ignored during this process. When the user-space application finally asks for events, the kernel does not need to scan anything; it simply checks the ready list.[3]

This architecture reduces the time complexity of waiting for events to a constant factor, scaling strictly with the number of active connections. A server handling 10,000 connections with 50 active clients does the exact same amount of work as a server handling 100 connections with 50 active clients.[4]

Beyond its internal data structures, the subsystem introduced a critical behavioral shift for application developers by offering two distinct operating modes. The default behavior is level-triggered, which continuously notifies the application as long as unread data remains in the buffer.[3]

While level-triggered mode is easier to program, it can lead to redundant notifications if an application only reads part of the available data. To maximize throughput, high-performance web servers utilize edge-triggered mode, activated by a specific flag.[3]

Solving the thundering herd

In edge-triggered mode, the kernel only notifies the application once when the socket transitions from an idle state to a ready state. If the application fails to drain the entire buffer, the kernel will not send another notification until a completely new packet arrives.[3]

This forces developers to write non-blocking code that loops continuously until the socket indicates the buffer is truly empty. By draining the socket completely in user space, the application drastically reduces the number of expensive context switches required to cross the kernel boundary.[1][4]

"The edge-triggered mode is what allows modern proxies to handle hundreds of thousands of concurrent connections with a tiny memory footprint," the Factlen Editorial Team notes. "It treats the kernel notification as a starting gun, rather than a continuous alarm."[4]

Despite its asymptotic advantages, the original implementation struggled with specific multi-core scaling architectures. When multiple worker threads monitored the same listening socket for incoming connections, a single new connection would wake up every sleeping thread simultaneously.[2]

This phenomenon caused massive CPU spikes as dozens of threads woke up, context switched into kernel space, and attempted to accept the connection. Only one thread would succeed, while the others encountered an error and went back to sleep.[2]

The limits of system calls

"The sad state of Linux socket balancing meant that adding more CPU cores could actually decrease total server throughput," engineers at Cloudflare explained in a 2017 technical analysis. The contention on the shared lock negated the benefits of the ready list.[2]

To resolve this, kernel developers introduced an exclusive wakeup flag in Linux 4.5, released in March 2016. When applied, the kernel guarantees that an incoming event will wake up one, and only one, of the threads monitoring the socket.[3]

This targeted wakeup mechanism restored linear scaling across multiple CPU cores. It allowed modern load balancers to distribute incoming traffic evenly across 64-core or 128-core processors without triggering catastrophic lock contention during traffic spikes.[2]

For nearly two decades, the combination of red-black trees and hardware-driven ready lists made this architecture the undisputed standard for Linux network programming. It successfully solved the initial scaling crisis and expanded seamlessly to handle ten million concurrent connections.[1][4]

However, the mechanism is not entirely free of overhead. Even with a highly optimized ready list, the application must still execute a system call to retrieve the events, a privilege transition that takes approximately 200 to 300 nanoseconds on modern processors.[4]