Distributed Caching Internals: Redis Eviction Policies, Cache Invalidation & Multi-Tier Architecture

1.1 The Reactor Pattern & The aeEventLoop Execution Model

Redis achieves massive throughput on a nominally single-threaded architecture by leveraging the Reactor pattern via its custom ae.c event-driven library. At its core, the aeEventLoop multiplexes I/O by wrapping kernel-level socket readiness notification systems (e.g., epoll on Linux, kqueue on BSD). The cycle heavily relies on registering and processing file events (AE_READABLE, AE_WRITABLE) while enforcing deterministic lockstep command execution.

The standard execution cycle triggers an epoll_wait dispatch. As sockets become readable, they enter input buffers where the RESP (REdis Serialization Protocol) is parsed. The main thread then fetches commands, executes them purely sequentially (avoiding mutex locks and data races), registers AE_WRITABLE handlers for output buffers, and loops. Additionally, the serverCron routine fires at 100 Hz to handle background operations like expiration and defragmentation.

sequenceDiagram
    participant Kernel as Linux Kernel (epoll)
    participant Mux as aeEventLoop
    participant IOT as I/O Threads (6.0+)
    participant Main as Main Thread execution
    
    Kernel->>Mux: epoll_wait (Sockets Ready)
    Mux->>IOT: AE_READABLE: Delegate Socket Read and RESP Parse
    IOT->>Main: Push Parsed Commands to Queue
    Main->>Main: Execute Commands (Strictly Single-Threaded)
    Main->>IOT: AE_WRITABLE: Delegate Output Buffer Writes
    IOT->>Kernel: Flush Sockets to Client
    Main->>Main: serverCron (100 Hz Background Tasks)
    

1.2 Jemalloc Architecture & Arena Allocation Dynamics

Redis fundamentally avoids the glibc default allocator (malloc) due to fragmentation and lock contention, favoring jemalloc. Jemalloc partitions memory into Arenas, dividing allocations into size classes: small (8B to 14KB), large (16KB to 7MB), and huge (8MB+). Memory blocks of the same size class are batched into slabs (or bins) which drastically reduces overhead and speeds up object creation.

Crucially, Redis explicitly disables jemalloc's Thread Caching (tcache) for the main thread. While tcache usually improves multi-threaded performance by maintaining thread-local free lists, it can cause severe memory accumulation in single-threaded workloads, as deallocated memory remains bound to the thread instead of returning to the central Arena, inflating RSS (Resident Set Size).

1.3 C-Level Object Memory Anatomy & Byte Layout

To understand exactly how our catalog-query-service objects sit in memory, we must deconstruct the C-level representation of a Redis key-value pair. Every entry in the global dictionary utilizes a dictEntry, which maps to a Redis Object (robj) wrapping the actual data.

/* dictEntry: 24 bytes (on 64-bit systems) */
typedef struct dictEntry {
    void *key;             // 8B pointer
    union {
        void *val;         // 8B pointer
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 8B pointer
} dictEntry;

/* robj: 16 bytes */
typedef struct redisObject {
    unsigned type:4;       // e.g., OBJ_STRING
    unsigned encoding:4;   // e.g., OBJ_ENCODING_RAW
    unsigned lru:LRU_BITS; // 24-bit LRU clock
    int refcount;          // 32-bit (4B) reference count
    void *ptr;             // 8B pointer to the actual SDS
} robj;

/* sdshdr8: 3 byte header */
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;           // 1B used length
    uint8_t alloc;         // 1B allocated length
    unsigned char flags;   // 1B type flag
    char buf[];            // Flexible array member
};

NexusShop Flash Deal Payload Allocation Calculation

Consider our canonical key: cache:catalog:flash_deals:v2 (28 bytes) pointing to an 11.4 KB JSON payload.

• The raw payload is 11,673 bytes (11.4 KB).
• Adding the SDS header (sdshdr16, 5 bytes) and null terminator (1 byte), the string requires 11,679 bytes.
• Jemalloc rounds this up to the nearest small size class slab bin, which is 12 KB (12,288 bytes).

This structural misalignment leads directly to 609 bytes of internal fragmentation per key ($12,288 - 11,679 = 609$). At a scale of millions of flash deal variants, this internal fragmentation severely impacts memory efficiency and $F_{\text{mem}}$.

graph TD
    subgraph Slabs["Jemalloc Slabs and Bins"]
        DE["dictEntry (24B)"] -->|*key| SDSKey["sdshdr8 + string (32B Slab)"]
        DE -->|*val| ROBJ["robj (16B Slab)"]
        ROBJ -->|*ptr| SDSPayload["SDS Payload (12 KB Slab Bin)"]
        
        SDSPayload -.-> USE["11,679 Bytes Used"]
        SDSPayload -.-> IFRAME["609 Bytes Internal Fragmentation"]
    end
    

1.4 Linux Virtual Memory, THP Hazards & Active Defragmentation

While jemalloc minimizes fragmentation efficiently, OS-level paging dynamics pose a massive threat to P99 latencies. The primary culprit is Transparent Huge Pages (THP). Linux attempts to collapse standard 4KB memory pages into 2MB huge pages to reduce Translation Lookaside Buffer (TLB) misses.

During a Redis background save (BGSAVE for RDB or AOF rewrite), the process calls fork(). Because the fork() leverages Copy-On-Write (COW), any write to a page by the main thread forces the OS to duplicate that page for the background process. If THP is enabled, a single 1-byte mutation in a key forces the kernel to copy an entire 2MB huge page, triggering memory latency spikes ranging from 50ms to over 200ms.

When external fragmentation (indicated by high $F_{\text{mem}}$) exceeds acceptable bounds, Redis operates its Active Defragmentation engine (activedefrag yes). Active defragmentation continuously scans dicts and reallocates sparse jemalloc slabs on the fly. To prevent CPU starvation during production peaks, it is strictly governed by background cycle limits:

• active-defrag-ignore-bytes 100mb: Prevents churn on insignificant fragmentation.
• active-defrag-threshold-lower 10: Only activates if fragmentation exceeds 10%.
• active-defrag-cycle-max 25: Caps CPU usage to 25%, preventing the main thread from stalling client requests during extensive memory compaction.

2.1 Why True LRU/LFU Is Mathematically Prohibitive in Redis

A true LRU cache requires maintaining a strict chronological ordering of accesses, traditionally implemented via a doubly linked list coupled with a hash map. Every GET or SET operation must detach the accessed node and relink it at the head of the list.

At NexusShop's scale (50M keys in L2), the memory tax of exact LRU is devastating. A doubly linked list requires two 64-bit pointers (prev and next) per key. This imposes a strict 16-byte overhead per entry:

Beyond memory consumption, strict LRU violates mechanical sympathy. Linked lists suffer from poor spatial locality, inducing relentless CPU cache-line thrashing (L1/L2 misses) during traversals. Furthermore, mutating pointers on every single read operation introduces unacceptable locking contention in dictionary lookups, destroying the single-threaded reactor throughput. A stateless, zero-mutation read mechanism is mandatory.

2.2 Approximated LRU Architecture

To eliminate the 16-byte overhead and read-mutation penalty, Redis uses an approximated LRU model built on random sampling and a shared global clock. As established in Section 1, the robj struct contains a 24-bit lru field. When a key is accessed, Redis cheaply copies the global server.lruclock into this field.

The server.lruclock is updated asynchronously via the serverCron() background loop. It ticks with a 1-second resolution. Because 24 bits max out at \( 2^{24}-1 \) seconds, the clock rolls over every 194 days.

When eviction triggers, Redis does not scan the whole keyspace. It executes dictGetSomeKeys() to randomly sample \( S_{\text{samples}} \) keys (default 5). These candidates are evaluated against a global 16-slot Eviction Pool (struct evictionPoolEntry).

graph LR
    A["dictGetSomeKeys()
Draw 5 Random Keys"] --> B["Calculate Delta_idle
for each key"]
    B --> C{"Delta_idle > Min(Pool)?"}
    C -- Yes --> D["Insertion Sort into
16-Slot Eviction Pool"]
    C -- No --> E["Discard Candidate"]
    D --> F{"Maxmemory breached?"}
    F -- Yes --> G["Evict Tail (Rightmost)
Key with Highest Delta_idle"]

The eviction pool persistently holds the best (most idle) candidates across multiple eviction cycles. Keys are inserted in ascending order of idle time. The rightmost key (the oldest) is sacrificed.

2.3 Logarithmic LFU: Bitfield Dissection & Frequency Math

While approximated LRU protects against temporal drift, it is blind to access frequency. Under LFU mode, Redis surgically repurposes the identical 24-bit robj.lru field to track both time and frequency simultaneously without allocating a single extra byte.

graph TD
    A["robj.lru (24 bits total overhead)"] --> B["LDT: Last Decrement Time (Upper 16 bits)"]
    A --> C["LOG_C: Logarithmic Counter (Lower 8 bits)"]
    B -.-> D["Timestamp in minutes (Modulo 65536, ~45 days)"]
    C -.-> E["Non-linear access frequency (Saturated at 255)"]

Because 8 bits can only natively represent 0-255, Redis employs a probabilistic increment step paired with a time-based decay. When a key is accessed, two mathematical operations occur:

1. The Decay Step

Frequency counts must decay over time to allow transiently hot keys to cool down, preventing cache stagnation. The decay is computed against the 16-bit LDT:

2. The Probabilistic Increment Step

After applying decay, Redis probabilistically increments the 8-bit LOG_C to track frequency. The probability of incrementing \( P_{\text{inc}} \) is inversely proportional to the current counter value and scaled by \(\alpha\) (the lfu-log-factor):

2.4 NexusShop Real-World Scenario: The Scan Pollution Problem

Consider a recurring failure at NexusShop: At 02:00 AM, a nightly batch scraper process iterates over the catalog-query-service to index 500,000 dormant, cold products. The L2 cache is at maxmemory capacity.

Under allkeys-lru (The Failure):
Every cold product scanned overwrites its robj.lru with the immediate server.lruclock. By definition, they become the "most recently used." Meanwhile, our canonical hot key, cache:catalog:flash_deals:v2, hasn't been accessed in the last 4 seconds. When the memory limit breaches, the random sampler evaluates cache:catalog:flash_deals:v2 against the scanned cold keys. The flash deals key has a higher \( \Delta_{\text{idle}} \) and gets flushed into the Eviction Pool. The result? Cache miss on the most critical payload, spiking PostgreSQL CPU and laying the groundwork for a catastrophic thundering herd stampede.

Under allkeys-lfu (The Rescue):
When a cold key is fetched, it defaults to LFU_INIT_VAL (LOG_C = 5). Our hot payload, cache:catalog:flash_deals:v2, has sustained millions of hits and sits saturated at LOG_C = 255. When the eviction sampler grabs a cold key (LOG_C = 5) and the flash deal key (LOG_C = 255), LFU flawlessly identifies the cold key as garbage. The cold products are rapidly churned out of the eviction pool while the flash deals key remains untouched. The scan pollution is completely neutralized.

2.5 Eviction Policy Matrix & Tuning \( S_{\text{samples}} \)

The precision of approximated eviction hinges on \( S_{\text{samples}} \). Tuning this value in redis.conf (maxmemory-samples) is a direct trade-off between CPU overhead and algorithmic accuracy.

• \( S_{\text{samples}} = 5 \) (Default): Provides an optimal balance. It rapidly yields candidates good enough to protect primary keys without burning excess CPU cycles traversing the dictionary tree.
• \( S_{\text{samples}} = 10 \): Approximates exact mathematical LRU/LFU perfectly, but doubles the CPU sampling overhead during critical memory pressure windows. Use only if cache thrashing costs heavily outweigh Redis CPU headroom.

3.1 Taxonomy of Caching Topologies & Write Strategies

To safely invalidate cache:catalog:flash_deals:v2, we must map out the synchronization topologies. The architectural choice dictates whether the cache acts as a lazy operational view or an inline proxy.

3.2 Formal Proof of Dual-Write Race Conditions

When implementing the Cache-Aside pattern in catalog-query-service, the absolute ordering of operations between PostgreSQL and Redis dictates the temporal window for data corruption. Let us formally evaluate the two canonical write paths.

Scenario A: Delete Cache THEN Update Database (Anti-Pattern)

If Thread 1 issues DEL cache:catalog:flash_deals:v2 and then begins a PostgreSQL transaction, it opens a massive, unbounded race window:

1. Thread 1: Deletes cache key.
2. Thread 2: Reads cache (MISS), queries PostgreSQL (Reads OLD price: $999).
3. Thread 1: Commits DB update (NEW price: $799).
4. Thread 2: Writes OLD price ($999) to Redis.

Result: Permanent cache corruption. The cache will serve $999 indefinitely until the next TTL expiration or LFU eviction, while the DB holds $799.

Scenario B: Update Database THEN Delete Cache

Inverting the order mathematically shrinks the race condition window to near zero, but does not eliminate it. For this race to occur, Thread 2 must experience an extreme context switch stall between reading the DB and writing to the cache, allowing Thread 1 to execute an entire DB transaction and cache deletion entirely within that stall window.

The Read-Replica Replication Lag Trap

Scenario B assumes a single monolithic database. In the NexusShop topology, we utilize 1 PostgreSQL 16 Primary and 3 Read Replicas. This introduces $T_{\text{lag}}$, the asynchronous WAL stream delay (typically 50-300ms depending on network partitions and disk IOPS). This completely invalidates Scenario B's safety guarantees.

sequenceDiagram
    participant W as Writer (Primary)
    participant R as Reader (Replica)
    participant DB_P as PG 16 Primary
    participant DB_R as PG 16 Replica
    participant Redis as Redis Cluster
    
    W->>DB_P: UPDATE products SET price=799
    DB_P-->>W: Commit ACK
    W->>Redis: UNLINK cache:catalog:flash_deals:v2
    Note over DB_P, DB_R: Async WAL Replication (300ms Lag Window)
    
    R->>Redis: GET cache:catalog:flash_deals:v2 (MISS)
    R->>DB_R: SELECT price FROM products
    Note over DB_R, R: Reads OLD price ($999) due to replica lag
    
    DB_P-)DB_R: Apply WAL (price=799)
    
    R->>Redis: SET cache:catalog:flash_deals:v2 999
    Note right of Redis: Permanent Stale Data!

3.3 Asynchronous Invalidation via Change Data Capture (CDC)

To eliminate distributed race conditions under read-replica lag, we must decouple the cache invalidation from the application tier entirely and bind it to the database's actual commit log (WAL). This is achieved via a Change Data Capture (CDC) pipeline.

flowchart LR
    subgraph NexusShop DB Tier
        P[PostgreSQL 16 Primary]
    end
    subgraph Streaming Tier
        DBZ[Debezium Connector]
        K[Kafka cdc:catalog:product_updates]
    end
    subgraph Invalidation Tier
        W[Go/Python CDC Worker]
        R[Redis Cluster]
    end
    P -- "pgoutput (Logical Decoding)" --> DBZ
    DBZ -- "Avro/JSON + LSN" --> K
    K -- "Consumer Group" --> W
    W -- "UNLINK" --> R

Why UNLINK instead of DEL?

In Section 1, we detailed the aeEventLoop reactor. DEL is a synchronous, blocking operation. If cache:catalog:flash_deals:v2 contained a massive serialized object (or if we were invalidating a large Redis Hash/Set with millions of elements), DEL iterates through the memory slabs to free the robj and dictEntry pointers on the main event loop, stalling all other client requests.

UNLINK executes in $O(1)$ time on the main thread. It merely unlinks the key from the dictionary space and increments a background task counter. A separate background thread defined in Redis's bio.c (Background I/O) handles the actual memory reclamation via jemalloc, maintaining uninterrupted P99 latency.

Handling Out-of-Order Deliveries: The LSN Version Vector

Kafka guarantees at-least-once delivery, meaning our invalidation worker might receive duplicate or out-of-order CDC events. A naive UNLINK is idempotent, but if we are actively pushing hydrated data into the cache from the CDC worker, we must prevent older row versions from overwriting newer ones. We embed the PostgreSQL Log Sequence Number (LSN) as a version vector.

import json
from confluent_kafka import Consumer
import redis
from typing import Dict, Any

# Initialize Redis client with connection pooling
redis_client = redis.Redis(host='redis-cluster.local', port=6379, decode_responses=True)

def process_cdc_event(event_payload: Dict[str, Any]) -> None:
    """
    Processes a Debezium CDC event for the products table.
    Payload includes 'after' state and PostgreSQL LSN (Log Sequence Number).
    """
    product_id = event_payload['after']['id']
    new_price = event_payload['after']['price']
    current_lsn = event_payload['source']['lsn']
    
    cache_key = f"cache:catalog:product:{product_id}"
    
    # Lua script for atomic Compare-and-Swap (CAS) based on LSN
    # Prevents older WAL events from overwriting newer cache states
    lua_script = """
    local current_lsn = redis.call('HGET', KEYS[1], 'lsn')
    if not current_lsn or tonumber(current_lsn) < tonumber(ARGV[2]) then
        redis.call('HSET', KEYS[1], 'price', ARGV[1], 'lsn', ARGV[2])
        redis.call('EXPIRE', KEYS[1], 3600)
        return 1
    end
    return 0
    """
    
    try:
        applied = redis_client.eval(lua_script, 1, cache_key, new_price, current_lsn)
        if applied:
            print(f"Updated {cache_key} to price {new_price} at LSN {current_lsn}")
        else:
            print(f"Ignored stale CDC event for {cache_key}. LSN {current_lsn} is older than cache.")
            
    except redis.RedisError as e:
        print(f"Redis pipeline failed: {e}")
        raise

3.4 Why Distributed 2PC (Two-Phase Commit) Is an Anti-Pattern

Engineers often attempt to solve cache consistency by wrapping PostgreSQL and Redis in a distributed transaction using the XA standard or Two-Phase Commit (2PC). This is a critical production anti-pattern.

• Event Loop Stalling: 2PC requires a distributed coordinator. If the coordinator sends a PREPARE command to Redis, and a network partition occurs, the lock is held indefinitely. Redis lacks native MVCC (Multi-Version Concurrency Control) for rollback isolation, meaning distributed locks halt the single-threaded reactor.
• CAP Theorem Violation: By coupling PostgreSQL and Redis in a synchronous transaction, the system's availability ($A$) is degraded to the multiplication of both systems' failure probabilities. If the cache tier experiences a rolling restart, all database write throughput drops to zero.

4.1 Multi-Tier Caching Architecture (L1 Heap + L2 Redis Cluster)

Bridging the sub-millisecond CPU local heap access with the robust scalability of a Redis Cluster requires a mathematically bound multi-tier architecture. In the NexusShop platform, the catalog-query-service relies on a Level 1 (L1) W-TinyLFU cache (Ristretto/Caffeine) handling hot keys like cache:catalog:flash_deals:v2, falling back to Level 2 (L2) Redis 7.2, and ultimately PostgreSQL 16.

Evaluating this for the NexusShop infrastructure, the fallback penalty bounds gracefully: $L_{\text{eff}} = 0.80 \cdot 50\mu\text{s} + 0.20 \cdot [0.95 \cdot 1500\mu\text{s} + 0.05 \cdot 35000\mu\text{s}] \approx 675\mu\text{s}$. (Note: With highly optimized L1 pipelines yielding 0.95+ hit rates, this bounds closer to ~210µs). This strict probability chain prevents tail latency spikes, but introduces thundering herd vulnerabilities on global expirations.

4.2 The Singleflight Concurrency Collapser (Request Coalescing)

At 45,000 requests per second, a cache miss on the 11.4 KB cache:catalog:flash_deals:v2 payload represents an imminent PostgreSQL death spiral. The Singleflight pattern (Request Coalescing) mitigates this by collapsing identical concurrent requests into a single downstream call.

Internally, a singleflight map maintains active execution promises protected by a mutex. When 45,000 threads miss the cache simultaneously, the first thread claims the map key and executes the DB query. The remaining 44,999 threads are parked on a broadcast channel (Go) or CompletableFuture (Java) waiting for the initial thread to resolve.

sequenceDiagram
    participant Others as 44k Waiting Threads
    participant Thread1 as Thread 1
    participant SF as Singleflight Group
    participant DB as PostgreSQL 16
    Thread1->>SF: Do("flash_deals:v2")
    SF->>SF: Lock Mutex, set state "inflight"
    SF->>DB: SELECT ... (35ms execution)
    Others->>SF: Do("flash_deals:v2")
    SF-->>Others: Park on Channel WaitGroup
    DB-->>SF: Return 11.4KB payload
    SF->>SF: Broadcast result and delete map key
    SF-->>Thread1: Return Result
    SF-->>Others: Unpark, Return Broadcast Result

4.3 XFetch: Optimal Probabilistic Early Expiration

Fixed TTLs naturally produce a cliff-drop where the item abruptly vanishes, forcing synchronous blocking (even with singleflight). The XFetch algorithm (Vattani et al.) pre-empts this by applying a probabilistic curve that forces an asynchronous background refresh before the TTL expires, while immediately returning the still-valid stale data to the requestor.

On every L1/L2 cache read, the application evaluates: if TTL_remaining ≤ Δt_fetch. At high TTLs, the logarithmic probability is effectively zero. As TTL_remaining approaches 0, the probability of an early refresh approaches 100%, gracefully staggering background recomputations to prevent stampedes.

4.4 Production Multi-Language Code Implementations

package cache

import (
	"context"
	"encoding/json"
	"math"
	"math/rand"
	"time"

	"github.com/dgraph-io/ristretto"
	"github.com/redis/go-redis/v9"
	"golang.org/x/sync/singleflight"
)

type MultiTierCache struct {
	l1    *ristretto.Cache
	l2    *redis.ClusterClient
	group singleflight.Group
}

type CacheEntry struct {
	Data     []byte
	Delta    float64 // DB compute time in seconds
	ExpireAt time.Time
}

func (c *MultiTierCache) GetFlashDeals(ctx context.Context, key string) ([]byte, error) {
	// L1 Check
	if val, found := c.l1.Get(key); found {
		entry := val.(CacheEntry)
		if c.shouldXFetch(entry) {
			go c.asyncRefresh(context.Background(), key)
		}
		return entry.Data, nil
	}

	// Singleflight L2 & DB fallback
	v, err, _ := c.group.Do(key, func() (interface{}, error) {
		// Check L2 Redis
		val, err := c.l2.Get(ctx, key).Bytes()
		if err == nil {
			var entry CacheEntry
			json.Unmarshal(val, &entry)
			c.l1.SetWithTTL(key, entry, 1, time.Until(entry.ExpireAt))
			if c.shouldXFetch(entry) {
				go c.asyncRefresh(context.Background(), key)
			}
			return entry.Data, nil
		}

		// DB Query Fallback (35ms execution)
		start := time.Now()
		data := fetchFromDB(key)
		delta := time.Since(start).Seconds()

		entry := CacheEntry{
			Data:     data,
			Delta:    delta,
			ExpireAt: time.Now().Add(5 * time.Minute),
		}
		
		b, _ := json.Marshal(entry)
		c.l2.Set(ctx, key, b, 5*time.Minute)
		c.l1.SetWithTTL(key, entry, 1, 5*time.Minute)

		return data, nil
	})

	if err != nil {
		return nil, err
	}
	return v.([]byte), nil
}

func (c *MultiTierCache) shouldXFetch(entry CacheEntry) bool {
	remaining := time.Until(entry.ExpireAt).Seconds()
	if remaining < 0 {
		return true
	}
	prob := -1.0 * entry.Delta * math.Log(rand.Float64())
	return remaining <= prob
}

package com.nexusshop.cache;

import com.github.benmanes.caffeine.cache.Cache;
import redis.clients.jedis.JedisCluster;
import java.util.concurrent.*;
import java.time.Instant;

public class MultiTierCache {
    private final Cache<String, CacheEntry> l1;
    private final JedisCluster l2;
    private final ConcurrentHashMap<String, CompletableFuture<byte[]>> flights;
    private final ExecutorService bgWorkers;

    record CacheEntry(byte[] data, double delta, Instant expireAt) {}

    public byte[] getFlashDeals(String key) throws Exception {
        CacheEntry entry = l1.getIfPresent(key);
        if (entry != null) {
            if (shouldXFetch(entry)) {
                bgWorkers.submit(() -> asyncRefresh(key));
            }
            return entry.data();
        }

        // Singleflight collapser
        return flights.computeIfAbsent(key, k -> CompletableFuture.supplyAsync(() -> {
            try {
                long start = System.nanoTime();
                byte[] dbData = fetchFromDB(k);
                double delta = (System.nanoTime() - start) / 1_000_000_000.0;
                
                return dbData;
            } finally {
                flights.remove(k);
            }
        }, bgWorkers)).join();
    }

    private boolean shouldXFetch(CacheEntry entry) {
        double remaining = java.time.Duration.between(Instant.now(), entry.expireAt()).toMillis() / 1000.0;
        if (remaining < 0) return true;
        double u = ThreadLocalRandom.current().nextDouble();
        double prob = -1.0 * entry.delta() * Math.log(u);
        return remaining <= prob;
    }
}

4.5 Serialization Wire Protocols: JSON vs Protobuf vs MessagePack

Using standard JSON for the 11.4 KB cache:catalog:flash_deals:v2 structure bloats L1 heap allocations, inflates L2 network transfer times, and exhausts Redis slab fragmentation. Migrating to binary protocols fundamentally rewrites the $L_{\text{eff}}$ lower bounds by minimizing CPU serialization cycles and memory footprints.

5.1 Incident Timeline & Forensic Analysis: Black Friday Flash Sale Launch

The failure originated from a strict, synchronized time-to-live (TTL) expiration without jitter on the cache:catalog:flash_deals:v2 key. When this 11.4 KB JSON payload expired simultaneously across all nodes, the system collapsed under the immediate stampede of 45,000 QPS.

sequenceDiagram
    participant User as Web/Mobile Clients
    participant Envoy as Envoy API Gateway
    participant Svc as catalog-query-service
    participant Redis as L2 Redis (cache:catalog:flash_deals:v2)
    participant PgB as PgBouncer
    participant DB as PostgreSQL 16
    
    User->>Envoy: GET /v1/products/flash-deals (45k QPS)
    Envoy->>Svc: Forward Requests
    Note over Svc,Redis: T-00:00:00: TTL Expires exactly at 00:00:00
    Svc->>Redis: GET cache:catalog:flash_deals:v2
    Redis-->>Svc: MISS (for 45,000 concurrent requests)
    Note over Svc,PgB: T+00:00:00.450: The Thundering Herd
    Svc->>PgB: 45k parallel DB Connection Requests
    PgB-->>Svc: Pool Exhausted (Max 200), Queueing...
    PgB->>DB: 200 concurrent complex materialized queries
    Note over DB: T+00:00:01.200: CPU 100%, MVCC Lock Contention
    DB-->>PgB: Query Latency > 8200ms
    PgB-->>Svc: Connection Timeout / Slow Read
    Svc-->>Envoy: Latency spikes beyond SLA
    Note over Envoy: T+00:00:03.500: Circuit Breaker Trips
    Envoy-->>User: HTTP 504 Gateway Timeout

5.2 SRE Diagnostic Runbook & War Room Triage

When the pager triggers, the immediate goal is to stabilize the database and shed load to restore partial service. The on-call engineers executed the following triage runbook:

1. Redis Diagnostics

First, verify if Redis is suffering from a hot key eviction, memory fragmentation, or massive keyspace misses.

# Check for massive keyspace misses (identifies stampede condition)
redis-cli -c -h redis-node-01 info stats | grep keyspace_misses

# Inspect latency spikes at the kernel/engine level
redis-cli -c -h redis-node-01 latency-doctor

# Identify scan pollution or large payloads causing network saturation
redis-cli -c -h redis-node-01 --bigkeys
redis-cli -c -h redis-node-01 --hotkeys

2. PostgreSQL Diagnostics

Because the Redis cache missed, the database absorbed the impact. We query pg_stat_activity to identify and terminate the thundering herd's stalled read connections to save the primary.

-- Inspect locked transactions and stalled client connections
SELECT pid, usename, state, wait_event_type, wait_event, query, 
       ROUND(EXTRACT(epoch FROM now() - query_start)) AS duration_sec
FROM pg_stat_activity
WHERE state = 'active' 
  AND query ILIKE '%flash_deals%'
ORDER BY duration_sec DESC;

-- Emergency triage: Terminate all stalled read connections for the query service
SELECT pg_terminate_backend(pid) 
FROM pg_stat_activity 
WHERE state = 'active' 
  AND usename = 'catalog_query_user' 
  AND (now() - query_start) > interval '2 seconds';

3. Emergency Traffic Shedding & Circuit Breaking

To give the backend time to recover, we temporarily applied an Envoy dynamic route configuration to shed 60% of anonymous traffic, returning a degraded static JSON payload for the flash deals.

# envoy-emergency-shedding.yaml
routes:
- match:
    prefix: "/v1/products/flash-deals"
  route:
    cluster: catalog_query_service
  typed_per_filter_config:
    envoy.filters.http.local_ratelimit:
      "@type": type.googleapis.com/envoy.extensions.filters.http.local_ratelimit.v3.LocalRateLimit
      stat_prefix: http_local_rate_limiter
      token_bucket:
        max_tokens: 15000  # Cap at 15k QPS
        tokens_per_fill: 15000
        fill_interval: 1s
      filter_enabled:
        runtime_key: local_rate_limit_enabled
        default_value:
          numerator: 100
          denominator: HUNDRED
      status: 503
      response_headers_to_add:
        - append_action: OVERWRITE_IF_EXISTS_OR_ADD
          header:
            key: x-fallback-mode
            value: "static-degraded-payload"

graph TD
    A["Inbound 45k QPS"] --> B["Envoy API Gateway"]
    B -->|Rate Limit Exceeded| C["Degraded Mock Cache 
 HTTP 503 / Static Payload"]
    B -->|Allowed Traffic 15k QPS| D["catalog-query-service"]
    D --> E["Redis Cluster"]
    D --> F["PostgreSQL via PgBouncer"]

5.3 Permanent Engineering Remediation Architecture

The outage highlighted structural flaws in how caching was applied to high-traffic anchor entities. We implemented a three-pillar permanent remediation strategy.

Remediation 1: Mathematical TTL Jitter

A synchronized TTL acts as a timebomb. We introduced mathematical TTL jitter to spread the expiration of distributed cache keys across a controlled time window, preventing coordinated miss cliffs. By distributing the misses, we stabilize the arrival rate ($\lambda$) in the queueing system.

Using Little's Law, we can see the impact on PgBouncer wait queues:

Remediation 2: Rolling Deployment of Singleflight + XFetch

We deployed the Singleflight and XFetch modules (detailed in Section 4). Singleflight ensures that even if a jittered cache miss occurs during a traffic spike, only one thread is allowed to traverse PgBouncer to execute the PostgreSQL query. The other 44,999 requests safely wait in memory for the single leader thread to populate the L1 and L2 caches.

Remediation 3: Redis Read Replicas (READONLY Mode)

To eliminate contention on the Redis primary write shards, we horizontally scaled read capacity. By configuring the Redis clients to execute the READONLY command upon connection, the catalog-query-service routes all GET operations for cache:catalog:flash_deals:v2 to the 6 Read Replicas, fully preserving the Primary for the write-heavy CDC invalidation events.

6.1 The Definitive Caching Architecture Decision Matrix

Choosing the optimal caching backend is not merely a function of throughput; it requires mapping workload primitives to the underlying memory allocators, thread models, and invalidation semantics. Below is a rigorous comparison of five industry-standard caching architectures.

Caching Tier Decision Tree

Use the following logic flow to determine the correct topology for your workload attributes.

graph TD
    A["Analyze Workload Attributes"] --> B{"QPS > 100K and High Read-Ratio?"}
    B -- Yes --> C{"Cross-Region Deployment?"}
    B -- No --> D["Single-Tier Redis Cluster"]
    C -- Yes --> E{"Requires Sub-Millisecond Reads?"}
    C -- No --> F["Dragonfly or Memcached"]
    E -- Yes --> G["Multi-Tier: L1 Caffeine + L2 Redis Active-Active"]
    E -- No --> H["Global Redis Cluster with Read-Replicas"]
    

6.2 Multi-Region Active-Active Distributed Caching & WAN Invalidation

As NexusShop expands across us-east-1 (Primary) and eu-central-1 (Active Replica), maintaining the canonical cache:catalog:flash_deals:v2 becomes a distributed systems challenge. The ~80ms transatlantic RTT fundamentally breaks synchronous cache reading—waiting 80ms for an L2 read violates our P99 SLAs.

To support localized read speeds with global consistency, two patterns emerge: CRDT-backed Redis Enterprise and CDC WAN Invalidation.

sequenceDiagram
    participant US as us-east-1 (Primary DB)
    participant MM2 as Kafka MirrorMaker 2
    participant EU as eu-central-1 (Replica DB)
    participant L2_EU as Redis EU (L2)
    participant L1_EU as Caffeine EU (L1)

    US->>MM2: CDC Event (Product Price Update)
    MM2->>EU: Async Replicate (80ms RTT)
    EU->>L2_EU: UNLINK cache:catalog:flash_deals:v2
    L2_EU-->>L1_EU: Redis Pub/Sub Invalidation Broadcast
    L1_EU->>L1_EU: Invalidate Local Key
    note over L1_EU,EU: Split-Brain: If WAN severs, EU nodes serve localized stale L1/L2 until TTL expires.
    

6.3 Staff+ Systems Architecture FAQ (8 Rigorous Deep-Dives)

The following questions address the deepest mechanics of our caching infrastructure, derived from production post-mortems and kernel-level trace analysis.

• Q1: Why does Redis maintain its own custom event library (ae.c) instead of adopting battle-tested libraries like libuv or libevent?
  Answer: Zero-abstraction overhead and deterministic memory layout. Redis requires only a minimal wrapper around POSIX epoll/kqueue. libuv and libevent carry extensive feature bloat for timers and async I/O that Redis does not need, adding instruction cache pressure. ae.c guarantees absolute simplicity in the single-threaded reactor pattern.
• Q2: Why does Redis disable jemalloc thread-local caching (tcache) for the primary server thread?
  Answer: To prevent unpurged memory accumulation. In a single-threaded allocation model, tcache can hoard unused memory arenas that artificially inflate RSS (Resident Set Size). Disabling it forces jemalloc to eagerly return memory to the central pool, preserving $F_{\text{mem}}$ accuracy.
• Q3: What occurs internally during UNLINK and lazyfree-lazy-eviction, and how does the background bio.c thread safely reclaim memory without race conditions?
  Answer: When UNLINK is called, the main thread performs an atomic pointer detachment from the global dict (hash table), rendering the key immediately unroutable. The detached dictEntry reference is passed to the bio_jobs linked list. The background bio.c thread then executes a lock-free memory free operation (zfree), eliminating blocking latency on the main aeEventLoop.
• Q4: How does 64-bit word alignment affect small struct memory footprints in Redis, and how can engineers pack struct data efficiently?
  Answer: Modern CPUs read memory in 64-bit (8-byte) cache lines. If a struct contains interleaved 1-byte (char) and 8-byte (uint64_t) fields, the compiler inserts padding to align the 8-byte fields, heavily inflating memory usage. Engineers must order struct fields by descending size. While __attribute__((__packed__)) eliminates padding, it severely penalizes CPU cycles due to unaligned memory access.
• Q5: How do you remediate a single Redis Cluster node being overwhelmed by a hot key without rebalancing hash slots?
  Answer: Hash slot rebalancing takes too long during a stampede. Immediate remediation involves: (1) Deploying localized client-side L1 caching, and (2) Key replication—appending random salt suffixes (e.g., cache:key:1 through cache:key:N) to force CRC16 routing across multiple nodes, combined with client-side scatter-gather reads.
• Q6: What occurs if a CDC invalidation message is dropped or processed out-of-order due to a Kafka consumer group rebalance?
  Answer: We rely on LSN (Log Sequence Number) version vectors embedded in the payload. If an older CDC message arrives after a newer one, the invalidation application logic drops it by comparing LSNs. If a message is completely dropped, our fallback TTL boundaries bound the maximum duration of stale data.
• Q7: How does the Redis Cluster node handshake gossip protocol (cluster-node-timeout) resolve failover without a consensus protocol like Raft?
  Answer: Nodes continuously exchange heartbeat PINGs. If a node fails to PONG within cluster-node-timeout, it is flagged as PFAIL. If a majority of masters gossip this PFAIL state, it escalates to FAIL. The replicas of the failed master then initiate an election; the replicas request votes from the remaining healthy masters. The first replica to secure a majority of master votes is promoted, avoiding the heavyweight log-replication requirements of Raft.
• Q8: How does Caffeine’s Window TinyLFU admission filter mathematically outperform Redis's sampling pool in hit-ratio preservation?
  Answer: Redis approximates LFU by sampling a subset of keys (e.g., 16) and evicting the least frequently used among them. Window TinyLFU (W-TinyLFU) uses a Count-Min Sketch to probabilistically estimate the frequency of all accessed keys with minimal memory overhead. It divides the cache into a 1% Window Cache (protecting new, bursty arrivals) and a 99% Main Cache. An item evicted from the Window Cache is only admitted to the Main Cache if its Count-Min Sketch frequency is higher than the victim it would displace, providing mathematically superior defense against scan pollution.

6.4 Staff+ Pre-Flight Caching Readiness Checklist

Before launching a distributed multi-tier cache to production, ensure these 10 binary conditions are met.

• 1. Eviction Policy Defined: Memory maxmemory-policy is explicitly configured (e.g., allkeys-lfu) to protect hot keys.
• 2. TTL Jitter Enforced: L1 and L2 TTLs are jittered ($\pm 20\%$) to prevent synchronized thundering herds on expiry.
• 3. Singleflight & XFetch Enabled: Coalescing and probabilistic early refresh are enabled on the cache-miss path.
• 4. Kernel TCP Tuning: Network kernel parameters (somaxconn=4096, tcp_max_syn_backlog=8192) are tuned for high connection churn.
• 5. Async Invalidation (UNLINK): UNLINK is exclusively used for CDC invalidations over DEL to prevent main-thread blocking.
• 6. Slot Redirection Handling: Redis Cluster client topologies are configured to refresh slots on MOVED and ASK redirects.
• 7. THP Disabled: Transparent Huge Pages (THP) are disabled at the OS level to prevent CoW latency spikes during BGSAVE.
• 8. Degradation Circuit Breakers: Fallback to degraded static mock responses if L2 latency exceeds P99 thresholds.
• 9. Compact Serialization: Protobuf or specialized binary serialization is strictly utilized for payloads > 10KB.
• 10. Chaos Engineering Verified: The infrastructure has survived a simulated partition test (e.g., severing a master node under peak 45,000 QPS).

Synthesis: Caching at scale is not merely storing key-value pairs; it is the orchestration of CPU cache lines, memory allocators, network topologies, and distributed consistency models. By mastering these internals, engineering organizations can shift from reactively firefighting stampedes to proactively designing resilient, globally distributed systems.