The C10K Problem and Beyond

In 1999 Dan Kegel wrote a short essay called “The C10K problem” (still online at www.kegel.com/c10k.html) asking a question that felt outrageous at the time: could a single server handle ten thousand simultaneous connections? The industry was building web servers with one-thread-per-connection and hitting a wall around 200-500 clients. Kegel catalogued the alternatives — non-blocking I/O with select, poll, kqueue, /dev/poll, and the then-experimental epoll patches — and made the case that C10K was a software architecture problem, not a hardware limit.

He was right. Within five years, nginx (2004) and lighttpd shipped event-loop-based HTTP servers that routinely served C10K on commodity boxes. By 2013 Robert Graham gave a Shmoocon talk titled “C10M” — ten million concurrent connections — arguing the next barrier was the kernel itself, and the answer was kernel-bypass networking (DPDK, later XDP, later io_uring). The C10K essay is still worth 20 minutes of your time in 2026 because the reasoning it teaches — measure the cost of your primitives, then choose — is timeless. The specific numbers are historical; the mental model is not.

The evolution, one primitive at a time

Era	Primitive	Complexity	Ceiling	Reason for ceiling
pre-1999	thread-per-connection	O(1) code, O(n) memory + ctx switches	~500-2k conns	8 MB stacks, ~1-3 μs ctx switch cost
1983	select(2)	O(n) per event	1024 fds (FD_SETSIZE)	fd_set bitmap capped at compile time
1997	poll(2)	O(n) per event	~10k, limited by scan	Whole fd array scanned every call
2002	epoll (Linux)	O(active events)	100k+ per thread	Kernel maintains ready list
2000	kqueue (FreeBSD/macOS)	O(active events)	100k+ per thread	Same idea, older, arguably cleaner API
1996	IOCP (Windows)	O(active events)	100k+	Completion-based, not readiness-based
2019	io_uring (Linux)	O(active) + zero-copy	1M+ per thread in benchmarks	SQE/CQE rings, batched syscalls

The conceptual leap from select/poll to epoll/kqueue/io_uring is: stop asking the kernel to scan all your fds every time; instead, register interest once, and let the kernel tell you which fds are ready. That is O(active) work per event batch instead of O(total fds). At 10k idle connections with 100 active, epoll does 100 units of work per iteration; poll does 10 000.

Why select and poll still exist

Because they’re portable (POSIX guarantees them) and adequate for hundreds of fds. Every scripting language’s default networking library uses select or poll under the hood. You’ll write select-based code in study questions and in embedded contexts. But no production high-throughput C server on Linux uses select anymore — they all use epoll, kqueue on BSD, or io_uring.

fd_set really is capped at 1024 on Linux glibc

A gotcha worth knowing: FD_SETSIZE is 1024 by default in glibc. You can rebuild with a higher value, but any library also compiled against the default will disagree with you about the size of fd_set, leading to memory corruption. The clean answer is “don’t use select above a few hundred fds.” This limit is one of C10K’s original bullet points and it hasn’t moved.

The reactor pattern in 30 lines of pseudocode

Every event-loop server on Earth is a variant of this:

int epfd = epoll_create1(EPOLL_CLOEXEC);

// register the listen socket for incoming connections
add_readable(epfd, listen_fd, /*data=*/listen_fd);

struct epoll_event events[MAX_EVENTS];
for (;;) {
    int n = epoll_wait(epfd, events, MAX_EVENTS, /*timeout_ms=*/-1);
    for (int i = 0; i < n; i++) {
        int fd = events[i].data.fd;
        uint32_t ev = events[i].events;

        if (fd == listen_fd) {
            // new connection
            int cfd = accept4(listen_fd, ..., SOCK_NONBLOCK | SOCK_CLOEXEC);
            add_readable(epfd, cfd, cfd);
            state_new(cfd);
        }
        else if (ev & EPOLLIN) {
            // read whatever is ready, feed to per-connection state machine
            read_until_eagain(fd);
            maybe_promote_to_writable(epfd, fd);
        }
        else if (ev & EPOLLOUT) {
            drain_write_buffer(fd);
            maybe_demote_to_readable_only(epfd, fd);
        }
        if (ev & (EPOLLHUP | EPOLLERR | EPOLLRDHUP)) {
            state_close(fd);
            epoll_ctl(epfd, EPOLL_CTL_DEL, fd, NULL);
            close(fd);
        }
    }
}

Read that until it’s boring. Then read redis/src/ae_epoll.c (file 08 walkthrough) and confirm it’s the same pattern with battle scars. Read nginx/src/event/ngx_epoll_module.c and confirm again. libuv’s src/unix/linux.c — same. The reactor is the shape.

Key property: the loop thread never blocks on a socket. It only blocks in epoll_wait. All the interesting logic is in the per-fd state machine read_until_eagain and drain_write_buffer run against. That’s why the loop can service 100k connections on one thread.

Why nginx and redis chose event loops

Igor Sysoev on nginx (paraphrasing his early talks): the goal was “handle 10k concurrent connections without buying a bigger server.” He explicitly copied the design ideas from earlier event-driven servers (thttpd, mathopd) and modernized them around epoll and later kqueue. nginx’s worker_processes count matches the number of CPU cores; each worker is an event loop bound to a core; the kernel load-balances SYNs via SO_REUSEPORT (added later). One thread per core, one event loop per thread, no work stealing. Simple and fast.

antirez (Salvatore Sanfilippo) on redis: in a widely-cited 2013 blog post (“Clarifications about Redis and Memcached” and later “An update on Redis persistence”), antirez argued that redis is deliberately single-threaded for command execution because (a) the working set fits in RAM, so the bottleneck is CPU cache and pointer chasing, not I/O; (b) a single-threaded event loop eliminates all lock overhead; (c) most redis workloads are ~150k ops/sec on one core, which is more than most apps ever need. Redis 6 (2020) added threaded I/O (recv/send off the main thread) while keeping command execution single-threaded — a targeted concession to network stack costs, not an architecture change.

The lesson: single-threaded event loops beat multi-threaded designs at high connection counts because they trade parallelism for cache locality and zero lock overhead. If you can shard state (nginx-per-core) or you don’t need parallelism (redis), you win. The moment your workload needs shared mutable state across cores, you’re back to threads + locks and you pay the lock tax.

The context-switch cost that kills thread-per-connection

A context switch on Linux costs roughly 1-3 μs on a modern x86-64 CPU (Brendan Gregg’s blog and numerous LWN benchmarks converge on this range; tsuna’s “context-switch” microbenchmark measured 1.2 μs on a 3 GHz Xeon in 2010, and modern Zen 4 / Alder Lake is broadly similar because the switch cost is dominated by TLB flush + kernel entry, not raw CPU speed).

So suppose you go thread-per-connection with 10 000 connections, each doing 100 syscalls/sec (a modest HTTP echo workload):

• Syscalls/sec: 10 000 × 100 = 1 000 000

• Context switches/sec: at least 2 × that (into kernel, back) → 2 000 000 ctx/sec

• CPU spent on ctx switches: 2 000 000 × 1.5 μs = 3 seconds of CPU per real second

That’s three cores burned on nothing but scheduling overhead. On a 4-core laptop you have 4 seconds of CPU per second; three of them are gone before the app does any work. Then add 8 MB of virtual memory per thread stack (10k threads × 8 MB = 80 GB VM — not resident, but TLB pressure is real), plus scheduler queue length pain, and you understand why thread-per-connection died.

An event loop turns those 1 M syscalls/sec into ~10k epoll_wait calls/sec, each returning a batch of ready events. Same amount of application work, orders of magnitude less kernel overhead. That’s the whole point.

The C10M problem — the successor

Robert Graham, C10M — Defending the Internet at Scale, Shmoocon 2013 (talk on YouTube; slides at c10m.robertgraham.com). Argument: past a few hundred thousand connections per machine, the kernel itself is the bottleneck. Every syscall crosses the user/kernel boundary; every packet goes through the netfilter stack, the socket buffer, the copy to userspace. The fix is kernel bypass: user-space networking with the NIC’s DMA rings mapped directly into your process.

The modern kernel-bypass stack in 2026:

• DPDK (Data Plane Development Kit, Intel origin, now Linux Foundation) — poll-mode drivers, no syscalls, no interrupts. Used by 6WIND, Cisco routers, F5 load balancers, and every telco NFV appliance. Serious learning curve.

• XDP (eXpress Data Path, in-kernel eBPF) — packets processed in the driver before the socket layer. Cloudflare uses XDP for L4 DDoS mitigation; Meta uses it for load balancing (Katran).

• io_uring (Linux 5.1+, stable 5.6+) — not strictly kernel-bypass, but batches syscalls and can register buffers so packet handling is nearly zero-copy. File 07 covers it in depth.

• AF_XDP sockets — hybrid: XDP redirects packets into a shared-memory ring your userspace reads. The best-of-both-worlds option.

For a laptop-scale server (this phase’s target: 100k rps on 4 cores) you do not need kernel bypass. epoll + non-blocking sockets is more than enough. You need C10M-class techniques when you’re building the middleboxes themselves — load balancers, DDoS scrubbers, packet analysers — at Meta/Cloudflare/Netflix scale.

What most people get wrong about this

They think one-thread-per-connection with pthread_create will scale. It won’t. The math above is why: at 10k connections each doing modest work, you burn multiple cores on nothing but context switches. Every senior engineer who’s shipped a network service in C knows this in their bones. Second-most-common mistake: reaching for io_uring on day one because it benchmarks fastest. Start with epoll — it’s supported everywhere Linux runs, it’s the API you’ll read in every existing codebase, and for anything below C1M-per-core it’s within 10-20% of io_uring performance. Upgrade when profiling says the syscall rate itself is your ceiling, not before.

Practice this week

1. Read Kegel’s C10K essay end-to-end (www.kegel.com/c10k.html). Note which primitives it recommends that no longer exist (/dev/poll, sigio); note which are still standard (epoll, kqueue).

2. Write the same TCP echo server three ways: (a) blocking, one client at a time, from file 05; (b) threaded, one pthread_create per accepted connection; (c) select-based, single-threaded, up to FD_SETSIZE connections. Benchmark each with wrk -c 200 -t 4 -d 30s http://localhost:8080/ (once you’ve added a trivial HTTP response). Watch (b) collapse around 1000 clients; watch (c) plateau.

3. Skim Graham’s C10M talk (25 min, YouTube). Note the four bottlenecks he identifies (packet handling, kernel data structures, locks, cache lines).

4. Read the first 300 lines of redis/src/ae.c — the event loop abstraction — as preview for file 08.

References

• Dan Kegel, “The C10K problem” — www.kegel.com/c10k.html. Last major revision 2014; still the canonical framing.

• Robert Graham, “C10M: Defending the Internet at Scale” — Shmoocon 2013 talk, YouTube. Slides on his site. 25 minutes.

• antirez, “Clarifications about Redis and Memcached” — antirez.com archives. His clearest defense of single-threaded event-loop design.

• Marc Brooker, “A Story About a Fish” (2021) — excellent illustration of tail-latency behavior in queueing systems, tangential but foundational.

• Cloudflare’s XDP writeups — blog.cloudflare.com under the “XDP” tag — the best public documentation of kernel-bypass in production.

• Beej’s Guide, chapter 7 — the friendly intro to select and poll if you want a gentler on-ramp.

---

Return to README.md · Next: 07_epoll_and_io_uring.md