Rate Limiter

API Rate Limiting System

Design the classes of a rate limiter: interchangeable algorithms behind one interface, per-tier and global rules checked in order, a retry-after on every refusal, and correct counting under concurrency.

Overview

A rate limiter decides, for each incoming request, whether to let it through or refuse it because the caller has sent too many recently. It protects a service from one noisy client, a runaway script or a traffic spike. A refused HTTP request usually gets status 429 Too Many Requests, which RFC 6585 defines and which may carry a Retry-After header saying how long to wait.

In a low-level design interview the question is about the objects: one interface that every algorithm implements, a small rule list that says which key each limit applies to (user, tier, whole service), time passed in so tests are exact, and a lock that makes 'count and decide' one step. The interviewer also expects you to compare the algorithms and to say which one you would pick and why.

Scoping the problem

What is the key: user, API key, IP, endpoint? — Decides the key function of each rule — User, plus a global cap
Are there tiers (free, paid)? — Different limits for the same rule — Yes
Should short bursts be allowed? — Token bucket allows them; a window may not — Yes, up to a set size
How exact must the count be? — Exact logs cost memory; counters approximate — Approximate is fine
One process or many servers? — Local state or a shared store — One process here; many is a follow-up
What does a refused caller get? — Status and headers — 429 with Retry-After

Core entities

ByTier is itself an Algorithm that forwards to the one configured for the caller's tier, so a tiered rule looks like any other rule to the limiter.

The algorithms side by side

Fixed window — Window number and a count — Twice the limit, across a window edge — The boundary burst below
Sliding log — Every accepted timestamp in the window — The limit, in any window-length span — Memory grows with the limit
Sliding counter — Two counts: this window and the last — About the limit; the estimate can be a little off either way — Assumes last window's requests were spread evenly
Token bucket — Tokens and the time of the last refill — The capacity at once, then the refill rate — Two numbers to explain to users (rate and burst)
Leaky bucket (not in the code) — A queue drained at a fixed rate — Nothing extra: output is smooth — Adds waiting instead of refusing

AWS API Gateway, for example, documents that it throttles with a token bucket, configured by a rate (tokens added per second) and a burst (the bucket's capacity).

The boundary burst

Take a limit of 3 per 10 seconds. A client sends 3 requests at 9.9 s and 3 more at 10.0 s. The demo runs this exact sequence against three algorithms.

Fixed window — all allowed — all allowed — 10.0 s starts a new window with a fresh count: 6 requests in 0.1 s
Sliding log — all allowed — refused — The three from 9.9 s are still within the last 10 s
Sliding counter — all allowed — refused — Previous window weighs 1.0 at the start of the new one: estimate 3

The sliding counter's estimate is previous count × the share of the previous window still inside the last 10 seconds, plus the current count. At 15 s that share is one half, so the estimate is 3 × 0.5 = 1.5 and one more request fits (1.5 + 1 = 2.5 is at most 3), and the next does not (3.5).

Token bucket, step by step

Capacity 3, rate 1 token per second. Tokens are refilled lazily: on each call, add (now − last) × rate, capped at the capacity, then spend one if there is one. Nothing runs in the background.

0 — 3 (new key) — 0 — allow — 2
0 — 2 — 0 — allow — 1
0 — 1 — 0 — allow — 0
0 — 0 — 0 — refuse — 0 — (1 − 0) ÷ 1 = 1 s
0.5 — 0 — 0.5 — refuse — 0.5 — (1 − 0.5) ÷ 1 = 0.5 s
1.0 — 0.5 — 0.5 — allow — 0

Checking a request

Each algorithm reads the key's state, decides and writes it back inside with self._lock. Without the lock, two threads could both read 'one token left' and both spend it. The demo sends 80 requests from 8 threads at the same instant to a bucket of 20 and asserts exactly 20 pass.

What you will be able to do

Put five algorithms behind one try_acquire interface and choose between them with a table.
Show the fixed-window boundary burst and how a sliding log or counter prevents it.
Trace a token bucket by hand, including the Retry-After value.
Combine per-tier and global rules and explain what happens when a later rule refuses.
Make each check atomic with a lock, and explain what changes when the state moves to a shared store.

Functional requirements

try_acquire(key, now) returns a Decision: allowed, remaining, and retry_after in seconds when refused
Algorithms: token bucket, fixed window, sliding log and sliding counter, all interchangeable
Rules pair a key function (user, tier, global) with an algorithm; RateLimiter.check runs them in order and reports which rule refused
Tiers: ByTier routes each (tier, id) key to that tier's algorithm
Idle token buckets are dropped once they have refilled to full

Non-functional requirements

O(1) time and memory per key for token bucket, fixed window and sliding counter; O(limit) for the sliding log
Concurrent requests for the same key are counted exactly: check and update happen under one lock
A new algorithm is a new Algorithm subclass; RateLimiter and the rules do not change
Time is passed in, so every decision in the tests is exact

Interview questions

Which algorithm would you pick for a public API, and why?
The per-user rule allowed a request and then the global rule refused it. Was the user charged?
How does this change with ten API servers behind a load balancer?
What should the client see when it is refused?