The Thundering Herd Problem

Why the thundering herd matters

Concurrency scales by having many workers wait on shared events — connections arriving, a lock releasing, a condition variable signalling, a cache entry filling. The thundering herd is what happens when the wakeup mechanism is broadcast instead of targeted: an event that can satisfy exactly one waiter wakes all of them. Every extra waiter that wakes performs a full round trip — scheduler dequeue, context switch, cache-warm, the syscall or check that reveals "nothing here for me," then re-block — and contributes nothing.

The damage is nonlinear in the worst way. The herd is largest when the machine is busiest, because a busy server has many workers parked on the same wait queue. So the moment a connection arrives under peak load — the moment you most need spare CPU — the kernel spends it waking a hundred workers to hand one connection to one of them. The others fight over the same runqueue locks and the same socket's spinlock, and on a multi-socket NUMA box the cache line for that wait queue bounces between cores. Tail latency (p99, p999) is where this shows up first, long before average latency moves.

How the herd forms, step by step

The canonical shape is the pre-fork server: a master process opens a listening socket, then fork()s N worker children. Because a forked child inherits the parent's open file descriptors, all N workers share the same listening socket, and each parks in accept().

1. All N workers block. Each worker's task is placed on the listening socket's kernel wait queue and marked non-runnable. Zero CPU used — this part is fine and desirable.
2. One connection arrives. The TCP handshake completes, the kernel moves the connection onto the socket's accept queue, and the socket becomes readable — one unit of work is now available.
3. The kernel wakes the queue. With a naive broadcast wakeup, the kernel walks the entire wait queue and marks all N workers runnable. The scheduler now has N tasks demanding a core.
4. One wins, N−1 lose. Whichever worker gets scheduled first calls accept(), dequeues the single connection, and starts serving it. The remaining N−1 workers wake, call accept(), find the queue empty, get EAGAIN (on a non-blocking fd) or immediately re-block. Their entire wakeup was wasted.

The same pattern reappears whenever a broadcast primitive sits between one event and many waiters: pthread_cond_broadcast() on a condition variable when only one waiter can proceed; every process in a futex wait woken by FUTEX_WAKE with a large count; and — the version most application engineers actually hit — the cache stampede.

The cache stampede variant

A cache stampede (a.k.a. dog-piling) is the thundering herd projected onto a cache. Suppose a single hot key — a rendered homepage, a popular product's price, an auth token's validation — is served from Redis or Memcached at, say, 50,000 requests per second, all cache hits. The backing database is provisioned only for the trickle of cache misses. Now the key's TTL expires.

Within the same millisecond, thousands of in-flight requests all miss the cache simultaneously. Each independently decides "cache is empty, I'll recompute," and they all hit the database with the identical expensive query. The database, sized for near-zero miss traffic, is suddenly asked to run the same query thousands of times at once. It saturates, queries queue, latency explodes, and — the vicious part — the recompute never finishes fast enough to refill the cache, so new arrivals keep missing too. This is how a routine TTL expiry cascades into an outage.

The insight that ties it to the socket case: the expiry is one event that should require one recomputation, but a broadcast (every request independently observing the miss) turns it into N recomputations.

Mitigations

All fixes share one idea: convert a broadcast wakeup into a targeted one, or spread a synchronized burst out over time.

• Exclusive wakeup (kernel level). Since Linux 2.4 (the fix landed in the 2.3 development series, prompted by the 1999 Mindcraft benchmarks), accept() uses an exclusive wait-queue entry: the kernel wakes one waiter per available connection instead of the whole queue. The herd returned when servers moved to epoll — each worker running its own epoll on a shared fd re-created the broadcast — so kernel 4.5 (2016) added EPOLLEXCLUSIVE, a flag on epoll_ctl that wakes only one epoll instance for a shared fd.
• SO_REUSEPORT (kernel level). Linux 3.9 lets every worker bind its own listening socket to the same port; the kernel hashes each incoming connection to exactly one socket. Each worker waits on its own queue, so an arrival wakes exactly one worker — no shared queue, no herd — at the cost of possibly uneven load and dropped connections if a worker exits with connections already hashed to it.
• Request coalescing / single-flight (app level). Deduplicate concurrent work by key: the first request for a key runs the computation, and every other concurrent request for the same key waits on that in-flight result and shares it. Go's singleflight and DataLoader-style batching implement this; N concurrent misses become 1 backend call.
• Jitter (app level). Randomize TTLs and retry backoffs so clients desynchronize. Expire keys at TTL × (1 ± rand), and use full-jitter backoff — sleep = random(0, base · 2^attempt) — so a fleet retrying after an outage arrives as a smooth ramp instead of a synchronized wall.
• Probabilistic early expiration (XFetch). A refinement where each request, on a near-expiry read, refreshes the key with a probability that rises as expiry approaches, so exactly one request usually refreshes it before it ever misses.

Fixes compared

	EPOLLEXCLUSIVE	SO_REUSEPORT	Request coalescing	Jitter / backoff
Layer	Kernel (epoll)	Kernel (socket)	Application	Application / client
Targets	accept() epoll herd	accept() socket herd	Cache stampede / dup work	Synchronized retry storms
Wakeups per event	~1 (not guaranteed exactly 1)	Exactly 1 (hashed)	1 compute per key	Spread over a window
Load balancing	Kernel-assisted, fairer	Hash-based, can skew	N/A	N/A
Key caveat	Not with EPOLLONESHOT	Drops on worker exit	Slow key blocks its waiters	Adds latency variance
Since	Linux 4.5 (2016)	Linux 3.9 (2013)	Any runtime	Any runtime

Fixing the epoll herd with EPOLLEXCLUSIVE

Each worker runs its own epoll on the shared listening fd. Without the flag, every worker's epoll_wait() returns on each arrival. Adding EPOLLEXCLUSIVE tells the kernel to wake just one.

// Pre-fork: master opens listen_fd, then fork()s N workers.
// Each worker runs this; listen_fd is shared via inheritance.

int epfd = epoll_create1(0);

struct epoll_event ev = {0};
ev.events = EPOLLIN | EPOLLEXCLUSIVE;  // wake only ONE waiter per event
ev.data.fd = listen_fd;
epoll_ctl(epfd, EPOLL_CTL_ADD, listen_fd, &ev);

struct epoll_event events[64];
for (;;) {
    int n = epoll_wait(epfd, events, 64, -1);
    for (int i = 0; i < n; i++) {
        if (events[i].data.fd == listen_fd) {
            // Drain the accept queue; loop because one wakeup
            // can correspond to several queued connections.
            for (;;) {
                int conn = accept4(listen_fd, NULL, NULL, SOCK_NONBLOCK);
                if (conn < 0) {
                    if (errno == EAGAIN || errno == EWOULDBLOCK) break;
                    if (errno == EINTR) continue;
                    break;  // real error
                }
                handle_connection(conn);
            }
        }
    }
}

Two correctness notes. First, EPOLLEXCLUSIVE guarantees "wake one or more," not "exactly one," so the accept4() loop must tolerate an empty queue (EAGAIN) — a woken worker may find another worker already took the connection. Second, you must drain in a loop: level-triggered epoll can coalesce multiple arrivals into one wakeup, so a single epoll_wait return may hide several pending connections.

Killing the cache stampede with single-flight

On the application side, coalesce concurrent misses so only one recompute per key ever reaches the backend.

import "golang.org/x/sync/singleflight"

var group singleflight.Group

// Many goroutines may call GetPrice("sku-42") at the same instant.
// Only the FIRST runs fetchFromDB; the rest block and share its result.
func GetPrice(ctx context.Context, sku string) (Price, error) {
    if p, ok := cache.Get(sku); ok {
        return p.(Price), nil          // fast path: cache hit
    }
    v, err, _ := group.Do(sku, func() (interface{}, error) {
        p, err := fetchFromDB(ctx, sku) // ONE db call for all waiters
        if err != nil {
            return nil, err
        }
        // Add jitter to the TTL so 1000 keys don't all expire together.
        ttl := 60*time.Second + time.Duration(rand.Int63n(15))*time.Second
        cache.Set(sku, p, ttl)
        return p, nil
    })
    if err != nil {
        return Price{}, err
    }
    return v.(Price), nil
}

group.Do(key, fn) is keyed deduplication: if a call for key is already in flight, subsequent callers don't run fn — they wait for the in-flight call and receive the same return value. So a stampede of 1,000 concurrent misses on "sku-42" issues exactly one database query. Two caveats: a slow or failing computation now blocks all its waiters (use a timeout and consider DoChan so callers can abandon it), and coalescing only helps per-process — across many machines you still get one recompute per machine, which is why serving a slightly stale value while a background refresh runs is often the better production posture.

A little history

The term predates Linux epoll by years. It was folklore in the BSD and early Apache era: Apache's pre-fork MPM had many children blocked in accept() on one socket, and on kernels without exclusive wakeup, every request woke the whole flock — so Apache added an accept mutex to serialize which single child was allowed to call accept() at a time. That mutex was itself a bottleneck, which is exactly why kernel-level exclusive wakeup (and later SO_REUSEPORT and EPOLLEXCLUSIVE) mattered: they push the "wake exactly one" decision down to where it's cheap. The phrase "thundering herd" itself borrows from the image of a stampeding herd — many bodies rushing at once toward a single trigger.

Common misconceptions and pitfalls

• "Modern kernels already fixed accept(), so I'm safe." They fixed the bare accept() herd. The moment you put your own epoll per worker on a shared fd, the herd is back unless you set EPOLLEXCLUSIVE. The fix moved layers; it didn't disappear.
• "EPOLLEXCLUSIVE wakes exactly one." No — it wakes one or more. It removes the O(N) storm but you must still handle a spurious wakeup where accept() returns EAGAIN.
• "Coalescing eliminates all duplicate backend load." Only within one process/instance. A 50-node fleet with per-process single-flight still sends up to 50 recomputes per key. Cross-node dedup needs a distributed lock or a shared "recompute in progress" marker.
• "Fixed exponential backoff is enough." Without jitter, everyone backs off by the same amount and retries in lockstep — you've just rescheduled the herd, not dissolved it. Full-jitter backoff is the standard fix.
• "Setting all TTLs to 3600s is simplest." Identical TTLs synchronize expiries. If you warm a cache with 10,000 keys in one loop, they'll all expire in the same second an hour later — a stampede you manufactured. Jitter the TTLs.
• "SO_REUSEPORT is strictly better, use it everywhere." Its hash-based distribution can leave one worker overloaded while others idle, and connections hashed to a worker that then exits can be dropped. It's a different tradeoff curve, not a free upgrade.