Many connections: epoll, kqueue, io_uring

A chat server with 10,000 open connections, most of them idle, has to notice the few that have something to say. On the recorded Mac one call to poll over 10,000 sockets, one of them with data, took several milliseconds, while the same wait with kqueue took under a microsecond, because kqueue already knew which sockets to watch.

This lesson explains the two ways a single thread can wait for many connections, readiness and completion, measures why poll slows down as connections grow, and shows what epollepoll: Linux's readiness interface for many descriptors: epoll_ctl adds a descriptor to an interest list kept in the kernel, and epoll_wait returns only the descriptors that are ready., kqueuekqueue: The readiness interface of macOS and the BSDs: one call, kevent, registers changes to the watched set in the kernel and returns the events that are pending. and io_uringio_uring: Linux's completion interface: the program and the kernel share a submission ring and a completion ring in memory, so a batch of operations needs one system call or none. each change.

Readiness or completion: two ways to wait for many connections

A thread per connection is the simplest server, and 10,000 connections then need 10,000 threads that mostly sleep. A single thread can serve them all instead, if the kernel can tell it which connections need attention. There are two ways to ask. A readinessreadiness interface: An I/O interface that tells a program which descriptors it can read or write now without blocking, as select, poll, epoll and kqueue do; the program then makes the call itself. interface answers “which sockets can I read or write without waiting?”, and the program then makes the read or write itself, with non-blocking calls. A completioncompletion interface: An I/O interface that takes a whole operation, buffer included, and later reports that it has finished, as io_uring and Windows I/O completion ports do. interface takes the whole operation, buffer included, and answers “which of my operations have finished?”. Step through one message both ways:

The readiness interfaces differ in where the list of watched sockets lives. select and poll take the whole list on every call. epoll, on Linux, keeps it in the kernel: epoll_ctl adds a descriptor to the interest list once, and epoll_wait returns only those on the ready list. kqueue, on macOS and the BSDs, does the same through one call, kevent, which registers changes and returns pending events together. io_uring, on Linux, is a completion interface: the program and the kernel share a submission ring and a completion ring, so a whole batch of operations needs one system call, or none. Windows has completion too, I/O completion ports.

Libraries hide the differences: libuv, which Node.js runs on, uses “epoll on Linux, kqueue on OSX and other BSDs” and IOCP on Windows. Three more names belong to readiness. Level-triggeredlevel-triggered: Readiness notification that reports a descriptor on every wait for as long as it is ready, for example while unread data is waiting. notification reports a descriptor for as long as it is ready, and edge-triggerededge-triggered: Readiness notification that reports a descriptor once each time new data arrives, not for as long as data waits. notification reports it once each time new data arrives. One-shot notification reports a descriptor once and then ignores it until the program asks for it again.

Why poll gets slower as connections grow, measured

poll receives an array of every descriptor to watch, and the kernel has to look at each one on every call, ready or not; select has the same cost and a hard limit, descriptors below FD_SETSIZE, 1024. A server that calls poll thousands of times a second over 10,000 sockets pays for 10,000 checks each time. The program below measures one wait with poll and one with kqueue as the number of watched connections grows, with a single connection holding data. It uses Python’s select module, whose poll and kqueue objects are thin wrappers around the system calls:

# The cost of one wait for events with poll and with kqueue, as the number of
# watched connections grows. One connection has data waiting; the rest are idle.
import resource
import select
import socket
import time

WAITS = 200
SIZES = [10, 100, 1000, 10000]

soft, hard = resource.getrlimit(resource.RLIMIT_NOFILE)
resource.setrlimit(resource.RLIMIT_NOFILE, (min(hard, 2 * max(SIZES) + 64), hard))


def microseconds_per_wait(wait) -> float:
    start = time.perf_counter()
    for _ in range(WAITS):
        ready = wait()
        assert len(ready) == 1
    return (time.perf_counter() - start) * 1e6 / WAITS


print("connections   poll (us)   kqueue (us)")
for n in SIZES:
    pairs = [socket.socketpair() for _ in range(n)]
    pairs[n // 2][1].send(b"x")  # one connection in the middle has data

    poller = select.poll()
    for ours, _ in pairs:
        poller.register(ours.fileno(), select.POLLIN)
    poll_us = microseconds_per_wait(lambda: poller.poll(0))

    kq = select.kqueue()
    changes = [select.kevent(ours.fileno(), select.KQ_FILTER_READ) for ours, _ in pairs]
    kq.control(changes, 0, 0)  # register every connection once
    kqueue_us = microseconds_per_wait(lambda: kq.control(None, 16, 0))

    print(f"{n:11} {poll_us:11.1f} {kqueue_us:13.1f}")
    kq.close()
    for ours, theirs in pairs:
        ours.close()
        theirs.close()

connections   poll (us)   kqueue (us)
         10         2.9           0.6
        100        31.4           0.6
       1000       305.1           0.6
      10000      9306.7           0.6

The poll column grows with the connections, about tenfold or more for every tenfold step, to several milliseconds at 10,000. The kqueue column hardly moves and stays under a microsecond, because the kernel already holds the watched set and returns only the one ready socket. At 10,000 connections the difference is thousands of times, for exactly the same answer. epoll gives Linux the same property: its manual page says it “scales well to large numbers of watched file descriptors”.

Practise: readiness, completion and the cost of a wait

The questions below cover both ways of waiting and what a wait costs. A question you miss is asked again before the session ends.

One event loop, from poll to kqueue and epoll Pro: opens with a Pro, Premium or Ultimate pass

Level- and edge-triggered: the hang, reproduced and fixed Pro: opens with a Pro, Premium or Ultimate pass

io_uring's rings, step by step Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• A readiness interface tells a program which connections it can read or write without waiting; a completion interface takes the whole operation and reports when it is done.
• select and poll are handed every watched descriptor on every call, so their cost grows with the connections: several milliseconds at 10,000 on the recorded Mac.
• epoll and kqueue keep the watched set in the kernel and return only the ready descriptors, so a wait stayed under a microsecond at any size.
• io_uring shares a submission ring and a completion ring with the kernel, so a batch of operations needs one system call or none.