LRU Cache & Rate Limiter
Two pieces of infrastructure every backend runs: a least-recently-used cache that evicts cold keys under a memory ceiling, and a token-bucket rate limiter that decides who gets a 429.
How it works in the real world
Caches and rate limiters answer the same question — what do I do when I cannot serve everything?
- Cache — remember expensive results so the second call is free.
- Evict — memory is finite, so when full, drop the least recently used key. Recency is a good proxy for what you'll need next.
- Measure — a cache with a poor hit rate is pure overhead, so count hits and misses.
- Limit — a token bucket refills at a steady rate and allows a burst up to its size. Stripe, GitHub and Cloudflare all shape traffic this way.
OrderedDict gives you O(1) recency tracking, which is exactly how functools.lru_cache works underneath.
A cache with hit tracking
Cache slow_lookup results in a dict. Count hits and misses across the call sequence, then print both and the hit rate to one decimal.
if key in cache: it's a hit. Otherwise call slow_lookup and store the result.
calls = ["a", "b", "a", "c", "a", "b"]
cache = {}
hits = misses = 0
def slow_lookup(key):
return key.upper() * 3
for key in calls:
if key in cache:
hits += 1
else:
misses += 1
cache[key] = slow_lookup(key)
print(f"hits: {hits}")
print(f"misses: {misses}")
print(f"hit rate: {hits / len(calls) * 100:.1f}%")
Run your code to check this step…
Evict the least recently used
With a capacity of 3, evict the least recently used key whenever a new one arrives full. A repeat access counts as a use. Print the evicted keys in order and what remains.
cache.move_to_end(key) marks a use; cache.popitem(last=False) removes the oldest.
from collections import OrderedDict
CAPACITY = 3
cache = OrderedDict()
evicted = []
for key in ["a", "b", "c", "a", "d", "e", "b"]:
if key in cache:
cache.move_to_end(key)
else:
if len(cache) >= CAPACITY:
evicted.append(cache.popitem(last=False)[0])
cache[key] = key.upper()
print(f"evicted: {evicted}")
print(f"remaining: {list(cache)}")
Run your code to check this step…
Wrap it in a class
Build an LRUCache class with get and put, tracking hits and misses. Exercise it with capacity 2 and print the lookups, the counters and the surviving keys.
get: on a hit, move_to_end and return; on a miss return None. put: evict with popitem(last=False) when at capacity.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.store = OrderedDict()
self.hits = 0
self.misses = 0
def get(self, key):
if key in self.store:
self.hits += 1
self.store.move_to_end(key)
return self.store[key]
self.misses += 1
return None
def put(self, key, value):
if key in self.store:
self.store.move_to_end(key)
elif len(self.store) >= self.capacity:
self.store.popitem(last=False)
self.store[key] = value
cache = LRUCache(2)
cache.put("x", 1)
cache.put("y", 2)
print(cache.get("x"))
cache.put("z", 3)
print(cache.get("y"))
print(cache.get("z"))
print(f"hits={cache.hits} misses={cache.misses}")
print(f"keys={list(cache.store)}")
Run your code to check this step…
Token-bucket rate limiting
Each user gets a bucket of 3 tokens refilling at 3/second. A request costs one token; with none left, answer 429. Print each request's verdict.
tokens = min(BURST, tokens + (now - last) * RATE) refills; spend one if tokens >= 1.
RATE = 3 # tokens refilled per second
BURST = 3 # bucket size
requests = [
("ana", 0.0), ("ana", 0.1), ("ana", 0.2), ("ana", 0.3),
("bo", 0.3), ("ana", 1.5), ("bo", 1.6),
]
buckets = {}
for user, now in requests:
tokens, last = buckets.get(user, (BURST, 0.0))
tokens = min(BURST, tokens + (now - last) * RATE)
if tokens >= 1:
allowed, tokens = True, tokens - 1
else:
allowed = False
buckets[user] = (tokens, now)
print(f"{now:>4} {user:<4} {'200 OK' if allowed else '429 Too Many Requests'}")
Run your code to check this step…
Project shipped!
You just built a complete, working lru cache & rate limiter — the same architecture running in production software. Pick your next build →