High-Throughput Distributed Caching: Stampede Mitigation, Probabilistic Early Expiration, and Redis Cluster

index

The Illusion of the Transparent Cache

Caching is often introduced as a simplistic key-value band-aid: place Redis in front of a slow SQL database, set a 10-minute Time-To-Live (TTL), and assume performance issues are solved.

In production environments handling 50,000 requests per second, caching is an active distributed subsystem with its own failure modes:

Cache Stampede (Thundering Herd): When a heavily accessed key expires, thousands of concurrent requests miss simultaneously, inundating the primary database with identical heavy queries and triggering database collapse.
Cache Penetration: Malicious or malformed queries requesting non-existent IDs bypass the cache completely and hit the database continuously.
Cache Avalanche: Hundreds of keys set with identical fixed TTLs expire at the exact same millisecond, causing catastrophic traffic surges on backend datastores.

1. The Cache Stampede Problem

Consider a viral product catalog page requested 10,000 times per second:

1
Timeline: Key Expires at T = 0
2
+-----------------------------------------------------------------------------------+
3
|  [T = 0.00s] Key 'product:9920' expires in Redis                                  |
4
|  [T = 0.01s] 500 concurrent incoming HTTP requests execute GET 'product:9920'     |
5
|  [T = 0.02s] All 500 requests get cache miss (nil)                                |
6
|  [T = 0.03s] All 500 requests independently execute:                              |
7
|              "SELECT * FROM products JOIN inventory JOIN pricing WHERE id = 9920" |
8
|  [T = 0.05s] PostgreSQL connection pool exhausted (CPU hits 100%, latency 8,000ms)|
9
+-----------------------------------------------------------------------------------+

To prevent this collapse, distributed engineers employ two primary defense patterns: Singleflight Request Coalescing and Probabilistic Early Expiration (XFetch).

2. Mitigation Strategy 1: Singleflight Request Coalescing

The Singleflight pattern ensures that for any given key, only one backend fetch operation is in flight at any given moment. All other concurrent requests sharing the same key pause and await the outcome of the single active worker:

1
Client 1 ----+
2
Client 2 ----+--> [Singleflight Group] ---> [Single Database Query] ---> DB (1 Load)
3
Client 3 ----+          |
4
                        v
5
          Distribute single result to all 3 clients concurrently

1
// Production Go implementation using golang.org/x/sync/singleflight
2
package cache
3

4
import (
5
    "context"
6
    "fmt"
7
    "time"
8
    "github.com/redis/go-redis/v9"
9
    "golang.org/x/sync/singleflight"
10
)
11

12
type ProductCache struct {
13
    rdb *redis.Client
14
    g   singleflight.Group
15
}
16

17
func (c *ProductCache) GetProduct(ctx context.Context, id string) (*Product, error) {
18
    cacheKey := fmt.Sprintf("product:%s", id)
19

20
    // 1. Try reading from Redis
21
    val, err := c.rdb.Get(ctx, cacheKey).Result()
22
    if err == nil {
23
        return deserializeProduct(val), nil
24
    }
25

26
    // 2. Cache Miss: Coalesce all concurrent callers into a single database execution
27
    data, err, _ := c.g.Do(cacheKey, func() (interface{}, error) {
28
        // Double check cache in case another caller populated it moments ago
29
        if v, e := c.rdb.Get(ctx, cacheKey).Result(); e == nil {
30
            return deserializeProduct(v), nil
31
        }
32

33
        // Execute expensive database operation
34
        product, err := queryDatabaseForProduct(ctx, id)
35
        if err != nil {
36
            return nil, err
37
        }
38

39
        // Populate cache with jittered TTL to prevent synchronization avalanches
40
        ttl := 15*time.Minute + time.Duration(deterministicJitter(id))*time.Second
41
        _ = c.rdb.Set(ctx, cacheKey, serializeProduct(product), ttl).Err()
42

43
        return product, nil
44
    })
45

46
    if err != nil {
47
        return nil, err
48
    }
49

50
    return data.(*Product), nil
51
}

3. Mitigation Strategy 2: The XFetch Probabilistic Algorithm

Published in 2015 by Vattani et al., the XFetch algorithm computes a probabilistic decision on every read: as the key approaches its expiration time, the probability of an early asynchronous background refresh increases proportionally to the computational cost of the query:

$\text{Evaluate Refresh Condition: } -\beta \times \delta \times \ln(\text{rand}()) > \text{remaining\_TTL}$

Where:

$\delta$ is the compute time taken to recompute the value (in seconds).
$\beta > 0$ is an aggression multiplier (typically set to $1.0$ ).
$\text{rand}()$ is a uniform random float between $0$ and $1$ .
$\text{remaining\_TTL}$ is the seconds remaining before the cache entry expires.

1
// TypeScript implementation of XFetch probabilistic early recomputation
2
interface CachedItem<T> {
3
  value: T;
4
  delta: number;   // Compute duration in seconds
5
  expiry: number;  // Absolute epoch timestamp (seconds)
6
}
7

8
async function xFetch<T>(
9
  key: string,
10
  ttlSeconds: number,
11
  computeFn: () => Promise<T>,
12
  beta: number = 1.0
13
): Promise<T> {
14
  const raw = await redisClient.get(key);
15
  const now = Date.now() / 1000;
16

17
  if (raw) {
18
    const item: CachedItem<T> = JSON.parse(raw);
19
    const remainingTTL = item.expiry - now;
20

21
    // Probabilistic early expiration check
22
    const shouldRefresh = -beta * item.delta * Math.log(Math.random()) > remainingTTL;
23

24
    if (!shouldRefresh) {
25
      return item.value;
26
    }
27
  }
28

29
  // Trigger recomputation
30
  const startTime = Date.now() / 1000;
31
  const freshValue = await computeFn();
32
  const delta = (Date.now() / 1000) - startTime;
33

34
  const payload: CachedItem<T> = {
35
    value: freshValue,
36
    delta: Math.max(0.01, delta),
37
    expiry: now + ttlSeconds,
38
  };
39

40
  // Store in Redis with safety buffer (TTL + 60s)
41
  await redisClient.set(key, JSON.stringify(payload), 'EX', ttlSeconds + 60);
42

43
  return freshValue;
44
}

Example (Why XFetch Outperforms Fixed TTLs)

With XFetch, keys never expire before being refreshed during active read traffic. As load increases, the probability of an early refresh naturally scales up, ensuring the cache is always warm while executing the underlying query only once per cycle.

4. Redis Cluster Topologies & Hash Slots

When dataset memory demands exceed a single machine’s RAM, or when network interface throughput exceeds 10Gbps, Redis must scale out across a Redis Cluster.

Redis Cluster does not use consistent hashing rings. Instead, it partitions data into 16,384 discrete Hash Slots.

1
[Cluster Topology: 16,384 Hash Slots]
2
+------------------------------------------------------------------------------------+
3
|  Node A: Master (Slots 0 – 5,460)         <-- Replica A (Async Read Replica)       |
4
|  Node B: Master (Slots 5,461 – 10,922)    <-- Replica B (Async Read Replica)       |
5
|  Node C: Master (Slots 10,923 – 16,383)   <-- Replica C (Async Read Replica)       |
6
+------------------------------------------------------------------------------------+
7

8
Hash Slot Mapping Formula:
9
  slot = CRC16(key) mod 16384

The Hash Tag Constraint (`{...}`)

In Redis Cluster, multi-key operations (such as transactions, MGET, or Lua scripts) are forbidden across keys residing on different nodes. If keys map to different hash slots, Redis returns a -CROSSSLOT Keys in request don't hash to the same slot error.

To force related keys into the exact same hash slot and node, wrap the partition key in curly braces:

# BAD: Keys hash to different slots across separate physical nodes
SET user:100:profile "{...}"      # CRC16("user:100:profile") -> Slot 3410 (Node A)
SET user:100:orders "{...}"       # CRC16("user:100:orders")  -> Slot 9812 (Node B)
MGET user:100:profile user:100:orders  # FAILS WITH CROSSSLOT ERROR!

# GOOD: Hash Tag forces CRC16 to hash ONLY the content inside {...}
SET {user:100}:profile "{...}"    # CRC16("user:100") -> Slot 7140 (Node B)
SET {user:100}:orders "{...}"     # CRC16("user:100") -> Slot 7140 (Node B)
MGET {user:100}:profile {user:100}:orders  # SUCCEEDS AT MICROSECOND SPEED!

5. Memory Eviction Policy Matrix

When Redis reaches maxmemory, it must discard data according to its configured eviction policy. Selecting the wrong policy can wipe authentication sessions or crash active workloads:

Eviction Policy	Mechanism	Ideal Production Use Case	Risk Factor
`volatile-lru`	Evicts least recently used keys with an explicit TTL	Mixed workloads (Sessions + Cache)	Retains eternal keys indefinitely
`allkeys-lru`	Evicts least recently used keys across entire database	Pure caching tiers	May drop important metadata
`volatile-lfu`	Evicts least frequently used keys with an explicit TTL	Protecting hot keys from cache misses	Takes time to build frequency data
`noeviction`	Never deletes data; returns error on new writes	Persistent queues / PubSub / Redis as DB	Fails writes immediately when full

1
# Production redis.conf memory settings
2
maxmemory 16gb
3
maxmemory-policy allkeys-lfu          # LFU preserves true hot keys over transient bursts
4
maxmemory-samples 10                  # Increases precision of sampled LFU algorithm

Production Takeaways

Jitter Every TTL: Never use flat constants like TTL = 3600. Add 10% random jitter (3600 + rand(360)) to eliminate synchronized cache avalanches.
Coalesce with Singleflight: Prevent thundering herd traffic against your primary database during cold starts using singleflight.
Use Hash Tags in Redis Cluster: Structure multi-key Redis Cluster keys with {tenant_id}:entity to guarantee slot co-locality.
Prefer LFU over LRU: In high-velocity read systems, allkeys-lfu prevents one-off batch scans from evicting genuinely popular hot keys.