Two components show up in almost every LLD interview and almost every real service: a rate limiter that protects the API from any one client, and an in-memory cache that keeps hot answers close. Both look like ten lines of code. Both have a version that works on a laptop and fails in production, and the difference is in the low-level choices: which algorithm, which data structure, what is shared between replicas, and what happens when the clock or the store misbehaves. This lesson designs both for the parcel-tracking API, class by class, and follows one request through them. By the end you can design, implement, and defend a token-bucket limiter and an O(1) LRU cache, and explain how each one behaves at a hundred times the traffic.
Difficulty: Advanced · Know this first: Lesson 167, Lesson 45, Lesson 15
This bar splits one API request. It is a worked example, not a measurement. In the good design the limiter and the cache are slivers and the replica read dominates; each failure makes one small component the biggest slice.
Move the sliders. A client bursts and then keeps sending. The bucket lets the burst through up to its capacity, then holds the client to the refill rate. Watch what reaches the database, and the load hop in the bar above.
effective limit = rate × pods (pods with their own buckets each enforce the full limit) · allowed/s = min(client rate, effective limit) · rejected/s = client rate − allowed
first second allows up to capacity × pods + rate × pods · the database can absorb 150 misses a second from one client before reads slow down.
The limit holds: the database sees what the contract allows
Three questions. No score is saved anywhere — this is just you against the material.
These two components grow in four levels: first the behaviour and the API, then the algorithm and data structure with their complexity, then concurrency and distribution across pods, and finally running them as production systems with failure modes, fairness, and observability.
At the basic level you define the behaviour before the code. The limiter answers one question: may this client make this request now? The cache offers get and put with a fixed capacity, and evicts the least recently used entry when full. Each comes with a small API and a handful of example cases written as tests.
Types:
Uses: public APIs, login endpoints, expensive queries, and any read path with hot keys.
Where it breaks: choosing an algorithm by name without writing the cases it must handle, such as "a client sends 200 requests in the first millisecond". The cases decide the algorithm.
Try it: Basic
A fixed-window limiter allows 100 requests per minute. What can a client do at 12:00:59 and 12:01:00?
Now do it: Write five test cases for a rate limiter, including a burst at a window boundary, before choosing its algorithm.
At the intermediate level you design the internals and state their complexity. The token bucket stores two numbers per client and refills lazily from elapsed time, so allow() is O(1) and idle clients cost nothing. The LRU cache pairs a hash map from key to node with a doubly linked list in recency order, so get, put, and evict are all O(1). The clock is injected, so tests can move time.
Types:
tokens = min(capacity, tokens + elapsed × rate) at each call.Uses: any in-process limiter or cache, and most LLD interview questions.
Scale and failure: at 200,000 entries an O(n) recency update costs tens of milliseconds per call, and the cache becomes the slowest hop. The cost of the O(1) design is more pointers and more careful code; the trade is worth it as soon as the cache holds more than a few hundred entries.
Try it: Intermediate
Which pair of structures gives an LRU cache O(1) get, put, and eviction?
Now do it: Implement the LRU from the Go deeper section and time get() at 1,000 and at 200,000 entries.
At the advanced level the components run on many threads and many pods. The in-process cache needs a lock or a concurrent structure, and coalesces concurrent misses per key. The limiter's state is shared and updated atomically, either in a store with atomic scripts or with local buckets that sync to a global count. Clock skew between hosts is handled by using the store's time, not each pod's.
Types:
Uses: horizontally scaled APIs, multi-tenant platforms, read-heavy services with hot keys.
Scale and failure: a shared store adds a network hop to every request and becomes a dependency: if Redis is down, the limiter must fail open (serve, unprotected) or fail closed (reject everyone), and that choice belongs in the design doc. A hybrid limiter cuts the hop at the cost of briefly allowing up to the sum of local budgets.
Try it: Advanced
The Redis behind the limiter goes down. What should the design already say?
Now do it: Use the simulator above with six pods and per-pod buckets. Then set pods to 1 and see what shared state changes.
At the master level the limiter and the cache are products with policies, owners, and dashboards. Limits are configured per plan and per endpoint, with costs per operation so an expensive search spends more tokens than a cheap read. Fairness matters: one tenant cannot starve the others. Caches are measured by hit ratio, eviction rate, memory, and stampede events, and tuned from those numbers.
Types:
Uses: public platforms and internal platforms with many tenants.
Trade-off: every policy knob is something to configure, explain, and support. The master-level design keeps defaults simple and documented, and adds knobs only where a real customer or incident has shown they are needed.
Try it: Master
One tenant's heavy search queries slow the API for everyone, though they stay within their request-per-second limit. What does a master-level limiter add?
Now do it: For one API you run, estimate the backend cost of its three most expensive endpoints relative to the cheapest. Those ratios are your token weights.
Both components fit in one screen each when the LLD is right. The token bucket takes its clock as a dependency so tests can move time; the LRU uses sentinel nodes so the list code has no empty-list special cases.
class TokenBucket:
def __init__(self, rate, capacity, clock):
self.rate, self.capacity, self.clock = rate, capacity, clock
self.tokens, self.last = capacity, clock()
def allow(self, cost=1):
now = self.clock()
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if self.tokens >= cost:
self.tokens -= cost
return True
return False
-- the same refill-and-take, atomic in Redis (KEYS[1] = bucket, ARGV = rate, capacity, now, cost)
local b = redis.call("HMGET", KEYS[1], "tokens", "last")
local tokens = tonumber(b[1]) or tonumber(ARGV[2])
local last = tonumber(b[2]) or tonumber(ARGV[3])
tokens = math.min(tonumber(ARGV[2]), tokens + (tonumber(ARGV[3]) - last) * tonumber(ARGV[1]))
local ok = tokens >= tonumber(ARGV[4])
if ok then tokens = tokens - tonumber(ARGV[4]) end
redis.call("HSET", KEYS[1], "tokens", tokens, "last", ARGV[3])
redis.call("EXPIRE", KEYS[1], 60)
return ok and 1 or 0The same five lines of arithmetic in both. In Redis they run as one script, so no other pod can interleave between the read and the write. In production, pass the time from the Redis server or a single source, not each pod's clock.
This runs as is. The LRU uses a dict plus a doubly linked list with sentinels; the bucket test moves a fake clock instead of sleeping.
# python3 lru_and_bucket.py
class Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key=None, val=None):
self.key, self.val, self.prev, self.next = key, val, None, None
class LRU:
def __init__(self, capacity):
self.cap, self.map = capacity, {}
self.head, self.tail = Node(), Node() # sentinels
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, n):
n.prev.next, n.next.prev = n.next, n.prev
def _push_front(self, n):
n.prev, n.next = self.head, self.head.next
self.head.next.prev = n
self.head.next = n
def get(self, key):
n = self.map.get(key)
if n is None:
return None
self._unlink(n); self._push_front(n)
return n.val
def put(self, key, val):
if key in self.map:
self._unlink(self.map[key])
n = Node(key, val); self.map[key] = n; self._push_front(n)
if len(self.map) > self.cap:
old = self.tail.prev; self._unlink(old); del self.map[old.key]
c = LRU(2)
c.put("P1", "in_transit"); c.put("P2", "delivered")
c.get("P1") # P1 is now most recent
c.put("P3", "created") # evicts P2, the least recent
print("cache:", {k: c.get(k) for k in ["P1", "P2", "P3"]})
t = [0.0] # a fake clock the test controls
class TokenBucket:
def __init__(self, rate, capacity, clock):
self.rate, self.capacity, self.clock = rate, capacity, clock
self.tokens, self.last = capacity, clock()
def allow(self):
now = self.clock()
self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
self.last = now
if self.tokens >= 1:
self.tokens -= 1
return True
return False
b = TokenBucket(rate=100, capacity=200, clock=lambda: t[0])
burst = sum(b.allow() for _ in range(300))
t[0] += 0.5 # half a second later: 50 tokens refilled
later = sum(b.allow() for _ in range(300))
print("burst allowed:", burst, "| after 0.5 s:", later)
Expected: cache: {'P1': 'in_transit', 'P2': None, 'P3': 'created'}, then burst allowed: 200 | after 0.5 s: 50. The burst gets the capacity, then the client is held to the rate. No sleep, no flaky timing: the clock is a dependency.
A public tracking API I worked on had a rate limiter that passed every test and every review. Each API pod kept its buckets in memory, which was fine for two years because the deployment ran two pods and the documented limit had a comfortable margin.
The limiter moved to Redis with an atomic script and a documented fail-open policy for reads and fail-closed for writes. The response headers now report the shared budget, so the partner could see what it was spending. The design review checklist gained a question for every per-instance state: what is the effective behaviour at the maximum replica count?
Design the low-level structure of a login throttle: after five failed passwords in ten minutes, an account is locked for fifteen minutes; separately, one IP address may try at most fifty logins a minute across all accounts. The login service runs on eight pods.
Is the lock per account, per account-and-IP, or both? Should a successful login reset the failure count? What does a locked account see, and does it reveal that the account exists? What happens if the shared store is unreachable: lock everyone out, or let logins through?
Say 2,000 login attempts a second at peak, a few percent failing. State is two small counters per active account and per active IP, expiring after minutes: a few hundred megabytes at most in Redis.
A FailureCounter per account with a sliding ten-minute window (sorted set of timestamps, or a counter per minute bucket); a TokenBucket per IP at 50 per minute; a LockPolicy object deciding lock length; all state in Redis behind atomic scripts; a Clock interface for tests. Sequence diagram for "fifth failure locks the account" and for "store unreachable".
Locking by account alone lets an attacker lock out any user by guessing; adding IP and device signals reduces that and adds state. Failing open during a store outage keeps logins working and removes brute-force protection briefly; failing closed is safer and is an outage. Identical error messages for "locked" and "wrong password" protect privacy and frustrate real users.