Labs/Data/caching

DataIntermediate

~30 min

Caching Strategies & Invalidation

Accelerate read throughput by orders of magnitude while mastering Cache-Aside, Write-Through, stampede defense, and cache consistency.

#Cache-Aside (Lazy Loading)#Write-Through & Write-Back#Cache Stampede (Thundering Herd)#Cache Penetration & Bloom Filters#TTL & Eviction Policies#Dual-Write Inconsistency

Overview

The Problem Statement

Relational databases and disk-backed datastores are bound by disk I/O, relational joins, indexing overhead, and connection pool limits. Repeatedly computing and querying the same static or semi-static data directly from the primary database leads to saturation, high p99 latencies, and scalability plateaus.

System Invariant:A cache is an optimization, not the source of truth; any cached entry must be reproducible from the primary store, and cache invalidation must prevent permanent divergence.

✓ When To Use

Read-heavy workloads with a high read-to-write ratio (e.g. 10:1 or 100:1).
Expensive computational results (e.g. aggregated reporting, parsed JSON, token validation).
Protecting downstream relational databases from traffic surges.

✕ When NOT To Use

Write-heavy workloads where data changes continuously before ever being read.
Strict real-time systems where reading stale data by even 1 millisecond causes regulatory violation.
Small, low-traffic applications where database queries execute in under 2ms without contention.

Why It Exists

Catastrophic Outage Scenario

A national news site breaks a major election story. The cached article key expires at 20:00:00. At that exact millisecond, 50,000 concurrent readers request the page. All 50,000 requests experience a cache miss and simultaneously query PostgreSQL to render the article. The database CPU hits 100%, IOPS exhaust, the primary database crashes, and the website goes offline globally—a classic Cache Stampede.

Downstream System Degradation:

Primary database CPU saturation and I/O starvation.
Latency degradation across unrelated write transactions sharing the database.
Out-of-memory crashes on cache nodes due to unconstrained key growth.
Silent data corruption when stale cache writes overwrite newer database records.

How It Works

Caching introduces a fast, volatile in-memory tier (e.g., Redis, Memcached) between the application and the persistent database.

In Cache-Aside (Lazy Loading), the application queries the cache first. If found (Cache Hit), data is returned in <1ms. If not found (Cache Miss), the application reads from the database, writes the result into the cache with a Time-To-Live (TTL), and returns.

In Write-Through, writes are made to the cache and the database synchronously in a single operation, ensuring high read consistency.

In Write-Back (Write-Behind), the application writes only to the cache and immediately acknowledges the client. An asynchronous worker flushes modified keys in batches to the database. This delivers immense write performance but risks data loss on cache node crashes.

Single-Node vs Distributed Reality:

In-process caching (e.g., Go sync.Map, Java Caffeine) provides sub-microsecond lookups with zero network serialization, but consumes process RAM and suffers from per-node inconsistency. Distributed caching (e.g., Redis Cluster) provides a unified cache across all application instances but adds 1-2ms network round trips.

Cache-Aside (Lazy Loading)

App checks cache -> on miss, reads DB and populates cache. On write, updates DB and invalidates (deletes) cache key.

+ Only caches requested data; resilient to cache node failure.

- Cache miss latency penalty; risk of reading stale data if invalidation fails.

Write-Through

App writes to cache, which synchronously writes to DB before returning.

+ Cache is never stale; immediate read availability.

- Higher write latency; caches unused data if writes exceed reads.

Probabilistic Early Expiration (XFetch)

As TTL approaches expiration, background workers probabilistically recompute the cache before it expires: time - beta * delta * ln(random()) > ttl.

+ Completely eliminates Cache Stampede without distributed locks.

- Slightly higher compute overhead near expiration.

Engineering Prediction Challenge

Prove It: Predict the System Behavior

Reason before simulating

System State Given

A popular article key 'article:top' with 10,000 concurrent readers expires from Redis at 12:00:00 (Cache Miss).

Prediction Question:

In a naive Cache-Aside implementation without singleflight or mutex locks, what happens to the primary PostgreSQL database?

Postgres seamlessly serves all 10,000 requests from its internal query buffer in 1ms.

A 'Cache Stampede' occurs: all 10,000 reader threads observe a cache miss and simultaneously query the database for the exact same row.

Redis automatically generates the missing row on the fly.

Interactive Visualizer

Simulate Cache-Aside hit and miss latency differentials (RAM 0.6ms vs Postgres 48ms). Watch TTL countdowns and mutation-triggered cache evictions.

Cache-Aside (Lazy Loading) & Invalidation Simulator

Key: shop:product:42

Redis In-Memory Tier

WARM (TTL: 15s)

KEY: shop:product:42

iPhone 16 Pro ($999)

Latency: ~0.5ms via RAM

PostgreSQL Primary Database

PERSISTENT (Source of Truth)

TABLE: products WHERE id = 42

iPhone 16 Pro ($999)

Latency: ~45ms via NVMe SSD + B-Tree Query

Cache warm. Key 'product:42' holds data with 15s TTL.

HIT0.8 ms

Build It Step-by-Step

The engineering blueprint. Expand each sequential milestone to examine requirements, architectural impacts, common pitfalls, and blueprint pseudocode.

Identify Expensive Read Queries & Key Naming

Structure keys hierarchically: `{service}:{entity}:{id}:{version}` (e.g., `shop:product:9482:v1`). Include schema version numbers to enable instant global cache busting during migrations.

Implement Cache-Aside Read Pattern

Execute GET key. If found, deserialize JSON/Protobuf and return. If nil, acquire read from DB, serialize, SET with TTL, and return.

function getProduct(id):
  key = "product:" + id
  val = cache.get(key)
  if val != null:
    return deserialize(val)
  
  data = db.query("SELECT * FROM products WHERE id = ?", id)
  if data != null:
    cache.set(key, serialize(data), ttl=3600)
  return data

Select Eviction Policy & Time-To-Live (TTL)

Always set an explicit TTL on every key. Configure Redis maxmemory eviction policy to `allkeys-lru` (Least Recently Used) or `volatile-lfu` (Least Frequently Used).

Implement Invalidation on Mutation

On database UPDATE or DELETE: update database first, then DELETE the cache key. Deleting is superior to updating because it prevents race conditions where an old write overwrites a newer write.

function updateProduct(id, updates):
  db.execute("UPDATE products SET ... WHERE id = ?", id)
  cache.delete("product:" + id)

Prevent Cache Stampede (Single-Flight Locking)

When a high-traffic key expires, use Go's `singleflight.Group` or Redis distributed mutex so only 1 thread queries the database, while other concurrent callers wait for the result.

Defend Against Cache Penetration & Breakdown

If a client queries non-existent ID `99999999`, the DB returns empty. Without caching, repeated requests hit the DB every time. Cache empty/null markers with a short TTL (e.g. 60 seconds) or deploy a Bloom filter.

Implement Health Degradation Fallback

Wrap cache calls with short timeouts (<10ms) and circuit breakers. If Redis crashes, bypass cache and read directly from DB under reduced traffic concurrency.

Code Implementation

Production-ready, idiomatic reference implementations across Go, TypeScript, Python, and Java with sticky language switching, copy-to-clipboard, and source download.

Core Architectural Design Decisions

Invariants & Mechanics

Decision 01

threading.Event coordinates parallel workers so only one thread executes loader().

Decision 02

Invalidation deletes cache key rather than writing to avoid dirty reads.

Algorithmic Complexity:Thread-safe O(1) coordination.

cache_aside.py•53 LOC

import json
import threading
import time
from typing import Callable, Any, Optional

class CacheAside:
    def __init__(self, cache_client, default_ttl_sec: int = 300):
        self.cache = cache_client
        self.default_ttl = default_ttl_sec
        self._lock = threading.Lock()
        self._inflight = {}

    def get_or_load(self, key: str, loader: Callable[[], Any], ttl: Optional[int] = None) -> Any:
        ttl_sec = ttl or self.default_ttl

        # 1. Probe cache
        try:
            val = self.cache.get(key)
            if val is not None:
                return json.loads(val)
        except Exception:
            pass # Fail open to DB

        # 2. Prevent stampede via synchronized mutex per key
        with self._lock:
            event = self._inflight.get(key)
            if event is None:
                event = threading.Event()
                self._inflight[key] = event
                is_leader = True
            else:
                is_leader = False

        if not is_leader:
            event.wait(timeout=5.0)
            # Re-read cache populated by leader
            cached = self.cache.get(key)
            if cached is not None:
                return json.loads(cached)
            return loader()

        try:
            fresh_data = loader()
            if fresh_data is not None:
                self.cache.setex(key, ttl_sec, json.dumps(fresh_data))
            return fresh_data
        finally:
            with self._lock:
                self._inflight.pop(key, None)
                event.set()

    def invalidate(self, key: str):
        self.cache.delete(key)

Implementation Strategy: Python implementation employing threading.Event leader-follower pattern to protect downstream databases from sudden cache stampedes across concurrent worker threads.

Thread-safe O(1) coordination.

Edge Cases & Failure Modes

Investigate real-world production incidents. Expand each failure mode to analyze symptoms, root causes, and defensive engineering mitigations.

Scenario: Cache Stampede (Thundering Herd)

Consequence: A heavily accessed key expires. 10,000 parallel requests miss simultaneously and overwhelm the primary database.

Engineering Solution: Deploy SingleFlight request collapsing or implement the XFetch probabilistic early recomputation algorithm.

Scenario: Cache Penetration

Consequence: Attackers query millions of non-existent IDs. Every request misses the cache and hits the database.

Engineering Solution: Cache empty/null results with a short 60-second TTL, or place a Bloom filter in front of the cache to intercept non-existent keys.

Scenario: Dual-Write Race Condition

Consequence: Thread 1 updates DB, then pauses. Thread 2 updates DB and updates cache. Thread 1 resumes and writes stale data into cache.

Engineering Solution: Never update cache values directly on DB mutations—always DELETE (invalidate) the cache key instead.

Production Considerations

Production checklist covering observability metrics, horizontal sharding, reliability fail-open patterns, and client identity security.

Scaling to 10x / 100x Traffic:

Implement multi-tier caching: L1 in-process memory (Caffeine/sync.Map) with 5-second TTL + L2 distributed Redis cluster with 1-hour TTL.
Add randomized TTL jitter (+/- 15%) to prevent mass synchronized key expirations.
Shard Redis across multiple nodes using Consistent Hashing.

Telemetry & Observability:

PROMETHEUS METRICS:

➔ cache_hits_total{store}

➔ cache_misses_total{store}

➔ cache_hit_ratio{store}

➔ cache_operation_latency_seconds (p50, p99)

DISTRIBUTED TRACES & LOGS:

➔ Trace span 'cache.get' with tags 'cache.hit: true/false'.

Trade-offs

Select an algorithm below to dynamically compare memory footprints, burst tolerance, boundary precision, and distributed suitability.

Approach	Advantages	Disadvantages	Use When
Cache-Aside (Lazy)	Only caches queried data; resilient to cache node failure.	Miss latency penalty; eventual consistency lag on updates.	Standard read-heavy application workflows.
Write-Through	Zero read misses for written data; high consistency.	Higher write latency; pollutes cache with unread writes.	Data that is guaranteed to be read immediately after creation.
Write-Back (Write-Behind)	Ultra-fast writes; absorbs intense write spikes.	Risk of data loss if cache crashes before flushing to DB.	High-volume analytics, IoT telemetry counters, gaming scoreboards.