22. Performance at Extreme Scale: Queueing, Tails, Metastability

22.1 Utilization vs latency (the curve every senior engineer should be able to draw)

For a simple M/M/1 queue, average time in the system is W = service_time / (1 − ρ), where ρ is utilization.

ρ (utilization)   latency multiplier 1/(1-ρ)
     50%                 2x
     70%                 3.3x
     80%                 5x
     90%                10x
     95%                20x
     99%               100x

Running hot is not efficient. It's fragile. This is why capacity targets of ~50–70% for latency-sensitive services are rational and not wasteful, and why a 10% traffic bump at 90% utilization causes an outage. Use Little's Law (L = λW) to size pools and queues.

22.2 Tail latency at scale

From Dean & Barroso, The Tail at Scale: if a request fans out to 100 servers, each with a 1% chance of being slow, then 63% of requests are slow (1 − 0.99^100). Techniques:

• Hedged requests (send a backup request after the p95 time; costs about 5% extra load).
• Tied requests (send to two servers; the one that starts first cancels the other).
• Micro-partitioning (many small shards per machine, for fast rebalancing).
• Selective replication of hot data.
• Good-enough results: return search results from 98% of shards at the deadline.

22.3 Metastable failures

A metastable failure is a state where the system stays broken even after the trigger is removed, because a sustaining effect keeps it overloaded. The usual sustaining effect is retries.

Trigger: brief DB slowdown (e.g. a deploy, a GC, a cache flush)
  → requests time out → clients retry → load 2-3x
  → DB slower → more timeouts → more retries → ...
  Trigger gone, but the retry load alone keeps the system above capacity.

Defenses: retry budgets and circuit breakers; load shedding by priority; LIFO queueing under overload (serve fresh requests that can still succeed); admission control; scaling before recovery (caches warm, enough capacity to drain backlogs); and a sustained-overload test in load testing (the scale guide covers how).

22.4 Capacity planning

Required capacity = forecast_peak_QPS / per_instance_QPS_at_target_util
                    × (1 + growth buffer)
                    + N+k redundancy (survive the loss of the largest failure domain)

Example: peak 120k QPS, 1 instance = 2k QPS at 60% util, 3 AZs, survive 1 AZ loss
  base = 120k / 2k = 60 instances
  survive 1 of 3 AZs → the remaining 2 AZs must carry 100% → 60 * 3/2 = 90 instances
  + 20% growth until next review → ~108 instances (36 per AZ)

22.5 🏗️ Flows: a metastable failure loop and adaptive concurrency control

          ┌──────────────────────── sustaining loop ─────────────────────────┐
          ▼                                                                    │
 Trigger (deploy / cache flush / brief network blip)                           │
   → latency ↑ → client timeouts ↑ → retries ↑ (load × 2-3)                    │
   → queues grow → every request waits longer → more timeouts ─────────────────┘
 Trigger removed: system STAYS down, because retry load alone exceeds capacity.
 Break the loop: shed load (drop to capacity), cap retries (budgets), drain queues,
                 then ramp traffic back up slowly.

Adaptive concurrency limit (Netflix concurrency-limits, TCP-Vegas style):

 measure: minRTT (no-load latency), sampleRTT (current)
 gradient = minRTT / sampleRTT        (1.0 = no queueing; 0.5 = latency doubled)
 newLimit = currentLimit × gradient + queueAllowance
 requests above limit → rejected immediately (fast 429/503) instead of queueing

22.6 Deeper: theory that explains production behavior

• Universal Scalability Law (Gunther): C(N) = N / (1 + α(N−1) + βN(N−1)). α is contention (serialized parts, as in Amdahl's law) and β is coherency cost (crosstalk between nodes). With β > 0, adding nodes eventually reduces throughput. That's why some clusters get slower as they grow (all-to-all gossip, distributed locks, cache coherency).
• Coordinated omission: closed-loop load generators stop sending while the server stalls, which hides the stall from percentiles. Use open-loop testing (scale guide §3.4).
• Container CPU throttling: a CFS quota (Kubernetes CPU limits) throttles a process that uses its quota early in a 100 ms period. A multithreaded service can be paused for tens of ms while its average CPU looks fine, which produces mysterious p99 spikes. Many teams remove CPU limits for latency-critical services (keeping requests) or tune the quota period.
• GC and the tail: stop-the-world pauses show up directly in p99.9. Mitigations: generational or low-pause collectors, smaller heaps per process, off-heap caches, and hedged requests across replicas.

22.7 🌍 In production

• AWS DynamoDB, September 20, 2015 (us-east-1): storage servers had to fetch their partition membership from a metadata service. A new feature (global secondary indexes) had made that membership data larger, so fetches took longer. A brief network issue made many servers re-request at once. Requests timed out and retried, keeping the metadata service overloaded long after the trigger. AWS had to pause requests and add capacity before the system recovered. A textbook metastable failure.
• Facebook Live ("Under the hood: Broadcasting live video to millions", 2016): a popular stream's segment requests are coalesced at edge caches, so one request goes upstream while thousands wait. Without that, a celebrity stream is a thundering herd against origin.
• Slack, January 4, 2021: the first workday after the holidays, with clients reconnecting on cold caches. The load spike met AWS Transit Gateway scaling limits and caused packet loss. Slack's autoscaling then provisioned many new instances at once, which added more load. A demonstration that recovery mechanisms can amplify incidents.
• Netflix concurrency-limits (open source): adaptive limits instead of hand-tuned thread pools, so services protect themselves when downstream latency changes.

22.8 ⚠️ Corner cases & deep details

• Autoscaling on the wrong signal: you scale app servers on CPU, but the bottleneck is DB connections. More app servers mean more connections and more DB contention, which makes things worse. Scale on the saturated resource, and cap concurrency toward the DB.
• Retries that line up with timeouts: clients time out at exactly 1 s and retry immediately, producing load waves at 1 s intervals. Jitter both timeouts and retries.
• Cold start after a deploy: JIT not warmed, connection pools empty, local caches empty, so the first minutes of every deploy are a mini-incident. Use warm-up traffic before marking an instance ready.
• FIFO under overload: everyone waits behind requests that will time out anyway. Use LIFO, or drop requests whose deadline has passed, under overload.
• Backlog drain after an outage: the queue holds 2 hours of work. Processing it at full speed overloads downstream systems, and the work may no longer be useful (expired notifications). Drain with rate limits and TTL filtering.