1 The Problem
We want an LRU (Least Recently Used) cache: it remembers the results of slow operations so repeats are instant, but holds only a fixed number of items — when full, it evicts the least recently used one. It teaches caching with eviction, the core technique for making slow systems fast.
Where this shows up: CPU caches, web caches, database query caches, CDN edge caches, Python’s own
@lru_cache. Caching is one of the highest-impact performance techniques in all of computing.2 How to Think About It
Think about what to keep and what to drop, before any code:
The plan — in plain English
1. Store results keyed by their input. → 2. On a request: if it is cached, return it instantly (a “hit”); if not, compute it, store it, and return (a “miss”). → 3. When full: evict the item used longest ago. → The trick is tracking order of use so we know which is least recently used.
3 The Build — explained part by part
Here is a complete LRU cache using an OrderedDict, which remembers insertion/use order. Each part is explained below.
Pythonlru.py
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict() # remembers order of use
def get(self, key):
if key not in self.cache:
return None
# Mark as most recently used by moving it to the end.
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
# Evict the least recently used (the first item).
self.cache.popitem(last=False)
if __name__ == "__main__":
cache = LRUCache(capacity=2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # 'a' is now most recent
cache.put("c", 3) # full -> evicts 'b' (least recent)
print("a:", cache.get("a")) # 1
print("b:", cache.get("b")) # None (evicted)
print("c:", cache.get("c")) # 3
What each part does — in plain words
OrderedDict — a dictionary that remembers the order items were added or touched. This order is exactly what we need to know which item is “least recently used”.get — on a hit,
move_to_end(key) marks it as most recently used (moves it to the back). So the front of the dict is always the least recently used item.put — add or update the value, moving it to the back (most recent). If the cache now exceeds capacity, evict.
self.cache.popitem(last=False) — the eviction: remove the first item, which (because of our move-to-end discipline) is the least recently used. This is the heart of LRU.
why LRU? — recently used things are likely to be used again soon, so keeping them and dropping the stale ones gives the best hit rate for a fixed size.
Common mistakes — and how to avoid them
✗ Forgetting to mark an item recent on
get — then eviction order is wrong.✓ Call
move_to_end on every hit.✗ Evicting the most recent instead of the least — backwards.
✓ Use
popitem(last=False) to remove the oldest (front) item.✗ Checking capacity before inserting — off-by-one errors.
✓ Insert first, then evict if over capacity.
4 Test & Prove Each Part
We test hits, misses, and — the crucial behaviour — that the least recently used item is evicted when full.
A stored value can be retrieved (a hit)
A missing key returns nothing (a miss)
When full, the least recently used item is evicted
Pythontest_lru.py
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key):
if key not in self.cache:
return None
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key, value):
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
def test_hit():
"""A stored value is returned."""
cache = LRUCache(2)
cache.put("a", 1)
assert cache.get("a") == 1
def test_miss():
"""A missing key returns None."""
assert LRUCache(2).get("x") is None
def test_evicts_least_recently_used():
"""The least recently used item is evicted when full."""
cache = LRUCache(2)
cache.put("a", 1)
cache.put("b", 2)
cache.get("a") # 'a' used; 'b' now least recent
cache.put("c", 3) # evicts 'b'
assert cache.get("b") is None
assert cache.get("a") == 1
assert cache.get("c") == 3
Run with pytest -v. The eviction test tells the whole story: we use “a” to make “b” the least recent, add “c” to overflow, and prove “b” (not “a”) was evicted. That precise behaviour is what makes it LRU.
5 The Interface
putcache.put(key, value)store (may evict)
getcache.get(key)value or None, marks as recent
Eviction (capacity 2)
put a, put b, get a, put c
-> b is evicted (least recently used)6 Run It & Automate It
Run it locally
python3 lru.pyWatch “b” get evicted when the cache overflows. Use it to cache slow function results.
Jenkins runs the tests automatically — each line explained below.
What you should see when it works
Terminala real run
a: 1
b: None
c: 3If it breaks — how to fix it
🚨 The wrong items get evicted.
Make sure both
get and put move touched keys to the end.🚨 The cache grows past capacity.
Your eviction check is missing or wrong — check
len > capacity after inserting.GroovyJenkinsfile
// Jenkinsfile — automated tests on every change.
pipeline {
agent any
stages {
stage('Get the code') { steps { checkout scm } } // download the code
stage('Install') { steps { sh 'python3 -m venv venv && . venv/bin/activate && pip install pytest' } } // test tool
stage('Test') { steps { sh '. venv/bin/activate && pytest -v' } } // run every test
}
post {
success { echo 'All tests passed.' }
failure { echo 'A test failed — look above.' }
}
}
🎯 Try this next — make it yours
- Decorator. Turn it into
@cachedto wrap any function. (Teaches: decorators.) - Stats. Track hit and miss rates. (Teaches: measuring effectiveness.)
- TTL. Expire entries after a time. (Teaches: time-based eviction.)
What you learned
You built an LRU cache with eviction — the core of caches everywhere, from CPUs to CDNs. You learned to track use-order with OrderedDict and evict the stalest item. Caching is one of computing’s highest-leverage techniques. Related: collections, functools.