1 Cache Fundamentals

1.1 What Caches Store and Why They Evict

Caches store copies of data or results that are expensive to obtain—such as computed objects, database query outputs, or fetched content. By serving future requests from faster storage, a cache reduces average response time. Eviction is necessary because cache storage is finite: when new items arrive and capacity is fully utilized, the system must reclaim space by discarding one or more existing entries. The eviction policy determines which entries are treated as least valuable for near-term or long-term reuse.

1.2 Capacity Constraints and Cache Hit/Miss Behavior

A cache hit occurs when a requested item is present; a miss occurs when it is absent and must be obtained from a slower source. Capacity strongly influences hit rate: with too little space, frequently used items may be removed before reuse, increasing misses. With enough space, the cache can retain working sets and improve performance. Even when total hit rate is high, the eviction policy can still affect latency distribution, particularly under heavy load where misses may cascade into deeper subsystems.

1.3 Eviction as a Control Mechanism

Eviction is not merely cleanup; it is a feedback control mechanism that shapes which items persist. Policies act on implicit assumptions about future access patterns, such as the idea that recently accessed data is likely to be accessed again soon. Through these assumptions, eviction determines the cache’s effective working set, the churn rate of entries, and the stability of performance as workloads change.

2 Eviction Policy Basics

2.1 Core Design Goals

Good eviction policies aim to maximize usefulness under constraints. Common goals include increasing cache hit rate, maintaining low response latency, and avoiding excessive metadata overhead. Another goal is robustness: the policy should perform reasonably well even when access patterns shift, object sizes vary, or traffic arrives in bursts.

2.2 Common Policy Inputs

2.2.1 Recency Signals

Recency signals track how recently an item was accessed or updated. Typical forms include “last accessed time,” reference bits, or an ordered list of usage. Recency-based methods often work well when workloads exhibit temporal locality, meaning recently requested items are more likely to be requested again.

2.2.2 Frequency Signals

Frequency signals estimate how often an item is accessed over some window or lifetime. This information can be captured with counters, sketches, or decayed counters. Frequency-oriented approaches aim to preserve consistently popular items even if they are not accessed within a short recent interval.

2.2.3 Size-Aware Decisions

When cache entries have different sizes, a policy that ignores size may evict many small items to make room for one large item, or preserve large items that crowd out numerous smaller, potentially more reusable entries. Size-aware policies incorporate object weight into selection decisions, seeking better space efficiency by considering value per byte rather than value alone.

2.3 Policy Evaluation Metrics

2.3.1 Hit Rate and Miss Penalty

Hit rate measures how often requests are satisfied by the cache. However, miss penalty varies by system: a cache miss for a cheap operation differs from a miss that triggers a slow network fetch or expensive computation. Evaluations often combine hit rate with measures of the cost of a miss to better reflect end-to-end impact.

2.3.2 Latency and Tail Performance

Average latency can hide important issues. Eviction policies influence queueing, backend load, and concurrency contention, which can change tail latency (e.g., 95th or 99th percentile). A policy with slightly lower hit rate might still produce better tail performance if it reduces backend saturation or avoids bursts of misses.

2.3.3 Workload Sensitivity

Many policies perform well for one class of workloads but poorly for others. Metrics include how rapidly performance degrades when access patterns deviate from the assumptions used by the algorithm (e.g., recency-heavy versus frequency-heavy patterns) and how quickly the cache recovers after a workload shift.

3.1 Least Recently Used (LRU)

LRU evicts the entry that has not been accessed for the longest time. It assumes that near-future requests resemble recent history, which is often true for interactive systems and many application workloads.

3.1.1 LRU Data Structures

A typical LRU implementation maintains a recency-ordered structure (often a doubly linked list) plus a hash map from keys to list nodes. On each access, the item is moved to the “most recent” position. When eviction is needed, the “least recent” tail element is removed. This design supports efficient updates but requires per-entry pointers or indices.

3.1.2 LRU Implementation Trade-offs

Exact LRU requires maintaining ordering updates on every access, which increases metadata traffic and synchronization cost in concurrent environments. Under high throughput, the overhead of list manipulation can offset the benefit of improved hit rate. Practical systems sometimes use approximate LRU variants or segment the recency structure to reduce overhead.

3.2 Least Frequently Used (LFU)

LFU evicts the entry with the lowest access count. It targets workloads where a stable set of items receives repeated requests over time, even if those items are not accessed in the immediate past.

3.2.1 Frequency Counters and Aging

Simple LFU can suffer from “frequency inflation,” where early items retain a large count long after popularity fades. To address this, implementations often apply aging or decay so that older accesses contribute less over time. Some policies use periodic counter resets, exponential decay, or window-based frequency estimation.

3.2.2 Doorknob-Style Variants

Variants such as Doorknob/door-style policies attempt to distinguish between items that show initial interest and those that have sustained interest. They often combine a probationary region (entries that have been seen once or briefly) with a protected region (entries that demonstrate continuing access), reducing the chance of keeping one-off popular-looking items.

3.3 First-In First-Out (FIFO)

FIFO evicts the oldest inserted entry regardless of access activity. It is easy to implement and has predictable behavior, but it can perform poorly when recently accessed items must remain available and older items keep being evicted despite being useful.

3.4 Random Eviction

Random eviction chooses an entry uniformly at random (or with some distribution) to remove. It reduces maintenance overhead and can be competitive in certain workloads where tracking exact recency or frequency is costly.

3.4.1 When Random Works Well

Random policies can work acceptably when request patterns are close to uniform, when cache entries have similar usefulness, or when approximate maintenance would otherwise introduce significant CPU overhead or contention. In systems where the metadata cost dominates, simpler policies may win in practice.

3.4.2 Probabilistic Considerations

Uniform random eviction has probabilistic behavior: it does not guarantee that the least useful item is removed. As load increases and working sets evolve, performance can vary run to run unless deterministic tie-breaking or controlled randomness is used.

3.5 Clock and Second-Chance Policies

Clock algorithms approximate LRU using a circular list plus per-entry reference bits. When an entry is considered for eviction, a reference bit indicates whether it was accessed recently; if set, the bit is cleared and the entry is skipped, granting a second chance.

3.5.1 Reference Bits and Approximation

Instead of updating full order on every access, reference bits are set on access and consulted during eviction scanning. This reduces overhead at the cost of accuracy: eviction may remove an entry that is not the true least recently used, but it often preserves the broad recency behavior with lower bookkeeping.

NRU categorizes entries based on whether they were referenced recently, often with simple binary or multi-bit state such as “recent” vs “not recent.” Related heuristics extend this idea by incorporating additional state, like update status or coarse frequency, to improve decision quality without full LRU maintenance.

4 Approximate and Scalable Eviction

4.1 Why Exact Policies Can Be Expensive

Exact recency or frequency policies require maintaining fine-grained metadata for each access. At scale, this can translate into high CPU use, synchronization overhead, larger memory footprints, and increased contention between threads. Approximate methods aim to capture the dominant signals while bounding the cost of maintaining them.

4.2 Windowed and Segmented Approaches

Windowing and segmentation restrict the scope of tracking, such as tracking recency within a moving time window or dividing the cache into partitions. These approaches can adapt better to changing workloads and can reduce the amount of state updated on each access.

4.2.1 Segmented LRU Concepts

Segmented LRU divides the cache into multiple regions representing different levels of confidence. New entries may enter a probation region; if they continue to be requested, they migrate to a protected region. This structure helps prevent one-time scans from displacing items that are genuinely frequently reused.

4.3 TinyLFU and Sketch-Based Ideas

TinyLFU refers to frequency estimation schemes that use compact counters or sketches to approximate how often items are requested. Rather than storing full per-key counts, such methods estimate popularity and use the estimates to guide admission and eviction. Sketch-based approaches reduce memory overhead while maintaining a usable signal about long-run popularity.

4.4 Admission vs Eviction Interactions

4.4.1 Typical Feedback Loops

Admission and eviction are coupled: eviction controls which resident items remain, while admission determines whether new items enter. If admission accepts too many low-value items, eviction churn increases; if admission is overly restrictive, the cache underutilizes space. Many modern designs rely on a feedback loop where frequency estimators and eviction decisions are tuned together to converge on a high-value resident set.

4.5 Eviction Cost Modeling

Eviction cost includes not only the act of removing an entry but also the maintenance work required to enable accurate decisions. Modeling can include CPU overhead per access (updating metadata), eviction-time scanning costs, and memory overhead for storing auxiliary structures. System designers often evaluate total cost as “work per request” plus “work per miss and eviction,” rather than focusing only on algorithmic ideal behavior.

5 Multi-Level Caches and Hierarchies

5.1 Cache Levels (L1, L2, L3)

Modern systems commonly use multiple cache layers. The closest cache level (e.g., L1) typically has the smallest capacity and lowest latency, while higher levels (e.g., L2 and L3) are larger but slower. Each level may use different eviction strategies suited to its latency budget and update frequency.

5.2 Cross-Level Eviction Effects

Eviction decisions at one layer can influence requests at another. If a lower-level cache retains data better, upper levels may see different temporal patterns and reduced miss bursts. Conversely, aggressive eviction at a lower level can increase miss traffic to upper or downstream systems. Effective tuning therefore considers the entire hierarchy rather than optimizing one layer in isolation.

5.3 Write Policies and Their Impact on Eviction

5.3.1 Write-Through vs Write-Back

Write-through caches update the next level on each write, potentially keeping downstream data more synchronized and reducing inconsistencies. Write-back caches mark entries as modified and defer propagation, which may affect how modified entries are treated during eviction. In some designs, eviction of modified entries triggers additional work such as write-back to maintain correctness.

5.4 Consistency Considerations (High-Level)

Consistency affects eviction because evicting an entry may require coordination with other cache levels or with a backing store. While the underlying correctness rules differ across implementations, the broad consequence is that eviction policies may need to account for data validity, coherence state, or update responsibility, adding constraints beyond performance alone.

6 Workload Patterns and Tuning

6.1 Temporal Locality and Recency Effects

Many interactive and system workloads exhibit temporal locality: the chance of reuse is higher soon after access. Recency-oriented policies often align well with this pattern, especially when the working set size is relatively stable. When temporal locality weakens, pure LRU behavior may become less effective.

6.2 Frequency Skew and Zipf-Like Access

In many environments, access frequency is skewed: a small fraction of items receive a large fraction of requests, often modeled by Zipf-like distributions. Under such conditions, frequency-based approaches or hybrid methods can preserve the dominant “hot” items while evicting colder entries that contribute little to hit rate.

6.3 Bursty Traffic and Hotspot Behavior

Bursts concentrate requests into short intervals, increasing the demand for rapid adaptation. During a burst, recency signals may quickly identify hot keys, while frequency signals may lag if the burst duration is shorter than the counting window. Bursty patterns can also create hotspots that temporarily crowd out less active keys, which impacts stability once the burst ends.

6.4 Skewed Object Sizes

If entry sizes vary widely, size effects can dominate eviction outcomes. A policy that maximizes hit rate per request may still perform poorly in terms of bytes stored, because one very large object can prevent many smaller objects from fitting. Size-aware strategies, along with weighting signals by object size, help align eviction with resource constraints.

6.5 Parameter Tuning Strategies

Tuning involves selecting parameters such as aging rates, window durations, segment sizes, and thresholds for protected versus probationary regions. Good tuning often targets the timescale over which popularity changes, the typical request rate, and the distribution of object sizes. Practical strategies include offline calibration using traces, online adaptation, and conservative rollout with monitoring.

7 Practical Implementation Notes

7.1 Eviction Data Structures

7.1.1 Linked Lists and Hash Maps

Linked lists provide an ordered structure for recency tracking, while hash maps support O(1) key lookup. Together they enable efficient updates on access and fast identification of eviction candidates. The downside is increased memory overhead for list pointers and more complex operations in multithreaded contexts.

7.1.2 Trees and Heaps

Some frequency-aware or score-based policies require ordering by counters or estimated values. Balanced trees and heaps can maintain such order, offering logarithmic insertion and extraction. These structures are typically heavier than simple lists but can support more nuanced selection criteria, such as evicting the minimum estimated score.

7.2 Concurrency and Thread Safety

In concurrent systems, eviction and access updates may race. Implementations may use locks, sharded data structures, lock-free or wait-free strategies, or batching. The key challenge is ensuring correctness of metadata (e.g., recency positions or reference bits) without turning eviction into a scalability bottleneck.

7.3 Background Eviction and Incremental Updates

Some systems perform eviction asynchronously to reduce request-path latency. Background eviction can remove expired or low-priority entries periodically, while incremental update mechanisms keep metadata reasonably current without blocking critical operations. This design can smooth eviction cost but may introduce temporary over-commit of capacity.

7.4 Memory Overhead Accounting

Beyond storing cached values, a cache includes metadata such as keys, pointers, counters, flags, and allocator structures. Eviction policies often trade accuracy for metadata size. Accurate overhead accounting helps determine the true effective capacity and prevents policies from appearing beneficial on paper while consuming a disproportionate share of memory.

8 Cache Eviction in Systems

8.1 Content Delivery and Edge Caches

Edge caches serve content close to users to reduce latency. Eviction at the edge influences both origin load and user experience. Workloads here may be dominated by large objects, geographic locality, and request bursts tied to events. Policies often incorporate heuristics that balance long-term popularity with quick adaptation to changing trends.

8.2 In-Memory Object Caches

In-memory caches are frequently used in application stacks for fast retrieval of computed results or frequently accessed data. Eviction in this environment must be mindful of CPU overhead and garbage collection or memory allocator effects. Size-aware and approximate strategies are common to maintain throughput while preserving a high hit rate.

8.3 Database and Application Caching Layers

Caching around databases may store query results, object graphs, or derived views. Eviction affects backend load by determining how long expensive queries remain reusable. Workloads can shift with traffic patterns and deployment changes; therefore, policies may be tuned to avoid excessive churn that would otherwise amplify database load during cache warmup or after restarts.

8.4 Browser and Client-Side Caching Concepts (Light Overview)

Client-side caching reduces repeat downloads and can improve perceived responsiveness. While client cache eviction is often governed by browser behavior and storage limits, the core idea remains: when storage is constrained, the system discards items to make space for new ones. Client eviction interacts with cache-control metadata and user behavior, so the effective access pattern can differ from server-side traces.

9 Failure Modes and Anti-Patterns

9.1 Thrashing and Poor Hit Rate

Thrashing occurs when eviction constantly removes items that will soon be requested again. This can happen when the working set size exceeds cache capacity or when the eviction policy reacts incorrectly to workload changes. Thrashing manifests as low hit rate, high miss rate, and increased pressure on upstream systems.

9.2 Hot Key Dominance and Starvation

Some policies, particularly those based heavily on frequency or protected regions, may allow a small number of hot keys to monopolize capacity. When that happens, less frequent but still important keys can be repeatedly evicted, leading to starvation and uneven performance. Mitigations include hybrid scoring, probationary handling, and size-aware constraints.

9.3 Misconfigured Capacity Units

Capacity misconfiguration is a practical source of failure. If the cache counts capacity in bytes but the configuration is given in items (or vice versa), the system may either over-evict or under-allocate. Similar issues arise when compression, metadata size, or allocator overhead is not accounted for, causing the cache to behave differently from expected capacity limits.

9.4 Overhead-Induced Performance Regressions

A policy that improves hit rate can still hurt end-to-end performance if its bookkeeping cost is too high. Excessive synchronization, heavy metadata allocations, and costly eviction scans can increase latency and reduce throughput. This failure mode highlights that eviction quality must be evaluated together with implementation cost.

10 Testing and Evaluation

10.1 Synthetic Workloads

Synthetic workloads generate controlled access patterns to compare policies. They can model temporal locality, varying degrees of skew, burstiness, and size distributions. While useful for isolating effects, synthetic tests may not reflect real system behavior, especially in how patterns evolve over time.

10.2 Production Traces and Replay

Production traces provide realistic request sequences. Replay systems simulate cache behavior by feeding traces into candidate policies and measuring hits, misses, eviction counts, and resource usage. Trace-based evaluation helps capture correlations and non-stationary behavior, but it must handle privacy, representativeness, and time scaling issues.

10.3 A/B Testing Eviction Policies

Online experiments can validate whether a policy improvement translates to real user-facing outcomes. A/B tests compare metrics such as error rates, latency percentiles, backend load, and cache hit rate under live traffic. Safe rollout requires guardrails to prevent regressions, including fallback strategies and limits on metadata or eviction rates.

10.4 Regression Monitoring for Cache Metrics

After deployment, monitoring detects drift in access patterns or performance regressions. Key metrics include cache hit ratio over time, miss latency, backend saturation indicators, eviction rate, and memory utilization. Regression monitoring supports ongoing tuning and helps distinguish policy issues from unrelated system changes such as network delays or database slowdowns.