System Design Trade-offs II — Retry Storms, Rate-Limiter Coordination, Sticky-Session Rehash & HA≠Lossless (Deep Dive)

Five gaps that only show up once components meet each other

Every individual page in this guide — the rate limiter, the write-heavy pipeline, the sticky-session load balancer, the cache — is correct in isolation. The gaps below only appear at the seams: a rate limiter that is provably correct on its own still fails to reduce load if clients don't cooperate; a limiter replicated across nodes multiplies its own limit unless something coordinates it; a write-heavy system's "at-least-once" default silently assumes a mechanism (idempotency) that lives on a different page; a load balancer's stickiness assumption breaks the moment autoscaling changes the node count; and "highly available" infrastructure quietly does not promise "no data lost." Each section below traces the failure with real numbers, names the fix, and labels the CAP/PACELC stance it takes.

1. Retry storms — a rate limiter only reduces load if clients back off

A rate limiter's job is to reject the excess above its capacity. That is not the same as reducing the load offered to the system — it only reduces load if the rejected callers stay away for a while. A client that receives 429 Too Many Requests and retries immediately simply re-presents the same request a moment later; from the system's point of view, the rejected slice never left. The limiter is doing its job (admitting exactly its capacity, every tick) and the system is still overloaded, because the traffic it rejected keeps coming straight back.

Traced: a single 1-second spike, two retry policies

Limiter capacity = 1000 req/s. At t=0 a burst of 4000 requests arrives (4×) — a cache-expiry stampede, a client-side retry bug, a deploy blip. After t=0, new (real, non-retry) demand returns to baseline 1000/s — exactly at capacity, no further spike from real users.

Model assumptions for the right-hand column, so the numbers are re-derivable: rejected retries re-spread over a jittered backoff window that doubles each round, so per-second retry arrivals roughly halve each tick (300 → ~150 → ~75 → ~38); and we conservatively let baseline traffic win every admission tie, so any retry that lands on a full tick is rejected. Real jittered admission decays at least this fast — the column is an upper bound on the storm.

The naive column never converges: a one-second spike becomes a permanent 4× overload, because the 3000 rejected every tick re-arrive whole on the next tick and get rejected again — a self-sustaining loop with no dependence on the original cause any more (this is the classic metastable failure: the trigger can be long gone and the system still won't recover on its own). The backoff+budget column throws away most of the rejected traffic outright (fail fast, no retry) rather than queuing it, and the fraction it does retry is delayed and shrinking each round (exponential backoff), so the offered load decays back toward capacity within about four seconds.

The controls, and where they live

• Exponential backoff: each retry waits longer than the last (1s, 2s, 4s, …) so a client that fails once doesn't hammer at the same rate.
• Jitter: randomize the wait so thousands of clients that failed at the same instant don't all retry at the same instant — without it, backoff alone still re-synchronizes everyone into a new, smaller thundering herd.
• Server-side Retry-After, honored: the 429/503 response should carry a concrete wait time; well-behaved clients read and obey it instead of guessing.
• Retry budgets: cap total retry traffic to a small fraction of normal volume (client-side, or a gateway-side token bucket dedicated to retries) — once spent, further failures fail fast instead of queuing, which is what actually bounds the worst case.

The LB-tier-specific view of this same mechanism — what happens when three independent hops (edge, service, DB proxy) each retry the same failure and the attempts compound multiplicatively — is traced in Load Balancing — Tier Sizing, Retry Storms, Load-Shedding, GSLB & L7-vs-Volumetric; this section is the rate-limiter-specific companion: the numbers above show what happens to the load at the limiter itself depending on whether the clients behind it cooperate.

2. Rate-limiter coordination cost — global exactness vs per-node multiplication

A rate limiter deployed behind N gateway nodes, each enforcing its limit against its own local, in-memory bucket, does not enforce the limit you think it does — it enforces N times that limit, because each node's bucket is unaware of the others.

Traced

Intended limit: 100 req/s per client. Deployed on 10 gateway nodes behind a round-robin load balancer, each running an independent local token bucket capped at 100/s. A single client whose requests are spread evenly across all 10 nodes can get up to 100 × 10 = 1000 req/s admitted — 10× the intended cap — with every individual node correctly enforcing its own 100/s.

Three ways to close the gap

• A — Shared counter (e.g. Redis INCR). Every node's admission check reads/writes the same central counter — the global count is exact, no multiplication. Cost: every request now pays a network hop to the counter store (latency added to every check, not just rejections), and that one key/store becomes both a hot key and a single point of failure the whole limiter now depends on.
• B — Divided local budget (limit ÷ N per node). Give each node 100/10 = 10/s. No coordination, no dependency, no extra latency — but wastes headroom: a client whose traffic (via sticky routing, geography, or plain bad luck) lands mostly on one node is capped at 10/s even though the intended limit was 100/s. The exact node-scoped analogue of the region-scoped "per-region hard split" stance in Multi-Region Rate Limiting.
• C — Local pre-aggregation + periodic flush. Count locally, flush deltas to a shared store on an interval (e.g. every 100ms) — cuts store load by roughly the flush-interval×request-rate ratio versus a per-request shared counter, at the cost of a bounded overshoot window. This is the mechanism traced in full, with the 20,000→200 ops/s worked numbers, in Rate-Limit Hot Keys — Sharding & Local Pre-Aggregation; option A above is exactly the "before" state that page's mitigations are fixing.

PACELC on the coordination choice

Option A (shared counter) is a consistency-over-latency stance even with no partition in sight — every check pays the round trip (Else: Latency vs Consistency → EC). Under an actual partition (the counter store unreachable from a node), the node must pick: fail closed and reject everything until the store is back (favors the limiter's exactness — PC-shaped), or fail open and admit locally-unlimited traffic until the store returns (favors availability — PA-shaped, and now the "exact global limit" property is exactly what's been given up). Options B and C are PA/EL by construction — no request's admission decision ever depends on a remote store being reachable.

3. Idempotency on retried writes — the write-heavy system's silent dependency

A write-heavy ingestion pipeline running at, say, 200,000 writes/sec (telemetry, event tracking, metrics) almost always runs on at-least-once delivery: client SDKs retry on timeout, and the broker/queue redelivers on a missed ack. That is not a corner case — at this rate, even a small fraction of transient timeouts (a slow node, a network blip, a broker rebalance) produces a steady stream of true duplicates, not an occasional one. A rate limiter's own retry budget (Section 1) makes this worse in a good way: it is deliberately encouraging retries as the correct response to a 429/503 — which means the write path downstream must already tolerate duplicates, or "the system handles retries gracefully" quietly becomes "the system corrupts the data during overload."

The resolution is the idempotency-key / dedup mechanism traced in full — including the check-then-act race and its atomic INSERT … ON CONFLICT fix — in Exactly-Once is a Myth — Idempotency & Dedup and Idempotency & "Exactly-Once Is a Myth"; the concrete charge-retry trace also lives in Section 3 of Load Balancing — Tier Sizing, Retry Storms, …. This page will not re-derive that mechanism — the trade-off-specific angle those pages don't cover is what it costs at write-heavy scale:

• The dedup store roughly doubles write volume. Every one of the 200,000 writes/sec now also writes (or checks) an idempotency-key record — the dedup store must be sized, sharded, and made highly available as its own write-heavy system, not bolted on as an afterthought.
• TTL must match the real retry horizon, not the happy path. Keys must outlive the maximum plausible redelivery window (client retry policy + broker redelivery + any downstream replay) — often hours, not the sub-second happy-path latency — or a late retry arrives after its key expired and the "impossible" duplicate reappears.
• The dedup key must be partitioned the same way the main write path is (e.g. hashed by event id), or the dedup store itself becomes the new hot shard under exactly the load pattern (a bursty retry storm) it exists to protect against.

4. Sticky-session rehash on autoscale

Sticky routing by hash(session_id) mod N is chosen so a given session always lands on the same node without any shared store. The mechanism has a fatal dependency the naive version never states: it assumes N is fixed. The moment autoscaling changes N — the exact event stickiness exists to survive — nearly every session gets remapped, which is the churn stickiness was supposed to avoid in the first place.

Traced: N: 3 → 15 (autoscale for a traffic spike)

Take the friendliest case possible for mod hashing: 15 is an exact multiple of 3, so hash mod 3 is fully determined by hash mod 15 (call it r): old node = r mod 3, new node = r.

Only r = 0, 1, 2 land on a new-node number that happens to equal their old node number — 3 of 15, i.e. 20% stay, 80% churn, in mod-N's best possible case. Scale to any N that is not a clean multiple of 3 (3→14, 3→17 — the ordinary case) and there is no shared factor to exploit at all: hash mod 3 and hash mod 14 are two near-uncorrelated computations. A session stays only when its mod-3 and mod-14 residues happen to coincide, which over the joint period of 42 holds for just 3 residues out of 42 — 1/14 stay (~7%), so ~93% of sessions are remapped (3→17 works out the same way: 1/17 stay, ~94% move).

Why consistent hashing doesn't have this failure mode

Consistent hashing scales node-by-node: going from 3 to 15 nodes is 12 individual insertions, and each insertion remaps only the sessions that literally fall in the one new node's arc of the ring — provably ~1/N of the keys at that step (1/4, 1/5, … 1/15), and it never revisits sessions outside that arc.

Total it up honestly, though: consistent hashing also moves 80% of sessions in total going 3→15. A session survives on its original node only if all 12 insertions miss it — probability (3/4)(4/5)…(14/15), a telescoping product that collapses to 3/15 = 20% stay. And no scheme can move less: in the balanced end state the 3 original nodes own only 3/15 of the keyspace, so at least 80% of sessions must move when capacity quintuples. The ring's win here is not a smaller total. It is that (a) it hits that unavoidable floor for any target N, while mod-N matches the floor only when the new count is an exact multiple and pays ~93% for 3→14; (b) each moved session goes straight to the one new node claiming its arc — sessions are never shuffled between surviving nodes; and (c) the churn arrives in 12 small ~1/N increments you can pace and health-check, instead of one cliff.

Crucially the per-step property does not depend on 15 sharing a factor with 3 — the same one-node-at-a-time step works identically whether the target is 4, 14, or 17. Mod-N's 80% "best case" only looked survivable because 15 happened to be 5×3; that's a property of the specific numbers, not of the mechanism. The ring mechanics, virtual nodes, and the failed-node worked trace are covered in What Is the Difference Between Rendezvous Hashing and Consistent Hashing…; the scale-in-specific version of this exact remap-cost argument (and the sticky-cookie-vs- external-store decision) is in Scale-In Safety & Connection Affinity — this section is the autoscale-up companion: the failure hits just as hard scaling out as scaling in, because either direction changes N.

5. HA ≠ lossless, and RTO isn't just "failover done"

"Highly available" describes what happens to traffic after a failure (a new node takes over and keeps serving) — it says nothing about what happens to data written just before the failure. Redis's default replication (used by both Sentinel and Cluster) is asynchronous: the primary acknowledges a write to the client before that write has necessarily reached any replica. If the primary crashes in the gap between "acked to client" and "replicated to a survivor," that write is gone — permanently — even though the client was told it succeeded, and even though the failover itself works exactly as designed.

Traced: an acked write that doesn't survive failover

Two separate costs are visible in that trace, and both are usually left out of an "HA" claim: a silent data-loss window (the acked write between t=0 and t=12s), and a recovery-time tail that most RTO numbers don't count — the system is back up at t=12s in the sense that it answers requests, but it runs slow until the new primary's working set is warm again, because a cold cache turns every read into an origin fetch (the stampede/thundering-herd mechanics for exactly this warm-up window are in Caching — Deep Stampede (XFetch), LRU Lock Contention & Redis Ops). A recovery-time objective that only measures "time until failover completes" is not measuring the thing the business actually experiences.

The CAP/PACELC label these pages derive but never name

Async replication (Redis Sentinel/Cluster's default) is an AP/EL stance: available and low-latency during normal operation (the primary never waits on a replica), and — since a lost write is a consistency failure, not an availability one — it also silently gives up durability of the most recent writes on failover, which is the practical form "giving up C" takes here. The alternative, synchronous replication (Redis WAIT, or any quorum-ack design), is CP/EC: no acked write can be lost to a single-node failure (assuming failover promotes by replication offset and the acking replica is reachable at election time), at the cost of every write paying a replica round-trip and the primary having to stall or reject writes when it can't reach a replica quorum. Neither choice is "more available" in absolute terms — they've each just decided which of durability or write-latency to sacrifice. The general form of this — replica lag, what "acked" actually means under async replication, and Raft's stricter alternative (leader completeness) — is covered in CAP/PACELC for Replication & Reads and Leader/Follower — Replica-Lag Anomalies, Failover Data Loss, …; this section is the concrete "your HA cache/store just did this" case.

Pitfalls

• Adding a rate limiter and declaring victory without checking whether clients back off — a naive-retry client turns "we now shed excess load" into "we now have a permanent multiple of the excess load."
• Sizing a distributed rate limiter's per-node local limit as if it were the global limit — it's the global limit only when there is exactly one node.
• Treating "we use a message queue, so delivery is exactly-once" as true — at-least-once + no dedup is the actual default, and it duplicates under real load, not just in theory.
• Autoscaling a sticky-session tier without checking what the hash function does to N — the churn "stickiness" was meant to prevent is precisely what a naive rehash causes on every scale event.
• Quoting "we run Redis Sentinel, we're HA" as if it implies zero data loss — HA is about traffic failover, not write durability; check the replication mode, not the failover feature.
• Measuring RTO as "time until the new primary answers pings" and ignoring the cache-rewarm tail, which is often the longer and more user-visible part of the outage.

Judgment layer

Global (shared-counter) vs per-node rate limiting

Reach for a shared counter when the limit is a hard contractual number (billing quotas, a security-sensitive cap) where exceeding it even briefly is unacceptable — pay the coordination latency and treat the store's availability as a first-class dependency. Reach for divided-budget or pre-aggregated local limiting for ordinary API quotas, where a limit that's briefly loose under uneven traffic is a fully acceptable trade for removing a shared dependency and its latency tax from every request's hot path. Combine — shard the shared counter and pre-aggregate locally — only once a single node's traffic to one client is itself large enough to be a hot key.

Synchronous vs asynchronous replication for "HA"

Choose synchronous replication (or a quorum write) wherever a lost acked write is a business incident, not an inconvenience — payments, orders, anything with a legal or financial record. Choose asynchronous replication — the default for caches, read replicas, and most session/telemetry stores — when write latency and availability matter more than the (usually small, bounded-by-lag) risk of losing the last few writes on a rare primary failure, and losing them is recoverable (the source of truth lives elsewhere, or the data is disposable). Either way, state the choice explicitly in a design review — "we're HA" is not an answer to "what happens to an acked write when the primary dies."

Takeaways

• A rate limiter reduces load only if clients back off — trace the naive-retry case before trusting a limiter's numbers; backoff + jitter + a retry budget is what actually bounds the worst case.
• Per-node local limiting multiplies the intended limit by the node count; closing that gap costs either a shared-counter's latency/hot-key/SPOF risk or a divided-budget's wasted headroom.
• At-least-once delivery is the default at write-heavy scale, not the exception — idempotency is a load-bearing dependency of "the system handles retries," and its dedup store must be sized like the write-heavy path it protects.
• Naive sticky-session hashing and "HA" infrastructure both hide a false assumption (N is fixed; replication is synchronous) — name the CAP/PACELC stance explicitly instead of assuming the comfortable case.

attempt = 0
max_attempts = 3
retry_budget = 0.3 * normal_qps   # cap retries as fraction of healthy traffic
base_delay = 1.0                  # seconds

while attempt < max_attempts:
    attempt += 1
    response = send_request()
    if response.ok:
        return response
    if attempt >= max_attempts or retries_this_second > retry_budget:
        return FAIL_FAST          # stop protecting the downstream
    # exponential backoff + full jitter
    sleep = random() * base_delay * (2 ** (attempt - 1))
    time.sleep(sleep)
return FAIL_FAST

> SET cart:42 "{\"items\":[],\"total\":85}"
OK
> WAIT 1 100
(integer) 1        # at least 1 replica acknowledged within 100 ms

Synthesized from the Google SRE Workbook (cascading failures, retry storms, load shedding), Redis Sentinel/Cluster replication and failover documentation, Stripe's idempotency-key API design, Karger et al.'s consistent-hashing paper, and Kleppmann's Designing Data-Intensive Applications (replication, PACELC, exactly-once). Re-authored/Deepened for this guide.