Proxy Cache Revalidation: Cache-Control, ETag, and Observable Correctness

Reverse-proxy caches and Content Delivery Networks (CDNs) are fundamentally shared memory paradigms. They possess the capability to multiplex a single origin representation across millions of clients. Consequently, they must rigorously enforce cache coherency, probabilistic eviction logic, and concurrency locks. Observing a HIT in an access log is superficial; the true engineering challenges lie in Shared Memory (shm) slab fragmentation, cache stampedes (thundering herds), and algorithmic replacement models. Caching without mathematical observability is indistinguishable from serving stale, corrupted, or insecure memory segments.

1. Cache Replacement Algorithms: LRU vs. LFU vs. ARC

When a proxy’s memory pool fills, it must evict objects. The naive choice is Least Recently Used (LRU), implemented via a doubly-linked list and a hash map. However, LRU is highly susceptible to “cache pollution” from sequential scans (e.g., a nightly backup script scraping all assets).

Modern edge proxies utilize advanced algorithms like ARC (Adaptive Replacement Cache) or W-TinyLFU. ARC mathematically maintains two LRU lists: $L_1$ for recently seen items and $L_2$ for frequently seen items. A tunable parameter $p$ dictates the boundary between them.

The state transition of ARC operates on a Markov Chain model. If a cache miss hits the ghost list $B_1$ (evicted recent items), $p$ is incremented to favor recency. If it hits $B_2$ (evicted frequent items), $p$ is decremented to favor frequency. This creates an autonomous, mathematically optimal eviction threshold.

$$ p_{new} = \min\left(c, p_{old} + \max\left(1, \frac{|B_2|}{|B_1|}\right)\right) $$

2. Nginx Shared Memory (shm) Architecture & Lock Contention

In multiprocess proxies like Nginx, the cache index is stored in a shared memory zone (shm_zone). Because multiple worker processes must read/write to this memory concurrently, it requires kernel-level concurrency control.

Nginx manages this using an internal slab allocator (ngx_slab_alloc) to prevent memory fragmentation, highly analogous to the Linux kernel’s slab allocator. Synchronization is achieved via spinlocks (ngx_shmtx_t) built on atomic CPU instructions (CMPXCHG).

// Nginx Spinlock acquisition for Cache Key insertion
// Source: ngx_shmtx.c
void ngx_shmtx_lock(ngx_shmtx_t *mtx) {
    ngx_uint_t  i, n;
    for ( ;; ) {
        // Atomic compare-and-swap (fast path)
        if (*mtx->lock == 0 && ngx_atomic_cmp_set(mtx->lock, 0, ngx_pid)) {
            return;
        }
        // CPU Pause to reduce Cache Line Bouncing / MESI bus traffic
        for (n = 1; n < mtx->spin; n <<= 1) {
            for (i = 0; i < n; i++) {
                ngx_cpu_pause(); 
            }
            if (*mtx->lock == 0 && ngx_atomic_cmp_set(mtx->lock, 0, ngx_pid)) {
                return;
            }
        }
        // Fallback to kernel futex yield
        ngx_shmtx_wakeup(mtx);
    }
}

Under massive high-concurrency MISS rates, spinlock contention causes violent CPU cache line bouncing (MESI protocol invalidations). Understanding this code dictates that you must tune proxy_cache_lock on; to collapse concurrent identical MISS requests into a single origin fetch.

3. Mathematical Eradication of Thundering Herds: X-Fetch Algorithm

When a highly requested object’s max-age expires, thousands of concurrent requests will suddenly MISS and hit the origin, causing a Database Meltdown (Thundering Herd / Cache Stampede). Standard stale-while-revalidate helps, but what if the proxy restarts? We use Probabilistic Early Expiration (X-Fetch), native to Varnish.

Instead of expiring exactly at TTL, a request has a probability $P$ of preemptively triggering a background revalidation. As the current time $t$ approaches the expiration time $t_{exp}$, the probability exponentially increases.

$$ P(\text{fetch}) = 1 – \exp\left(-\frac{\Delta t}{\beta \cdot \text{TTL}}\right) $$

Where $\Delta t = t_{exp} – t$, and $\beta$ is a tuning constant controlling the aggressiveness of the prefetch. By injecting randomized jitter into the expiration decision, the deterministic cache stampede is mathematically smoothed into a manageable curve of origin hits, guaranteeing zero latency spikes.

4. eBPF: Profiling Memory Allocation Penalities

To measure true cache latency, observing HTTP headers is insufficient. Using eBPF, we trace the memory allocation functions within the proxy. By hooking uprobe:nginx:ngx_http_file_cache_read and uprobe:nginx:ngx_slab_alloc, we can plot histograms of disk I/O blocking time vs shared memory lookup time.

If the eBPF histogram shows the 99th percentile ($P_{99}$) of ngx_slab_alloc exceeding 10ms, your shared memory zone is heavily fragmented, or lock contention is severe. The solution is not more cache, but increasing proxy_cache_path keys_zone=name:size and adjusting slab sizes.

5. Architecture Observability Checklist

• Vary & Key Fragmentation: Cache keys must deterministically include required headers via the Vary header. Failure to normalize Accept-Encoding (e.g., gzip vs br) results in redundant origin fetches.
• Mutex and Request Collapsing: Utilize cache locks (proxy_cache_lock) to coalesce simultaneous cache misses.
• Probabilistic Prefetching: Implement X-Fetch algorithms or stale-background-fetch to eradicate origin CPU spikes.
• eBPF Slab Monitoring: Continuously monitor proxy memory fragmentation using kernel tracing.

6. Cache Failure Troubleshooting Matrix

Cache incidents are difficult because old content can come from the browser, CDN edge, reverse proxy, or application cache. The matrix below gives each layer a visible header or metric so a reader can prove where stale content is being served.

References

• RFC 9111: HTTP Caching
• ARC: Adaptive Replacement Cache Algorithm
• Nginx Source Code: ngx_slab.c and ngx_shmtx.c
• Probabilistic Early Expiration (Varnish / X-Fetch paper)