SD System Design In Depth
0%
From-Scratch Build

Singleflight & Stampede Coalescer

In-flight request deduplication (Go singleflight pattern) combined with stale-while-revalidate soft TTL caching and probabilistic XFetch early recomputation to eliminate cache stampedes.

~30 min Intermediate Lessons: Cache concurrency control, Cache availability and database fallback, Caching layers, Distributed cache design, TTL expiration and cache reapers
Interactive Build Lab 0/4 Steps Completed

Code & Verify in the Browser Workbench

Complete 4 progressive engineering steps in JavaScript, TypeScript, or C++20 (WebAssembly) against an in-browser Node.js v22, Bun v1.1 & Clang/WASI runtime (virtual filesystem, loopback TCP/HTTP, and automated unit tests) — zero local setup required.

1. The Cache Stampede (Dogpiling) Problem

When a hot cache key (e.g., homepage configuration or celebrity profile at 50,000 QPS) expires at $t = 60.000\text{s}$, thousands of concurrent worker threads see a cache miss simultaneously. If every thread independently queries the primary database to recompute the value, database CPU spikes to 100% and p99 latency collapses—a failure mode known as a Cache Stampede or Thundering Herd.

sequenceDiagram participant C1 as Caller 1 (Leader) participant C2 as Callers 2..500 (Followers) participant SF as Singleflight Group participant DB as Primary Database C1->>SF: do("hot-key", loader) SF->>DB: Execute 1 SQL Query (in-flight registered) C2->>SF: do("hot-key", loader) [499 concurrent arrivals] Note over SF,C2: Subscribed to Leader's in-flight Promise DB-->>SF: Return Row Payload (18ms) SF-->>C1: { value, shared: true, callers: 500 } SF-->>C2: { value, shared: true, callers: 500 }

Three Defense Layers Combined in This Build

  1. In-Flight Request Coalescing (SingleflightGroup): Inspired by Go's golang.org/x/sync/singleflight. A Map<key, { promise, callers }> ensures that while a key is being fetched, all subsequent requests for the same key await the exact same Promise.
  2. Dual-Horizon Stale-While-Revalidate (softTtlMs + hardTtlMs): Entries have both a soft expiration and a hard expiration. Between softExpireAt and hardExpireAt, callers immediately receive the slightly stale value ($0\text{ms}$ blocking latency) while a single coalesced background task refreshes the cache.
  3. Probabilistic Early Expiration (XFetch): Using Vattani et al.'s optimal stochastic formula: $$\text{Recompute when } t - \Delta \cdot \beta \cdot \ln(\text{rand}()) \ge \text{softExpireAt}$$ Keys that take longer to recompute ($\Delta$) probabilistically trigger a background refresh before softExpireAt.

2. Exception & Cancellation Hygiene

A critical bug in naive Promise-memoization caches is forgetting to evict the key from the in-flight map when the Promise rejects—permanently poisoning the key with a rejected Promise. Using a try / finally block guarantees this._inFlight.delete(key) runs on both resolution and rejection.

3. Verification & Running the Lab

bash
node demo.js
node test.js