Platform Engineering · Lesson 168

LLD Case Study: A Rate Limiter and an LRU Cache, Class by Class

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

Run it as:

When it breaks, I check

One thing to remember

Where the time goes

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.

Try it: what a token bucket lets through

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.

100effective limit / s
100allowed / s, steady
500rejected / s (429)
300allowed in the first second

The limit holds: the database sees what the contract allows

Check yourself

Three questions. No score is saved anywhere — this is just you against the material.

Basic to master

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.

Basic — Behaviour first: what allow() and get() promise

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:

  • Fixed window: N requests per clock minute. Simple, and allows 2N across a window boundary.
  • Sliding window log or counter: smoother, and more state per client.
  • Token bucket: an average rate plus an allowed burst, the most common choice for APIs.
  • Cache policies: LRU, LFU, FIFO, and TTL-based expiry, often combined.

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.

Intermediate — Algorithms, data structures, and complexity

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:

  • Lazy refill: tokens = min(capacity, tokens + elapsed × rate) at each call.
  • Hash map plus doubly linked list for O(1) LRU; sentinel head and tail nodes remove edge cases.
  • Clock and time-source interfaces for deterministic tests.
  • Size accounting by entries or by bytes, enforced on every put.

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.

Advanced — Concurrency and distribution across pods

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:

  • Atomic refill-and-take in Redis with a Lua script, keyed per client.
  • Hybrid limiters: a local bucket per pod for speed, reconciled with a global budget periodically.
  • Lock striping or sharded caches to reduce contention on one lock.
  • Singleflight: one in-flight load per key, with waiters sharing its result.

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.

Master — Running them as production systems

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:

  • Weighted costs per operation and tiered limits per plan.
  • Global and regional limits, and what a client experiences when it fails over between regions.
  • Adaptive limits: lower limits automatically when the backend is unhealthy.
  • Cache observability: hit ratio per key class, eviction reasons, memory per entry, hot-key detection.

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.

Go deeper

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 0

The 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.

An O(1) LRU, and a test with a fake 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.

One time it broke

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.

Timeline

  • MondayAutoscaling is tuned for the holiday season: the API now runs twelve pods at peak instead of two.
  • Wednesday, 10:00A partner's new integration polls every parcel in its account, once a second. It is within the documented limit per connection, and its HTTP client opens many connections.
  • 10:20Read replica CPU climbs to 95 percent. Real customers' status requests go from 30 ms to two seconds.
  • 10:45The traffic is traced to one key, allowed about twelve times its limit because each pod granted the full limit independently.
  • 11:10The key is capped at the gateway by hand. The replica recovers within minutes.

What changed after

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?

If you remember nothing else

Design exercise

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.

Clarifying questions to ask

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?

Rough sizing

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.

Shape of the answer

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".

Trade-offs to name

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.

Saved on this device, in this browser.
Next in this series · Lesson 169
Service Boundaries: Domain-Driven Design, Bounded Contexts, and Aggregates

The hardest design question is not inside a service. It is where one service ends and the next begins. Draw the line in the right place and teams ship independently, data has one owner, and a failure stays local.

Go to Lesson 169 →

Or browse the full course from the Lessons index.