Overview

An eviction policy decides which resident entry a cache removes when a new entry is admitted beyond capacity. Four policies cover almost every replay-and-measure task:

Policy	Data structure	On hit	On admit	Eviction choice
LRU	OrderedDict	Move to tail	Append at tail	Pop head
LFU	{key: freq} + insertion order	freq[k] += 1	freq[k] = 1	Min freq, tiebreak by insertion order
FIFO	OrderedDict	Nothing	Append at tail	Pop head
S3FIFO	Three FIFO queues + freq[k]	freq[k] = min(freq+1, cap)	Admit to small; ghost-hit admits to main	Second-chance on main; small drains to main/ghost

Each has subtleties that trip naive implementations.

LRU

Use an OrderedDict where the tail is the most-recently-accessed key. On hit, move_to_end. On miss + insert, append; pop from head if over capacity.

Most common bug: forgetting to update recency on a hit. Without the refresh, LRU degenerates to FIFO — hit rate drops substantially on any workload with recency structure.

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self._d = OrderedDict()

    def contains(self, k): return k in self._d

    def access(self, k):
        if k in self._d:
            self._d.move_to_end(k)
        else:
            self._d[k] = None
            if len(self._d) > self.capacity:
                self._d.popitem(last=False)