System design interview

Hi, I'm Alex. In this round we'll design a system together, about forty-five minutes. The whiteboard is on the right; draw as you go, and talk me through your decisions. There's no single right answer. We'll keep a few minutes at the end for your questions. Before that, what are you working on these days?

Hi. I'm in my final year, computer science. This term I'm doing a project with a small logistics startup, Fennick Freight, on their parcel tracking API. So, mostly backend: Python, Postgres, a bit of Redis for caching tracking pages, because carriers hammer the same parcel IDs. It's been fun, and a bit scary, it's the first time my code has real users. Nothing at the kind of scale you see in these interviews, though.

Okay. What did the Redis cache fix for you?

Response times, mostly. One carrier was polling every parcel every thirty seconds, and the tracking page did four joins. With a cache with a short expiry, the database load dropped by, I think, two thirds. And then we added a per-carrier limit, which, funnily enough, is sort of today's topic, I guess. It was just a counter with an expiry, nothing clever.

Okay. Here's the problem. Design a distributed rate limiting service used by hundreds of internal APIs to protect themselves from overload and abuse. Take it wherever you want; start when you're ready.

Okay. Before I draw anything, a few questions. What are the limits keyed on: per user, per API key, per IP, something else? And do the rules change often, or are they basically static config?

Per API key, per user, per IP and per endpoint, and combinations of those. Teams want to change rules without a deploy, sometimes several times a day.

And the scale and the latency budget? Since it sits in the request path of every call, it can't be slow.

About a million decisions per second at peak, across all the APIs. A decision should add under five milliseconds.

Okay. And when we're unsure, is it worse to let a few extra requests through, or to block good traffic? That decides a lot of the failure behaviour.

Wrongly blocking good traffic is worse. Occasional over-admission is fine. And the limiter must not become a single point of failure.

One more: is it one region, or several? And are limits usually per second, per minute?

One region for now. Limits are mostly per second and per minute, some per day.

Got it. So let me write down the requirements. Functional: for each request, check it against all the rules that match it, and return allow or deny. Teams can create and edit rules at runtime. Non-functional: under five milliseconds added, a million checks a second, highly available, no single point of failure, and when in doubt we let traffic through. Accuracy can be approximate, a few percent over the limit is fine. And I'd like to be able to see what's being denied.

How much state is that?

Um, let me estimate. Say ten million active keys at any time, across users, API keys and IPs; IPs are probably most of it. For a token bucket I need the tokens and a timestamp, so maybe sixteen bytes, plus, you know, the key itself and the hash overhead, call it, um, a hundred bytes per entry. That's, uh, ten million times a hundred, a gigabyte. So it fits in memory, on a few machines with headroom. Even ten times more keys would be fine across a cluster.

And the request rate on that store?

If every decision touches the store once, a million operations a second. More, if a request matches several rules. A single Redis node does maybe a hundred thousand simple operations a second, a bit fewer with scripts, so roughly ten shards, more with headroom. Sixteen, say. That's a sizable cluster but not crazy.

Okay, so my first idea, the simplest thing: every API calls a central rate limiter service before handling a request, and the service keeps one counter per key in Redis. INCR with an expiry, so a fixed window per minute, like what I did at Fennick. If the counter is over the limit, deny.

What does the API look like?

Something like check, with the request's attributes: API key, user ID, IP, endpoint, and a cost, usually one, but an expensive call like a bulk export could cost more. It returns allowed or not, the remaining tokens, and a retry-after in milliseconds, so the API can send a proper four-twenty-nine with a Retry-After header. The service works out which rules match; the caller doesn't need to know the rules.

Walk me through one request. Where do the five milliseconds go?

The API receives a request and calls the limiter, the limiter calls Redis, and back... um, that's two network hops in sequence. Inside one data center that's maybe half a millisecond to a millisecond each, so it fits, with room for some queueing. But, hmm, at a million a second the limiter service becomes the thing everything depends on.

And what happens if the limiter is down?

Then every API is either blocked, or if they time out and allow, nothing is protected. So it's a single point of failure, which you said it must not be. I'd rather make it a sidecar next to each API instance: no extra network hop, and the sidecar talks to Redis directly. If one sidecar dies, it only affects its own pod.

Why a sidecar and not a library?

A library would be even cheaper, no process boundary at all. But with hundreds of APIs they're probably in different languages, so I'd have to write and upgrade the client in each one, and upgrades would depend on every team redeploying. A sidecar is one implementation, and we can roll it out ourselves. The cost is a local call over localhost, which is well under a millisecond.

Which algorithm would the sidecar use?

Not the fixed window I started with: fixed windows let a client send double the limit around the window boundary, a full minute's worth at the end of one window and again at the start of the next. So a token bucket: per key we store the tokens left and the last refill time, and refill on every read based on the time that passed. It allows short bursts up to the bucket size, which fits 'don't block good traffic'. A sliding window log is more exact, but it stores every timestamp, which is too much memory at a million a second.

Sliding window counter?

Um, that's the one with two fixed windows and a weighted sum? The current window's count plus the previous window's count times the fraction of it that's still inside the sliding window. That's cheap, two counters per key, and close enough in practice. It's honestly also a fine choice. I'd still go with the bucket because teams think in 'a hundred a second with bursts of two hundred', and that maps directly to the refill rate and the capacity.

How do you make the check-and-decrement safe when many sidecars hit the same key?

If two sidecars read the bucket, both see one token, and both write back zero, we admitted two. So the read, refill and decrement have to be one atomic step. In Redis I'd use a Lua script, which runs atomically on the shard. And Redis is sharded by a hash of the key, so one key always lives on one shard, so there's no cross-shard coordination for a single key.

Walk me through the script.

It gets the key, so a hash with tokens and last refill. Takes the current time... um, actually, time is a problem, the sidecars' clocks differ, and if one is ahead it refills too much. I'd use the Redis server time inside the script, so one clock per key. Then tokens becomes the min of the capacity and tokens plus elapsed time times the rate. If tokens is at least the cost, subtract and allow, else deny and compute the retry-after from the deficit. Write back, set an expiry so idle keys disappear on their own, and return the result.

What exactly is a key? Spell out the data model.

A rule has an ID, a scope, like per user on endpoint X, a rate and a capacity. The bucket key in Redis is the rule ID plus the value of the dimension, so something like rl, colon, rule 42, colon, user 1234. The value is a small hash with two fields, tokens and last refill. The rule itself, the rate and capacity, lives in the sidecar's memory and gets passed into the script as arguments, so Redis doesn't need to know about rules at all. That also means a rule change applies on the next check without touching Redis.

Why Redis and not something else?

Mostly because it's in memory, sub-millisecond, and it can run the check atomically with a script. Memcached is just as fast but has no scripting, so I'd need compare-and-swap loops, which get ugly on a hot key. A database like Postgres or DynamoDB is too slow and too expensive per operation at a million a second. A custom in-memory service would work too, but then we'd be building and running our own Redis. I'd only do that later if Redis became the limit.

How does a sidecar know which shard holds a key?

With Redis Cluster, the key is hashed into one of, I think, sixteen thousand three hundred and eighty-four slots, with CRC16, and each node owns a range of slots. The client caches the slot map and goes straight to the right node; if the map is stale, it gets a MOVED reply and refreshes. What happens to in-flight requests during resharding, honestly, I don't know the details. I'd have to read up on that.

One request matches four rules. How many round trips?

Four keys, user, API key, IP and endpoint, possibly on four different shards. If I do them one by one that's four hops in sequence, which eats the budget. I'd send them in parallel, so latency is the slowest one, not the sum. Um, but then one could allow and another deny, and the allowed ones have already taken a token.

Does that matter?

A little: a denied request still costs tokens on the other keys, so a user who's hitting the endpoint limit also burns their own user budget. Given we prefer over-admission, I'd mostly accept it, or refund the tokens asynchronously after a deny. I wouldn't do a distributed transaction for this, it's far too slow for five milliseconds.

How does the sidecar find the rules that match a request quickly?

There could be thousands of rules, so not a linear scan per request. I'd index them by endpoint first, with an exact-match map plus a small prefix tree for path patterns like slash orders slash star. Then for the few rules on that endpoint, check which dimensions apply: does it have an API key, which user. Rules that apply to every endpoint, like a global per-IP rule, sit in their own list. That should be microseconds. The index gets rebuilt whenever new rules arrive, and swapped in atomically, so a request never sees half the rules.

And the API, when it gets a deny?

Returns a four-twenty-nine with Retry-After. Well-behaved clients back off with jitter. Internal clients we control should use a shared client library that respects it, otherwise they retry immediately and make the overload worse.

Put numbers on the request path now, end to end.

Okay. The API to the sidecar over localhost, maybe a tenth of a millisecond. Rule matching, microseconds. Then the Redis calls in parallel, inside one data center, about half a millisecond at the median, but the p99 could be two or three milliseconds when a shard is busy. So the median is under a millisecond and the tail is what matters. That's why I want the hard timeout at about two milliseconds, and after that the sidecar decides locally. So we stay under five even in the bad case.

Let's stress it. One tenant suddenly sends most of the traffic on a single key. What happens?

That key's shard gets hot. Every check for that key goes to one Redis node, and a single node tops out at maybe a hundred thousand a second, and it slows down every other key on that shard. Um, the sidecar could keep a local bucket for that key and only sync with Redis every hundred milliseconds, so it spends a share of the limit locally. It over-admits a bit between syncs, which we said is acceptable.

How much can it over-admit?

Roughly... if every sidecar can spend its local share for one sync interval before it hears from Redis, the worst case is about one interval of extra traffic per sidecar. I'm not sure of the exact bound, I'd have to work it out.

Try it with numbers. A limit of a thousand a second, fifty sidecars.

Okay. If each sidecar gets an equal share, that's twenty a second each. Hmm, but the traffic isn't spread equally, so the share is wrong for most of them... If instead each sidecar can spend up to the full rate locally for a hundred milliseconds, that's a hundred requests each before syncing, times fifty is five thousand in a tenth of a second. That's way over. So the local share has to be smaller, like the limit divided by the number of sidecars that are actually seeing that key, which Redis can count. Then the error is bounded by about one sync interval of the global rate, so about a hundred extra per interval.

When does a key switch to the local mode?

The sidecar can count its own calls per key; above some rate, say a few hundred a second, it switches that key to local mode. Or Redis tells it, since the script can see how often a key is hit. I'd start with the sidecar deciding, it's simpler.

Next. Now the Redis shard holding a set of keys goes down. Say it's peak traffic.

Then the sidecar can't get a decision for those keys. Since blocking good traffic is worse, it fails open for them, but keeps a local bucket as a rough limit, so one sidecar can't let through unlimited traffic. And we alert on it. Each shard has a replica, so failover should take seconds, not minutes. The sidecar needs a tight timeout on Redis, like two milliseconds, so a slow shard doesn't eat the whole budget.

What does the replica have?

Redis replication is asynchronous, so it's slightly behind. After failover some buckets are a bit fuller than they should be, so we over-admit for a moment. Again, acceptable. I wouldn't pay for synchronous replication here, that would add latency to every single check.

And if Redis runs out of memory?

Every bucket has a TTL, so idle keys go away by themselves. If it still fills up, I'd set the eviction policy to evict keys with a TTL, least recently used first. An evicted bucket comes back full, so the worst case is over-admission for that key, which fits the policy. The important thing is that Redis never starts rejecting writes, because then every check errors out and we fail open everywhere at once. Um, and with the cluster bus, when a node is under memory pressure, the gossip—

Let's stay at the level of what the sidecar sees.

Sure. From the sidecar's side: slower replies and timeouts, which look like a shard failure, so it's the same fail-open path with the local bucket, and an alert.

Some limits are per day. Does the token bucket still work?

Mm, it works mathematically, the refill rate is just tiny, a thousand a day is about one every ninety seconds. But it means the TTL has to be longer than a day, and teams usually mean 'resets at midnight', not 'refills smoothly'. For daily quotas I'd use a plain counter keyed by the date, with an expiry of a couple of days. Those are more like billing quotas than overload protection anyway, they don't need to be checked on the hot path at the same precision.

A client sends a burst from ten thousand IPs.

So per-IP limits don't help, each IP is under its limit. That's where the per-endpoint and per-API-key limits matter: if it's all one API key, its bucket runs dry and we deny. If there's no key, like a public login endpoint, the per-endpoint global limit protects the service, but then good users get blocked too.

Which you said is the worse outcome.

Right. Um. I could... prioritise. Keep a reserved part of the capacity for keys and users we've seen before with good history, and shed the unknown traffic first. Grouping IPs by subnet would help too, ten thousand IPs are often a few ranges. But honestly, at that point it's more of a DDoS problem, and I'd expect something at the edge to absorb most of it before it ever reaches the internal APIs.

And the rules. How do they get to the sidecars?

A rules service with its own database, Postgres is fine, it's tiny and changes rarely compared to the traffic. The sidecars pull the rules every few seconds and cache them in memory, so matching a request to rules never leaves the pod.

What if someone pushes a bad rule that blocks all traffic?

Oh. Hmm. I guess we'd roll it back quickly? Maybe someone reviews rule changes before they go out.

Within five seconds every sidecar has it.

Right, so a review doesn't save us when the mistake gets through, and rollback is too late. Then... the rules service could validate a rule before accepting it, like reject a limit of zero on a whole endpoint, or a limit far below the current traffic. And, um, maybe roll it out to a few sidecars first and watch the deny rate before it goes everywhere. I haven't thought about how you'd do that cleanly, it's a bit vague.

And if the rules service is down?

The sidecars keep the last rules they have, they're cached, so nothing changes for running pods. New sidecars starting up would need a copy, so I'd also publish a snapshot to object storage that they can read at startup, and the rules service writes it on every change.

Different kind of change. A new region is added with its own traffic, and some API keys are used from both regions.

Um, I'd keep a Redis cluster per region and give each region its own share of each limit. A truly global limit across regions would need cross-region calls in the request path, which is tens of milliseconds and kills the five-millisecond budget. So limits become per region, maybe rebalanced every few seconds by a background job that looks at where the traffic actually is. The rules themselves can be replicated, they're small.

What breaks first at ten times the load?

The Redis cluster, ten million operations a second. I'd add shards, that part scales horizontally, and lean more on local buckets for keys with high traffic, so most decisions never leave the pod. The rules pull is tiny, it scales fine. And the metrics pipeline, actually, if we log every decision; I'd aggregate in the sidecar and only ship counts.

What are the weakest parts of your design?

Um, the rule rollout, definitely, I only half have an answer there. And the multi-rule check, the tokens taken by a request that's denied elsewhere. And I never defined how the over-admission is measured, I'd want a metric for that, like admitted versus limit per key.

How would you monitor it?

Per sidecar: decision latency, the Redis error and timeout rate, fail-open count, and deny rate per rule. An alert when a single rule's deny rate jumps, which also catches the bad-rule case. And a dashboard per API team, so they can see their own limits.

How would you test this before it's in front of real traffic?

Load test with replayed production traffic, so the key distribution is realistic, including the hot keys, because synthetic uniform traffic would hide the hot-shard problem. Then failure tests in a staging cluster: kill a Redis primary at peak and check that the fail-open rate spikes and recovers, and that latency stays under five milliseconds. And a test for the bad-rule case, push a zero rule and make sure validation rejects it.

How would you roll the sidecar out?

Shadow mode first: it makes decisions and logs them, but never denies. Compare with what the APIs see and tune the rules, then turn on enforcement per API, starting with the ones that want it most, probably the ones that have been overloaded before.

Version two?

A self-service UI for rules with a dry-run button that shows how much traffic a rule would have denied yesterday. I think that also helps the bad-rule problem, people would see the zero-limit mistake before saving it.

Okay. We have a few minutes left. Any questions for me?

Yes. How do teams usually split work like this, like who would own something like a rate limiter?

Usually a platform or infrastructure team owns shared pieces like this, with the API teams as its customers. The hiring team can tell you how it works for this particular role.

Okay. And how much of the job is design versus writing code, for a new grad?

Mostly code at first, with design reviews you'd sit in on and contribute to over time. The specifics vary by team.

And is there anything about this kind of service that usually surprises people when they actually build it?

Usually the operational side: rule changes, debugging why a request was denied, and who gets paged when the limiter itself misbehaves. The algorithm tends to be the easy part.

That makes sense. Thanks, that's all from me.

Thanks, that's time. You'll get your report in a few minutes.