Linux Event Loops & Async I/O: epoll vs io_uring

Building web servers, high-concurrency proxies (like Nginx, HAProxy, and Envoy), or async runtimes (Node.js, Tokio, and libuv) requires handling tens of thousands of concurrent open socket connections (the C10K / C1000K problem).

Over the last 25 years, Linux async I/O has evolved through three distinct paradigms: select / poll, epoll, and io_uring.

---

1. Summary & Key Takeaways

• POSIX select() / poll() Bottleneck: Scans the entire file descriptor array linearly ($O(N)$) on every loop iteration. With 10,000 open sockets, inspecting 5 active sockets forces 10,000 array checks in the kernel.
• Linux epoll ($O(1)$): Uses an in-kernel Red-Black Tree to track open sockets and a Ready List populated by NIC interrupts. Calling epoll_wait() returns only active file descriptors in $O(1)$ time.
• Linux io_uring: Eliminates kernel context switch overhead entirely! Uses a pair of lock-free circular ring buffers - a Submission Queue (SQ) and a Completion Queue (CQ) - shared directly between user space and the kernel via mapped memory.
• Zero-Syscall Mode (IORING_SETUP_SQPOLL): A kernel thread polls the Submission Queue directly, allowing user applications to submit read/write I/O requests with zero system calls.

---

2. Interactive Async I/O & Event Loop Benchmark

Simulate workload performance below with up to 10,000 concurrent sockets across POSIX select, Linux epoll, and io_uring!

Linux Async I/O & Event Loop Benchmark

Compare O(N) select/poll vs O(1) epoll vs Zero-Syscall io_uring Ring Buffers

select / poll O(N)epoll O(1)io_uring Ring

Concurrent Network Sockets:1,000 Connections

Simulate Workload

Submission Queue (SQ)

User Space writes I/O requests without syscalls

0 Entries

Completion Queue (CQ)

Kernel posts completed I/O results asynchronously

0 Completed

Processed Events0

Kernel Syscalls0 (Polled Ring)

Time ComplexityO(1) Ring

---

3. Kernel Architecture Comparison

graph TD
    subgraph Select["POSIX select / poll"]
    A1["App User Space"] -->|"1. Syscall 10k FDs"| K1["Kernel Array Scan O(N)"]
    K1 -->|"2. Copy Active List"| A1
    end

    subgraph Uring["Linux io_uring Ring"]
    U2["App User Space"] -->|"Push SQEs"| SQ["Submission Queue Ring"]
    SQ -->|"SQPOLL Kernel Thread"| CQ["Completion Queue Ring"]
    CQ -->|"Read CQEs (0 Syscalls)"| U2
    end

---

4. Async I/O Protocol Matrix

Interface	Time Complexity	Kernel Copy per Loop	Syscalls per I/O	Max Concurrency
select()	$O(N)$ Linear	Copy full FD set	1 per loop iteration	1,024 (FD_SETSIZE)
poll()	$O(N)$ Linear	Copy array of pollfd	1 per loop iteration	Unlimited (RAM bounded)
epoll()	$O(1)$ Constant	None (Red-Black Tree)	1 per batch (epoll_wait)	Millions
io_uring	$O(1)$ Constant	Zero (Shared Mapped Ring)	Zero (SQPOLL mode)	Millions