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))