Distributed Caching Patterns & Eviction

1. What It Is & Why It Exists

The Core Problem

Persistent storage engines (relational databases, document stores, and distributed filesystems) are fundamentally bounded by disk I/O, disk seek latencies, B-Tree index locking, and multi-tenant connection pools. Typical database query latency ranges from $2\text{ ms}$ to over $50\text{ ms}$.

In high-throughput distributed applications handling hundreds of thousands of read requests per second, querying disk-bound databases directly causes:

• Connection Pool Exhaustion: Available database worker threads and TCP sockets saturate within milliseconds.
• CPU & Lock Contention: Intensive query parsing, table lock contention, and buffer pool churn degrade database throughput.
• Cascading Latency Cliffs (Tail Latency Explosion): P99 and P99.9 latency spikes exponentially, causing upstream service timeouts, client retry storms, and total system brownouts.

The Breakdown: The Unshielded Database Collapse

Concrete Proof: Unshielded Database vs. Distributed Cache

Consider an e-commerce platform processing $200,000\text{ read QPS}$ during a promotional event, where access follows an 80/20 Pareto distribution (80% of queries target 20% of catalog items):

---

The First-Principles Solution: In-Memory Caching

In-memory caching places high-speed, volatile RAM stores (e.g., Redis, Memcached, DynamoDB DAX) between the application tier and the primary persistence layer. Accessing RAM takes $\approx 100\text{ ns}$ compared to $\approx 1\text{ ms} - 10\text{ ms}$ for solid-state disk operations—a speedup of $10,000\times$ to $100,000\times$.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

---

2. Core Mechanics & Caching Design Patterns

Caching Design Patterns Deep-Dive

1. Cache-Aside (Lazy Loading)

• Read Path: The application queries the cache first. On a cache hit, data is returned immediately. On a cache miss, the application queries the database, writes the retrieved value to the cache with a Time-To-Live (TTL), and returns data to the client.
• Write Path: The application updates the database first, then evicts (deletes) the corresponding key from the cache (DEL key).
• Trade-Offs:
  • Pros: Memory-efficient (only queried data is cached); resilient to cache node failures (cache misses gracefully fall back to the DB).
  • Cons: Initial read experiences cache miss latency; vulnerable to dual-write race conditions if not paired with cache eviction.

2. Write-Through

• Mechanics: The application writes directly to the caching layer. The cache synchronously writes data to the underlying database before returning success to the client.
• Trade-Offs:
  • Pros: Cache is never stale; subsequent reads are guaranteed hits.
  • Cons: High write latency (incurs RAM + DB round-trip latency); pollutes cache with data that may never be read again.

3. Write-Behind (Write-Back)

• Mechanics: The application writes directly to the cache, which immediately acknowledges success ($< 1\text{ ms}$). An asynchronous background worker batches dirty cache entries and writes them to the database periodically.
• Trade-Offs:
  • Pros: Extreme write throughput; absorbs write bursts and collapses multiple writes to the same key into a single DB write.
  • Cons: High risk of data loss—if the cache node crashes before flushing dirty pages, uncommitted updates are permanently lost.

4. Refresh-Ahead (Proactive Caching)

• Mechanics: The cache framework analyzes access frequency and automatically reloads keys from the database before their TTL expires.
• Trade-Offs:
  • Pros: Eliminates cache miss latency for hot keys.
  • Cons: Mispredicting access patterns causes unnecessary database load refreshing cold keys.

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

---

Formal Mathematical Formulations

1. Effective Access Time (EAT)

The performance of a tiered memory architecture is governed by its Cache Hit Ratio ($H$):

$\text{Hit Ratio } (H) = \frac{N_{\text{hits}}}{N_{\text{hits}} + N_{\text{misses}}}$

$\text{Effective Access Time (EAT)} = (H \times T_{\text{cache}}) + ((1 - H) \times T_{\text{storage}})$

Where $T_{\text{cache}}$ is in-memory retrieval latency ($0.5\text{ ms}$) and $T_{\text{storage}}$ is primary database query latency ($15.0\text{ ms}$).

2. Probabilistic Early Expiration (The XFetch Algorithm)

To prevent the Cache Stampede without distributed locks, the XFetch algorithm computes an asynchronous early refresh decision dynamically during read queries:

$\text{Trigger Early Refresh if: } -\beta \times \delta \times \ln(U) > \Delta$

Where:

• $\Delta = \text{TTL}_{\text{expiration}} - t_{\text{current}}$ (time remaining until expiration).
• $\delta$ is the observed execution time required to compute/fetch the item from the database.
• $\beta > 0$ is the aggressiveness multiplier (typically $\beta = 1.0$).
• $U \sim \text{Uniform}(0, 1)$ is a random floating-point value.
• As $\Delta \to 0$, the probability of triggering an asynchronous background refresh approaches $1.0$, guaranteeing that at least one client thread refreshes the cache before expiration.

---

Eviction Policies & In-Memory Data Structures

When cache memory reaches its configured maxmemory limit, the eviction policy determines which keys are purged:

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

In-Memory Node Layout

A production LRU node inside a doubly-linked list contains pointers and payload metadata:

---

State-Transition Trace: LRU Doubly-Linked List Eviction

Under capacity limit $C = 3$ entries, with initial state [C, B, A] (Head = C [MRU], Tail = A [LRU]):

---

Eviction Algorithm Comparison Matrix

---

3. Data Migration, Anti-Entropy & Consistency Protocols

Maintaining consistency between a primary relational database and an external caching tier across distributed networks requires addressing the Dual-Write Concurrency Problem:

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

The Invalidation Rule: Never Update, Always Invalidate

To prevent race conditions where out-of-order network packets store stale data in cache indefinitely, never write updated entities directly into the cache. Always execute an atomic Cache Invalidation (DEL key):

$\text{Write Sequence: } \text{Database.Update}() \implies \text{Cache.Delete}(\text{key})$

Asynchronous Anti-Entropy via Change Data Capture (CDC)

In microservice architectures, application code may crash between updating the database and evicting the cache. To achieve guaranteed eventual consistency, production systems decouple cache invalidation from application logic using CDC (Change Data Capture):

Interactive Architecture Diagram
100%Fit100%
Synthesizing vector architecture diagram...

1. Transactional Guarantee: The application writes only to the database. The database writes changes atomically to its append-only transaction log (WAL / MySQL Binlog).
2. Streaming Invalidation: A CDC connector (e.g., Debezium) streams change events to Apache Kafka.
3. Consumer Eviction: Dedicated invalidator workers consume events and execute DEL {tenant}:user:{id} against Redis clusters, guaranteeing cache invalidation even if application instances crash.

3. Online Cluster Resharding, Anti-Entropy & Graceful Draining

• Slot Migration Protocol: Redis Cluster distributes 16,384 slots across primary nodes. During dynamic scaling:
  1. Set target shard state: CLUSTER SETSLOT <slot> IMPORTING <source_node_id>.
  2. Set source shard state: CLUSTER SETSLOT <slot> MIGRATING <target_node_id>.
  3. Batch migrate keys atomically: MIGRATE <target_ip> <port> "" 0 5000 KEYS <key1> <key2>....
  4. Commit slot assignment: broadcast CLUSTER SETSLOT <slot> NODE <target_node_id> to all cluster nodes.
• Client Redirection Handling (ASK vs. MOVED): In-flight keys on migrating slots return -ASK <slot> <target_ip:port>. The client issues an ASKING prefix command to the target node for that single query without updating its local slot routing cache. Once the slot fully commits, queries return -MOVED <slot> <target_ip:port>, prompting clients to refresh their cluster topology map asynchronously.
• Replica Synchronization & Draining: Replicas synchronize state via an in-memory ring buffer (repl-backlog). On brief network blips, partial resynchronization (PSYNC <replication_id> <offset>) avoids full RDB disk dumps. During node decommissioning, operators trigger CLUSTER FAILOVER TAKEOVER to elevate the replica gracefully and drain existing client TCP connections with zero data loss.

---