Rate Limiting Algorithms

1The core idea#

A rate limiter answers one question: given this request, do I let it through right now, or reject it (usually with HTTP 429)?

The mental model I use: a bouncer at a club door with a clicker.

• People show up, the bouncer decides who gets in based on some rule about how fast they are allowed in.
• The easy part is "let them in." The hard part is the counting, the fairness, and what happens when you have ten bouncers at ten doors who all need to agree on one total.

You rate limit for a few reasons, and a good interviewer wants you to name them:

• Protect the backend from overload (one buggy client hammering you with 5,000 requests a second).
• Enforce fairness, so one noisy tenant does not starve everyone else.
• Enforce business rules (free tier gets 100 calls a day, paid tier gets 100k).
• Blunt abuse, like credential stuffing on a login endpoint.

2How it works#

Four algorithms are worth knowing. Here they are in order of how often they show up in real systems.

Token bucket. A bucket holds up to N tokens, refilling at a steady rate.

• Tokens refill at, say, 10 per second. Every request removes one. Empty bucket means reject.
• An idle client lets the bucket fill to its cap, so it can then spend all N in one burst.
• This is "100 requests per minute, but a batch of 20 at once is fine."
• Stripe, GitHub, and AWS all run some flavor of this.

Leaky bucket. Requests queue in the bucket and drain at a fixed rate, like water through a hole.

• Overflow means drop the request.
• Output is perfectly smooth. No burst ever reaches your backend.
• Good when the thing downstream genuinely cannot take spikes, like a payment processor that wants a steady 50 transactions per second.

Fixed window counter. Divide time into fixed buckets (each calendar minute) and count.

• One counter per key, cheap to store, dead simple.
• Exceed the limit in the current minute, reject.
• The catch is the boundary, which I hit in pitfalls.

Sliding window. Two variants, one exact and one practical.

• Sliding window log stores a timestamp per request and counts how many fall inside the trailing window. Exact, but memory grows with traffic.
• Sliding window counter keeps the current and previous fixed-window counts and blends them by how far into the current window you are. Nearly as accurate as the log, almost as cheap as fixed window.
• The counter variant is what I reach for most in practice.

A worked example with real numbers#

"N tokens, refill rate R" stays abstract until you run numbers through it, so let me make token bucket concrete.

Setup: you sell an API at 60 requests per minute per key, and you allow a short burst.

• Capacity N = 60 tokens, refill rate R = 1 token per second (60 per minute).
• Store two numbers per key: tokens (current count) and last_refill (a timestamp).
• No background timer. You refill lazily on each request, which keeps it O(1) and cheap.

The per-request math, on a request at time now:

elapsed   = now - last_refill          # seconds since last touch
tokens    = min(N, tokens + elapsed * R)
last_refill = now
if tokens >= 1:
    tokens -= 1
    allow()
else:
    reject()                            # 429, Retry-After = ceil((1 - tokens) / R)

Now walk a real timeline for one key, N = 60, R = 1/sec:

Three things fall out of this table that interviewers love:

• Burst is bounded by N, steady rate by R. The client got 60 through instantly, then had to wait. Over any long stretch, throughput averages back to 1/sec. That is the "100 per minute, batch of 20 is fine" behavior exactly.
• Refill caps at N. At t=70 the bucket saturated at 60, it did not overflow to 69. Idle time does not bank unlimited credit.
• Retry-After is free math. When tokens is 0, the client waits (1 - 0) / R = 1 second. Hand them the exact number instead of making them guess.

The per-request decision flow#

Here is the decision a limiter runs per request:

And here is where the limiter actually sits in a distributed setup. The detail that matters: the counter lives in a shared store, not in each node's process memory.

3Trade-offs#

The algorithm choice is a trade between accuracy, memory, and burst behavior.

One number to anchor the memory column.

• Sliding window log at 10k active keys, each averaging 200 requests in the window, with a 16-byte timestamp entry: 10,000 x 200 x 16 is roughly 32 MB just for timestamps, and it grows with traffic.
• Sliding window counter for the same 10k keys is two integers each, a few hundred KB flat.
• That is why I almost never ship the log version at scale.

The trade-off that actually matters in a distributed system is a different axis: accuracy versus latency and cost.

A precise global limit (shared exact):

• Every request touches a shared counter (Redis, usually) before you answer.
• That is a network round trip on the hot path, call it 0.5 to 1 ms inside a datacenter, added to every single request.
• You can shard the counter at high volume, but a single key cannot be sharded, so one hot tenant hammering one key creates a hotspot on one Redis node.

The cheaper alternative (local approximate):

• Each of your 40 nodes keeps its own counter and you divide the global limit by 40. A 200k/sec budget becomes 5k per node.
• No shared state, no round trip, near-zero latency.
• The cost: it is only approximate. Uneven traffic across nodes, or a node restarting and losing its counter, drifts the real global rate from your target.

So the honest interview answer: local approximate for protection, a shared exact counter for anything a customer can see on an invoice. Overshoot a protection limit and nothing breaks. Overshoot a billing limit and you give away money or overcharge, and now you have a support ticket.

4Where it is used#

A limiter shows up at every layer traffic passes through. Each spot picks the algorithm that fits its job.

• Public API gateways. Stripe, GitHub, Twilio publish limits and return 429 with a Retry-After header. Token bucket or sliding window, enforced at the gateway so your backend never sees the flood.
• Login and auth endpoints. The goal is abuse prevention. Limit per IP and per account, because a smart attacker spreads across IPs. Often a hard, low limit with exponential backoff.
• Internal service-to-service. Protecting a fragile downstream, like a legacy database or a vendor with its own quota. Leaky bucket shines here, smoothing traffic to a steady drip.
• CDN and edge. Cloudflare and similar run it at the edge, close to the client, so bad traffic dies before it crosses an ocean to your origin.

When would I not add a rate limiter?

• On a purely internal, trusted, low-traffic path where a new Redis dependency buys more operational risk than it removes.
• Do not rate limit for the sake of it.

5Common pitfalls and gotchas#

These are the places I see candidates fall, roughly in the order they come up.

The fixed-window boundary burst. The classic.

• Limit is 100 per minute. A client sends 100 at 12:00:59 and 100 more at 12:01:00.
• Both windows are individually under the limit, but you served 200 in one second. A 2x overshoot right when you least want it.
• Sliding window counter fixes this, which is the main reason it exists.

Race conditions on the counter. Read-count-then-write is not atomic.

• Two nodes both read "99," both think they are under 100, both write "100," and you let 101 through.
• The fix is an atomic operation: INCR in Redis, or a small Lua script that does the check and increment in one round trip.
• Reach for read-modify-write under concurrency and I always push on this.

Forgetting the key dimension. "Rate limit the API" is not specific. Per what?

• Per IP, per API key, per user ID, per endpoint, they are all different.
• NAT means thousands of real users can share one IP, so per-IP limits punish the innocent.
• Good systems limit on several keys at once and reject if any is exceeded.

No graceful response. A bare 429 with no Retry-After leaves clients guessing.

• They retry immediately, often all at once, and hammer you harder.
• Give them the header. From the token bucket example, that number is just ceil((1 - tokens) / R) seconds. No excuse for leaving it out.

The limiter becoming the bottleneck or single point of failure.

• If every request blocks on one Redis node and it dies, does your whole API go down?
• Decide your failure mode on purpose: fail open (allow traffic when the limiter is down, protecting availability) or fail closed (reject, protecting the backend).
• Most public APIs fail open. Say which you chose and why.

Clock skew across nodes. Window math depends on time.

• If node clocks drift by a few seconds, window boundaries disagree, and the lazy-refill elapsed math computes wrong.
• Anchor on the shared store's clock, or use NTP, and do not assume local clocks agree.

6How it shows up in interviews#

The question usually starts open: "design a rate limiter for our API." Here is how I grade it.

Weak answer. "I will use a counter per user and reset it every minute." Then it stops.

• That is fixed window with the boundary bug baked in.
• No mention of where the counter lives, no concurrency story, no response design.
• Probe with "two nodes both see count 99 at the same instant, now what?" and it stalls. You have read about this, not built it.

Strong answer. Same opening, but it moves through a predictable arc, and I am visibly happier at each step:

• Clarify the goal first. "Are we protecting the backend, or enforcing a paid quota? That changes whether I can tolerate an approximate limit." One question that changes the whole design, and asking it signals seniority.
• Name the key. Per user, per IP, per endpoint, and why. Mention limiting on several at once and rejecting if any is exceeded.
• Pick an algorithm and justify it. "Sliding window counter, because fixed window lets a client double the rate at the boundary and the log version eats roughly 32 MB at 10k keys. Token bucket if the product wants controlled bursts." That sentence alone clears the bar for most intermediate roles.
• Put the counter in a shared store and make it atomic. "Redis INCR with a TTL," or "a Lua script so the check, refill, and decrement are one atomic step." This is the detail that separates shippers from readers.
• Address scale and failure. Hotspot on a popular key, the local-versus-global trade-off, and your fail-open-or-fail-closed call. Mention the 429 and a Retry-After with an exact wait.

Put side by side: the weak answer names one algorithm and stops at the happy path. The strong answer names the goal, picks an algorithm for a reason, puts state somewhere real, makes it atomic, and has a plan for when it breaks. Same five minutes, completely different signal.

The probe I use most: "You are at 500k requests per second and every request hits Redis for the counter. What breaks?"

• The single hot key becomes a hotspot on one Redis node.
• The network round trip adds 0.5 to 1 ms to every request.
• The move is local-approximate per node (divide 500k by node count), or shard by key, accepting slightly fuzzy limits in exchange for not melting Redis.

Reason through that out loud and you have shown me you understand the cost of coordination in a distributed system, which is the whole point.

Depth on two algorithms beats name-dropping five. Know token bucket and sliding window counter cold, know why you would pick each, and know the distributed pitfalls.

For a full end-to-end walkthrough, see the related System Design Question: "Design a Distributed Rate Limiter."