Cache Eviction Policies: LRU, LFU, FIFO, and TTL-Based Strategies

In this tutorial, you will learn about Cache Eviction Policies: LRU, LFU, FIFO, and TTL. We cover key concepts, practical examples, and best practices to help you master this topic.

Cache eviction policies determine which data to remove when the cache reaches its memory limit, using strategies like LRU, LFU, FIFO, and TTL-based eviction to maximize hit rates while respecting memory constraints.

flowchart TD
    Memory[Cache Full] --> Policy{Eviction Policy}
    Policy -->|LRU| LRU[Remove Least Recently Used]
    Policy -->|LFU| LFU[Remove Least Frequently Used]
    Policy -->|FIFO| FIFO[Remove Oldest Inserted]
    Policy -->|TTL| TTL[Remove Expired Keys]
    Policy -->|Random| Random[Remove Random Key]
    LRU --> Result[Memory Freed]
    LFU --> Result
    FIFO --> Result
    TTL --> Result
    Random --> Result

What You'll Learn

• LRU, LFU, FIFO, and random eviction algorithms
• Redis eviction policies: volatile-lru, allkeys-lru, volatile-lfu, allkeys-lfu
• When each policy performs best based on access patterns
• Application-level eviction strategies

Why It Matters

The right eviction policy can improve cache hit rates by 15-30% compared to a mismatched policy. For a 4 GB Redis cache serving 100K req/s, this means 15,000-30,000 fewer database calls per second and millions of dollars saved in database infrastructure.

Real-World Use

DodaZIP's file metadata cache uses allkeys-lfu because a small set of files (the most popular 1%) accounts for 80% of accesses. LFU keeps these hot files in cache while evicting the long tail. Switching from allkeys-lru improved the hit rate from 82% to 94%.

LRU Eviction

Removes the least recently accessed keys first:

import redis
import time

r = redis.Redis(decode_responses=True)

class LRUCache:
    def __init__(self, redis_client, max_size=100):
        self.r = redis_client
        self.max_size = max_size
        self.access_order_key = "lru:access_order"

    def get(self, key):
        """Get value and update access time."""
        value = self.r.get(key)
        if value is not None:
            self.r.zadd(self.access_order_key, {key: time.time()})
        return value

    def set(self, key, value, ttl=3600):
        """Set value and evict LRU if needed."""
        current_size = self.r.zcard(self.access_order_key)
        if current_size >= self.max_size and not self.r.exists(key):
            oldest = self.r.zpopmin(self.access_order_key, 1)
            if oldest:
                old_key = oldest[0][0]
                self.r.delete(old_key)
                print(f"Evicted (LRU): {old_key}")

        self.r.setex(key, ttl, str(value))
        self.r.zadd(self.access_order_key, {key: time.time()})

for i in range(110):
    cache = LRUCache(r, max_size=100)
    cache.set(f"key:{i}", f"value:{i}")

for i in range(5):
    print(f"key:{i} exists: {r.exists(f'key:{i}')}")

print(f"Cache size: {r.zcard('lru:access_order')}")

Expected output:

Evicted (LRU): key:0
Evicted (LRU): key:1
...
Evicted (LRU): key:9
key:0 exists: False
key:1 exists: False
key:2 exists: False
key:3 exists: False
key:4 exists: False
Cache size: 100

LFU Eviction

Removes the least frequently accessed keys first:

import redis
from collections import defaultdict

r = redis.Redis(decode_responses=True)

class LFUCache:
    def __init__(self, redis_client, max_size=100):
        self.r = redis_client
        self.max_size = max_size
        self.freq_key = "lfu:frequencies"

    def get(self, key):
        """Get value and increment frequency."""
        value = self.r.get(key)
        if value is not None:
            self.r.zincrby(self.freq_key, 1, key)
        return value

    def set(self, key, value, ttl=3600):
        """Set value and evict LFU if needed."""
        current_size = self.r.zcard(self.freq_key)
        if current_size >= self.max_size and not self.r.exists(key):
            lowest_freq = self.r.zpopmin(self.freq_key, 1)
            if lowest_freq:
                old_key = lowest_freq[0][0]
                self.r.delete(old_key)
                print(f"Evicted (LFU): {old_key}")

        self.r.setex(key, ttl, str(value))
        self.r.zincrby(self.freq_key, 1, key)

cache = LFUCache(r, max_size=10)

for i in range(5):
    cache.set(f"hot:{i}", f"hot_value:{i}")
for i in range(20, 30):
    cache.set(f"cold:{i}", f"cold_value:{i}")

for i in range(20):
    cache.get("hot:0")
for i in range(5):
    cache.get("hot:1")

for i in range(10, 15):
    cache.set(f"new:{i}", f"new_value:{i}")
    print(f"  Added new:{i}")

print(f"\nHot key hot:0 exists: {r.exists('hot:0')}")
print(f"Hot key hot:1 exists: {r.exists('hot:1')}")

Expected output:

Evicted (LFU): cold:20
Evicted (LFU): cold:21
...
  Added new:10
  Added new:11
Hot key hot:0 exists: True
Hot key hot:1 exists: True

Redis Eviction Policies

Redis provides built-in eviction policies configurable via maxmemory-policy:

import redis

r = redis.Redis(decode_responses=True)

class RedisEvictionDemo:
    def __init__(self):
        self.policies = {
            "noeviction": "Return errors when memory limit reached",
            "allkeys-lru": "Evict least recently used from all keys",
            "allkeys-lfu": "Evict least frequently used from all keys",
            "volatile-lru": "Evict LRU only among keys with TTL",
            "volatile-lfu": "Evict LFU only among keys with TTL",
            "allkeys-random": "Evict random keys from all keys",
            "volatile-random": "Evict random keys with TTL",
            "volatile-ttl": "Evict keys with shortest TTL first",
        }

    def recommend(self, workload_type):
        """Recommend a policy based on workload characteristics."""
        recommendations = {
            "uniform_access": {
                "policy": "allkeys-lru",
                "reason": "All keys accessed equally, LRU handles bursts well"
            },
            "skewed_access": {
                "policy": "allkeys-lfu",
                "reason": "Few hot keys dominate, LFU keeps them cached"
            },
            "ttl_only": {
                "policy": "volatile-ttl",
                "reason": "Only cache data with known expiration"
            },
            "session_store": {
                "policy": "volatile-lru",
                "reason": "Sessions have TTL, LRU handles natural expiry"
            },
        }
        return recommendations.get(workload_type, {
            "policy": "allkeys-lru",
            "reason": "Safe default for most workloads"
        })

demo = RedisEvictionDemo()

for name, desc in demo.policies.items():
    print(f"  {name:20s} - {desc}")

print()
workloads = ["uniform_access", "skewed_access", "session_store"]
for w in workloads:
    rec = demo.recommend(w)
    print(f"{w:20s} -> {rec['policy']} ({rec['reason']})")

Expected output:

  noeviction           - Return errors when memory limit reached
  allkeys-lru          - Evict least recently used from all keys
  allkeys-lfu          - Evict least frequently used from all keys
  volatile-lru         - Evict LRU only among keys with TTL
  volatile-lfu         - Evict LFU only among keys with TTL
  allkeys-random       - Evict random keys from all keys
  volatile-random      - Evict random keys with TTL
  volatile-ttl         - Evict keys with shortest TTL first

uniform_access        -> allkeys-lru (All keys accessed equally, LRU handles bursts well)
skewed_access         -> allkeys-lfu (Few hot keys dominate, LFU keeps them cached)
session_store         -> volatile-lru (Sessions have TTL, LRU handles natural expiry)

Common Mistakes

• Using allkeys-lru when access patterns are highly skewed — hot keys accessed millions of times are evicted at the same rate as recently-added cold keys. Use allkeys-lfu for skewed access.
• Using noeviction in production — this causes writes to fail when memory is full. Unless you monitor memory closely and scale proactively, use an eviction policy.
• Not distinguishing between volatile and allkeys policies — volatile policies only evict keys with TTLs set. If most keys lack TTLs, volatile policies are ineffective.
• Relying solely on eviction without setting TTLs — eviction handles memory pressure, but TTLs provide freshness. Use both for best results.
• Using LFU for data with seasonal popularity — LFU permanently favors old popular keys over new ones. Use LRU for trending data that has short popularity bursts.

Practice Questions

1. What is the difference between LRU and LFU eviction?
2. When would you choose allkeys-lru over allkeys-lfu?
3. Why does the volatile-ttl policy require keys to have TTLs set?
4. What happens when noeviction is configured and memory is full?
5. How does LFU handle the onboarding of new popular content?

Challenge

Build an eviction policy simulator. Generate access patterns: uniform, skewed (80/20), seasonal (cyclical popularity), and burst (sudden spike). Run each pattern against LRU, LFU, FIFO, and random eviction policies. Measure hit rate, memory usage, and the time to reach Steady State. Report which policy wins for each pattern.

FAQ

Mini Project

Build an eviction policy evaluator that connects to a Redis instance and simulates different access patterns. For each policy, the tool should: (1) load the cache with 10,000 keys, (2) generate 100,000 reads following the access pattern, (3) measure hit rate and database calls avoided, and (4) output a comparison table. Run across all 8 Redis eviction policies.

What's Next

Continue with Cache Memory Management to learn about memory limits, fragmentation, and monitoring. Then explore Cache Clustering for horizontal scaling with Redis Cluster.