# Distributed rate limiting without a global bottleneck

> Design distributed rate limiting with token buckets, Redis coordination, bounded overshoot, failure policies, and practical scaling trade-offs for multi-region services.

- URL: https://ferdousazad.com/blog/distributed-rate-limiting
- Author: Ferdous Azad (Founder @ DataXgen AI)
- Published: 2026-11-12
- Updated: 2026-11-12
- Tags: rate-limiting, distributed-systems, devops, cloud-infrastructure

A rate limiter that checks every request against one central store can become the bottleneck it was meant to prevent. A limiter that checks only local state can quietly let a fleet exceed its quota. The design challenge is choosing how much coordination you need—and what you’ll do when that coordination fails.

## Problem statement and requirements

Design a service that enforces limits across many API servers. A customer with a limit of 100 requests per second should not receive 100 requests per second *per server* just because traffic is spread across the fleet.

The limiter needs to decide whether to allow a request, reject it, or defer it. It also needs to tell clients when they can try again, and give operators a way to change policies without restarting application servers.

### Functional requirements

- Apply limits by API key, tenant, user, IP address, route, or a combination.
- Support sustained rates and short bursts.
- Return a decision quickly enough to fit in the request path.
- Distribute policy updates and expose metrics for allowed and rejected requests.
- Support different failure behavior for different routes.

A request might be checked against several policies: a per-user limit, a tenant-wide quota, and a stricter limit for an expensive endpoint. The request is allowed only if all applicable checks pass.

### Non-functional requirements

The limiter should add low and predictable latency, remain available during partial failures, and avoid large quota errors when traffic crosses servers or regions. These goals conflict: strict global coordination costs latency and availability, while local decisions are fast but can overshoot.

For sizing, assume **100,000 requests per second**, **one million active limit keys**, and a typical key receiving only a small fraction of total traffic. These are design assumptions, not benchmark results. The hot-key case—one tenant receiving a large share of traffic—needs separate attention.

## Choose an algorithm before choosing a datastore

The algorithm defines the limit’s behavior. The storage architecture determines how faithfully that behavior holds across machines.

| Algorithm | Strength | Main drawback |
|---|---|---|
| Fixed window | Cheap and simple | Can allow nearly twice the limit at a boundary |
| Sliding log | Accurate rolling window | Stores a timestamp per request |
| Sliding counter | Lower memory than a log | Approximate near window boundaries |
| Token bucket | Allows controlled bursts | Requires atomic state updates |
| Leaky bucket | Smooths output rate | Often queues or delays requests |

For most API gateways, the token bucket is a useful starting point. It models a sustained rate plus a burst allowance. A bucket with capacity `B = 20` and refill rate `r = 1 token/second` can accept a burst of 20 requests, then sustain one request per second as tokens return.

For a request costing `c` tokens, calculate:

```text
elapsed = max(0, now - last_refill)
tokens = min(capacity, tokens + elapsed * refill_rate)

if tokens >= c:
    tokens -= c
    allow
else:
    reject
```

The refill calculation and token deduction must be atomic. If two servers read the same token count and update independently, both can spend the same token.

## High-level architecture

A practical design uses a shared authority for exact decisions, then adds local quota leases where the request volume makes a shared lookup too costly.

```mermaid
flowchart LR
    Client["Client request"] --> Gateway["API gateway"]
    Gateway --> Cache["Policy cache"]
    Gateway --> Local["Local quota manager"]
    Local -->|Lease exhausted| Router["Key-to-shard router"]
    Router --> Store["Rate-limit state shard"]
    Store --> Router
    Router --> Local
    Local --> Decision["Allow or reject"]
    Config["Policy control plane"] --> Cache
    Gateway --> Metrics["Metrics and alerts"]
    Local --> Metrics
    Store --> Metrics
```

The policy cache holds rules, not authoritative token counts. For a normal request, the gateway checks its local lease. If it has quota, the decision is local. When it runs low, it requests another lease from the state shard responsible for that key.

The shard is the authority for allocating quota. It atomically deducts a lease from the global bucket before granting it. This avoids a datastore round trip for every request while ensuring that two gateways cannot independently claim the same tokens.

A simpler deployment can skip leases and perform an atomic token-bucket update in a shared store for every request. That gives clearer global behavior, but it puts every request on the coordination path.

## Data model

A policy describes what is limited and how:

```text
policy_id
key_dimensions: [tenant_id, route]
capacity: 20
refill_rate: 1 token/second
cost: 1 token/request
action: reject
version: 42
```

The dimensions produce a stable state key, such as `tenant-123:route-search`. Avoid relying on a raw client-supplied identifier; normalize and validate dimensions before building the key.

The authoritative token-bucket state needs only:

```text
tokens
last_refill_time
policy_version
```

A lease-based implementation also tracks the quota granted to each gateway and its expiry. The central bucket is charged when the lease is issued, not when the gateway spends each token. Any unused quota may be wasted when a lease expires. Refunding it safely requires knowing that the gateway cannot still spend it.

State updates should use integer or fixed-point token units rather than floating-point arithmetic. Time handling also matters: use a consistent clock at the authority, or clamp negative elapsed time to zero. Clock skew between gateways should not be allowed to mint tokens.

## Key components

### Policy control plane

The control plane validates and versions policies, then publishes updates to gateways. A version lets a gateway detect stale configuration and helps operators trace a decision back to the rule that produced it.

Policy changes need a defined rollout behavior. If a limit is lowered, existing leases can temporarily exceed the new target unless they are revoked or allowed to drain. Revocation is stricter but adds coordination and can disrupt in-flight traffic.

### Request-path evaluator

The evaluator extracts identity dimensions, selects the matching policies, and checks them in a predictable order. Rejecting early avoids spending work on later checks, but the order should not produce confusing client behavior.

For example, a request that passes a per-user limit but fails the tenant limit should still be rejected. If the system returns retry information, it should reflect the policy that actually blocked the request.

### State shards

Partition state by a stable hash of the limit key. Each key should have one authoritative owner for atomic updates. In Redis, a Lua script can perform refill, comparison, and deduction as one operation; in a sharded setup, keys must be placed so that the operation runs on the shard that owns them.

A single hot key can overwhelm its shard even when total traffic is modest. Per-key sharding cannot split one key’s serialized updates without changing the consistency model.

### Decision and response layer

An allowed request proceeds. A rejected request should receive a clear status and, where appropriate, a `Retry-After` value derived from the time needed to refill enough tokens. Keep internal details out of the response; expose the limit and reset metadata only if the API contract supports it.

## Scaling & bottlenecks

At the assumed 100,000 requests per second, a shared-store check for every request means up to 100,000 state operations per second before retries, multiple policies, or other traffic are counted. That may be acceptable for a well-sized system, but it makes the datastore part of the request’s latency and availability path.

Leases reduce that traffic by reserving batches of tokens. Larger leases mean fewer coordination calls, but more unused capacity can be stranded on quiet gateways. Smaller leases preserve capacity but increase store traffic. This is a direct tuning trade-off, not a free optimization.

Hot tenants need special treatment. A single key’s exact token-bucket updates are inherently serialized. Possible responses include allocating sub-quotas to gateway groups, using leases, or accepting bounded overshoot. Each changes the guarantee. A design that claims both perfectly exact global enforcement and independent local decisions is hiding a coordination cost.

Multi-region deployments add another choice. Routing each key to a home region preserves a single authority, but distant requests pay cross-region latency and a region failure can interrupt enforcement. Maintaining independent regional buckets improves availability, but the combined allowance can exceed the intended global limit. Regional quotas can cap that overshoot, at the cost of uneven capacity when traffic shifts.

Capacity planning should include key cardinality as well as request rate. Expiring inactive state avoids unbounded growth, but expiry must be longer than the relevant bucket’s refill horizon or the limiter can accidentally reset a partially depleted bucket.

## Trade-offs

**Exactness versus availability:** A centralized atomic check gives a strong per-key limit while the authority is reachable. During a partition, gateways must either wait, reject, or make local decisions that may overshoot.

**Latency versus datastore load:** Checking every request is straightforward to reason about. Leases cut coordination traffic and request-path latency, but add quota accounting, expiry behavior, and stranded capacity.

**Burst tolerance versus smoothing:** Token buckets admit bursts up to their capacity. Leaky-bucket behavior is a better fit when the system must smooth work before a constrained downstream service, but queuing introduces delay and requires queue limits.

**Fairness versus utilization:** Fixed regional or gateway allocations protect a global ceiling, but one region can run out while another has unused capacity. Dynamic reallocation improves utilization but requires more coordination.

Choose the failure policy by endpoint. A read API might fail open briefly to preserve availability, while a costly operation or security-sensitive action may need to fail closed. “Fail open” is not a harmless default: it means the configured limit is no longer guaranteed.

## Lessons from production

Treat the limiter as an admission-control system, not just a counter. Measure allowed and rejected decisions, state-store latency, lease grant rate, hot keys, policy propagation delay, and fail-open events. A rising rejection count can indicate abuse, a policy mistake, or a bug in identity extraction.

Test boundary behavior explicitly. Fixed windows can admit a burst immediately before and after a boundary; token buckets can permit a full bucket after a quiet period; leases can leave unused quota stranded. These are algorithm properties, not edge cases to patch away.

Keep the response path bounded. If the authority is slow, set a timeout and apply the route’s chosen fallback rather than letting requests pile up behind an unbounded wait. The fallback should be observable, since silently bypassing limits hides outages until downstream systems feel them.

## Interview tips

Start by asking what “limit” means: a sustained rate, a burst ceiling, a rolling window, or a concurrency cap. Those are different constraints and may need different mechanisms.

Then state your consistency target. For example: “The per-tenant bucket is exact within one region while the authority is available; during a partition, this expensive route fails closed.” That sentence makes the architecture easier to evaluate than a generic promise of global rate limiting.

Finally, estimate the coordination path. Count active keys, request checks per second, policies per request, and expected hot-key concentration. Explain what changes when a shared lookup becomes too expensive, and quantify the overshoot you’re willing to accept if you add local leases.

## Key takeaways

- Token buckets are a practical default when APIs need both a sustained rate and bounded bursts.
- Distributed correctness depends on atomic state updates or centrally allocated quota; local counters alone multiply the allowance.
- Leases reduce request-path coordination, but trade exact utilization for lower datastore load.
- Define behavior for hot keys, regional failures, stale policies, and state-store timeouts before deployment.
- A rate limit is only useful if its failure mode matches the cost of the operation it protects.