Design a distributed rate limiter

A service that limits how many requests each client can make, enforced consistently across many API servers.

Why interviewers ask it

It tests algorithms (token bucket and windows), shared state across servers, atomic updates and failure handling, all in one small system.

Functional requirements

Non-functional requirements

From version 1 to the final design

  1. Version 1: an in-memory counter per user on one server.
  2. Version 2: many servers, so the counters move to Redis.
  3. Version 3: atomic updates with a Lua script, a token bucket for bursts, and rules from configuration.
  4. Version 4: several regions, a fail-open fallback, and monitoring of rejected requests.

The design, step by step

  1. The limiter runs as middleware in the API gateway.
  2. Rules are loaded from a config store and cached locally.
  3. Counters live in a Redis cluster and are checked and updated atomically with a Lua script (or INCR plus EXPIRE for fixed windows).
  4. Over the limit → 429 with Retry-After.

Deep dives

Common mistakes

Not true: Shared counter: read it, add one and write it back as separate steps; that works across servers.
In fact: Two servers can read the same value and both let a request through, so the limit is passed. Use one atomic operation, such as Redis INCR or a Lua script.

In the interview

I'd enforce limits in the API gateway using a token bucket per client and rule, with state in a Redis cluster updated atomically by a Lua script, adding about a millisecond. Rules come from configuration. Requests over the limit get 429 with Retry-After. If Redis is unavailable, the gateway fails open with a local backup limit.

Part of Unit 8: High-level design questions in the free System Design course.