Design a distributed rate limiter

“Design a rate limiter for our public API. Each API key gets a limit, and we run hundreds of gateway servers.”

On one machine, a rate limiter is simple. You keep a counter for each client in memory, and the low level design builds that class. The distributed version is harder, and the algorithm is the easy part. The real questions are about everything around it. Where does the count live, when 330 servers each see a slice of a client’s traffic? How do two servers avoid spending the same last request? And what happens when the counter store goes down?

This page answers those questions in order. We start with a bucket in one gateway’s memory, and let the numbers break it. Then we test the finished design where sharing is hardest: the choice of algorithm, an outage, and three regions.

The framework

1. 01Answer
2. 02Scope
3. 03Numbers
4. 04Build
5. 05Stress
6. 06Failures
7. 07Wrap up

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains each part.

1. Each client gets a token bucket. Think of a bucket that fills with tokens at a steady rate, up to a maximum. Each request takes one token. No token, no request: the client gets 429 Too Many Requests.
2. The buckets live in Redis, shared by all gateways. One small script checks and takes a token in a single step, so two gateways can never spend the same token.
3. Redis is split into 32 shards by API key. All the buckets of one key sit on one shard, so one call checks every rule for a request.
4. Busy clients take tokens in batches. A gateway takes, say, 33 tokens at once and spends them from memory. This cuts Redis calls about ten times, and it can only under-count, never over-count.
5. If Redis is down, each gateway limits on its own, roughly. The API stays up. Only a few security rules, like login attempts, refuse instead.

Scope it

A few questions change this design a lot. The answers are the assumptions the rest of the page builds on.

Interviewerminute 0

Design a rate limiter for our public API. Hundreds of gateway servers, each API key has a limit.

What they are testing

Whether you ask who is limited, how exact the limit must be, and what happens when the limiter breaks.

These four questions matter most:

• Who is limited? Each API key. Requests without a key are limited by IP address, so a flood of bad logins can’t reach the login service at full speed.
• How much traffic? 400,000 requests a second on average, and 1,000,000 at peak. At 10,000 a second, one Redis server would do everything.
• How exact must a limit be? A client may get at most about 1% more than its limit. Being held a little under for a moment is fine. If limits were billed, we’d need a slower, exact design.
• What if the limiter itself breaks? The API must stay up. Most limits become approximate. Security limits refuse instead.

That last question usually decides more of the design than the algorithm does.

Limits are written as a rate with a burst, such as “100 a second, with bursts of 200”. A key can have several rules at once, like that plus “5,000 a minute”. A request passes only if every rule allows it.

From these answers we make four promises:

• The limiter is fast. It adds under 1 ms to a normal request, and under 2 ms for 99% of them.
• The limiter never takes the API down. If Redis breaks, good traffic still flows.
• Limits are close. In normal running, a client gets at most about 1% over its limit.
• Rule changes are quick. A new limit reaches every gateway within 10 seconds.

We leave out network floods (DDoS), billed monthly quotas, and protecting backends from overload. That last one is a different tool, which we come back to at the end.

Go deeperMore questions, and what each changes1 min

Question	We assume	If the answer were different
What shape are the limits?	A rate with a burst, plus a per-minute cap	Only “N per hour” with no bursts would make a sliding window counter natural
Global or per region?	Global per key; the API runs in three regions	Per-region limits remove the regions step entirely
Internal traffic too?	No, only the public API	Service-to-service limits move the check into a proxy next to each service
Counts must survive?	No. Losing them gives each client one burst	Billed counts need durable storage, and that’s slower

Clients also need to be told. A refused request gets 429 with Retry-After, and every response carries the remaining budget. Operators can change rules live, and can try a new rule in shadow mode first: it logs what it would refuse, without refusing anything.

The numbers that decide it

Now we work out how big this is. Each number should lead to a decision.

Assumptions

API requests a second at peak

1 million

Requests a second one gateway node handles

5,000

Share of requests that call Redis

100%

Limiter scripts a second per Redis shard

50,000

API keys active in an hour

1 million

Typical limit, requests a minute

1,000

Gateways330gateway nodes at peak

One gateway handles about 5,000 requests a second. At the 1,000,000 a second peak, kept about 60% busy, that’s about 330 gateways.

So we limits can't live in gateway memory. Each gateway sees only about 1/330 of a client's traffic.

Redis calls1M/sat peak

If one script checks all of a request’s rules, that’s 1,000,000 calls a second at peak. One Redis server runs about 50,000 short scripts a second safely, because Redis runs one command at a time.

So we split the counters across shards from day one: about 20 at peak, and 32 for room to grow.

Memory200 MBtoken buckets

About 1 million API keys are active in any hour. A token bucket is two numbers, about 100 bytes in Redis. Two buckets per key is 200 MB in total.

So we memory doesn't matter. Every decision is about calls per second.

Latency0.2–1 msper Redis round trip

A Redis call takes 0.2 to 0.5 ms inside one data centre, and about 1 ms across data centres in a region.

So we we can afford exactly one Redis call per request. Checking and taking must be one command, never a read followed by a write.

You can change the numbers in the calculator. At 10 times the traffic, with every request calling Redis, we’d need 200 shards. If only 10% of requests call Redis, which batches of tokens achieve, it’s back to 20.

Change an assumptionReset to the page's numbers

API requests a second at peak

1 million

Requests a second one gateway node handles

5,000

Share of requests that call Redis

100%

Limiter scripts a second per Redis shard

50,000

API keys active in an hour

1 million

Typical limit, requests a minute

1,000

Gateway nodes at 60% busy

330

Hundreds of nodes behind a round-robin balancer: a limit kept in each node is meaningless, so counters must be shared.

Redis script calls a second

1,000,000/s

Redis shards for the counters

20

More than one node: shard the counters by API key with a hash tag (stage 3).

Token bucket memory (2 rules a key)

200 MB

About 100 bytes a bucket. Memory never forces sharding; throughput does.

Sliding window log memory

80 GB

Too big for what it buys: use a sliding window counter or a token bucket, at about 100 bytes a key.

Limiter traffic to Redis

250 MB/s

About 250 bytes per call, request and reply. Not a design driver.

Build the design

We start with the simplest design that works. Then we let the numbers break it, one at a time. Each step fixes only what broke, adds only the boxes that fix needs, and says what the fix costs.

Step 1. A bucket in one gateway’s memory

The simplest limiter lives inside the API gateway. The gateway keeps one token bucket per API key in its own memory, and checks it before the request goes anywhere else. On one gateway this is exact and costs almost nothing.

Distributed rate limiter · architecture

Stage 1: One gateway, buckets in memory

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasional

API requests per second:

1,000,000

400k average1M peak10M (10×)30M

Stage 1 of 6

One gateway, buckets in memory

Why this stage

Nothing yet.

This is the smallest design that enforces a limit per API key.

What we add

An API gateway that checks a token bucket per API key in its own memory before forwarding to the API services.

What it costs

One node carries every request, and its buckets die with it.

At 1M api requests per second, API gateways is 20000% busy. Stage 2 is the fix.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

• One gateway node handles about 5,000 requests a second, with TLS, auth and the limit check. The fleet runs near 60% busy.
• One Redis primary runs about 50,000 short Lua scripts a second at a safe level. Redis runs commands on one thread, so a script blocks its shard while it runs.

Calls to Redis

• Until stage 5, every request is one script call.
• With leases, only about 10% of requests reach Redis, because most traffic comes from a few busy keys.

Where does the check run? In the API gateway, as a small filter. The gateway already knows the API key and the route, which is all a limit needs. And a refused request then costs nothing behind the gateway.

Why this breaks. We have 330 gateways, not one. If each of them kept its own bucket, a client spread across all of them would get 330 times its limit. Dividing the limit by 330 fails the other way. A key allowed 100 a second would get 0.3 a second on each gateway, so a small burst landing on one gateway is refused.

So the count must be shared by every gateway.

Go deeperOther places the check could run1 min

Option	How it works	Good	Bad
Library in each service	Each backend checks the shared store	Limits can use business data	Every team ships it; a refusal has already cost a backend hop
Proxy next to each service	A small proxy beside each service checks first	Any language; fits internal traffic	Thousands of proxies hold store connections
Gateway filter	The gateway checks before routing, straight to Redis	Refusals stop at the edge; one place	Limits that need business data are awkward
Separate limiter service	Gateways call a limiter service, which calls Redis	Central logic, fewer Redis connections	A second network hop on every request

A separate limiter service is Envoy’s model. It suits many different proxies sharing limits, but it doubles the network hops. With 330 gateways and 2 connections each, Redis only sees 660 clients per shard, which is fine.

Step 2. Shared counters in Redis

So the buckets move to Redis, a fast in-memory store that every gateway can reach.

Distributed rate limiter · architecture

Stage 2: Shared counters

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasional

Play

PreviousNext

Stage

12

API requests per second:

1,000,000

400k average1M peak10M (10×)30M

Stage 2 of 6

Shared counters

Why this stage

One gateway tops out near 5,000 requests a second and the peak is 1,000,000, so about 330 gateways.

Buckets in each gateway would give every client 330 times its limit.

What we add

A load balancer, a fleet of stateless gateways, and one Redis holding every bucket.

A Lua script refills, checks and takes in one atomic step.

What it costs

A network round trip on every request, and one Redis node that every request depends on.

At 1M api requests per second, Redis Cluster is 2000% busy. Stage 3 is the fix.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

• One gateway node handles about 5,000 requests a second, with TLS, auth and the limit check. The fleet runs near 60% busy.
• One Redis primary runs about 50,000 short Lua scripts a second at a safe level. Redis runs commands on one thread, so a script blocks its shard while it runs.

Calls to Redis

• Until stage 5, every request is one script call.
• With leases, only about 10% of requests reach Redis, because most traffic comes from a few busy keys.

Sharing a counter brings a race. Say a gateway reads the bucket, decides, and writes it back. In the gap between the read and the write, another gateway reads the same value. Both see one token left, and both let a request through:

Two gateways spend the last token, and the fix

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Cache

The fix is a Lua script that runs inside Redis. Redis runs a script from start to finish before any other command (Redis docs). So the read and the write can’t be split. The script does three things in one step:

1. Refill the bucket from the time passed since its last use.
2. Check that every rule for this key has a token.
3. Take a token from every rule, or from none.

“All or none” matters. If the per-second rule refuses a request, the request shouldn’t use up the per-minute budget too. The script also reads Redis’s own clock, so 330 gateway clocks that drift apart can’t refill a bucket early.

JRedisLimiter.javaPyscript_runner.pyC#RedisLimiter.csGoscript_runner.goTSscript-runner.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// One rule of a plan, for example "100 a second, bursts of 200" or "5,000 a minute".
record Rule(String name, double ratePerSec, double burst) {}

// What the gateway needs to answer: allow or 429, and the numbers for the RateLimit headers.
record Decision(boolean allowed, long remaining, long retryAfterMs) {}

// The Redis client. Production loads the script once and calls EVALSHA with the digest, so
// each check sends a 40 byte hash instead of the whole script.
interface ScriptRunner {
    List<Long> eval(String script, List<String> keys, List<String> args);
}

final class RedisLimiter {
    // Every bucket of a request is refilled, checked and taken inside ONE script. Redis runs a
    // script to completion before any other command, so two gateways can never both read
    // "1 token left" and both take it. That race is the whole reason this is a script.
    static final String TAKE = """
        local t = redis.call('TIME')  -- Redis's clock, not the gateway's: 300 clocks drift
        local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)
        local want = tonumber(ARGV[1])
        local level, grant = {}, want
        for i, key in ipairs(KEYS) do
          local rate, burst = tonumber(ARGV[2 * i]), tonumber(ARGV[2 * i + 1])
          local s = redis.call('HMGET', key, 'tokens', 'ts')
          local tokens = tonumber(s[1]) or burst          -- a new key starts full
          local elapsed = math.max(0, now - (tonumber(s[2]) or now))
          level[i] = math.min(burst, tokens + elapsed * rate / 1000)  -- lazy refill
          grant = math.min(grant, math.floor(level[i]))
        end
        if grant < 1 then                                 -- all or nothing: a refused
          local wait = 0                                  -- request takes from no bucket
          for i = 1, #KEYS do
            local rate = tonumber(ARGV[2 * i])
            wait = math.max(wait, math.ceil((1 - level[i]) * 1000 / rate))
          end
          return {0, 0, wait}
        end
        local left = math.huge
        for i, key in ipairs(KEYS) do
          local rate, burst = tonumber(ARGV[2 * i]), tonumber(ARGV[2 * i + 1])
          redis.call('HSET', key, 'tokens', level[i] - grant, 'ts', now)
          -- A bucket idle long enough to be full is the same as no bucket: let it expire.
          redis.call('PEXPIRE', key, math.ceil(burst * 1000 / rate) + 1000)
          left = math.min(left, level[i] - grant)
        end
        return {grant, math.floor(left), 0}
        """;

    private final ScriptRunner redis;

    RedisLimiter(ScriptRunner redis) { this.redis = redis; }

    Decision check(String apiKey, List<Rule> rules) {
        // The {hash tag} puts every bucket of one key in the same cluster slot, so one script
        // on one shard sees them all. Without it, Redis Cluster refuses a multi-key script.
        List<String> keys = new ArrayList<>();
        List<String> args = new ArrayList<>(List.of("1"));   // want one token
        for (Rule r : rules) {
            keys.add("rl:{" + apiKey + "}:" + r.name());
            args.add(Double.toString(r.ratePerSec()));
            args.add(Double.toString(r.burst()));
        }
        List<Long> out = redis.eval(TAKE, keys, args);       // one round trip, about 0.5 ms
        return new Decision(out.get(0) > 0, out.get(1), out.get(2));
    }
}

Each bucket is a tiny Redis record with two numbers: how many tokens are left, and when it was last used. Nothing runs in the background to refill buckets. Each check works out the refill from the time that has passed. So an idle bucket can simply be deleted when it would be full again.

rl:{key_8f3}:s   ->  { tokens: 141.4, ts: 1793142622215 }    per-second rule
rl:{key_8f3}:m   ->  { tokens: 4210.0, ts: 1793142622215 }   per-minute rule

The client sees the result in headers on every response, and a refused request gets 429 with Retry-After, the number of seconds to wait:

429 Too Many Requests
Retry-After: 1
X-RateLimit-Limit: 200
X-RateLimit-Remaining: 0

Common mistake

Answering 503 or 403 when a client is over its limit

429 means “you, specifically, are sending too much”, so the client should slow down. 503 means “we are overloaded”, and the client did nothing wrong. 403 means “you may never do this”, so clients stop retrying for good. Mixing them breaks every client’s retry logic.

Step 3. Split Redis by API key

At peak, one Redis server would be 20 times over its limit. So the counters move to a Redis Cluster of 32 shards, each with a backup copy in another data centre.

The cluster decides which shard owns a key by hashing it. Here’s the trick: the part of the key in braces, {key_8f3}, is the only part hashed. So both buckets of one API key land on the same shard, and one script can check both.

Distributed rate limiter · architecture

Stage 3: Shard the counters

Grow itTrace a request

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasional

Play

PreviousNext

Stage

123

API requests per second:

1,000,000

400k average1M peak10M (10×)30M

Stage 3 of 6

Shard the counters

Why this stage

At the 1,000,000 a second peak one Redis node would be 20 times over its roughly 50,000 scripts a second.

What we add

A Redis Cluster of 32 primaries, each with a replica.

A hash tag on the API key keeps all of one key’s buckets on one shard, so one script still sees them all.

What it costs

Replication is asynchronous, so a failover can forget the last few milliseconds of counts.

One very busy key still lands on one shard.

At 1M api requests per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

• One gateway node handles about 5,000 requests a second, with TLS, auth and the limit check. The fleet runs near 60% busy.
• One Redis primary runs about 50,000 short Lua scripts a second at a safe level. Redis runs commands on one thread, so a script blocks its shard while it runs.

Calls to Redis

• Until stage 5, every request is one script call.
• With leases, only about 10% of requests reach Redis, because most traffic comes from a few busy keys.

Follow an allowed request and a refused one through the design:

Distributed rate limiter · architecture

Trace a request: Allowed request

Allowed requestOver the limit

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasionalHop in motionHops doneResponse

Play

PreviousNext

Allowed request: step 1 of 5

API clients to Load balancer

GET /v1/orders with an API key. The load balancer terminates TLS and picks any gateway: no stickiness, so the next request from this key can land anywhere.

1 ms of a 5 ms budget

1. API clients → Load balancer1 ms
2. Load balancer → API gateways0 ms
3. API gateways → Redis Cluster1 ms
4. API gateways → API services0 ms
5. Response

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Common mistake

Adding read replicas to Redis

Every check is a write, because it takes a token. Read replicas add nothing but out-of-date counts. Counters scale with shards. The replica is only there to take over if the main copy fails.

Go deeperSizing the cluster1 min

At peak, gateways make about a million script calls a second. One Redis server runs about 50,000 of these scripts a second while staying under half busy. That is why one server would be 20 times over. 32 shards give each one about 31,000 calls a second, with room for a busy hour.

Memory doesn’t matter here. Each bucket is two numbers, about 100 bytes with Redis’s own overhead. Ten million active keys with two rules each is about 2 GB across the whole cluster. Idle buckets expire on their own, so the total stays small.

Each shard has a backup copy in another data centre. If the main copy dies, the backup takes over in 10 to 20 seconds. The stress test on Redis going down covers what gateways do in those seconds. Gateways keep 2 open connections to each shard, so each shard sees about 660 clients, which Redis handles easily.

Step 4. Rules that change live

Support may need to raise one customer’s limit right now. On-call may need to clamp an abusive key within a minute. But rules must never be read from a database on every request.

So rules live in a database, and a rules service turns them into one snapshot: a single versioned file of every rule, a few MB. It pushes “version N is out” to every gateway. Each gateway loads the new snapshot and swaps to it in one step, so a request never sees half a rule set.

Distributed rate limiter · architecture

Stage 4: Rules that change live

Grow itTrace a request

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasional

Play

PreviousNext

Stage

1234

API requests per second:

1,000,000

400k average1M peak10M (10×)30M

Stage 4 of 6

Rules that change live

Why this stage

Not load: a requirement.

Plans change, support raises one customer’s limit, and on-call must clamp an abusive key within seconds, without a gateway deploy.

What we add

A rules database and a rules service that compiles rules into an immutable snapshot and pushes it to every gateway, which swaps it in atomically.

What it costs

For a few seconds after a change, gateways can disagree about a limit.

At 1M api requests per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

• One gateway node handles about 5,000 requests a second, with TLS, auth and the limit check. The fleet runs near 60% busy.
• One Redis primary runs about 50,000 short Lua scripts a second at a safe level. Redis runs commands on one thread, so a script blocks its shard while it runs.

Calls to Redis

• Until stage 5, every request is one script call.
• With leases, only about 10% of requests reach Redis, because most traffic comes from a few busy keys.

Three habits keep live rule changes safe. New rules start in shadow mode for a day. New snapshots go to 1% of gateways first. And every emergency override has an expiry date, so a forgotten clamp can’t quietly limit a customer for months.

This is enough for a mid-level answer. A token bucket per key, one atomic script in sharded Redis, and rules pushed to gateway memory. Step 5 and the stress tests are what make it a senior answer.

Go deeperThe rules table and admin API1 min

CREATE TABLE rules (
  id          BIGSERIAL PRIMARY KEY,
  scope       TEXT        NOT NULL,   -- 'plan', 'key', 'ip', 'endpoint'
  match       JSONB       NOT NULL,   -- {"plan":"pro","endpoint":"search"}
  limits      JSONB       NOT NULL,   -- [{"name":"s","rate":100,"per":"1s","burst":200}]
  mode        TEXT        NOT NULL,   -- 'enforce' or 'shadow'
  fail_mode   TEXT        NOT NULL,   -- 'open' or 'closed'
  expires_at  TIMESTAMPTZ,            -- emergency overrides always expire
  reason      TEXT        NOT NULL,
  version     BIGINT      NOT NULL
);

PUT /admin/v1/overrides/key_8f3
{ "limits": [ { "name": "s", "rate": 10, "per": "1s" } ],
  "expiresAt": "2026-10-28T09:00:00Z", "reason": "INC-4411: retry storm" }

When several rules match, the most specific wins: a key’s own override, then plan and endpoint, then plan, then the default. fail_mode is set per rule, because a login limit and an orders limit should behave differently when Redis is down.

Go deeperHow a bad rule is caught before it hurts1 min

A wrong rule can do as much damage as an outage. Set a limit ten times too low, and good customers get refused everywhere at once. So a new rule goes out in three stages.

1. Shadow mode. The rule is checked, but never enforced. Gateways log what it would have refused. After a day, someone reads that log. A rule that would have refused a big customer gets fixed before it is ever enforced.
2. 1% of gateways. The new snapshot goes to a few gateways first. If refusals jump there, the rollout stops on its own.
3. Everyone. Only then does every gateway load it.

Emergency overrides skip shadow mode, because they exist to act fast. That is exactly why each one must carry an expiry date and a reason.

Step 5. Token leases for very busy clients

One more number breaks the design. A big customer is allowed 100,000 requests a second, and every one of them lands on the single shard that owns its key. That shard can run about 50,000 scripts a second. So one busy client can slow down every other client on its shard.

The fix is token leases. Instead of asking Redis for one token per request, a gateway asks for a batch: its share of 100 ms of the limit. For the 100,000 a second customer on 300 gateways, that’s 33 tokens. It spends them from memory, and fetches the next batch in the background when half are gone. So a busy key almost never waits on Redis.

This changes which way the error goes. Tokens leave the bucket before they’re spent, so the gateways together can never let in more than the bucket allows. The error can only be under: if a gateway stops seeing the key, its unused tokens are lost. That’s at most about 100 ms of the limit, for a moment.

JLeasingLimiter.javaPyleasing_limiter.pyC#LeasingLimiter.csGoleasing_limiter.goTSleasing-limiter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// The stage 2 script with want > 1: take up to `want` tokens from Redis in one round trip.
interface TokenStore {
    Grant take(String key, int want);
}

record Grant(int granted, long retryAfterMs) {}

// Each gateway keeps a small lease of tokens per busy key and spends it from memory. Tokens are
// taken from Redis BEFORE they are spent, so the fleet can never admit more than the bucket
// holds. The price is the other way round: tokens stranded on a gateway that stops seeing the
// key are lost, so a client can be held a little under its limit, never over it.
final class LeasingLimiter {
    private static final long LEASE_TTL_MS = 1_000; // a lowered limit takes effect within a second

    private static final class Lease {
        int tokens;
        long expiresAt;
        long deniedUntil;   // negative cache: a client over its limit costs no Redis calls
        boolean refilling;
    }

    private final TokenStore store;
    private final LongSupplier clock;
    private final int gateways;                     // fleet size, from service discovery
    // Idle entries are evicted after a few seconds in production (not shown).
    private final Map<String, Lease> leases = new ConcurrentHashMap<>();

    LeasingLimiter(TokenStore store, LongSupplier clock, int gateways) {
        this.store = store;
        this.clock = clock;
        this.gateways = gateways;
    }

    // This gateway's share of 100 ms of the limit. A 100/s key on 300 gateways gets 1, which is
    // exactly the per-request check of stage 2, so quiet keys lose no accuracy at all.
    int batchFor(double ratePerSec) {
        return (int) Math.max(1, ratePerSec / gateways / 10);
    }

    boolean tryAcquire(String key, double ratePerSec) {
        Lease l = leases.computeIfAbsent(key, k -> new Lease());
        int batch = batchFor(ratePerSec);
        synchronized (l) {
            long now = clock.getAsLong();
            if (l.tokens > 0 && now < l.expiresAt) {
                l.tokens--;
                // Refill at half empty, off the request path, so a busy key never waits on Redis.
                if (l.tokens < batch / 2 && !l.refilling) refillInBackground(key, l, batch);
                return true;
            }
            // Leased tokens are already paid for, so only an empty lease checks the negative cache.
            if (now < l.deniedUntil) return false;
        }
        Grant g = store.take(key, batch);           // empty or expired: one round trip, as before
        synchronized (l) {
            long now = clock.getAsLong();
            if (g.granted() == 0) {
                l.deniedUntil = now + g.retryAfterMs();
                return false;
            }
            add(l, g.granted() - 1, now);           // one token is this request's
            return true;
        }
    }

    private void refillInBackground(String key, Lease l, int batch) {
        l.refilling = true;
        CompletableFuture.supplyAsync(() -> store.take(key, batch)).whenComplete((g, err) -> {
            synchronized (l) {
                l.refilling = false;
                // On an error, spend what is left; the blocking path and its fallback take over.
                if (err == null && g.granted() > 0) add(l, g.granted(), clock.getAsLong());
            }
        });
    }

    private static void add(Lease l, int tokens, long now) {
        if (now >= l.expiresAt) l.tokens = 0;       // expired tokens are dropped, never revived
        l.tokens += tokens;
        l.expiresAt = now + LEASE_TTL_MS;
    }
}

Quiet keys stay exact for free. A key allowed 100 a second gets a batch of 1 on 300 gateways, which is the normal per-request check. Most API traffic comes from a few busy keys. So with leases, only about 10% of requests still call Redis one by one.

Distributed rate limiter · architecture

Stage 5: Local token leases

Grow itTrace a request

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasional

Play

PreviousNext

Stage

12345

API requests per second:

1,000,000

400k average1M peak10M (10×)30M

Stage 5 of 6

Local token leases

Why this stage

At 10 times the traffic, 10,000,000 scripts a second would need about 200 shards, and one tenant at 100,000 a second already overloads its shard today.

What we add

Gateways lease small batches of tokens for busy keys and spend them from memory, and cache "denied until" for keys that are over their limit.

What it costs

Tokens stranded on a gateway are lost, so a busy client can sit a few percent under its limit for a moment.

Never over.

At 1M api requests per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

• One gateway node handles about 5,000 requests a second, with TLS, auth and the limit check. The fleet runs near 60% busy.
• One Redis primary runs about 50,000 short Lua scripts a second at a safe level. Redis runs commands on one thread, so a script blocks its shard while it runs.

Calls to Redis

• Until stage 5, every request is one script call.
• With leases, only about 10% of requests reach Redis, because most traffic comes from a few busy keys.

Go deeperFollow a lease through the design, and other options2 min

Distributed rate limiter · architecture

Trace a request: Busy key, leased tokens

Allowed requestOver the limitBusy key, leased tokens

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasionalHop in motionHops doneResponse

Play

PreviousNext

Busy key, leased tokens: step 1 of 5

API clients to Load balancer

A large tenant sending 100,000 requests a second, about 300 a second on each gateway.

1 ms of a 5 ms budget

1. API clients → Load balancer1 ms
2. Load balancer → API gateways0 ms
3. API gateways → Redis Clusterasync
4. API gateways → API services0 ms
5. Response

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

Approach	How it works	Error	Redis calls
Check every request	The core design	Exact	1 per request
Count locally, sync every 100 ms	Each gateway counts, adds its count to Redis, reads the total	Over: up to 100 ms at the client’s full rate	10 a second per gateway per key
Token leases	Take a batch in advance, spend it from memory	Under, never over	About 10 a second per gateway per key
Split the bucket	k smaller buckets, each with 1/k of the limit, on k shards	Under when traffic is uneven	1 per request, spread out

With leases, the 100,000 a second customer costs its shard about 3,000 calls a second, not 100,000.

Per-IP limits have their own hot keys. Thousands of users behind one office or mobile network share an IP address. So per-IP limits are generous, and only stop floods. With IPv6, one person controls billions of addresses, so we limit by the address prefix, not the full address.

Stress it

The design is complete. Now we test it in the four places a limiter is known to struggle: the choice of algorithm, one very busy client, Redis going down, and one limit across three regions. Only the last one adds a new box.

Choosing the algorithm

Interviewerminute 20

Why a token bucket? Compare it to the alternatives, with numbers.

What they are testing

Whether you know what each algorithm gets wrong and what it costs per key.

There are four common algorithms:

Algorithm	What it stores per key	Memory, 1M keys at 1,000/min	Accuracy	Bursts
Fixed window	1 counter	about 70 MB	Up to 2 times the limit at a window boundary	Uncontrolled at the boundary
Sliding window log	The time of every recent request	about 80 GB	Exact	Exactly the limit in any window
Sliding window counter	2 counters	about 140 MB	Close; assumes last window was spread evenly	Smoothed
Token bucket	2 numbers	about 100 MB	Exact for “rate r, burst b”	Up to b at once, then r a second

A fixed window counts requests per calendar minute. Its flaw is the boundary. 100 requests at 12:00:59 and 100 more at 12:01:00 is twice the limit in two seconds. A sliding window log is exact, but it stores every request’s time: 80 GB here. A sliding window counter keeps this minute’s and last minute’s counts, and estimates the rolling total. Cloudflare measured it on 400 million requests, and only 0.003% got the wrong answer (Cloudflare).

We pick the token bucket, because our plans are written as “a rate with a burst”, and that’s exactly what a bucket enforces. A refusal also says exactly when the next token arrives, which is the Retry-After value. And an expensive request can simply take more tokens.

Common mistake

"A leaky bucket is just a token bucket"

There are two leaky buckets. As a meter, it’s a token bucket upside down, and behaves the same. As a queue, it holds requests and lets them out at a fixed rate. That adds waiting instead of refusing. It’s useful in front of a fragile service, and wrong for an API that should answer 429 at once.

Go deeperWhat a token bucket really promises1 min

We use a token bucket for the per-minute rule too: 83 tokens a second, with a maximum of 5,000. So one script handles both rules. But know what that means. A bucket enforces a steady rate, not a count per calendar window. A key that was idle for a minute can spend 5,000 at once, then more as the bucket refills. So its busiest 60 seconds can see about twice the stated number.

That’s the intended meaning of “a rate with a burst”. When a rule must mean “at most N in any window”, or users expect a reset time like “your hour resets at 14:00”, use a sliding window counter instead. The same script can hold one.

A related algorithm, GCRA, stores just one timestamp per key and behaves the same as a token bucket. It’s what the redis-cell module uses.

One very busy client

Now a different busy client: a broken retry loop sending 300,000 requests a second against a limit of 1,000. Over 99% of its requests are refused. But each refusal is still a script call on its shard, so a client we refuse can still slow down everyone else on that shard. On a CPU graph it looks just like a big customer within its limit.

Leases don’t help here, because there are almost no tokens to hand out. The fix is a refusal cache. When Redis answers “no tokens, retry in 120 ms”, the gateway refuses that key from memory until then, without asking again.

A gateway spends a lease, refills it, then caches a refusal

Scroll or pinch to zoom, drag to pan

• Color key
• Cache
• Service

With the refusal cache, the broken retry loop costs its shard about 3,000 to 6,000 calls a second, not 300,000. It only asks Redis again when its retry time is up.

When Redis is down

Now a Redis shard stops answering. Do we let everything through, or refuse everything?

There are two simple answers, and both are wrong on their own:

• Refuse everything (“fail closed”). Now the limiter is the outage. One shard down means one in 32 customers can’t use the API.
• Let everything through (“fail open”). A runaway client can overload the backends for the 10 to 20 seconds it takes a backup to take over.

We do something in between. Each Redis call gets a 5 ms time limit. After 5 failures in a row, a circuit breaker stops calling that shard for 2 seconds, so gateways stop waiting on it. Meanwhile, each gateway enforces the rule on its own, at its share of the limit, times 2 for uneven traffic. A runaway client stays capped at about twice its limit, and normal clients are rarely refused.

A shard fails: timeout, breaker, local limits, recovery

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Cache

JGuardedLimiter.javaPyguarded_limiter.pyC#GuardedLimiter.csGoguarded_limiter.goTSguarded-limiter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// A rule as in stage 2, plus what it does when Redis cannot answer.
record Rule(String name, double ratePerSec, double burst, boolean failClosed) {}

// The stage 2 check, with a 5 ms client timeout. It throws when Redis is slow or down.
interface RemoteLimiter {
    boolean tryAcquire(String key, Rule rule) throws Exception;
}

// The single-node token bucket from the low level design, kept in the gateway's memory.
interface LocalLimiter {
    boolean tryAcquire(String key, double ratePerSec, double burst);
}

// Wraps the Redis check so a counter outage degrades the limits instead of the API.
final class GuardedLimiter {
    private static final int TRIP_AFTER = 5;      // consecutive failures before the breaker opens
    private static final long OPEN_MS = 2_000;    // then Redis is tried again
    private static final double SLACK = 2.0;      // traffic is never spread perfectly evenly

    private final RemoteLimiter remote;
    private final LocalLimiter local;
    private final LongSupplier clock;
    private final int gateways;                   // fleet size, from service discovery
    // One breaker per Redis shard in production, so one bad shard degrades only its keys.
    private final AtomicInteger failures = new AtomicInteger();
    private volatile long openUntil;

    GuardedLimiter(RemoteLimiter remote, LocalLimiter local, LongSupplier clock, int gateways) {
        this.remote = remote;
        this.local = local;
        this.clock = clock;
        this.gateways = gateways;
    }

    boolean tryAcquire(String key, Rule rule) {
        long now = clock.getAsLong();
        // While the breaker is open, skip Redis: paying a 5 ms timeout on every request would
        // turn a counter outage into a latency outage for the whole API.
        if (now < openUntil) return degraded(key, rule);
        try {
            boolean allowed = remote.tryAcquire(key, rule);
            failures.set(0);
            return allowed;
        } catch (Exception e) {
            if (failures.incrementAndGet() >= TRIP_AFTER) {
                openUntil = now + OPEN_MS;
                failures.set(0);
            }
            return degraded(key, rule);
        }
    }

    private boolean degraded(String key, Rule rule) {
        // Login attempts, OTP and SMS sends: an outage must not become a brute-force window.
        if (rule.failClosed()) return false;
        // Behind a round-robin balancer each gateway sees about 1/N of a key's traffic, so it
        // enforces 1/N of the limit, with slack, in one local bucket per key and rule.
        double share = SLACK / gateways;
        return local.tryAcquire(
                key + ":" + rule.name(), rule.ratePerSec() * share, Math.max(1, rule.burst() * share));
    }
}

A few rules are the security control itself: login attempts, password resets, and text messages that cost money to send. Letting those through during an outage invites password guessing or fraud. So these rules refuse instead. That’s why fail_mode is set per rule, not per gateway.

One limit across three regions

The API runs in three regions, and a customer’s limit is global. How do we enforce it?

Asking a home region for every check would add 70 to 150 ms from the other two. So each region must decide on its own, while the total stays near the limit. Giving each region the full limit allows up to 3 times the limit. Giving each a fixed third starves a client that only uses one region.

So each region gets a share that follows traffic. Every 10 seconds, each region reports usage for its busiest keys. A quota balancer sets each region’s share in proportion to recent traffic, with a small minimum so a region can absorb a sudden shift. Shares are pushed to gateways like any other rule. It’s the lease idea one level up: regions lease a share of a global budget.

Distributed rate limiter · architecture

Stage 6: Global limits across regions

Grow itTrace a requestBreak it

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasional

Play

PreviousNext

Stage

123456

API requests per second:

1,000,000

400k average1M peak10M (10×)30M

Stage 6 of 6

Global limits across regions

Why this stage

Not load: a requirement.

The API runs in three regions and a customer’s limit is global, but a cross-region check would add 70 to 150 ms to every request.

What we add

Each region enforces its own share of every limit with its own Redis.

A quota balancer moves shares toward where each key’s traffic is, every 10 seconds.

What it costs

When a client’s traffic moves between regions, it can be held under its global limit for up to about 10 seconds.

At 1M api requests per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

The numbers behind the busy bars

What one machine can do

• One gateway node handles about 5,000 requests a second, with TLS, auth and the limit check. The fleet runs near 60% busy.
• One Redis primary runs about 50,000 short Lua scripts a second at a safe level. Redis runs commands on one thread, so a script blocks its shard while it runs.

Calls to Redis

• Until stage 5, every request is one script call.
• With leases, only about 10% of requests reach Redis, because most traffic comes from a few busy keys.

The cost: if a client’s traffic moves between regions, it’s held a little under its global limit until the next rebalance, about 10 seconds. It is never over.

When things break

Interviewerminute 41

A Redis primary dies at peak. Walk me through the next 30 seconds.

What they are testing

Whether the API stays up and you can say how wrong the limits are while it recovers: time limits, breaker, local limits, a backup taking over, a few lost counts. One minute.

Our promise was that the limiter never takes the API down. The first 30 seconds of a Redis failure go like this. Calls time out after 5 ms. Breakers open, and gateways switch to local limits. Login and SMS rules refuse. About 15 seconds later, the backup copy takes over as the main shard. Breakers try again, and shared counts resume. A few recent token takes were never copied to the backup, so a few clients get a few extra requests, once.

Click any box to break it and see what users would notice:

Distributed rate limiter · architecture

Break it: what fails, who notices, what users see

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasional

Break

A Redis shardA gateway nodeRules serviceRules databaseQuota balancerAPI services overloadedLoad balancer or region

Failure: click any box to break it

A Redis shard goes down

What breaks

Scripts for the keys on that shard (about 1/32 of them) time out until its replica is promoted, about 10 to 20 seconds.

How we notice

Script timeouts and errors per shard; the circuit breaker opening on many gateways at once.

What users see

Nothing visible for most clients.

Keys on that shard get approximate local limits; login and SMS rules refuse until it is back.

What we do

A 5 ms timeout and a per-shard circuit breaker switch gateways to local buckets at 1/N of the limit.

The replica takes over; it may have lost the last few milliseconds of counts, which lets a few extra requests through.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.

One failure isn’t the limiter’s at all, and people often miss it. A rate limiter enforces fairness between clients. It doesn’t know what the backends can handle. When every client is within its plan, but the total is more than the backends can take, the services themselves must shed load and answer 503.

Go deeperEvery failure, and what users see2 min

Part	Failure	What users see	How we notice	What we do
Redis shard	Primary down	Nothing for most; login and SMS refused for 10–20 s	Timeouts per shard, breakers opening	Breaker and local limits; backup takes over; a few counts lost
Gateway	Crash	A few failed requests, retried	Health checks, about 10 s	Removed from the load balancer; its leases expire within 1 s
Rules service	Down	Nothing; rule changes wait	Snapshot age above 60 s	Gateways keep the last snapshot
Rules database	Down	Nothing; edits fail	Admin API errors	Managed failover in about 30 s
Quota balancer	Down	Clients moving between regions held under the limit	Share age above 60 s	Old shares fall back to a fixed split after 5 minutes
API services	Overloaded	Slow responses or 503, while every limit is green	Service latency	Load shedding in the services
Whole region	Down	Traffic moves in 1 to 2 minutes	External test requests	Its shares move to the other regions

Go deeperWhich way the error goes, path by path1 min

The design never promises “exact”. It promises which way the error goes, and how big it can be.

Path	Promise	What a client can see
Quiet keys, one shard	One script at a time per key	Exactly its limit
Busy keys, leased tokens	Never over; under by unused leases	Up to about 100 ms of its limit missing, for a moment
A shard fails over	The newest takes may be lost	A few requests over the limit, once
Local limits during an outage	Roughly 1 to 2 times the limit	Looser limits for 10 to 20 seconds
Regions	Shares add up to the limit	Under the global limit for about 10 s after traffic moves
Rules	Every gateway within 10 s	Old and new limits on different gateways for a few seconds

The Lua script makes one check atomic on one shard. It doesn’t make the whole limiter exact. That’s fine, because the requirement is “at most about 1% over in normal running”. A limiter that must be exact, such as a paid quota, needs every write copied before it answers, and accepts the slower speed.

Go deeperRunning it: alerts and abuse1 min

Wake someone up when: the limiter adds over 2 ms for the slowest 1% of requests for 10 minutes; any shard’s breaker is open on more than 10% of gateways; any gateway is more than 60 seconds behind the current rules; or the 429 rate for a plan jumps against last week. A bad rule looks exactly like a wave of abuse, and this alert catches both.

Abuse. Per-IP limits run before login, so password guessing can’t reach the login service at full speed. A client that rotates API keys to escape its limit is caught by a rule over all keys of one organization. Headers only ever show the caller its own budget.

Wrap up

The whole design

Here is everything we built, in the order we built it. Use the buttons to step through it.

Distributed rate limiter · architecture

The full design, stage by stage

Color keyServiceDatabaseBackground workerNew in this stageAsync or occasional

Play

PreviousNext

Stage

123456

API requests per second:

1,000,000

400k average1M peak10M (10×)30M

Stage 6 of 6

Global limits across regions

Why this stage

Not load: a requirement.

The API runs in three regions and a customer’s limit is global, but a cross-region check would add 70 to 150 ms to every request.

What we add

Each region enforces its own share of every limit with its own Redis.

A quota balancer moves shares toward where each key’s traffic is, every 10 seconds.

What it costs

When a client’s traffic moves between regions, it can be held under its global limit for up to about 10 seconds.

At 1M api requests per second, every part has headroom. Raise the traffic until something turns red.

Pinch or tap the zoom buttons to read small labels.Drag any box to move it. Reset puts every box back.The whole design. Step through it: local buckets, shared counters, shards, live rules, token leases, then three regions.

The numbers behind the busy bars

What one machine can do

• One gateway node handles about 5,000 requests a second, with TLS, auth and the limit check. The fleet runs near 60% busy.
• One Redis primary runs about 50,000 short Lua scripts a second at a safe level. Redis runs commands on one thread, so a script blocks its shard while it runs.

Calls to Redis

• Until stage 5, every request is one script call.
• With leases, only about 10% of requests reach Redis, because most traffic comes from a few busy keys.

The decisions, and what each one costs

Decision	We chose	We gave up	We’d choose differently if
Where it runs	A filter in the API gateway, straight to Redis	Limits that use business data	Limits were for internal services (a proxy)
Algorithm	Token bucket, all rules in one script	Calendar windows users can reason about	Limits were “N per hour” (sliding window counter)
Atomic check	Lua script on the shard	Freedom to make scripts long	Only fixed windows were needed (INCR)
Counter store	Redis Cluster, split by API key	Counts surviving a failover	Limits were billed (a durable store)
Busy keys	Token leases and a refusal cache	A few percent of the limit for a moment	Exactness both ways mattered more than speed
Redis outage	Local limits; security rules refuse	Exact limits during an outage	The backends had no protection of their own
Regions	Shares that follow traffic	The full limit in one region during a shift	Limits could be per region
Rules	Pushed, versioned snapshots	Instant changes everywhere	Rules changed many times a second

How to spend 45 minutes

• 0 to 5. Who is limited, how exact, and what happens when the limiter breaks.
• 5 to 10. 330 gateways, a million Redis calls a second, memory doesn’t matter, one call per request.
• 10 to 20. Build it: local buckets, then shared buckets, the race and the script, shards, live rules. A mid-level answer can stop here.
• 20 to 26. Token leases for the busy client.
• 26 to 41. The stress tests: the algorithm, the broken retry loop, Redis going down, then regions.
• 41 to 45. A primary dying at peak, then your own questions.

Never skip the race and the atomic script, or the fail-open question. If time is short, drop regions.

Follow-up questions

Interviewer asksSome endpoints are much more expensive than others. How do you limit by cost?

Give each route a cost in the rules: 5 tokens for search, 1 for a simple read. A request of cost c passes only if every bucket holds c tokens. When the cost is only known afterwards, take an estimate first, and settle the difference after the response.

Interviewer asksA customer says they were limited at 80 a second on a 100 a second plan. How do you debug it?

Sampled decision logs per key say which rule refused, where, and whether the answer came from Redis, a lease or the outage fallback. The usual causes are an override still in place, a region share behind moved traffic, or the per-minute rule firing. The 429 body names the rule, so ask for it.

Go deeperMore follow-up questions2 min

How would you add a daily quota of 10,000 requests per key? A daily quota is a count customers check against invoices, not a rate. Keep a counter per key per day, and add gateway counts to it in batches every few seconds. A few requests over is fine. If it’s billed, the official count comes from request logs, not Redis.

Should refused requests count against the limit? Not in a token bucket. A refused request takes no token, so a client that backs off recovers at the refill rate. Counting refusals keeps a client that ignores 429 locked out until it stops. That’s a policy choice worth writing down, because it surprises clients that retry once.

How would you limit concurrent requests instead of requests per second? “At most 20 in flight per key” protects slow endpoints better than a rate. The hard part is a gateway crashing before it subtracts one. So store each request in flight with its start time, and drop entries older than the request timeout. A lost subtraction then fixes itself.

What changes at 100 times the traffic? About 200 shards, and over 30,000 gateways. That many gateways shrinks every batch towards 1, so busy keys call Redis 100 times more. Fix it by leasing per group of gateways, through a small middleman in each data centre.

Further reading

• Rate limiting, partitioning and consistency models on this site, and the low level design of a rate limiter for the single-node classes.
• Scaling your API with rate limiters, Stripe engineering: token buckets in Redis, and why a load shedder is a separate tool from a rate limiter.
• How we built rate limiting capable of scaling to millions of domains, Cloudflare: the sliding window counter and its measured error.
• envoyproxy/ratelimit: the open source global rate limit service behind Envoy, with Redis counters and a local cache of keys that are over their limit.