Load-induced capacity loss

How does capacity fall as load rises, and how does that open the metastable band?

Plain queueing does not produce this. In the simple single-server queue, the service rate μ is a constant. Raising ρ makes the wait W explode, but never reduces the service rate. For a second stable state to exist, something must make C itself a decreasing function of load. Otherwise the broken state drains and recovers on its own.

The retrograde region of the Universal Scalability Law

The Universal Scalability Law (USL) is a model of how throughput grows as you add workers or load. It has a contention term α (work that must be done one at a time) and a coherency term β (the cost of keeping workers consistent with each other, which grows with the square of the number of workers). With β > 0 there is a retrograde region: throughput falls after a peak. Any mechanism with β > 0 supplies the supply-side half of metastability for free.

The recurring examples:

• Cache working-set churn: more concurrent requests mean a lower hit rate, which means a higher cost per request.
• Lock and latch contention: waiting consumes the CPU that would have finished work.
• Memory pressure forcing spill: when memory runs short, each operator writes intermediate data to disk (spill). An in-memory operation becomes an I/O-bound one and the per-request cost can change by an order of magnitude.
• Connection-pool or thread-pool exhaustion: this converts service into waiting.

(The runtime-internal versions, GC and compaction debt, are the topic of Death spirals.)

A worked case: the lock convoy

A convoy needs a lock plus a scheduler. (A lock lets only one thread at a time run a protected piece of code, called the critical section. The scheduler is the part of the operating system that decides which thread runs on a CPU core.) It looks like head-of-line blocking, but the mechanism is a loop:

1. A thread holds a short-duration lock. Then it is descheduled: the OS stops it because its time slice ended, or it blocks on I/O, or it takes a page fault (a wait for memory to be loaded).
2. Every other thread that wants the lock queues up behind it.
3. When the holder runs again and releases the lock, the queue drains one thread at a time. Each released thread soon needs the next shared lock, and they all arrive together.

The group has become a convoy: it moves in lockstep. The lock's throughput drops from "as fast as the critical section" (microseconds) to "as fast as the scheduler can switch threads", which is roughly three orders of magnitude (about 1,000 times) worse. A context switch (the OS pausing one thread and running another) costs far more than the tiny critical section. That is C falling under load, from contention alone.

A convoy is self-sustaining: once formed, it persists, because each release event re-synchronizes the group. Removing the original cause (the preemption) does not disperse it. The fixes:

• Never sleep or block while holding a lock. Keep the critical section short and bounded.
• Adaptive spinning: spin (loop and check) for a short time before blocking. If the expected hold time is shorter than a context switch, blocking is strictly worse than spinning.
• Lock-free data structures where the algorithm allows. (These let threads make progress without holding a lock.)
• Randomize the release order to destroy the synchronization: the same logic as jitter, now applied to a lock queue.

Two routes into bistability

Either alone can open the band. Together, the band opens at a load you would call comfortable. And both are invisible in steady-state benchmarking, because both are measured in the regime you are trying to avoid.