Cache Eviction Policies – "How You Decide What to Remove When Cache Is Full"

Eviction policies determine which cached entries to remove when the cache is full and needs space

Cache eviction is a policy or algorithm that determines which item(s) to remove from a cache when it reaches its maximum capacity. It’s a crucial aspect of cache management to maintain efficiency and performance.

Policy	Description	Typical Use
LRU (Least Recently Used)	Removes least recently used item	General-purpose caching
LFU (Least Frequently Used)	Removes least accessed item	Skewed traffic where few items dominate
FIFO (First In First Out)	Removes oldest inserted item	Simple caches
Random	Removes a random item	High-throughput caches like Redis
Time-based Expiry	Removes items after TTL expires	CDN, session storage

LRU Least Recently Used

LRU stands for Least Recently Used, which is a popular cache eviction policy used in computing. When a cache reaches its size limit and needs to make space for new items, LRU removes the item that has not been accessed or used for the longest time—i.e., the “least recently used” item is evicted.

LRU implementation

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1  # Cache miss
        else:
            self.cache.move_to_end(key)  # Mark recently used
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            evicted_key, evicted_value = self.cache.popitem(last=False)  # Evict least recently used
            print(f"Evicted: {evicted_key}")

# Usage Example:
cache = LRUCache(2)

cache.put(1, 'A')
cache.put(2, 'B')

print(cache.get(1))  # returns 'A', cache: {2:'B', 1:'A'}

cache.put(3, 'C')  # Evicts key 2
print(cache.get(2))  # returns -1 (evicted)
print(cache.get(3))  # returns 'C'

LFU Least Frequently Used

Evict the key with the lowest access frequency. Ties can be broken by recency or arbitrary order.

LFU

from collections import defaultdict, OrderedDict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.min_freq = 0
        self.key_to_val = {}           # key → value
        self.key_to_freq = {}          # key → freq
        self.freq_to_keys = defaultdict(OrderedDict)
        # freq → keys in order of insertion (to break ties by recency)

    def _update_freq(self, key: int):
        freq = self.key_to_freq[key]
        # remove from current freq list
        del self.freq_to_keys[freq][key]
        if not self.freq_to_keys[freq]:
            del self.freq_to_keys[freq]
            if freq == self.min_freq:
                self.min_freq += 1
        # add to next freq list
        self.key_to_freq[key] = freq + 1
        self.freq_to_keys[freq + 1][key] = True

    def get(self, key: int) -> int:
        if key not in self.key_to_val:
            return -1
        self._update_freq(key)
        return self.key_to_val[key]

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        if key in self.key_to_val:
            # update value and frequency
            self.key_to_val[key] = value
            self._update_freq(key)
            return

        if len(self.key_to_val) >= self.capacity:
            # evict LFU key
            # min_freq holds the smallest freq currently in cache
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.key_to_val[evict_key]
            del self.key_to_freq[evict_key]
            print(f"Evicted LFU key: {evict_key}")

        # insert new key with freq = 1
        self.key_to_val[key] = value
        self.key_to_freq[key] = 1
        self.freq_to_keys[1][key] = True
        self.min_freq = 1

# Usage Example:
cache = LFUCache(2)
cache.put(1, 'A')  # cache: {1:'A'}
cache.put(2, 'B')  # cache: {1:'A', 2:'B'}
print(cache.get(1))  # returns 'A', freq of 1→2
cache.put(3, 'C')    # evicts key 2 (freq=1), inserts 3
print(cache.get(2))  # returns -1 (evicted)
print(cache.get(3))  # returns 'C'

FIFO First in last out

Evict the oldest entry—i.e., the one that was inserted earliest.

LFU

from collections import deque

class FIFOCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}          # key → value
        self.queue = deque()     # track insertion order

    def get(self, key: int) -> int:
        return self.cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # update value but keep insertion order
            self.cache[key] = value
            return

        if len(self.cache) >= self.capacity:
            evict_key = self.queue.popleft()
            del self.cache[evict_key]
            print(f"Evicted FIFO key: {evict_key}")

        self.cache[key] = value
        self.queue.append(key)

# Usage Example:
cache = FIFOCache(2)
cache.put(1, 'A')
cache.put(2, 'B')
cache.put(3, 'C')  # evicts key 1
print(cache.get(1))  # -1
print(cache.get(2))  # 'B'
print(cache.get(3))  # 'C'

Random Eviction

Evict a random entry when capacity is exceeded.

import random

class RandomCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key → value

    def get(self, key: int) -> int:
        return self.cache.get(key, -1)

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            return

        if len(self.cache) >= self.capacity:
            evict_key = random.choice(list(self.cache.keys()))
            del self.cache[evict_key]
            print(f"Evicted Random key: {evict_key}")

        self.cache[key] = value

# Usage Example:
cache = RandomCache(2)
cache.put(1, 'A')
cache.put(2, 'B')
cache.put(3, 'C')  # randomly evicts either 1 or 2
print(cache.get(1), cache.get(2), cache.get(3))