Understanding Non-Blocking I/O: From select() to epoll, kqueue, and io_uring

Every high-throughput network engine—from Node.js and Nginx to Redis, Envoy, and Netty—relies on an event loop. At the foundation of every event loop sits an operating system syscall that answers one deceptively simple question:

“Out of these 100,000 active client connections, which ones have data ready for me to read or write right now without blocking?”

How operating systems answered this question over the last thirty years is one of the most fascinating engineering journeys in systems programming. This article traces that evolution from $O(N)$ linear scans in select() to $O(1)$ event callbacks in epoll/kqueue, and finally to true zero-syscall asynchronous I/O with io_uring.

1. The Naive Era: Thread-per-Connection and the C10K Problem

In the 1990s, early web servers like Apache MPM Prefork handled concurrency by dedicating a thread or process to each active TCP connection:

// Blocking server loop
while (1) {
    int client_fd = accept(server_fd, ...);
    pthread_create(&thread_id, NULL, handle_client, (void*)(intptr_t)client_fd);
}

This model works when handling a few hundred concurrent users. But as internet traffic surged, servers hit what Dan Kegel famously termed the C10K problem in 1999: handling 10,000 simultaneous connections on a single machine.

Thread-per-connection falls apart due to two physical bottlenecks:

1. Memory overhead: Each thread requires a dedicated stack ($2\text{ MB}$ to $8\text{ MB}$ by default). 10,000 threads consume $20\text{--}80\text{ GB}$ of RAM purely in idle stack allocations.
2. Context-switching thrashing: When thousands of threads wake up simultaneously, the CPU spends more cycles saving/restoring CPU registers and invalidating L1/L2 CPU caches than executing application logic.

To scale, servers needed a single thread capable of monitoring thousands of idle sockets simultaneously.

2. The First Multi-Descriptor Syscalls: select() and poll()

POSIX introduced select() in 1983 to monitor multiple file descriptors:

int select(int nfds, fd_set *readfds, fd_set *writefds, 
           fd_set *exceptfds, struct timeval *timeout);

Why select() Doesn’t Scale: $O(N)$ Copying and Scanning

select() has two fatal design flaws:

1. Fixed Descriptor Limit: fd_set is a fixed-size bitmask governed by FD_SETSIZE (hardcoded to 1024 on Linux). You cannot monitor descriptor 1025 without recompiling libc.
2. Double Linear Scanning: On every single call, the user program must copy the bitmask into the kernel. The kernel scans every descriptor from $0$ to $N-1$ to check readiness. When select() returns, the user program must again loop through all $N$ descriptors to find which bit flipped:

User Space                     Kernel Space
┌──────────────┐   select()   ┌─────────────────────────────┐
│  fd_set mask │ ───────────► │ Iterates over fds 0 to 1023 │
│  (1024 bits) │              │ Checks readiness on each... │
└──────────────┘              └──────────────┬──────────────┘
       ▲                                     │
       │                                     ▼
       └──────────────────────── Answers which fds are ready

Even if only 1 socket out of 1,000 has data, you pay an $O(N)$ computational tax on every iteration.

poll() eliminated the 1024 limit by accepting an array of struct pollfd, but the fundamental $O(N)$ kernel-copy and scan bottleneck remained identical.

3. The Modern Readiness Paradigm: epoll and kqueue

In the early 2000s, kernel designers realized: The set of monitored sockets changes slowly, but readiness events happen constantly.

Instead of re-passing thousands of descriptors to the kernel every millisecond, why not tell the kernel once which descriptors to track?

• Linux introduced epoll (Linux 2.6, 2002)
• FreeBSD / macOS introduced kqueue (FreeBSD 4.1, 2000)

Inside epoll’s Kernel Data Structures

When you call epoll_create(), the Linux kernel allocates two internal data structures inside kernel memory:

                epoll instance (epfd)
                          │
       ┌──────────────────┴──────────────────┐
       ▼                                     ▼
┌──────────────────────────────┐   ┌──────────────────────────────┐
│       Red-Black Tree         │   │          Ready List          │
│                              │   │                              │
│ Stores monitored fds (O(logN)│   │ Doubly-linked list of events │
│ fast insertion, search, del) │   │ that fired readiness         │
└──────────────────────────────┘   └──────────────┬───────────────┘
                                                  │
                                                  ▼
                                       epoll_wait() returns
                                       ONLY active events in O(1)

1. Red-Black Tree: Tracks all file descriptors registered via epoll_ctl(EPOLL_CTL_ADD). Inserting or deleting a descriptor is $O(\log N)$.
2. Ready List (Doubly-Linked List): When network packets arrive at a Network Interface Card (NIC), hardware interrupts trigger socket receive callbacks. The kernel driver directly places only the active file descriptor into epoll’s Ready List.

When user code calls:

int n = epoll_wait(epfd, events, MAX_EVENTS, timeout);

The kernel doesn’t scan anything. If 3 sockets have data, it copies exactly those 3 items into the user-space events array in $O(1)$ time.

4. Level-Triggered vs. Edge-Triggered Polling

epoll supports two event delivery semantics:

Level-Triggered (Default)

epoll_wait() notifies you repeatedly as long as the socket buffer contains unread bytes. If 1,000 bytes arrive and you read 200 bytes, the next epoll_wait() will immediately wake up again for the remaining 800 bytes. This is safe and forgiving.

Edge-Triggered (EPOLLET)

epoll_wait() notifies you only when the state changes (e.g. from no data to new data arriving). If you don’t read all 1,000 bytes in a single loop until getting EAGAIN or EWOULDBLOCK, the remaining bytes sit stranded in the buffer and you will never receive another notification!

// Edge-Triggered Read Pattern: MUST drain completely
while (1) {
    ssize_t count = read(fd, buf, sizeof(buf));
    if (count == -1) {
        if (errno == EAGAIN || errno == EWOULDBLOCK) {
            // Buffer is completely drained, return to epoll_wait
            break;
        }
        perror("read error");
        break;
    } else if (count == 0) {
        // Client closed connection
        close(fd);
        break;
    }
    process_data(buf, count);
}

5. The Next Frontier: io_uring

Even with epoll, high-performance storage or network servers spend up to $30\text{--}40\%$ of CPU time in syscall overhead (switching between User Space and Kernel Ring 0, executing TLB flushes, and mitigating CPU speculative execution vulnerabilities like Meltdown/Spectre).

In 2019, Jens Axboe introduced io_uring into Linux 5.1:

Rather than telling you when a socket is ready to read (synchronous notification), io_uring performs true asynchronous completion: you tell the kernel “read 4KB from fd into this buffer,” and the kernel executes it asynchronously.

User Space                                           Kernel Space
┌────────────────────────────────┐                 ┌──────────────────┐
│  Submission Queue (SQ Ring)    │ ──Lockless───►  │  Kernel Worker   │
│  [Op 1: Read fd 5 into buf_a]  │   Shared Ring   │  Executes DMA /  │
│  [Op 2: Write fd 8 from buf_b] │   Buffer        │  Socket read     │
└────────────────────────────────┘                 └────────┬─────────┘
                                                            │
┌────────────────────────────────┐                          │
│  Completion Queue (CQ Ring)    │ ◄──Lockless──────────────┘
│  [Result 1: 4096 bytes read]   │    Shared Ring
│  [Result 2: 128 bytes written] │    Buffer
└────────────────────────────────┘

Why io_uring is Revolutionary:

• Lock-Free Ring Buffers: User space and kernel space communicate across memory-mapped circular ring buffers without locks.
• Batched Syscalls: A program can enqueue 50 read/write operations into the Submission Queue (SQ) and execute them with a single io_uring_enter() syscall.
• Kernel Polling Mode (IORING_SETUP_SQPOLL): A dedicated kernel thread can poll the ring buffer continuously. Submitting and consuming I/O operations requires zero syscalls!

6. Architectural Summary

Understanding this progression explains why modern runtimes have evolved the way they have. Whether you’re configuring an edge proxy in Go, fine-tuning an event loop in Rust with Tokio, or building network microservices in C, understanding the underlying kernel mechanism ensures your system scales predictably.