This Shit is Hard: Taming the Thundering Herd

If you have ever run a Kubernetes controller at scale, you know the moment. Everything is humming: keys trickle into the workqueue, workers drain them, and latency is flat. Then something completely routine happens. You roll out a new version. The leader fails over. The resync period fires. Suddenly, every key in your controller's key-space slams into the workqueue at the same instant. Queue depth goes vertical, and the fresh, genuinely urgent work (the customer-facing kind) is stuck in line behind a full re-audit of the world. Nothing is wrong, but everything is on fire.

I spent years of my Knative days studying this exact problem alongside maintainers like Ville Aikas, Markus Thömmes, Nghia Tran, Victor Agababov, and Dave "Dr. Potato" Protasowski. We instrumented it, jittered it, and built increasingly clever machinery to live with it. At Chainguard, we finally got to attack the root cause instead. In classic "This Shit is Hard" fashion, the fix worked beautifully, right up until our own success bred a sequel: a failure mode I have taken to calling "the revenge of the herd."

The herd, explained

The Kubernetes controller pattern is one of my favorite pieces of systems design. Informers watch the API server and mirror objects into a local cache. Event handlers boil every change down to a small key that means "go reconcile this thing." A workqueue feeds those keys to worker goroutines. The workqueue's semantics are brilliant:

• Incoming work is deduplicated by key,

• At most one worker processes a given key at a time,

• A key can be re-queued while it is in progress (it will simply run again after it completes),

• Concurrent work is bounded, and queued work is processed in a deterministic order.

The problem is that this queue lives in memory, inside a single elected leader, and its lifetime is coupled to the process. That coupling creates the herd. Because the queue evaporates whenever the process dies, correctness demands that the whole world be re-derived every time it comes back: a restart re-lists everything, and every object arrives as an "add." A failover means the new leader does the same. And on a fixed, unjittered timer (ten hours by default in Knative), the informer replays every object in its cache back through the handlers just in case an event was missed. That periodic resync is defense in depth: watches drop events, caches drift, and reconcilers have bugs, so periodically revisiting every key is the backstop that guarantees the system converges anyway. You cannot simply turn it off without giving up that safety net.

The ecosystem's mitigations are all flavors of "spread out the timers." kube-controller-manager multiplies its resync period by a random factor between 1x and 2x so that controllers "don't get into lock-step." controller-runtime added 10% jitter to its sync period. These keep separate controllers from stampeding together, but each controller still dumps its entire key space into its own queue in one shot.

In Knative, we went further on two fronts. We built a two-lane workqueue so that global resyncs drain through a slow lane and cannot starve event-driven work. And I drove a design for per-reconciler leader election, which shards each reconciler's key-space into buckets, each with its own resource lock, so that replicas divide the keys among themselves, informer caches stay warm on every replica, and a failover redistributes only the fallen replica's buckets instead of re-electing the whole world. Both helped, with limited effectiveness. The herd was managed, but never eliminated.

Make the queue durable, make the reconcilers disposable

Even in our Knative days, we were fairly dogmatic that the core reconciliation functions be stateless: a reconcile takes a key, observes the world, and converges it, remembering nothing in between. What was not stateless was everything wrapped around those functions. The semi-stateful informer machinery (the watches, the caches, and the in-memory workqueue they feed) lived in-process, took time to warm up, and chained those beautifully stateless functions to long-lived, leader-elected processes. That resident state is what kept us from leveraging serverless infrastructure for reconciliation.

When we started building the reconciliation framework that powers much of the Chainguard Factory, we wanted the Kubernetes workqueue's semantics without the in-process state. The first insight was almost embarrassingly simple: make the queue durable, and the reconcilers can finally be stateless all the way down.

Our workqueue is backed by cloud object storage. Every key is literally an object: queued/{key} or in-progress/{key}. Creating objects with "no overwrite" semantics gives us deduplication for free: enqueueing a key that is already queued fails the write, and that failure is the success case. In-progress keys carry a lease that is periodically heartbeated; if the lease expires, the work is considered orphaned and returned to the queue. A dispatcher lists the queue state (on a cron, and on Pub/Sub nudges when new keys land), tops up to the configured concurrency, and invokes the reconciler with a small gRPC request carrying, well, the key.

The reconcilers themselves are ordinary stateless services. They hold no caches, no queues, no leases, and elect no leaders. They scale up when the dispatcher sends work, and all the way down to zero when they do not.

Here is the payoff: restarts stopped meaning anything. When a reconciler deploys, fails over, or gets OOM-killed, the queue is exactly where it was because it was never inside the process to begin with. No re-list, no global resync, no herd. Over time, the queue grew to include attempt counting, exponential backoff, dead-lettering, priorities, and delayed delivery ("not before" timestamps), but the core has stayed the same handful of object-storage verbs.

A resync that respects the clock

Durability killed the accidental herds, but we still needed the deliberate one. A healthy reconciler revisits every key on purpose: to catch an event that got dropped, to apply new logic after a code change, to notice drift in the outside world. Kubernetes does this too; it just does it all at once. A naive backstop cron that enqueues the entire key-space would faithfully recreate the stampede we had just escaped.

The resync backstop should be period-aware. If the goal is "every key gets revisited at least once per period," nothing says they must be revisited together. So we smear. Each key is hashed, together with a salt, into a minute-granularity bucket spread across the period: take a SHA-256 of the salt and the key, mod by the number of minutes in the period, and that is the key's minute. The salt changes every resync, so keys reshuffle each period; no key is permanently pinned to a busy minute or forever stuck behind the same neighbors. Our first implementation ran a cron once per period that enumerated the key space and enqueued every key with a delay: "Process this, but not before minute 743." Deduplication handles the collisions gracefully, and if real, event-driven work shows up for a parked key, the earlier eligibility wins, so the backstop never slows down fresh work.

Together, these two insights eliminated the clock-aligned thundering herd outright. Deploys, failovers, and resyncs stopped being events at all. Our stateless reconcilers routinely chew through key spaces in the hundreds of thousands, at concurrencies ranging from a small handful to a few hundred, depending on how much abuse the downstream systems can absorb. A half-million-key domain, revisited over a 24-hour period, shows a background hum of about 350 keys per minute instead of a half-million-key spike. We declared victory.

You can probably see where this is going.

The revenge of the herd

As we brought our entire APK inventory under reconciliation (about half a million keys, and growing), we noticed something odd: we were struggling to saturate our workers. Reconcilers were running below their configured concurrency, even though plenty of work was available to assign to them. When we dug in, the bottleneck was the enumeration itself: it was taking longer to list the queue and find the eligible work than it took to actually process some of the keys, so the dispatcher could not deal work as fast as the workers could finish it.

Our original design was explicit and unbothered about the dispatcher's full scan of the queued/ prefix. The reasoning went: if the backlog of runnable work is ever that large, the scan is the least of your problems, because you have already fallen prohibitively far behind. That reasoning was sound, but the period-aware resync backdrop undermined its premise. The period-long resync was parking the entire key space in the queue as delayed work. The backlog was now enormous and perfectly healthy: half a million keys, nearly all of them ineligible until some specific minute later in the day. Every dispatch pass had to wade past hundreds of thousands of not-yet-ready keys to find the few dozen that were actually due.

The herd had not died. It was standing in the queue wearing "not before" sticky notes, and we had to walk the entire length of it, over and over, to find work. The herd was fighting back.

Resync on a tick, not a period

The fix was our final insight: stop using the queue as a parking lot for the future.

Instead of one cron firing per period and enqueueing everything with long delays, the resync cron now fires on a short tick (say, every 15 minutes) and enqueues only the slice of the key-space that is due within that tick. The bucketing math is unchanged; what changed is where the salt comes from. Rather than choosing a fresh salt per resync run, we derive it from the wall clock truncated to the period. Every tick within the same period, therefore, computes exactly the same key-to-minute assignment (no coordination or stored state is required), and the assignment still reshuffles automatically when the next period begins. Each firing enumerates the key space from the system of record, keeps only the keys whose minute bucket falls within the current tick's window, and enqueues those few with at most a tick's delay.

The semantics are identical to what I shared earlier: every key is revisited once per period, smeared minute-by-minute across it, and reshuffled each period. But the queue never holds more than one tick's worth of the future. (If this rhymes with the per-reconciler leader election work above, it should. It is key space sharding again, except the shards are slices of time rather than replicas.) For our half-million-key inventory on a 24-hour period with 15-minute ticks, each firing enqueues roughly 5,000 keys with delays under 15 minutes, instead of 500,000 keys parked for up to a day. The dispatcher's scan once again sees only work that is due now or imminently, and the full key space enumeration happens exactly once per tick, against a cheap listing of the system of record, rather than on every single dispatch pass.

What the herd taught us

Here are the three lessons we learned in doing this, in the order we were forced to learn them:

1. The thundering herd is an architecture problem, not a tuning problem. Jitter reschedules the stampede; durability ends it. Once the queue outlives the process, a deploy or failover no longer implies "re-enqueue the world."

2. A queue is for work you intend to start soon. The moment we parked an entire period's future inside it, every reader paid a tax on every pass. Time-based scheduling belongs upstream of the queue, in the resync, not inside it.

3. Defense in depth and smooth load are not in tension. A salted, period-aware, tick-sliced resync gives you "every key, every period" without ever queueing more than the next few minutes.

The whole apparatus (the durable workqueue, the dispatcher, and the tick-based resync sharding) is open source as part of our DriftlessAF reconciler framework and its Terraform modules, which drive the reconciliation of our package and image catalogs every day.

The herd is quiet now. Then again, we thought that once before. Our herd keeps growing in leaps and bounds (more packages, more images, more ecosystems, and hundreds of thousands more keys), so we have no illusions: it will find new ways to fight back, and we will be forced to keep innovating right along with it.

If you are interested in learning more about this work and how it can benefit you, get in touch with our team today.