Cache Eviction Policy

Eviction policies must balance two competing signals:

• Recency: How recently was the data accessed? (e.g., LRU)
• Frequency: How often is the data accessed? (e.g., LFU)

Pure LRU is vulnerable to cache pollution from sequential scans that evict frequently-used hot items. LRU-K bridges this gap by tracking the timestamp of the last K references, effectively filtering out one-hit wonders while retaining genuinely popular content. This is critical in Content Delivery Networks where a viral video segment exhibits high frequency, while a one-time DNS lookup only shows recency.

A time-to-live (TTL) is an explicit expiration timestamp assigned to each cached object. Unlike capacity-driven eviction, TTL enforces content freshness by removing data that has exceeded its validity period, regardless of access patterns.

• Absolute TTL: Object expires at a fixed wall-clock time (e.g., a stock price valid for 15 minutes).
• Sliding TTL: Expiration resets on each access, keeping frequently-read data alive.

In MEC Caching for autonomous vehicles, stale sensor data must be evicted aggressively using short TTLs to prevent decisions based on outdated environmental models.

Advanced policies incorporate the latency penalty of a cache miss to prioritize eviction candidates. The algorithm calculates a value score, often defined as:

Score = (Fetch Cost × Frequency) / Size

• Fetch Cost: The round-trip time to retrieve the object from the origin server.
• Size: Larger objects consume more cache slots, so size-aware policies like GDStar optimize for byte-hit ratio rather than object-hit ratio.

This is essential in Joint Caching and Computing scenarios where evicting a pre-computed inference result could trigger an expensive GPU-bound recomputation.

Exact LRU requires maintaining a global doubly-linked list, which introduces lock contention in high-throughput, multi-threaded caches like Redis. Production systems often use approximate eviction:

• Redis Allkeys-LRU: Samples N random keys and evicts the least recently used among the sample.
• Clock (Second Chance): A circular buffer with a reference bit. The algorithm scans for an unreferenced page, clearing bits as it goes.

These approximations achieve near-LRU performance with O(1) complexity per eviction, critical for Edge Pre-fetching nodes handling millions of requests per second.

Modern caches partition storage into segments with distinct eviction policies to prevent destructive interference between workload types:

• Segmented LRU (SLRU): Uses a probationary segment for new entries and a protected segment for items accessed at least twice. Eviction occurs only from the probationary segment.
• TinyLFU: A frequency sketch (Count-Min Sketch) filters infrequent items before they enter the main cache, providing near-optimal hit ratios with minimal memory overhead.

This architecture underpins Caffeine, the high-performance Java caching library used in Apache Kafka and Apache Cassandra.

Learned policies use neural networks to predict an object's future reuse distance, replacing hand-crafted heuristics:

• Feature Engineering: Inputs include access frequency, recency, object size, content type, and temporal patterns (e.g., time of day).
• LSTM-Based Predictors: Recurrent networks model sequential access patterns to forecast if an object will be requested again within a lookahead window.

In Proactive Caching for video streaming, an ML model can predict that a specific video tile will not be revisited, preemptively evicting it to make room for predicted popular content from a Content Popularity Prediction engine.

A key performance indicator measuring the percentage of content requests successfully served from a cache versus those requiring retrieval from the origin server. A high hit ratio directly correlates with reduced latency and backhaul offloading.

• Formula: Hits / (Hits + Misses) × 100
• Impact: A 1% improvement in hit ratio can reduce origin traffic by 5-10% in large CDNs
• Relationship to eviction: The eviction policy directly determines which items remain available, making it the primary lever for optimizing this metric

A metric ensuring that cached data remains valid and consistent with the origin server, often managed through TTL-Based Invalidation mechanisms. Stale content violates correctness guarantees and can propagate outdated information to end users.

• TTL (Time-To-Live): An explicit expiration timestamp assigned by the origin server
• Stale-While-Revalidate: Serves stale content immediately while asynchronously refreshing in the background
• Eviction interaction: Freshness constraints may override eviction policy decisions, forcing removal of valid-but-expired entries before the algorithm would naturally evict them

The principle that recently requested content is likely to be requested again soon, a foundational concept for designing effective caching algorithms. This observation underpins the entire LRU (Least Recently Used) family of eviction policies.

• Real-world example: Breaking news articles receive 90% of their total traffic within the first 6 hours of publication
• LRU-K extension: Tracks the time of the last K references rather than just the most recent one, filtering out one-hit wonders that pollute the cache
• Counter-example: Some workloads exhibit scanning patterns where temporal locality breaks down entirely

A probability distribution commonly used to model content popularity in networks, stating that the frequency of a request is inversely proportional to its rank. The most popular item is requested roughly twice as often as the second most popular, three times as often as the third, and so on.

• Formula: f(k) ∝ 1/k^s where s is the skew parameter (typically ~1)
• Implication: A small fraction of content (the head) generates the majority of traffic, making eviction of tail items relatively safe
• Cache sizing: Zipfian distributions mean that doubling cache size yields diminishing returns after a certain threshold

A reinforcement learning approach for solving the exploration-exploitation dilemma in caching. The cache must balance exploiting known popular content against exploring new items that might become popular.

• Thompson Sampling: A Bayesian method that samples from posterior distributions to decide which content to cache
• Contextual Bandits: Incorporate features like time-of-day or user demographics into the caching decision
• Advantage over static policies: Bandit-based eviction adapts to concept drift where content popularity distributions shift over time, unlike fixed policies such as LRU

An advanced technique that uses index coding to create coded multicast opportunities, significantly reducing peak traffic by serving multiple requests with a single transmission. This fundamentally changes the eviction calculus.

• Mechanism: During placement, the cache stores carefully designed coded fragments rather than complete files
• Delivery phase: A single multicast transmission satisfies multiple distinct requests simultaneously
• Eviction implication: Traditional eviction policies designed for uncoded content must be redesigned, as the value of a cached fragment depends on the global placement across all caches in the network