How to design a distributed rate limiter for high-traffic REST APIs?

Question

2

Overview

Rate limiting protects backend web servers from denial-of-service (DoS) attacks, brute-force attempts, and resource starvation. In a distributed environment with multiple API gateways, rate limiting logic must be centralized and operate with ultra-low latency.

Common Rate Limiting Algorithms

Token Bucket: Allows temporary burst traffic up to bucket capacity.
Leaky Bucket: Smooths out traffic spikes by processing requests at a fixed rate.
Sliding Window Counter: Prevents edge-burst traffic at window boundaries while remaining memory efficient.

Atomic Sliding Window Counter via Redis Lua Script

Using a Lua script inside Redis guarantees atomic execution and eliminates race conditions in concurrent web environments:

local key = KEYS[1]
local now = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit = tonumber(ARGV[3])
local clearBefore = now - window

redis.call('ZREMRANGEBYSCORE', key, 0, clearBefore)
local currentRequests = redis.call('ZCARD', key)

if currentRequests < limit then
    redis.call('ZADD', key, now, now)
    redis.call('EXPIRE', key, window)
    return 1
else
    return 0
end

1 Answer

Write Your Answer

Answer 1

A distributed rate limiter controls how many requests a client can make within a given period across multiple API servers. For high-traffic REST APIs, the limiter must be accurate enough to enforce quotas, fast enough to sit on every request, highly available, and horizontally scalable.

1. Define the requirements

Before choosing an algorithm, clarify:

Limit: e.g. 1,000 requests/minute per API key.
Scope: per user, API key, IP, endpoint, organization, or a combination.
Burst behavior: whether short bursts above the average rate are allowed.
Consistency: strict enforcement vs. approximate enforcement.
Failure behavior: fail-open or fail-closed if the limiter's datastore is unavailable.
Latency target: ideally only a few milliseconds added to the request path.
Scale: requests per second, number of clients, and number of API servers.

For example:

POST /payments → 100 requests/minute per API key
GET /products → 1,000 requests/minute per API key

2. Choose a rate-limiting algorithm

Token Bucket

The most common choice for APIs.

Each client has a bucket containing tokens:

Capacity = maximum burst size.
Tokens are replenished at a fixed rate.
Each request consumes one or more tokens.
If no token is available, return HTTP 429 Too Many Requests.

For example, a bucket with capacity 100 and refill rate 10 tokens/second allows a burst of 100 requests while sustaining 10 requests/second.

Advantages: supports bursts, simple, efficient, and works well for distributed systems.

Leaky Bucket

Requests enter a queue and are processed at a fixed rate.

Advantages: produces a smooth request rate.
Disadvantage: queueing can introduce latency and memory pressure.

Fixed Window

Count requests during intervals such as:

12:00:00–12:00:59

Simple and inexpensive, but it has a boundary problem: a client could send 1,000 requests at 12:00:59 and another 1,000 at 12:01:00.

Sliding Window

Tracks request activity over a moving interval.
It is more accurate than fixed windows but generally requires more state.

For most high-traffic APIs, Token Bucket is a strong default.

3. Use a shared distributed store

The main challenge is that API traffic is distributed across many application servers:

                    ┌── API Server 1
Client ── Load Balancer ── API Server 2
                    └── API Server 3
                              │
                              ▼
                    Distributed Rate Limiter
                              │
                              ▼
                     Redis Cluster

If each API server maintains its own counter, a client can bypass the intended limit simply by having requests routed to different servers.

Instead, all servers should consult shared state.

Redis is commonly used because it provides:

Very low latency.
Atomic operations.
Horizontal scaling through clustering.
TTL/expiration support.
Lua scripts for atomic multi-step operations.

The key might look like:

rate_limit:{api_key}:{endpoint}

4. Make the check atomic

A critical requirement is that checking and consuming capacity must happen atomically.

This is unsafe:

GET counter
if counter < limit:
    INCREMENT counter

Two API servers can read the same value simultaneously and both approve requests.

Instead, perform the entire operation atomically using a Redis Lua script or an equivalent atomic datastore operation.

Conceptually:

request arrives
      │
      ▼
calculate tokens that should have refilled
      │
      ▼
atomically:
  - read bucket
  - refill tokens
  - check available tokens
  - consume token if available
  - update expiration
      │
      ├── allowed ──► API handler
      │
      └── rejected ─► HTTP 429

The operation should return enough information for the application to construct useful rate-limit headers.

5. Return standard rate-limit information

For rejected requests, return:

HTTP/1.1 429 Too Many Requests
Retry-After: 3

It is also useful to expose headers such as:

RateLimit-Limit: 1000
RateLimit-Remaining: 42
RateLimit-Reset: 12

Clients can then implement backoff rather than repeatedly retrying requests that will be rejected.

6. Handle high-cardinality traffic

A large API may have millions of API keys or users.

Don't create permanent state for every client. Give inactive buckets a TTL so they disappear automatically.

For example:

rate_limit:user123:endpointA → expires after inactivity

This prevents the rate-limit store from growing indefinitely.

For extremely high cardinality, consider:

Sharding keys across Redis nodes.
Separating hot and cold clients.
Local caching where approximate enforcement is acceptable.
Hierarchical limits.

7. Consider hierarchical rate limits

Real APIs often need multiple limits simultaneously:

Global:
  1,000,000 requests/sec

Organization:
  100,000 requests/min

User:
  1,000 requests/min

Endpoint:
  100 requests/min

A request is allowed only if all applicable limits have capacity.

This prevents a single organization or expensive endpoint from consuming disproportionate resources.

For expensive operations, you can also use weighted tokens:

GET /products       → 1 token
POST /search        → 5 tokens
POST /report        → 20 tokens

8. Decide what happens when Redis fails

This is an important availability trade-off.

Fail-open

If the limiter is unavailable, allow requests.

Pros: API remains available.
Cons: attackers or traffic spikes can bypass protection.

Fail-closed

If the limiter is unavailable, reject requests.

Pros: protects downstream systems.
Cons: a rate-limiter outage can become an API outage.

A practical design often uses different policies for different endpoints. For example, a critical read endpoint may fail open, while an expensive payment/reporting operation may fail closed.

9. Protect against hot keys

A single extremely active API key can become a Redis hot key.

Possible mitigations include:

Sharding especially hot clients.
Local token buckets combined with global quotas.
Limiting at the edge before traffic reaches the application.
Using multiple independent limits rather than one extremely contended key.
Deploying rate limiting close to the traffic source.

For very large systems, rate limiting can be performed at several layers:

Internet
   │
   ▼
CDN / API Gateway
   │       ← coarse global/IP limits
   ▼
Load Balancer
   │
   ▼
Application
   │       ← user/API-key limits
   ▼
Database / expensive service
           ← resource-specific protection

10. Keep the request path lightweight

The rate limiter is executed for potentially every request, so avoid expensive operations.

A good request path is roughly:

HTTP request
    ↓
Authenticate
    ↓
Determine rate-limit key
    ↓
Atomic Redis operation
    ↓
Allowed?
 ┌──┴──┐
Yes    No
 ↓      ↓
API    429

Avoid network calls to multiple independent services just to determine whether a request should be accepted.

11. Monitor the limiter itself

Track:

Allowed requests/sec.
Rejected requests/sec.
Rate-limit latency.
Redis latency.
Redis errors/timeouts.
Number of active rate-limit keys.
Hot keys.
Rejection rate by API key, organization, IP, and endpoint.
Percentage of requests failing open/closed.

Alert on unusual rejection spikes and datastore degradation.

12. A production-oriented design

A scalable architecture could look like:

                  ┌──────────────────┐
                  │ CDN / API Gateway│
                  └────────┬─────────┘
                           │
                    coarse rate limit
                           │
                           ▼
                  ┌──────────────────┐
                  │ Load Balancer    │
                  └────────┬─────────┘
                           │
             ┌─────────────┼─────────────┐
             ▼             ▼             ▼
         API Server     API Server     API Server
             │             │             │
             └─────────────┼─────────────┘
                           ▼
                  ┌──────────────────┐
                  │ Redis Cluster    │
                  │                  │
                  │ Atomic Lua       │
                  │ Token Buckets    │
                  └──────────────────┘

The API servers remain stateless, while Redis stores the distributed rate-limit state.

13. Important edge cases

A production implementation should also consider:

Clock differences between servers.
Redis failover.
Network partitions.
Retry storms.
Client retries after 429.
Configuration changes while buckets already exist.
Multiple API regions.
Distributed Redis across regions.
Large bursts after an outage.
Administrative bypasses for trusted internal clients.

For multi-region APIs, a single globally shared limiter can introduce latency. A common approach is regional rate limiting with a global quota, accepting a small amount of enforcement looseness in exchange for lower latency and better availability.

Final recommendation

For a high-traffic REST API, a strong baseline design is:

Token Bucket + Redis Cluster + atomic Lua operation + TTL-based state + API Gateway protection + hierarchical quotas + 429 responses + monitoring.

The key design principle is that rate-limit state must be shared and updated atomically. Everything else—algorithm choice, sharding, failure policy, multi-region architecture, and local caching—should be driven by the required accuracy, traffic volume, latency, and availability guarantees.