Operating systems
Part 3 of 6 · Linux I/O Models & Event Loopsselect vs poll vs epoll vs kqueue - Readiness, Level vs Edge Triggering & Thundering Herds
Readiness multiplexing lets one thread wait on many fds. **`select`** (1983, BSD) passes bitmaps of fds into the kernel on every call, is capped at `FD_SETSIZE` (1024 on glibc), and both kernel and app scan all of them. **`poll`** removes the cap with an array of `pollfd`, but still copies and scans the whole set every call: O(watched). **`epoll`** (Linux 2.6) keeps the interest set inside the kernel (`epoll_ctl` once per fd) and `epoll_wait` returns only the ready ones: O(ready). **`kqueue`** (FreeBSD/macOS) is the BSD equivalent and also handles timers, signals, process and file events through one API. On top of that you choose **level-triggered** (keep telling me while data remains, the default and the safest) or **edge-triggered** (`EPOLLET`, tell me once per change, and you must drain to `EAGAIN`). At multi-thread scale you also have to handle the **thundering herd** and accept distribution.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
Where does the interest set live for select, poll, and epoll?
Answer
In your bitmap for select, in your array for poll, and in the kernel for epoll and kqueue.
L2
What is FD_SETSIZE?
Answer
The compile-time cap on select, 1024 on glibc. poll and epoll are limited by the process fd rlimit instead.
L3
Why is epoll faster at 100,000 connections?
Answer
poll scans every watched fd. epoll_wait returns only the ready ones, often a few dozen.
L4
What does level-triggered mean?
Answer
Every epoll_wait reports the fd again while it is still readable or writable.
L5
What bug does edge-triggered mode cause if you read partially?
Answer
The remaining bytes never produce another wake-up. The connection looks hung.
L6
What bug does level-triggered EPOLLOUT cause?
Answer
A socket with space in the send buffer stays writable, so a permanent EPOLLOUT spins the loop.
L7
How do you stop a thundering herd on accept?
Answer
EPOLLEXCLUSIVE, SO_REUSEPORT with one listener per worker, or a single acceptor thread.
Failure modes
Edge trigger leaves unread bytes stranded
A partial read consumes the only notification. The leftover payload sits in the socket until some later write happens to wake you.
Level-triggered EPOLLOUT spin
The fd is always writable, so the loop never blocks in epoll_wait.
Thundering herd on a shared listener
Every worker wakes, one accept succeeds, and the rest get EAGAIN.
Misconceptions
poll fixed select.
poll removed FD_SETSIZE. It still copies and scans the whole array on every call.
Edge-triggered is always faster, so it is the default.
It saves wake-ups only after you drain to EAGAIN. The safe default is level-triggered.
epoll makes disk reads non-blocking.
Regular files always report ready. The block happens inside read.
Interviewer traps
Quoting a big-O without saying what n is.
Say O(watched) for poll and O(ready) for epoll, and give the 100,000 versus 50 example.
Closing a dup'd fd and assuming epoll dropped it.
epoll watches the open file description. EPOLL_CTL_DEL before the last close in setups that dup or fork.
Design scenario
Same prompt for every reader.
Requirements
Explain the scan cost, the stranded-byte bug, and one accept-distribution fix. Do not propose a new protocol.
Traffic / scale
100,000 mostly idle connections, 50 ready per turn, eight acceptors on one port.
Latency
Stranded bytes show up as hung requests. The herd shows up as wasted wake-ups.
Consistency
A partial read must not lose the rest of the stream. Accepts must not all land on one worker by accident.
Availability
A spinning EPOLLOUT starves every other fd on that loop.
Failure assumptions
- Handlers sometimes read a fixed 10 bytes.
- Several threads wait on one listener.
Constraints
- Do not scan all 100,000 fds per wake.
- Do not leave EPOLLOUT armed with an empty queue.
Prompt
A gateway process watches 100,000 sockets. About 50 are active. After a deploy that switches the listener to EPOLLET, some clients stall until they send another packet. A second service with eight workers on one listening socket shows most workers waking for every accept.
API
Which flag do you add for edge mode, and what must the read loop do?
Data
How many fds does select refuse past the glibc cap?
Architecture
How does this interact with SO_REUSEPORT on a load balancer?
Level-triggered unless you already drain
Prefer
epoll or kqueue, level-triggered, EPOLLOUT only while pending
The kernel returns the ready set. You may read some and come back. Writable interest is armed only when the outbound queue is non-empty.
- Cost tracks ready fds.
- A partial read is still reported next time.
- libuv and Python selectors use this shape.
Alternative
Edge-triggered, or select on every connection
EPOLLET is what Nginx uses, and it is correct only if every wake drains to EAGAIN. select still copies a bitmap capped at FD_SETSIZE.
- A short read strands the rest of the bytes.
- poll removes the cap and keeps the O(n) scan.
- A shared listening socket wakes every waiter.
Interest list, ready list, then level or edge
Both arms loop back to epoll_wait. The edge arm is the one that strands bytes.
- 1
Add each socket once
epoll_ctl registers the fd. The kernel keeps the interest set in a red-black tree. - 2
A packet marks the fd ready
The socket callback pushes the fd onto the ready list. Idle fds stay off that list. - 3
Level keeps the fd ready
You can read some bytes. The fd stays reported while data remains. - 4
Edge reports the change once
If you stop before EAGAIN, the leftover bytes do not wake you again.
The four APIs compared
select | poll | epoll (Linux) | kqueue (BSD/macOS) | |
|---|---|---|---|---|
| Interest set lives | In your bitmap, copied each call | In your array, copied each call | In the kernel (epoll_ctl) | In the kernel (kevent changelist) |
| Cost per wait | O(max fd) | O(n watched) | O(ready) | O(ready) |
| fd limit | FD_SETSIZE = 1024 (glibc) | None (rlimit) | None (rlimit) | None (rlimit) |
| Triggering | Level | Level | Level or edge (EPOLLET), EPOLLONESHOT | Level or edge (EV_CLEAR), EV_ONESHOT |
| Non-socket events | No | No | Via eventfd, timerfd, signalfd | Native timers, signals, process, vnode events |
| Portability | Everywhere (incl. Windows sockets) | POSIX | Linux only | BSDs, macOS |
| Batch registration | n/a | n/a | One epoll_ctl per change | Many changes in one kevent() call |
Decisions
- 1
1. App creates epoll instance
- next2. epoll_ctl ADD each socket once
- 2
2. epoll_ctl ADD each socket once
- next3. Kernel keeps interest list as red-black tree
- 3
3. Kernel keeps interest list as red-black tree
- next4. Packet arrives, socket callback puts fd on ready list
- 4
4. Packet arrives, socket callback puts fd on ready list
- next5. epoll_wait returns only ready fds
- 5
5. epoll_wait returns only ready fds
- next6. Level or edge triggered?
- ?
6. Level or edge triggered?
- level7a. Read some bytes, fd stays on ready list while data remains
- edge EPOLLET7b. Must read until EAGAIN, no second wake for old data
- 7
7a. Read some bytes, fd stays on ready list while data remains
- next5. epoll_wait returns only ready fds
- 8
7b. Must read until EAGAIN, no second wake for old data
- next5. epoll_wait returns only ready fds
Lesson map
select vs poll vs epoll vs kqueue - Readiness, Level vs Edge Triggering & Thundering Herds
>-
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB s1["1. App creates epoll instance"] s2["2. epoll_ctl ADD each socket once"] s3["3. Kernel keeps interest list as red-black tree"] s4["4. Packet arrives, socket callback puts fd on ready list"] s5["5. epoll_wait returns only ready fds"] s6["6. Level or edge triggered?"] s7["7a. Read some bytes, fd stays on ready list while data remains"] s8["7b. Must read until EAGAIN, no second wake for old data"] s1 -->|continues| s2 s2 -->|continues| s3 s3 -->|continues| s4 s4 -->|continues| s5 s5 -->|continues| s6 s6 -->|level| s7 s6 -->|edge EPOLLET| s8 s7 -->|continues| s5 s8 -->|continues| s5
Why O(ready) matters (cost model, runnable)
A gateway with 100k connections where only 50 are chatty at any instant: poll scans 100k entries per wake-up, epoll hands back 50.
// Why epoll beats select/poll at scale: per-wakeup work is O(watched) vs O(ready).
// A cost model (not a benchmark). Pure TypeScript.
const busyConns = 50; // 50 chatty connections; the rest are idle (typical gateway)
console.log("watched_fds | select/poll fd checks | epoll ready items | ratio");
for (const n of [100, 1_000, 10_000, 100_000]) {
const ready = Math.min(n, busyConns);
// select/poll: copy the whole interest set to the kernel and scan it, every call.
const pollWork = n;
// epoll: interest set lives in the kernel (epoll_ctl once); wait returns ready list.
const epollWork = ready;
console.log(
`${String(n).padStart(11)} | ${String(pollWork).padStart(21)} | ${String(epollWork).padStart(17)} | ${(pollWork / epollWork).toFixed(0)}x`
);
}
// select() additionally caps at FD_SETSIZE (usually 1024) descriptors.
console.log("select() hard limit: FD_SETSIZE = 1024 on glibc");Output:
watched_fds | select/poll fd checks | epoll ready items | ratio
100 | 100 | 50 | 2x
1000 | 1000 | 50 | 20x
10000 | 10000 | 50 | 200x
100000 | 100000 | 50 | 2000x
select() hard limit: FD_SETSIZE = 1024 on glibcExpectedwatched_fds | select/poll fd checks | epoll ready items | ratio 100 | 100 | 50 | 2x 1000 | 1000 | 50 | 20x 10000 | 10000 | 50 | 200x 100000 | 100000 | 50 | 2000x select() hard limit: FD_SETSIZE = 1024 on glibc
Press Run. Snippets must be self-contained — no network, files, or native modules.
Level vs edge triggered on a real kernel (runnable)
We send 100 bytes, then read only 10 each time epoll wakes us. Level-triggered keeps waking us because data remains; edge-triggered wakes once and the remaining 90 bytes are stranded until new data arrives.
# Level-triggered vs edge-triggered epoll, observed on a real Linux kernel.
# Linux only (select.epoll). Python 3.8+.
import select, socket
def ready_after_partial_read(edge: bool) -> list:
a, b = socket.socketpair()
b.setblocking(False)
ep = select.epoll()
mask = select.EPOLLIN | (select.EPOLLET if edge else 0)
ep.register(b.fileno(), mask)
a.send(b"x" * 100) # 100 bytes arrive: one "edge" (state change)
seen = []
for step in range(3):
events = ep.poll(timeout=0.05) # ask the kernel: who is readable?
seen.append(len(events))
if events:
b.recv(10) # deliberately read only 10 of the 100 bytes
ep.close(); a.close(); b.close()
return seen
lt = ready_after_partial_read(edge=False)
et = ready_after_partial_read(edge=True)
print("level-triggered: ready events per poll =", lt) # keeps reporting while data remains
print("edge-triggered : ready events per poll =", et) # reports once; 90 bytes now stranded
print("rule: with EPOLLET you must read until EAGAIN on every wakeup")Output:
level-triggered: ready events per poll = [1, 1, 1]
edge-triggered : ready events per poll = [1, 0, 0]
rule: with EPOLLET you must read until EAGAIN on every wakeupLevel vs edge: which to choose, and what happens if you choose the other
| Level-triggered (default) | Edge-triggered (EPOLLET) | |
|---|---|---|
| Notifies | Every epoll_wait while the condition holds | Once per transition (new data, new space) |
| Reading rule | Read as much as you like; you'll be told again | Must read/accept/write until EAGAIN every time |
| Bug if misused | Busy wake-ups if you register for EPOLLOUT and have nothing to write | Hung connections: leftover bytes never trigger a new wake |
| Syscall efficiency | Slightly more wake-ups | Fewer wake-ups, used by Nginx and many high-perf servers |
| Multi-threaded | Same fd can wake several threads | Combine with EPOLLONESHOT and re-arm after handling |
- Choose level-triggered unless you have a measured reason. libuv and Python's
selectorsuse level-triggered semantics. It's forgiving. - Choose edge-triggered when you already drain to
EAGAIN(most mature servers do) and want fewer wake-ups. Forgetting to drain is the classic "connection randomly hangs under load" bug. - Only register
EPOLLOUTwhen you have pending writes, then remove it. With level triggering, a writable socket is almost always writable, so a permanentEPOLLOUTbecomes a 100% CPU spin.
Thundering herd and accept distribution
- The herd: several threads or processes wait on the same listening socket; one connection arrives; all wake; one wins
accept(), the rest getEAGAINand go back to sleep. Wasted wake-ups scale with workers. EPOLLEXCLUSIVE(Linux 4.5) wakes only one (or a few) of the waiters on a shared epoll target.SO_REUSEPORT(Linux 3.9) gives each worker its own listening socket on the same port; the kernel hashes connections across them. Even distribution, no herd, but a slow worker still gets its share of new connections (Cloudflare's write-up shows the trade-off versus a shared queue).- Single acceptor thread that hands fds to worker loops (Netty boss/worker groups) is the portable alternative.
- Gotcha: epoll registers the open file description, not the fd number. Closing an fd that was
duped or inherited acrossforkdoesn't remove it from the interest list. AlwaysEPOLL_CTL_DELbefore close in complex setups.
Pros and cons
| API | Pros | Cons |
|---|---|---|
select | Universal, simple | 1024 fd cap, O(n) copies and scans, rebuild bitmaps every call |
poll | No cap, simple | Still O(n) per call; slow past a few thousand fds |
epoll | O(ready), scales to 100k+ fds, edge/oneshot modes | Linux-only, subtle semantics (fd vs description, fork), files always "ready" |
kqueue | O(ready), batches changes, unified timers/signals/process events | Not on Linux; different semantics to port |
Interview Q&A
Why is epoll faster than poll for 100k connections?
Answer
poll copies the full array into the kernel and the kernel checks every fd on each call, so cost scales with connections. epoll keeps the interest set in the kernel and maintains a ready list fed by socket callbacks, so epoll_wait cost scales with ready fds. With mostly idle connections that's orders of magnitude less work.
Explain level vs edge triggering and a bug each can cause.
Answer
Level reports readiness as long as it holds; leaving EPOLLOUT registered when you have nothing to write spins the CPU. Edge reports only transitions; if you read part of the data and stop, you won't be woken for the rest, and the connection appears to hang.
What's the thundering herd and how do you avoid it?
Answer
Many waiters woken for one event, only one succeeds. Use EPOLLEXCLUSIVE, SO_REUSEPORT per-worker listeners, or a single acceptor that distributes connections.
Why can't epoll make file reads non-blocking?
Answer
Regular files always report readable and writable; the blocking happens inside read on a page-cache miss. Use a threadpool or io_uring for files.
How do epoll and kqueue differ for a library author?
Answer
kqueue lets you submit many changes and fetch events in one kevent call and natively supports timers, signals and process events; epoll needs one epoll_ctl per change and uses timerfd/signalfd/eventfd for non-socket events. Libraries like libuv, mio and Go's netpoller hide both behind one interface.
What does EPOLLONESHOT change?
Answer
The fd is disabled after one event until you re-arm it with epoll_ctl. Combined with edge triggering, it lets several threads share a set without two threads reading the same fd at once.
How is kqueue different for someone writing libuv or mio?
Answer
One kevent call can both apply a batch of changes and return events. Timers, signals, and process events are native filters. epoll needs a separate epoll_ctl per change and timerfd, signalfd, or eventfd for non-socket sources.
Why can SO_REUSEPORT still overload one worker?
Answer
The kernel hashes new connections onto listeners. A worker that gets slow keeps its share of new connections. A shared queue or a single acceptor can steer away from a stuck worker. The Cloudflare write-up is the usual reference for that imbalance.
Check yourself
On paper, 100 bytes arrive and you read 10. Write the next three epoll_wait results for level mode and for EPOLLET. Then say which bug you would ship.
Elsewhere in the library
These pages stay as they are. This lesson only points at them: L4 and L7 load balancing, WebSocket fan-out, mutexes and deadlocks.