Designing a Distributed Cache: Eviction Policies, Cache Coherence, and Multi-Tier Caching at Scale

A cache is the first line of defense against latency. Most systems introduce one early, as a Redis cluster fronting a database, and treat it as an infrastructure detail. That works until you hit roughly 50K requests per second and start seeing thundering herds, stale reads across nodes, and a single hot key turning one shard into a bottleneck.

At that point, caching stops being infrastructure and becomes a design problem. This article walks through how to think about that design: eviction algorithms, coherence models, write patterns, multi-tier architectures, and the failure modes you will encounter in production.

Why a Naive Cache Breaks Under Load

A single Redis instance feels frictionless. You get a cache hit, you return the value. You get a miss, you query the database, write to cache, return the value. The code looks like this:

async function getUser(userId: string): Promise<User | null> {
  const cached = await redis.get(`user:${userId}`);
  if (cached) return JSON.parse(cached);

  const user = await db.query('SELECT * FROM users WHERE id = $1', [userId]);
  if (user) await redis.setex(`user:${userId}`, 300, JSON.stringify(user));
  return user;
}

This pattern has four failure modes that only appear at scale:

1. Cache stampede: 10,000 requests arrive simultaneously for the same key that just expired. All of them miss and all of them hit the database.
2. Thundering herd: A cache node goes down. Every request that was hitting that node now goes to the database at once.
3. Hot key saturation: One key (a celebrity user profile, a trending product) gets read 100,000 times per second. A single Redis node handles around 100K ops/sec total, so one key can consume the entire capacity of a shard.
4. Stale coherence: You have two cache nodes. One gets an invalidation signal; the other does not. Reads are now inconsistent depending on which node handles the request.

Each of these has a specific solution. None of them is “just add more Redis nodes.”

Eviction Policies: Choosing the Right Algorithm

When the cache fills up, the eviction policy determines what gets removed. The wrong choice is not obvious until you measure your hit rate and find it lower than expected.

LRU (Least Recently Used)

LRU evicts the entry that was accessed least recently. It models temporal locality well: if you accessed something recently, you will probably need it again soon.

The problem with LRU is scan resistance. A batch job that reads 10 million infrequently-used records will flush every hot entry from the cache, because LRU has no concept of frequency, only recency.

Redis implements a probabilistic LRU by sampling a configurable number of keys and evicting the oldest among the sample. It is not true LRU but has similar characteristics with much lower memory overhead.

// Redis config equivalent
// maxmemory-policy allkeys-lru
// maxmemory-samples 10  (higher = more accurate, more CPU)

// Application-level LRU for L1 in-process cache
class LRUCache<K, V> {
  private map = new Map<K, V>();
  private capacity: number;

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  get(key: K): V | undefined {
    if (!this.map.has(key)) return undefined;
    const value = this.map.get(key)!;
    // Move to end (most recently used)
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }

  set(key: K, value: V): void {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.capacity) {
      // Delete the first (least recently used) entry
      this.map.delete(this.map.keys().next().value);
    }
    this.map.set(key, value);
  }
}

LFU (Least Frequently Used)

LFU evicts the entry with the lowest access count. It is scan-resistant and good for workloads where a subset of keys is consistently hot. The weakness is frequency decay: a key that was hot six hours ago but is now cold keeps a high count and resists eviction.

Redis 4.0 introduced an LFU policy with a logarithmic counter and configurable decay. The lfu-decay-time setting controls how quickly old frequency counts decrease.

Use LFU when your hot set is stable and your access pattern is frequency-driven (content libraries, product catalogs). Use LRU when recency matters more (session data, recent feeds).

TTL-Based Eviction

TTL is not a full eviction policy but a correctness mechanism. Every cache entry should have a TTL unless you have a deliberate strategy for manual invalidation. Without TTL, stale data accumulates indefinitely.

The classic mistake is using a uniform TTL for all keys. Product pages, user profiles, and exchange rates have very different staleness tolerances. Build TTL into the data model:

const TTL_CONFIG: Record<string, number> = {
  'user:profile': 300,      // 5 minutes
  'product:detail': 3600,   // 1 hour
  'exchange:rate': 30,      // 30 seconds
  'session:token': 86400,   // 24 hours
};

async function setCached<T>(
  key: string,
  value: T,
  prefix: string
): Promise<void> {
  const ttl = TTL_CONFIG[prefix] ?? 60;
  await redis.setex(key, ttl, JSON.stringify(value));
}

Eviction Policy Comparison

Policy	Scan-resistant	Frequency-aware	Memory overhead	Best for
LRU	No	No	Low	Session data, recent feeds
LFU	Yes	Yes	Medium	Product catalogs, stable hot sets
TTL	N/A	N/A	None	Time-sensitive data, correctness
Random	Yes	No	None	Uniform access distributions

Cache Coherence in Multi-Node Setups

When you run multiple cache nodes, or multiple application servers each with their own in-process cache, you have a coherence problem: which node has the current value?

Write-Through

In write-through, every write to the database is also written to the cache synchronously. The cache is always consistent with the database, but write latency increases.

async function updateUser(userId: string, data: Partial<User>): Promise<User> {
  const updated = await db.query(
    'UPDATE users SET ... WHERE id = $1 RETURNING *',
    [userId]
  );
  // Synchronous cache write
  await redis.setex(`user:${userId}`, 300, JSON.stringify(updated));
  return updated;
}

Write-through is appropriate when read-after-write consistency matters and writes are infrequent relative to reads.

Write-Behind (Write-Back)

In write-behind, writes go to the cache immediately and are flushed to the database asynchronously. Write latency drops significantly, but you risk data loss if the cache node fails before the flush completes.

class WriteBehindCache {
  private writeQueue: Map<string, { value: unknown; timestamp: number }> = new Map();
  private flushInterval: NodeJS.Timeout;

  constructor(private redis: Redis, private db: Database, intervalMs = 1000) {
    this.flushInterval = setInterval(() => this.flush(), intervalMs);
  }

  async write(key: string, value: unknown): Promise<void> {
    await this.redis.set(key, JSON.stringify(value));
    this.writeQueue.set(key, { value, timestamp: Date.now() });
  }

  private async flush(): Promise<void> {
    const entries = [...this.writeQueue.entries()];
    this.writeQueue.clear();
    await Promise.all(
      entries.map(([key, { value }]) => this.db.upsert(key, value))
    );
  }
}

Write-behind requires durable queuing (write the queue to disk or a message broker) before it is safe for financial or critical data.

Cache Invalidation Patterns

For distributed setups, cache-aside with explicit invalidation is the most practical model. On write, delete the cache entry. On read miss, repopulate it.

The subtlety is invalidation ordering. If you delete the cache entry before committing the database write, a concurrent reader will repopulate from stale data. If you delete after the commit, you have a window where stale data is still served. The correct order is: commit database write, then delete cache entry.

For multi-region deployments, use Redis Pub/Sub or a message bus to broadcast invalidations:

async function invalidateAcrossNodes(key: string): Promise<void> {
  // Delete locally
  await redis.del(key);
  // Broadcast to all nodes
  await redis.publish('cache:invalidate', key);
}

// Each node subscribes
subscriber.subscribe('cache:invalidate', (key) => {
  localCache.delete(key);
});

Multi-Tier Caching Architecture

A single Redis cluster is one tier. Production systems at scale typically need three:

L1: In-process cache (Node.js Map or LRU). Sub-millisecond access, no network hop. Limited to a few hundred MB per process. Consistency is harder because each process has its own copy.

L2: Shared cache (Redis cluster). Single-digit millisecond access. Shared across all application nodes. Your primary cache layer.

L3: Persistent cache (Redis with AOF/RDB persistence, or a dedicated cache database). For expensive computations that survive cache restarts. Full recomputation might take minutes.

class MultiTierCache {
  private l1: LRUCache<string, string>;

  constructor(
    private l2: Redis,
    private l3: Redis,
    l1Capacity = 1000
  ) {
    this.l1 = new LRUCache(l1Capacity);
  }

  async get(key: string): Promise<string | null> {
    // L1 check
    const l1Value = this.l1.get(key);
    if (l1Value !== undefined) return l1Value;

    // L2 check
    const l2Value = await this.l2.get(key);
    if (l2Value !== null) {
      this.l1.set(key, l2Value); // Populate L1
      return l2Value;
    }

    // L3 check
    const l3Value = await this.l3.get(key);
    if (l3Value !== null) {
      this.l1.set(key, l3Value);
      await this.l2.setex(key, 300, l3Value); // Populate L2
      return l3Value;
    }

    return null;
  }

  async set(key: string, value: string, ttl: number): Promise<void> {
    this.l1.set(key, value);
    await this.l2.setex(key, ttl, value);
    await this.l3.setex(key, ttl * 10, value); // L3 has longer TTL
  }
}

The tradeoff with L1 is coherence. Two application instances have different L1 caches, so a write on instance A does not invalidate the L1 on instance B. Solutions are: very short L1 TTLs (5-10 seconds), invalidation broadcasts via Pub/Sub, or restricting L1 to immutable data (configuration, static content).

Production Failure Modes and Mitigations

Cache Stampede

When a popular key expires, all concurrent requests miss and race to repopulate it. The mitigation is a distributed lock with probabilistic early expiration.

async function getWithLock<T>(
  key: string,
  ttl: number,
  fetch: () => Promise<T>
): Promise<T> {
  const cached = await redis.get(key);
  if (cached) return JSON.parse(cached);

  const lockKey = `lock:${key}`;
  const acquired = await redis.set(lockKey, '1', 'NX', 'EX', 10);

  if (!acquired) {
    // Another process is repopulating; wait and retry
    await new Promise(resolve => setTimeout(resolve, 50));
    return getWithLock(key, ttl, fetch);
  }

  try {
    const value = await fetch();
    await redis.setex(key, ttl, JSON.stringify(value));
    return value;
  } finally {
    await redis.del(lockKey);
  }
}

Probabilistic early expiration is an alternative: recompute the value slightly before it expires, using a formula that accounts for the computation time. This spreads the recomputation across time rather than concentrating it at expiry.

Thundering Herd on Node Failure

When a cache node fails, the keys it owned redistribute across remaining nodes. Those keys are cold. Every request for them is a cache miss.

Consistent hashing reduces the blast radius: only the keys owned by the failed node miss, not all keys. Most Redis cluster clients implement this automatically.

For additional protection, use a secondary read replica. If the primary shard is unreachable, read from the replica. Writes can be buffered and retried.

Hot Key Mitigation

A single key that receives a disproportionate share of reads will saturate a single shard regardless of cluster size. Three mitigations:

Key replication: Write the hot value to multiple shards under different keys (product:123:shard:0, product:123:shard:1). Reads distribute randomly across shards.

const SHARD_COUNT = 10;

async function getHotKey(baseKey: string): Promise<string | null> {
  const shard = Math.floor(Math.random() * SHARD_COUNT);
  return redis.get(`${baseKey}:shard:${shard}`);
}

async function setHotKey(baseKey: string, value: string, ttl: number): Promise<void> {
  await Promise.all(
    Array.from({ length: SHARD_COUNT }, (_, i) =>
      redis.setex(`${baseKey}:shard:${i}`, ttl, value)
    )
  );
}

Local caching with short TTL: Push the hot key into the L1 in-process cache with a 5-10 second TTL. 100,000 requests per second across 10 application servers becomes 10,000 per server, handled entirely in-process.

Read-through with coalescing: If multiple requests arrive for the same missing key within a short window, execute only one database query and fan the result back to all waiters. This is the singleflight pattern:

class SingleFlight {
  private inflight = new Map<string, Promise<unknown>>();

  async do<T>(key: string, fetch: () => Promise<T>): Promise<T> {
    if (this.inflight.has(key)) {
      return this.inflight.get(key) as Promise<T>;
    }
    const promise = fetch().finally(() => this.inflight.delete(key));
    this.inflight.set(key, promise);
    return promise;
  }
}

Monitoring the Cache in Production

Cache hit rate is the primary signal. A hit rate below 80% usually means TTLs are too short, the cache is too small, or the access pattern is not cacheable. Instrument every cache operation:

async function timedCacheGet(key: string): Promise<string | null> {
  const start = performance.now();
  const value = await redis.get(key);
  const duration = performance.now() - start;

  metrics.histogram('cache.get.duration_ms', duration);
  metrics.increment(`cache.get.${value !== null ? 'hit' : 'miss'}`);

  return value;
}

Track eviction rate separately from miss rate. High eviction with a high hit rate means the cache is the right size but under memory pressure. High miss rate with low eviction means the access pattern is not matching the cached key set.

Watch for memory fragmentation in Redis. After heavy churn, fragmentation can cause a 20-30% effective capacity reduction. INFO memory reports mem_fragmentation_ratio; values above 1.5 warrant a restart or active defragmentation.

Tradeoffs Summary

Concern	Approach	Cost
Stampede prevention	Distributed lock or probabilistic early expiry	Lock contention on misses
Hot key	Key sharding or L1 local cache	Write amplification or coherence complexity
Coherence in multi-tier	Short L1 TTL or Pub/Sub invalidation	Network overhead or added infrastructure
Node failure	Consistent hashing + read replicas	Replication lag, cost
Write consistency	Write-through	Increased write latency
Write throughput	Write-behind	Risk of data loss on node failure

Closing

A distributed cache that works at 1,000 requests per second will break in specific, predictable ways at 100,000. The failure modes are not random: they are stampede, hot key saturation, incoherent reads, and cascading misses after node failure. Each has an established solution. The engineering work is understanding your access pattern clearly enough to know which problems you are actually facing, then applying the right mitigation without over-engineering the ones you are not.

Start with a single Redis cluster and instrument hit rate, miss rate, and eviction rate from day one. Those three signals will tell you when and where to add tiers.