Each test is 5 questions with varying difficulty.
AI Prep covers AI Agents, Generative AI, ML Fundamentals, NLP & LLMs and a lot more, with adaptive tests and daily challenges. Fully offline on Android. Free to try, one-time unlock for lifetime access.
Cache eviction policies are the fundamental decision-making algorithms that determine which data to remove from a cache when it reaches capacity. In 2026, as high-throughput distributed systems and AI inference engines demand sub-millisecond latency, understanding these policies is critical for engineers designing performant storage layers. Whether you are building a KV store, managing a Redis cluster, or optimizing a KV Cache for LLMs, you must understand the trade-offs between temporal locality (LRU) and frequency-based access (LFU). Interviewers ask about these policies to evaluate your ability to reason about memory constraints, access patterns, and algorithmic complexity. Junior engineers are expected to explain the basic mechanics of FIFO and LRU, while senior candidates must demonstrate how to implement these with O(1) complexity, handle concurrency, and select the optimal policy for specific workloads like write-heavy vs. read-heavy systems.
Cache eviction policies directly impact the cache hit ratio, which is the primary lever for reducing latency and database load. A poorly chosen policy can lead to cache thrashing, where useful data is constantly evicted, forcing expensive re-fetches from primary storage. In production environments like those at Netflix or Uber, a 1% improvement in hit ratio can save millions in infrastructure costs. These policies are high-signal interview topics because they expose a candidate's grasp of data structures. A strong answer goes beyond defining LRU; it discusses the overhead of maintaining doubly-linked lists versus hash maps, the impact of frequency skew in LFU, and how to handle 'scan resistance' where one-time large scans pollute the cache. With the rise of LLM inference, where KV Cache memory management is a bottleneck, the ability to design efficient eviction strategies for high-dimensional tensors is more relevant than ever in 2026.
The cache eviction architecture consists of a lookup mechanism (hash map) for O(1) access and an ordering mechanism (linked list or frequency heap) for eviction decisions. When a request arrives, the system checks the hash map. If present, the ordering mechanism is updated (e.g., node moved to head in LRU). If absent, a new entry is created, and if the cache is full, the tail element is evicted.
Incoming Request
↓
[Hash Map Lookup]
↓
[Ordering Mechanism]
(List/Heap/Tree)
↓ ↓
[Update Node] [Evict Tail]
↓ ↓
[Data Storage] [Free Memory]
↓
Cache Hit/MissStore metadata for evicted items to track 'what would have been hit' to improve future eviction decisions.
Trade-offs: Increases memory usage for metadata but significantly improves hit ratio.
Split the cache into a 'probationary' and 'protected' segment to prevent large scans from flushing the cache.
Trade-offs: More complex to implement but prevents cache pollution.
Periodically divide all frequency counts by two to prevent old, high-frequency items from staying forever.
Trade-offs: Requires background processing but keeps the cache relevant.
| Reliability | Use write-through or write-around policies to ensure cache consistency during failures. |
| Scalability | Distribute cache across nodes using consistent hashing to avoid global lock contention. |
| Performance | Target O(1) for all cache operations; use lock-free data structures for high concurrency. |
| Cost | Optimize memory usage by using compact data structures and avoiding object overhead. |
| Security | Prevent cache poisoning by validating keys and limiting cache size per user/tenant. |
| Monitoring | Track cache hit ratio, eviction rate, and latency per operation. |
LRU (Least Recently Used) evicts items based on the time of last access, focusing on temporal locality. LFU (Least Frequently Used) evicts items based on the total number of times an item has been accessed, focusing on frequency. LRU is generally easier to implement and performs well for most workloads, while LFU is better for workloads with highly skewed frequency distributions but is more complex to maintain.
LRU is simpler to implement with O(1) complexity using a doubly-linked list and a hash map. LFU requires maintaining frequency counts, which often involves a priority queue or a complex frequency-list structure, leading to higher overhead. Additionally, LFU can suffer from 'stale' items that were popular in the past but are no longer needed, whereas LRU naturally adapts to shifting access patterns.
Cache thrashing occurs when the cache is too small for the working set, causing items to be evicted shortly after being loaded. This leads to a constant cycle of evictions and re-fetches, resulting in a very low hit ratio and high latency. It is often solved by increasing the cache size, optimizing the eviction policy, or filtering out one-time access patterns.
Yes, they are often used together. LRU manages the cache size by evicting the least recently used items when the cache is full, while TTL (Time To Live) ensures that stale data is removed even if the cache is not full. This combination is common in production systems like Redis to maintain both memory limits and data freshness.
Scan resistance refers to the ability of a cache to handle large, one-time data scans without flushing out the existing, frequently accessed data. Standard LRU is not scan-resistant because a large scan will fill the cache with new, one-time items, evicting the 'hot' data. Segmented LRU or admission policies are used to mitigate this.
Redis implements LFU by using a 24-bit counter for each key that tracks access frequency. This counter is updated probabilistically to save space and is subject to 'decay' over time, meaning the frequency count decreases if the key is not accessed for a while. This allows Redis to evict items that were popular in the past but are no longer being accessed.
In write-through caching, data is written to the cache and the underlying storage simultaneously, ensuring high consistency but higher latency. In write-back caching, data is written only to the cache, and the update to the underlying storage is deferred until the item is evicted. Write-back is faster but introduces a risk of data loss if the cache fails before the storage is updated.
A cache stampede (or thundering herd) occurs when a popular cache item expires, and multiple concurrent requests try to recompute or fetch the value from the database simultaneously. This can overwhelm the database. It is typically mitigated using locking (only one request fetches), probabilistic early recomputation, or background refreshing.
The hash map provides O(1) access to the nodes in the doubly-linked list. Without the hash map, finding an item in the cache would require a linear scan of the list, which is O(N). The hash map stores the key and a pointer to the corresponding node in the list, allowing the cache to locate, update, or remove an item in constant time.
No. LFU is only better when access frequency is the primary predictor of future access. If the workload is highly temporal (e.g., items are only needed for a short period), LRU will perform much better. LFU also has the overhead of maintaining frequency counts and the risk of 'stale' items dominating the cache if not properly aged.
AI Prep covers AI Agents, Generative AI, ML Fundamentals, NLP & LLMs and a lot more, with adaptive tests and daily challenges. Fully offline on Android. Free to try, one-time unlock for lifetime access.