Design a Rate Limiter

A rate limiter has compact domain logic — "has this client exceeded their quota?" — the mark of a utility problem where the design work is precision, not breadth. That work centers on three concerns: choosing an algorithm whose state is cheap and deterministic, keeping per-client accounting independent, and making the allow/deny check safe when many threads evaluate the same client simultaneously. The design separates the policy-enforcement shell from the pluggable algorithm inside it.

See It in Action

The demo runs the finished design: one rate limiter giving each client an independent quota. Pick a client, spend its allowance with each request, and watch it refill over time. Spamming one client never touches another's allowance — the per-client independence at the heart of the design.

Clarifying Requirements

The functional requirements we will commit to: the limiter is keyed per client string; each client gets a quota of requests per configurable window; a request is either allowed or denied; and the accounting is computed lazily at request time using integer arithmetic so the behaviour is deterministic and reproducible in tests. Timestamps are supplied explicitly rather than read from a wall clock, making the whole system testable without mocking.

Which counting algorithm enforces that quota is the first design decision, not a requirement. Several schemes can do it and they differ sharply in memory and burst behavior. Before reading on, decide which one limits bursts without paying unbounded memory per client.

So the design uses a token bucket: each client holds tokens that refill at a steady rate, and a request is allowed only when a token is available to spend. The flowchart traces what that does on every request:

Core Entities

The token bucket is chosen, but one fork remains before the class list. The requirements still name sliding-window log and fixed-window counter as options a real system might switch to, so: should the counting algorithm be baked directly into the limiter, or sit behind an interface the limiter holds a reference to? Decide before reading on.

With that decided, the entity list is three things.

A RateLimitStrategy is the pluggable algorithm interface. It answers one question: "should this request be allowed, given the current timestamp?" The interface lets us swap token bucket for sliding-window log or fixed-window counter without touching the surrounding machinery.

A TokenBucket is a concrete strategy, and the mental model is worth building before the code. Picture a bucket that holds up to capacity tokens. Every request takes one token out; if the bucket is empty, the request is denied. Tokens are added back at a steady rate — capacity tokens over each window of time — filling only up to the brim. So capacity is the size of the burst you tolerate and window is how long a fully drained bucket takes to refill. With capacity = 10 and window = 60s, a client can fire 10 requests at once, then about one more every 6 seconds as tokens trickle back.

Refill is lazy. Rather than a background timer adding tokens every few milliseconds — which would burn CPU on idle clients and want a thread per bucket — the bucket adds nothing until a request actually arrives. At that moment it asks "how many tokens would have refilled since I last looked?" and adds them in one step. Same arithmetic, computed only when it matters; the last_refill timestamp is the "when I last looked" marker.

That count of would-be tokens is refill = floor(elapsed * capacity / window). The refill rate is capacity / window tokens per unit of time, so over elapsed units the bucket has earned elapsed * capacity / window of them; floor rounds down because you cannot add a fraction of a token. With capacity = 10, window = 60 seconds, and elapsed = 18 seconds, that is floor(18 * 10 / 60) = floor(3) = 3 tokens. That floor is also where the accounting gets subtle.

So when the refill would fill the bucket (tokens + refill >= capacity), tokens are set to capacity and last_refill is snapped to the current timestamp, discarding idle overflow time. Otherwise tokens are added and last_refill advances by floor(refill * window / capacity), so the fractional remainder carries forward and avoids drift.

The limiter has to enforce the quota separately for each client. That raises one more structural question before the orchestrator takes shape.

A RateLimiter is the orchestrator. It owns a dictionary mapping client strings to their per-client bucket. When a request arrives, it looks up or creates the bucket and delegates to the strategy. This is the one object the outside world talks to.

The entities-overview diagram shows how the three objects are connected at runtime:

Designing the Classes

With the entities settled, the next job is to derive each class's state and behavior directly from the requirements — no fields added because they "seem natural," only fields demanded by a specific requirement. The guiding principle is Tell, Don't Ask: each class enforces its own rules internally rather than exposing raw data for callers to manipulate.

RateLimitStrategy

State: none. The interface carries no data — it is a pure behavioral contract.

Behavior: one method, allow(timestamp: int) -> bool. The timestamp is passed in rather than read from a wall clock so every concrete strategy is independently testable without mocking time. The return value is a boolean; the caller decides what string to return to the user, keeping the strategy focused entirely on the allow/deny decision.

TokenBucket

The requirements specify a token bucket with a configurable capacity and refill window. Refill is lazy and uses integer arithmetic. These three sentences determine the state entirely.

State: _capacity (the ceiling — tokens never exceed this), _window (the number of time units for a full refill), _tokens (the current count, decremented on each allowed request), and _last_refill (the timestamp of the last refill event). A new bucket starts at capacity tokens with _last_refill set to the client's first-request timestamp — not to zero — so no free refill is awarded on arrival.

Behavior: allow(timestamp: int) -> bool. This single method does three things in order: compute how many tokens to add, update the token count and pointer, then consume one token if any remain. The critical design decision is the integer refill math:

refill = floor(elapsed * capacity / window)

This avoids floats entirely. elapsed * capacity is computed first (integer multiplication), then divided by window with floor division. The result is exact and deterministic across all runtimes. The bucket then branches on whether the refill would fill it. If tokens + refill >= capacity, tokens are set to capacity and _last_refill is snapped to timestamp — discarding idle overflow time. This prevents a long idle gap followed by many same-timestamp requests from each re-triggering a refill and granting more than capacity allows in total; after snapping, every subsequent same-timestamp call sees elapsed = 0 and adds nothing. If the refill only partially fills the bucket, tokens are added and _last_refill advances by floor(refill * window / capacity) — exactly the wall-time consumed by the tokens just added — preserving the fractional remainder for the next call.

RateLimiter

The requirements say the limiter is keyed per client. Each client gets an independent bucket with the same capacity and window. These requirements determine the state: _capacity and _window (held so new buckets can be constructed on demand) and _buckets (a dictionary from client string to RateLimitStrategy).

Behavior: request(client: str, timestamp: int) -> str. The method looks up the client in _buckets; if the client is new, it creates a fresh TokenBucket with the client's first timestamp as start. It then delegates to bucket.allow(timestamp) and returns "allow" or "deny". The method never touches token counts directly — that is Tell, Don't Ask in action. RateLimiter tells the bucket "decide this request," and the bucket decides.

Note that _buckets is typed as dict[str, RateLimitStrategy] — the orchestrator knows only the interface, not the concrete class. Swapping TokenBucket for a SlidingWindowLog requires no change to RateLimiter.

Reading the diagram: the RateLimiter holds a map of RateLimitStrategy instances — each a TokenBucket at runtime, one per client. The map is keyed on the client string and created lazily on first request. The public surface the outside world touches is just rate_limiter(capacity, window, instructions) — a single entry point that replays a command stream. Everything else is private.

Try It Yourself

Before reading the implementation, build it. Implement a function rate_limiter(capacity, window, instructions) that replays a sequence of commands and returns one result string per request.

Parameters:

capacity is the maximum number of tokens in each client's bucket (also the initial fill level). window is the number of time units required for a full refill. The refill rate is capacity / window tokens per time unit, computed with integer math: refill = floor(elapsed * capacity / window). If tokens + refill >= capacity, tokens are set to capacity and last_refill is snapped to timestamp (discarding idle overflow time, so a long idle gap followed by many same-timestamp requests yields exactly capacity allows). Otherwise, last_refill advances by floor(refill * window / capacity), preserving the fractional remainder.

Commands:

Each instruction is a list of strings. The only command is ["request", client, timestamp]: at integer time timestamp, attempt to spend 1 token for client. Timestamps are non-decreasing. For each request, append "allow" if a token was available, or "deny" otherwise.

A new client's bucket starts full at capacity tokens, with last_refill set to the timestamp of their first request (not to zero), so no free refill is awarded on arrival.

Run your solution against the test cases. The reference implementation follows below.

Code Walkthrough

The design is three small classes. Each section below walks through the implementation in the same order as the class design: interface first, then the concrete strategy, then the orchestrator, then the entry function.

Full Solution

Run and Test

The exercise drives the design through a command stream so it can be checked deterministically. The input supplies an explicit timestamp with every request rather than reading a wall clock, which means the same input always produces the same output — no time.sleep, no mocking.

The sequence diagram below traces a single request call through all three objects:

Trace test 2 to see the contract. Capacity is 3, window is 10 (so 3 tokens refill over 10 time units, meaning 1 token per 10/3 ≈ 3.33 units in float terms, but in integer math floor(elapsed * 3 / 10)).

Requests at t=0: the bucket starts full at 3 tokens.

request alice 0  → allow (tokens: 3→2)
request alice 0  → allow (tokens: 2→1)
request alice 0  → allow (tokens: 1→0)
request alice 0  → deny  (tokens: 0, elapsed=0, refill=0)

At t=10: elapsed = 10, refill = (10 * 3) // 10 = 3. Since tokens + refill = 0 + 3 >= 3 (capacity), the full-bucket branch runs: tokens = 3, last_refill snapped to 10.

request alice 10 → allow (tokens: 3→2)
request alice 10 → allow (tokens: 2→1)
request alice 10 → allow (tokens: 1→0)
request alice 10 → deny  (tokens: 0, elapsed=0, refill=0)

The other tests cover two independent clients (test 3, whose buckets are completely separate), a sub-window partial refill at t=2 in a capacity-2/window-4 configuration (test 4), capacity-1 strict one-at-a-time enforcement (test 5), and a 1-token-per-unit partial refill at t=1 in a capacity-5/window-5 configuration (test 6).

Concurrency and Thread Safety

In production, a rate limiter sits in the request path of a multi-threaded server. Many goroutines or threads evaluate the same client's bucket at the same time. The read-check-decrement sequence inside allow is not atomic, which creates a race on the last token.

Suppose Alice's bucket holds exactly 1 token and two threads arrive simultaneously:

Both threads see tokens = 1, both pass the check, and both decrement. The limiter allows two requests where only one should have been permitted. This is the classic lost-update race.

The fix is a per-client lock guarding the read-check-decrement sequence. The RateLimiter acquires the bucket's lock before calling allow and releases it after:

Thread 2 now sees the post-decrement state and correctly returns deny.

The critical design choice is where to place the lock. A single global lock on the RateLimiter is simple but serialises all clients: Alice's request blocks Bob's even though their buckets are completely independent. The right level is one lock per client — but a per-bucket lock alone is not enough, because the bucket itself is created on the first request and that creation is its own race. If two first requests for a new client both find no bucket, both create a full one, and both allow, the later map write hides one of them and a decrement is lost. The fix has two levels: make get-or-create atomic, then lock the bucket. In Java, ConcurrentHashMap.computeIfAbsent does both — it creates the bucket exactly once under the map's bin lock, and each bucket carries a ReentrantLock for the refill-and-decrement. In Python, hold a limiter-level lock (or a striped lock keyed on the client, below) just long enough to get-or-create the bucket, then acquire that bucket's threading.Lock for allow.

For very high client counts — millions of distinct keys — even per-client locks can be heavy if kept as live objects. Lock striping bounds memory: allocate a fixed pool of N locks (typically 128 or 256) and assign each client to a stripe via hash(client_key) % N. The pool size is constant regardless of client count, and contention is low because clients spread across stripes. Two clients can share a lock only by hash collision, and the critical section (a few integer operations) is short enough that the wait is negligible. This is the same idea used in ConcurrentHashMap's internal segment design.

The deterministic exercise above sidesteps concurrency entirely — timestamps are caller-supplied and commands are sequential — which is the right choice for a testable interface. In a real deployment, timestamps come from time.monotonic() or System.nanoTime() inside the lock, so the refill math and the consume step are always atomic with respect to each other.

Extensions

Every extension is a new concrete class behind the same interface — RateLimiter never changes:

A sliding-window log records the exact timestamp of every request in a deque. On each check, entries older than the window are evicted, then the remainder is counted. If the count is below the limit, the new timestamp is recorded and the request is allowed. This gives exact per-second semantics with no burst at window boundaries, at the cost of O(limit) memory per client. Implementing it as a second RateLimitStrategy concrete class requires zero changes to RateLimiter.

A fixed-window counter divides time into fixed buckets (per second, per minute) and keeps a counter per bucket. It uses O(1) state and is easy to implement in Redis with INCR and a TTL. The trade-off is a burst at window boundaries: a client can send limit requests at the end of one window and limit more at the start of the next, doubling the effective rate for one instant.

Distributed rate limiting replaces the in-process state with Redis so multiple server instances share the same quota per client. The simplest approach is a Redis fixed-window counter: each allow call increments a key scoped to the client and the current time window (INCRBY), rejects the request if the count exceeds the limit, and sets a TTL on the key so it expires at window end. This is a different algorithm from the in-memory token bucket above — it counts requests in a fixed window rather than tracking a token count and a last-refill timestamp. A true distributed token bucket requires an atomic Lua script that reads the stored token count and last-refill timestamp, computes the refill, decrements, and writes back — all in one server-side operation. The RateLimitStrategy interface absorbs either choice: a RedisFixedWindowCounter implements the same allow method, routing to Redis instead of an in-memory counter.

Per-tier limits add a second dimension: different client tiers (free, pro, enterprise) get different capacities and windows. The RateLimiter looks up the tier at client-creation time and constructs the bucket with tier-appropriate parameters. The strategy interface is unchanged.

Each extension lands by adding a class or swapping an implementation, never by rewriting the RateLimiter.

Quiz

Test your understanding of the key design decisions in this rate limiter.