Skip to main content
← PROBLEMS / SYSTEM-DESIGN
An end-to-end domain learning journey

Design a Thundering-Herd Cache Stampede
Shield with Singleflight Coalescing.

Combine L1 in-process caching, Redis L2 with Stale-While-Revalidate, a Consistent-Hash Singleflight Coalescer tier, and Probabilistic Early Refresh.
Start the journey7 stages
FIRST PRINCIPLES. PRODUCTION SCALE.
The idea to keep with you

Design a distributed caching and stampede-shield layer protecting a PostgreSQL origin (max 2,000 QPS) behind 200 stateless API pods serving 500K QPS total, where celebrity-product flash sales can trigger 100K concurrent misses on a single key with < 15 ms p99 latency.

From patterns to decisions.

Combine L1 in-process caching, Redis L2 with Stale-While-Revalidate, a Consistent-Hash Singleflight Coalescer tier, and Probabilistic Early Refresh.

Full walkthrough · 7 stages
01
STAGE 01 · CAPACITY MATHfoundation

Quantifying Pod-Level vs. Cluster-Wide Amplification.

Assume 500K total QPS across 200 API pods (2,500 QPS/pod) and a PostgreSQL origin ceiling of 2,000 QPS.

If 20 hot keys expire simultaneously, local-only singleflight emits 20 * 200 = 4,000 origin queries—double the database limit. Consistent-hash coalescing reduces that to 20 * 1 = 20 origin queries (1% of DB capacity).

STAGE 01 · CAPACITY MATH

Amplification Math

Amplification MathIngress / BaselineCore EngineScale ConstraintGuard & VerifyBottleneck SignalProduction OutcomeTarget SLAexposes

1.Stage Objective: Show why 200 stateless pods require cluster-wide key affinity rather than local-only coalescing.

2.Level (Foundation): Assume 500K total QPS across 200 API pods (2,500 QPS/pod) and a PostgreSQL origin ceiling of 2,000 QPS.

3.Operational Invariant: Cluster-wide key affinity cuts 4,000 pod-level misses down to 20 origin queries.

Caption: Cluster-wide key affinity cuts 4,000 pod-level misses down to 20 origin queries.

02
STAGE 02 · MULTI-TIER CACHEfoundation

L1 Process Cache + L2 Redis with Dual-TTL SWR.

Store {payload, soft_ttl_ts, hard_ttl_ts} in Redis. When now < soft_ttl_ts, return immediately (< 2 ms). When soft_ttl_ts <= now < hard_ttl_ts, serve the stale payload immediately to the caller while triggering an async singleflight background refresh.

Only when now >= hard_ttl_ts (cold miss) does the caller block on the Singleflight Coalescer.

STAGE 02 · MULTI-TIER CACHE

Dual-TTL Stale-While-Revalidate

Dual-TTLStale-While-RevInput StateCore EngineCore MechanismGuard & VerifyInvariant CheckProduction OutcomeOutput Statetransforms

1.Stage Objective: Separate logical freshness (`soft_ttl`) from physical eviction (`hard_ttl`) to serve stale reads during origin refreshes.

2.Level (Foundation): Store `{payload, soft_ttl_ts, hard_ttl_ts}` in Redis. When `now < soft_ttl_ts`, return immediately (< 2 ms). When `soft_ttl_ts <= now < hard

3.Operational Invariant: Serving stale payloads between soft_ttl and hard_ttl shields users from origin refresh latency.

Caption: Serving stale payloads between soft_ttl and hard_ttl shields users from origin refresh latency.

03
STAGE 03 · COALESCER RINGintermediate

Consistent-Hash Routing & Bounded-Wait Singleflight.

Use Maglev or Ketama consistent hashing with 150 virtual nodes per coalescer pod so key K always hashes to primary node P(K) (with backup B(K) if P(K) fails health checks).

class StampedeShield:
    def __init__(self, ring, singleflight, redis_client, origin_fn) -> None:
        self.ring = ring
        self.sf = singleflight
        self.redis = redis_client
        self.origin_fn = origin_fn

    def get_with_shield(self, key: str, now: float) -> bytes:
        entry = self.redis.get_entry(key)
        if entry and now < entry.soft_ttl:
            return entry.payload
        if entry and now < entry.hard_ttl:
            self._trigger_async_refresh(key)
            return entry.payload
        try:
            val, _ = self.sf.do(key, lambda: self._fetch_and_populate(key), wait_timeout=0.05)
            return val
        except TimeoutError:
            if entry:
                return entry.payload
            raise
STAGE 03 · COALESCER RING

Consistent-Hash Coalescer Tier

Consistent-HashCoalesceValidated InputCore EngineAtomic StepGuard & VerifyError / Retry GuardProduction OutcomeCommitted Resultexecutes

1.Stage Objective: Route identical cold-miss keys to a deterministic coalescer node with bounded waiting and fallback.

2.Level (Intermediate): Use Maglev or Ketama consistent hashing with 150 virtual nodes per coalescer pod so key `K` always hashes to primary node `P(K)` (with backu

3.Operational Invariant: Consistent-hash routing funnels cold misses for key K to one coalescer with 50 ms bounded wait.

Caption: Consistent-hash routing funnels cold misses for key K to one coalescer with 50 ms bounded wait.

04
STAGE 04 · XFETCHintermediate

Eliminating Cold Misses via Probabilistic Early Refresh.

Each read computes -delta * beta * ln(rand()), where delta is the last recomputation duration and beta = 1.0. If now - delta * beta * ln(rand()) >= soft_ttl, one caller triggers an async Singleflight refresh early.

Hot keys are refreshed proactively, while cold keys never waste background CPU.

STAGE 04 · XFETCH

XFetch Early Refresh Curve

XFetch EarlyRefresh CurHot PathCore EnginePartition / IndexGuard & VerifyLatency / RAM BoundProduction OutcomeScaled Statebounds

1.Stage Objective: Refresh hot keys asynchronously before expiration using the XFetch algorithm.

2.Level (Intermediate): Each read computes `-delta * beta * ln(rand())`, where `delta` is the last recomputation duration and `beta = 1.0`. If `now - delta * beta *

3.Operational Invariant: Probability of background refresh ramps up smoothly just before soft_ttl without waking cold keys.

Caption: Probability of background refresh ramps up smoothly just before soft_ttl without waking cold keys.

05
STAGE 05 · HOT-KEY PROTECTIONadvanced

Protecting the Coalescer Node from 100K QPS on One Key.

If 100K QPS hits one coalescer pod for product:999, even a fast hash lookup can saturate that pod's NIC. Solve this with a 2-second L1 in-process cache on every API pod (absorbing 99%+ of hot reads locally) plus 2-choice power-of-two sharding (K#0, K#1) only when qps(K) > threshold.

STAGE 05 · HOT-KEY PROTECTION

L1 Absorption + Hot-Key Fan-Out

L1 Absorption +Hot-KeyFault TriggerCore EngineIsolation BoundaryGuard & VerifyFallback / QuarantineProduction OutcomeProtected Pathisolates

1.Stage Objective: Prevent a single coalescer pod from becoming a CPU/network bottleneck on a 100K-QPS celebrity key.

2.Level (Advanced): If 100K QPS hits one coalescer pod for `product:999`, even a fast hash lookup can saturate that pod's NIC. Solve this with a **2-second L1 i

3.Operational Invariant: Short-lived L1 caches on API pods absorb 99% of celebrity traffic before it reaches the coalescer ring.

Caption: Short-lived L1 caches on API pods absorb 99% of celebrity traffic before it reaches the coalescer ring.

06
STAGE 06 · FAILURE ISOLATIONadvanced

Origin Circuit Breakers, Negative Caching & Shedding.

Cap concurrent origin queries per shard via a semaphore (e.g., max 500 in-flight). If PostgreSQL p99 exceeds 200 ms, trip the circuit breaker: immediately return hard_ttl stale data if available or short-circuit with 503 Retry-After.

Cache NOT_FOUND tombstones for 30s (negative caching) to block cache-penetration attacks.

STAGE 06 · FAILURE ISOLATION

Semaphore + Negative Cache Guard

Semaphore +Negative CacCheckpoint / LogCore EngineReplay / SyncGuard & VerifyConsistency GateProduction OutcomeRecovered Stateverifies

1.Stage Objective: Prevent slow origin queries from piling up goroutines/threads on coalescer pods.

2.Level (Advanced): Cap concurrent origin queries per shard via a semaphore (e.g., max 500 in-flight). If PostgreSQL p99 exceeds 200 ms, trip the circuit breake

3.Operational Invariant: Bounded origin semaphores and 30s negative tombstones protect PostgreSQL from slowdowns and miss attacks.

Caption: Bounded origin semaphores and 30s negative tombstones protect PostgreSQL from slowdowns and miss attacks.

07
STAGE 07 · OBSERVABILITYadvanced

Tracking Coalesce Ratio, Stale-Serve Rate & Ring Churn.

Emit singleflight_coalesce_ratio (followers / leaders), stale_serve_rate, xfetch_early_refresh_count, and origin_qps. During rolling deployments, use graceful draining on the coalescer ring so in-flight leaders finish and populate Redis before pod termination.

STAGE 07 · OBSERVABILITY

Coalescer Telemetry & Draining

Coalescer TelemetryTelemetry SignalDrainingSLO ThresholdValidation GateCircuit BreakerProduction OutcomeSafe Degradationtrips

1.Stage Objective: Measure stampede shield effectiveness and detect consistent-hash ring imbalance.

2.Level (Advanced): Emit `singleflight_coalesce_ratio` (followers / leaders), `stale_serve_rate`, `xfetch_early_refresh_count`, and `origin_qps`. During rolling

3.Operational Invariant: Graceful ring draining and coalesce-ratio metrics keep deployments stampede-free.

Caption: Graceful ring draining and coalesce-ratio metrics keep deployments stampede-free.

Practice · Explain the consequences

Practice: Make the trade-off yourself.

Question 1 of 3
Score: 0/3

Why does local-only Singleflight on 200 API pods still risk overwhelming a 2,000-QPS PostgreSQL origin?

Recommended Learning Flow