Why Is epoll So Fast? Deep Dive into Its Data Structures, Locking and ET/LT Modes

Overview

Candidates interviewing at top internet companies often encounter questions about epoll’s data structures, implementation principles, interaction with the protocol stack, thread‑safety locking, and the distinction between ET and LT modes. This article provides a systematic, interview‑ready analysis.

epoll Data Structures

epoll maintains at least two collections:

Total set of file descriptors (fd)

Ready‑fd set

Each fd maps to a TCB, forming a key‑value pair (key=fd, value=TCB). Three possible in‑memory structures are considered:

Hash table – O(1) lookup but cannot size the underlying array appropriately for unknown fd counts.

Red‑black tree – O(log N) lookup, requires only a root node at creation, no wasted space.

B/B+ tree – Designed for disk indexes, unsuitable for pure memory use.

Consequently, the total fd set is stored in a red‑black tree, while the ready‑fd set, which is FIFO and has no priority, is stored in a linear queue.

struct epitem {
    RB_ENTRY(epitem) rbn;
    LIST_ENTRY(epitem) rdlink;
    int rdy; // exists in list

    int sockfd;
    struct epoll_event event;
};

struct eventpoll {
    ep_rb_tree rbr;
    int rbcnt;
    LIST_HEAD( ,epitem) rdlist;
    int rdnum;

    int waiting;
    pthread_mutex_t mtx; // rbtree update
    pthread_spinlock_t lock; // rdlist update
    pthread_cond_t cond; // block for event
    pthread_mutex_t cdmtx; // mutex for cond
};

Relationship Between Red‑Black Tree and Ready Queue

The same node participates in both structures: when a node becomes ready, its existing pointers are linked into the ready queue without deletion from the tree.

/* node layout shown above */

epoll Working Environment

Three parts interact:

Application APIs (epoll_create, epoll_ctl, epoll_wait)

epoll core (red‑black tree + ready queue)

Protocol‑stack callbacks (the stack parses packets and notifies epoll)

When the Protocol Stack Triggers Callbacks

For each fd, the five‑tuple (srcIP, srcPort, dstIP, dstPort, protocol) uniquely identifies the node in the red‑black tree. The callback receives the fd and event type, then:

Finds the corresponding node via the five‑tuple.

Adds the node to the ready queue.

The stack generates callbacks at five moments:

After the three‑way handshake completes (EPOLLIN).

After receiving data and sending ACK (EPOLLIN).

After sending data and receiving ACK (EPOLLOUT).

After receiving FIN and sending ACK (EPOLLIN).

After receiving RST and sending ACK (EPOLLERR).

Comparison with select/poll

select/poll must copy the entire fd set on each call, leading to O(N) overhead even when only a few fds are ready. epoll registers interest once (epoll_ctl) and only copies ready events (epoll_wait), avoiding the copy of the full set.

poll determines readiness by traversing all fds, which is slower at large scales. In low‑I/O scenarios poll can be faster, but beyond roughly 500–1024 fds epoll dominates.

Thread‑Safety Locking Strategy

Three APIs are available to user space:

epoll_create – creates a new red‑black‑tree root; no contention.

epoll_ctl – may modify the tree; requires a mutex lock on the entire tree.

epoll_wait – consumes the ready queue; requires a spinlock on the queue.

Callbacks that move nodes from the tree to the queue lock both structures (mutex for the tree, spinlock for the queue).

epoll_ctl()   → lock red‑black tree (mutex)
epoll_wait()  → lock ready queue (spinlock)
callback()   → lock red‑black tree (mutex) & ready queue (spinlock)

ET vs LT Implementation

Edge‑triggered (ET) fires only once when a condition becomes true; level‑triggered (LT) fires repeatedly as long as the condition remains true. The difference is realized by how many times the protocol‑stack callback is invoked: a single callback for ET, repeated callbacks for LT when data remains in buffers.

Implementation details can be seen in the Linux source file fs/eventpoll.c (function ep_send_events).

Conclusion

Understanding epoll’s red‑black‑tree storage, ready‑queue handling, protocol‑stack callbacks, locking mechanisms, and the ET/LT distinction equips candidates to answer interview questions confidently and demonstrate deep Linux I/O knowledge.