Operating System & Network I/O: Epoll, Event Loops, Direct I/O, and Linux io_uring

1. Problem and Motivation

In the late 1990s, Dan Kegel formulated the C10K Problem: how can a web server handle 10,000 concurrent client connections simultaneously on a single machine?

At the time, operating systems and servers (such as Apache HTTPD 1.3) allocated one OS thread per client connection:

+---------------------------------------------------------------------------------------------------+
|                                THE ONE-THREAD-PER-CLIENT COLLAPSE                                 |
+---------------------------------------------------------------------------------------------------+
|  1. Thread Memory Overhead: Each thread allocates an 8 MB stack by default in Linux. 10,000      |
|     threads consume 80 Gigabytes of RAM strictly for stack pointers before serving a byte.       |
|  2. Kernel Context Switching: When thousands of threads become ready simultaneously, the CPU      |
|     spends 80% of its execution cycles saving and restoring CPU registers, flushing Translation   |
|     Lookaside Buffers (TLB), and thrashing L1/L2 caches rather than executing application code.   |
|  3. Lock Contention & Thread Thrashing: Operating system run-queues become clogged; scheduling    |
|     latency jumps from microseconds to hundreds of milliseconds.                                  |
|  4. The Syscall Overhead Tax: In the post-Spectre/Meltdown era, every system call incurs kernel   |
|     page-table isolation (KPTI) switches, costing 1,000+ CPU cycles per invocation.              |
+---------------------------------------------------------------------------------------------------+

Modern systems software—NGINX, Node.js, Redis, Envoy, and Netty—solved C10K and now routinely scale to C10M (10 million concurrent connections) by moving to Non-Blocking Asynchronous Event-Driven Architectures powered by the Linux kernel’s epoll and io_uring subsystems.

2. Mental Model & Architectural Overview

The operating system I/O stack bridges hardware block devices, memory buffers, and user-space processes:

SYSTEM ARCHITECTURE BLUEPRINTCOMPUTER ARCHITECTURE

⤢Expand

ARCHITECTURAL FLOW · STEP 1 OF 4

1. Traditional read()/write() Multi-Copy Overhead

Standard read/write requires 4 context switches and 2 CPU memory copies (Page Cache -> User Buffer -> Socket Buffer), thrashing CPU L1/L2 caches.

Architectural Invariant: Memory Bus Contention: Copying 10Gbps across the system bus wastes up to 60% of CPU cycles purely on memory movement.

ARCHITECTURAL FLOW · STEP 2 OF 4

2. Zero-Copy sendfile() & Scatter-Gather DMA

sendfile(2) eliminates CPU copies: disk controller DMAs data into Page Cache, and NIC DMAs directly from Page Cache via header descriptors.

Architectural Invariant: Throughput Multiplier: Zero CPU data copying enables NGINX and Kafka to achieve line-rate saturation (40GbE+) with single-digit CPU usage.

ARCHITECTURAL FLOW · STEP 3 OF 4

3. Linux epoll O(1) Ready List Mechanics

Sockets are stored in a kernel Red-Black tree. When a packet arrives, the NIC hardware interrupt triggers ep_poll_callback(), inserting the socket into a Ready List in O(1).

Architectural Invariant: C10K to C1000K: Unlike select/poll which scan all O(N) sockets linearly, epoll_wait() returns only the active O(1) ready descriptors.

ARCHITECTURAL FLOW · STEP 4 OF 4

4. Linux io_uring: Lockless Shared-Memory Queues

Application and kernel share Submission Queue (SQ) and Completion Queue (CQ) via mmap(2). With SQPOLL enabled, kernel polling processes requests with ZERO syscalls.

Architectural Invariant: Syscall Overhead Elimination: Post-Spectre/Meltdown page table isolations made syscalls expensive; io_uring achieves sub-microsecond NVMe/network IOPS.

The Three Foundational Paradigms:

1. Multiplexed Event Loops (epoll): A single thread (or one thread per CPU core) monitors hundreds of thousands of active socket file descriptors. When a network packet arrives, the kernel notifies the event loop in $O(1)$ time, allowing one thread to interleave requests across thousands of clients without context switching.
2. Zero-Copy Data Pipelines (sendfile): Traditional file transfers require staging data through user-space RAM buffers. Zero-copy primitives instruct the kernel to stream data directly from the OS Page Cache to network interface cards via DMA, eliminating CPU memory bus traffic.
3. Lockless Shared Ring Buffers (io_uring): Rather than executing synchronous system calls, applications submit I/O requests to an in-memory Submission Queue (SQ) ring and collect completed operations from a Completion Queue (CQ) ring, achieving true asynchronous zero-syscall execution.

Foundational Bridge: DNS Resolution, TCP Handshake, Congestion Control & HTTP/1.1–HTTP/3 Multiplexing

Understanding kernel socket I/O requires tracing how client packets traverse the network stack before reaching epoll or io_uring:

1. Hierarchical DNS Resolution & Anycast: A client resolves api.example.com by querying a recursive resolver, which traverses the Root (.), TLD (.com), and Authoritative nameservers (cached via TTLs). Production ingress pairs authoritative DNS with BGP Anycast so TCP connections terminate at the topologically nearest edge Point of Presence (PoP).
2. TCP 3-Way Handshake & Bandwidth-Delay Product (BDP):
   • Establishing a TCP connection requires SYN $\to$ SYN-ACK $\to$ ACK ($1\text{ RTT}$) before application bytes flow, plus $1\text{ RTT}$ for TLS 1.3 key exchange (unless 0-RTT session resumption is active).
   • Maximum single-connection throughput is bounded by the Bandwidth-Delay Product: $$\text{BDP}=\text{Bandwidth}\times \text{RTT},{\text{Throughput}}_{\max }=\frac{\text{Receive Window (RWND)}}{\text{RTT}}$$
   • Congestion Control (CUBIC vs. BBR): Traditional loss-based CUBIC halves the congestion window (cwnd) on packet loss, mistaking shallow switch buffer drops for congestion. Google’s BBR (Bottleneck Bandwidth and Round-trip propagation time) probes actual delivery rate and minimum RTT, sustaining $2\times \text{–}10\times$ higher throughput over lossy WAN links without inducing bufferbloat.
3. Protocol Evolution & Head-of-Line (HoL) Blocking:
   • HTTP/1.1: Serializes requests per TCP socket; without pipelining, $K$ concurrent requests require $K$ TCP connections, exhausting ephemeral ports and memory.
   • HTTP/2: Multiplexes binary frames (HEADERS, DATA) over a single TCP connection with HPACK header compression. This solves application-layer HoL blocking, but suffers from transport-layer HoL blocking: a single lost TCP packet stalls all multiplexed HTTP/2 streams inside the kernel until TCP retransmits the missing sequence number.
   • HTTP/3 (QUIC over UDP): Moves stream multiplexing and TLS 1.3 encryption into userspace over UDP. Each QUIC stream is sequenced independently—a lost UDP datagram stalls only the single affected stream while all other streams continue delivering bytes immediately.

3. Terminology & Core Mechanics

• File Descriptor (FD): An unsigned integer index maintained by the OS kernel in a process’s file table, representing an open file, socket, pipe, or device.
• Blocking vs. Non-Blocking I/O: In blocking mode (O_NONBLOCK unset), calling read() suspends the thread until data arrives. In non-blocking mode, read() returns immediately with EAGAIN or EWOULDBLOCK if no bytes are ready.
• DMA (Direct Memory Access): A hardware capability allowing disk controllers and network cards to read and write directly to system DRAM without CPU intervention.
• Page Cache: The Linux kernel’s unified in-memory cache holding pages read from or written to persistent block storage.
• Context Switch: The process of storing the state of a CPU (registers, program counter, stack pointer) and switching execution from user space to kernel space (or between two threads).
• Direct I/O (O_DIRECT): A flag passed to open(2) instructing the Linux kernel to bypass the Page Cache entirely, streaming data directly between user buffers and disk blocks.
• io_uring: A high-performance asynchronous Linux system call interface introduced by Jens Axboe in kernel 5.1, based on shared memory ring buffers.

4. Internal Workings & Algorithms

1. The Multiplexing Evolution: select vs. poll vs. epoll

+---------------------------------------------------------------------------------------------------+
|                                 I/O MULTIPLEXING EVOLUTION                                        |
+---------------------------------------------------------------------------------------------------+
| Feature            | select(2) (1983)           | poll(2) (1997)           | epoll(7) (2002)              |
+--------------------+----------------------------+--------------------------+------------------------------+
| Data Structure     | Fixed-size bitmask (1024)  | Array of struct pollfd   | Red-Black Tree + Ready List  |
| Max Monitored FDs  | Fixed limit: 1024          | Unlimited                | Unlimited                    |
| Syscall Overhead   | Re-copies bitmask each time| Re-copies array each time| Sockets registered ONCE      |
| Time Complexity    | O(N) linear kernel scan    | O(N) linear kernel scan  | O(1) event return            |
| Notification Model | Level-Triggered only       | Level-Triggered only     | Level-Triggered & Edge-Trig  |
+--------------------+----------------------------+--------------------------+------------------------------+

How epoll Achieves $O(1)$ Performance:

1. The Interest Tree (Red-Black Tree): When an application registers a socket with epoll_ctl(epfd, EPOLL_CTL_ADD, fd, &ev), the kernel inserts the descriptor into an internal red-black tree (epitem). Adding, searching, and removing descriptors takes $O(\log N)$ time and happens only once per connection lifecycle.
2. The Hardware Interrupt Callback: When network packets arrive at the physical NIC, the NIC triggers an interrupt. The driver processes the packet and executes the internal kernel callback ep_poll_callback().
3. The Ready List (Doubly Linked List): The callback immediately appends the ready socket’s epitem to a doubly linked list (rdllist) in $O(1)$ constant time.
4. The epoll_wait() Invocation: When the event loop calls epoll_wait(epfd, events, maxevents, timeout), the kernel checks if rdllist is non-empty. If so, it copies only the active ready events to user space and returns in $O(1)$ time. It never scans idle sockets.

2. Level-Triggered (LT) vs. Edge-Triggered (ET)

[ Incoming Socket Buffer: 4096 bytes arrive ]
                    |
                    v
          +-------------------+
          | epoll_wait() fires|
          +-------------------+
                    |
                    v
    Application reads only 1024 bytes (3072 bytes remain)
                    |
                    +------------------------------------+
                    |                                    |
                    v                                    v
       Level-Triggered (LT):                 Edge-Triggered (ET):
   Next epoll_wait() FIRES AGAIN!        Next epoll_wait() DOES NOT FIRE!
   (Because buffer is still not empty)   (Waits for NEW state transition!)
                                         Unread 3072 bytes are STUCK!

3. Zero-Copy Mechanics: sendfile(2)

When serving a static file (e.g., streaming a video or serving a web asset):

Traditional I/O (4 Copies, 4 Context Switches):
Disk -> [DMA Copy] -> Page Cache -> [CPU Copy] -> User RAM -> [CPU Copy] -> Socket Buffer -> [DMA Copy] -> NIC
Context Switches: 1. read() enter, 2. read() exit, 3. write() enter, 4. write() exit.

Zero-Copy sendfile() (0 CPU Copies, 2 Context Switches):
Disk -> [DMA Copy] -> Page Cache ------------------------------> [Scatter-Gather DMA] --------------> NIC
                                      |
                                      +-> (Only small descriptor copied to Socket Buffer)
Context Switches: 1. sendfile() enter, 2. sendfile() exit.

By keeping data entirely within the Page Cache and using Scatter-Gather DMA, the CPU memory bus is completely bypassed, liberating memory bandwidth for application logic.

5. Mathematical & Performance Model

1. Memory Bandwidth Savings of Zero-Copy

Let:

• $V$: Volume of data served per second ($10\text{ GB/sec}=80\text{ Gbps}$ line rate).
• $B_{\text{RAM}}$: DDR5 memory bus bandwidth ($\approx 50\text{ GB/sec}$).

Under Traditional I/O (2 CPU memory copies): $$\text{Memory Bus Traffic}=2\times V=2\times 10\text{ GB/s}=20\text{ GB/s}$$ Memory bus utilization: $$\text{Bus Utilization}=\frac{20\text{ GB/s}}{50\text{ GB/s}}=40\%$$ $40\%$ of all system memory bandwidth is wasted copying identical bytes across cache lines!

Under Zero-Copy sendfile(2): $$\text{CPU Memory Copies}=0⟹\text{Memory Bus Waste}=0\text{ GB/s}$$ Memory bus utilization drops to $0\%$, allowing the server to saturate multiple 100 GbE network cards without CPU memory bus saturation.

2. Syscall Elimination in io_uring

In high-IOPS storage workloads (such as NVMe SSDs delivering 1,000,000 IOPS):

• Syscall cost: $t_{\text{syscall}}\approx 800\text{ nanoseconds}$ (with KPTI and Retpoline mitigations).
• Time spent solely in kernel context switching for 1M IOPS: $$T_{\text{context}}=10^6\times 800\text{ ns}=0.8\text{ seconds per second}=80\%\text{ of 1 CPU core!}$$

Under io_uring with IORING_SETUP_SQPOLL:

• The application writes submission entries to shared memory.
• A kernel kthread polls the ring buffer without syscalls.
• Syscall overhead = $0\text{ nanoseconds}$, freeing up to $80\%$ of CPU cycles for database query evaluation.

6. Real Implementation & Systems Comparison

7. Production Code Engine: Event Loop & epoll Simulator

The following TypeScript implementation demonstrates the core architecture of an event-driven runtime (like libuv / Node.js), featuring an $O(1)$ ready queue, non-blocking descriptor polling, and a priority timer min-heap:

/**
 * Production-Grade Event Loop & I/O Multiplexer Simulator
 * Demonstrates epoll-style readiness registration, non-blocking reads, and timer scheduling.
 */

export interface EpollEvent {
  fd: number;
  events: 'EPOLLIN' | 'EPOLLOUT' | ('EPOLLIN' | 'EPOLLOUT')[];
  handler: (fd: number) => void;
}

export class EpollSimulator {
  // Kernel Red-Black Tree simulation: Monitored Descriptors
  private monitoredFds = new Map<number, EpollEvent>();
  // Kernel Ready List (Doubly linked list simulation)
  private readyList: number[] = [];
  // Simulated socket buffers in kernel space
  private socketBuffers = new Map<number, Uint8Array>();

  public ctl(op: 'ADD' | 'DEL', fd: number, event?: EpollEvent): void {
    if (op === 'ADD' && event) {
      this.monitoredFds.set(fd, event);
    } else if (op === 'DEL') {
      this.monitoredFds.delete(fd);
      this.readyList = this.readyList.filter((id) => id !== fd);
    }
  }

  /**
   * Simulates NIC hardware interrupt: packet arrival triggers kernel callback
   */
  public injectNetworkPacket(fd: number, data: Uint8Array): void {
    this.socketBuffers.set(fd, data);
    if (this.monitoredFds.has(fd) && !this.readyList.includes(fd)) {
      // O(1) append to ready list
      this.readyList.push(fd);
    }
  }

  /**
   * epoll_wait: Returns only active file descriptors in O(1) time
   */
  public wait(): number[] {
    const active = [...this.readyList];
    this.readyList = []; // Drained for Level-Triggered re-evaluation
    return active;
  }

  public readNonBlocking(fd: number): Uint8Array | null {
    const buffer = this.socketBuffers.get(fd);
    if (!buffer || buffer.length === 0) {
      return null; // EAGAIN / EWOULDBLOCK
    }
    this.socketBuffers.delete(fd);
    return buffer;
  }
}

/**
 * Single-Threaded Reactor Event Loop
 */
export class ReactorEventLoop {
  private isRunning = false;
  public epoll = new EpollSimulator();
  private timers: { executeAt: number; callback: () => void }[] = [];

  public setTimeout(callback: () => void, delayMs: number): void {
    this.timers.push({ executeAt: Date.now() + delayMs, callback });
    this.timers.sort((a, b) => a.executeAt - b.executeAt);
  }

  /**
   * One tick of the event loop
   */
  public tick(): void {
    const now = Date.now();

    // 1. Execute expired timers
    while (this.timers.length > 0 && this.timers[0].executeAt <= now) {
      const timer = this.timers.shift()!;
      timer.callback();
    }

    // 2. Poll I/O via epoll_wait
    const activeFds = this.epoll.wait();
    for (const fd of activeFds) {
      const data = this.epoll.readNonBlocking(fd);
      if (data) {
        // Process message in user space
        console.log(`[EventLoop] Received ${data.length} bytes from FD ${fd}`);
      }
    }
  }
}

function runDemo(): void {
  console.log("=== Operating Systems: Epoll & Reactor Event Loop Simulation ===");
  const reactor = new ReactorEventLoop();
  reactor.epoll.ctl('ADD', 10, {
    fd: 10,
    events: 'EPOLLIN',
    handler: (fd: number) => {
      console.log(`Handler invoked for ready descriptor FD ${fd}`);
    },
  });
  console.log("Registered non-blocking socket FD 10 in epoll interest list");
  reactor.epoll.injectNetworkPacket(10, new Uint8Array([72, 101, 108, 108, 111])); // "Hello"
  const readyFds = reactor.epoll.wait();
  console.log(`Epoll wait returned ${readyFds.length} ready file descriptors: [${readyFds.join(", ")}]`);
  for (const fd of readyFds) {
    const data = reactor.epoll.readNonBlocking(fd);
    console.log(`  Read ${data?.length} bytes from FD ${fd}`);
  }
}

runDemo();

8. Page Cache, Dirty Writeback & Direct I/O

The Linux Page Cache acts as a transparent caching layer between filesystems and disk hardware:

[ Application write(fd, buf, len) ]
                 |
                 v
+-------------------------------------------------------+
|                   LINUX PAGE CACHE                    |
| - Writes marked "Dirty" in RAM                        |
| - Syscall returns immediately (Latency < 2 us)        |
+-------------------------------------------------------+
                 |
                 | Asynchronous Per-BDI Flusher Threads ([kworker/u*:*-flush-*])
                 | Triggers when vm.dirty_background_ratio reached (default 10%;
                 | note: kswapd reclaims pages under free-memory pressure, whereas
                 | per-BDI flushers write back dirty pages in the background)
                 v
+-------------------------------------------------------+
|               PHYSICAL NVMe / SSD DISK                |
+-------------------------------------------------------+

The O_DIRECT Decision:

• Use Page Cache: Web servers, logs, and general apps benefit from read-ahead caching and asynchronous write buffering.
• Bypass Page Cache (O_DIRECT): High-performance database engines (such as MySQL InnoDB, ScyllaDB, and PostgreSQL’s proposed Direct I/O) manage their own internal buffer pools. Allowing the OS to cache pages causes Double Buffering (wasting 50% of RAM) and unpredictability from OS kernel page cache evictions.

9. Failure Modes, Operational War Stories & Debugging

10. Knowledge Check

Review the core operating system and I/O principles, then complete the 4-question interactive assessment quiz at the end of this lesson:

1. $O(1)$ epoll: Articulate why Red-Black tree registration and Ready List callbacks eliminate linear socket scanning.
2. Edge-Triggered Drain: Explain why sockets in EPOLLET mode must be read until EAGAIN or EWOULDBLOCK is returned.
3. Zero-Copy: Trace how sendfile(2) bypasses CPU RAM copies and cuts context switches from 4 to 2.
4. io_uring: Contrast the lockless ring buffer design of io_uring with traditional system-call based I/O.

11. Practical Exercises & Deliverables

Exercise 1: Benchmark sendfile(2) vs. read()/write()

Problem: Measure the throughput difference between standard buffer copying and kernel zero-copy file transmission.
Deliverable:

1. Write a C, Rust, or Go program that serves a 1 GB file over a local TCP socket using standard 64 KB read() + write() buffers.
2. Implement an alternative serving path using sendfile(2).
3. Measure CPU utilization, context switches (perf stat), and memory bandwidth. Prove that zero-copy slashes CPU utilization by over 60%.

Exercise 2: Simulate Event Loop Starvation

Problem: A slow synchronous calculation blocks the entire single-threaded event loop, delaying all network I/O.
Deliverable:

1. Using the ReactorEventLoop class from Section 7, register 10 active network file descriptors.
2. Inject a blocking task that sleeps for 200ms inside an event callback.
3. Observe how subsequent network packets and timers are delayed. Refactor the code to partition the long task across multiple non-blocking event loop ticks.

12. Summary & Architectural Decision Guide

• Use epoll (Level-Triggered) for standard network servers (NGINX, Redis) where robustness against partial reads and manageable debugging complexity are paramount.
• Use epoll (Edge-Triggered) only with non-blocking sockets in an explicit EAGAIN drain loop when event notification overhead must be minimized.
• Use io_uring (Linux 5.1+) for high-throughput disk I/O, storage engines (RocksDB, PostgreSQL 17+ async I/O experiments), or ultra-dense socket multiplexing (>100k connections) to eliminate syscall boundary crossing.
• Use O_DIRECT with Custom Buffer Pools in relational and analytical database engines to avoid double-caching and unpredictable OS dirty-page writeback stalls.

13. Authoritative References & Version Context

• Jens Axboe (2019), “Efficient IO with io_uring”, Linux Kernel Technical Whitepaper — kernel.dk/io_uring.pdf
• Jonathan Corbet, Alessandro Rubini, and Greg Kroah-Hartman (2005), “Linux Device Drivers (3rd Edition)”, O’Reilly Media (Chapter 15: Memory Mapping and DMA) — lwn.net/Kernel/LDD3/
• Linux Manual Pages — epoll(7), epoll_ctl(2), and io_uring(7) — man7.org/linux/man-pages/man7/epoll.7.html
• Version Context: Linux kernel epoll invariants apply from Linux 2.6 through 6.x; io_uring specifications reflect Linux 5.1+ baseline and 6.x production features (IORING_FEAT_NODROP, SQPOLL).