Request Rate Limiting with Token Bucket Algorithm

Request rate limiting is a mechanism to constrain how frequently clients can send requests to a backend service. It prevents overload during traffic spikes, ensures fair resource allocation, and protects downstream systems. The token bucket algorithm is a widely adopted method for implementing flexible, burst-capable rate limiting that adapts to varying request patterns.

Implementing Rate Limiting with Token Bucket

Core Mechanics of the Algorithm

A token bucket maintains a reservoir of tokens. Each incoming request consumes one token. Tokens are added to the bucket at a fixed rate, up to a maximum capacity. When the bucket is full, excess tokens are discarded. Requests are served immediately if a token is available; otherwise, they are queued, rejected, or delayed.

The algorithm is defined by two parameters:

• rate: Number of tokens added per second (e.g., 10 tokens/second).
• burst: Maximum number of tokens the bucket can hold (e.g., 50 tokens).

For a request arriving at time t, the bucket state is:

• current_tokens = min(burst, previous_tokens + rate × (t − last_update_time))
• If current_tokens ≥ 1, the request is allowed and 1 token is consumed.
• Otherwise, the request is rejected (e.g., with 429 Too Many Requests).

Configuring Rate Limits in a Backend Service

Rate limiting is typically applied at the API gateway or service level. A common configuration pattern uses a declarative format in the service’s runtime configuration.

rate_limiter:
  default:
    rate: 10
    burst: 50
    window: 60
    enforce: true
    header: "X-RateLimit-Remaining"
    response:
      status: 429
      body:
        error: "RateLimitExceeded"
        message: "Request limit exceeded"
        retry_after: 60

• rate: The steady rate of tokens per second.
• burst: Maximum tokens in the bucket.
• window: Duration over which the rate is calculated (e.g., 60 seconds).
• enforce: Whether to reject requests when the bucket is empty.
• header: Name of the header to expose current limit status.
• response: HTTP response shape when rate limiting is triggered.

This configuration applies to all routes unless overridden per route.

Applying Limits to Specific Endpoints

To apply different limits to different endpoints, define route-specific configurations.

rate_limiter:
  routes:
    /api/v1/users:
      rate: 5
      burst: 25
      header: "X-RateLimit-Users"

    /api/v1/search:
      rate: 20
      burst: 100
      window: 30
      enforce: true
      response:
        status: 429
        body:
          error: "SearchRateLimit"
          message: "Too many search queries in a short time"

Each route uses its own bucket, independent of others. A client calling /api/v1/users sees a 5 requests/second limit with a 25-token burst, while /api/v1/search allows 20 requests/second with higher burst capacity and a shorter window.

Integrating with HTTP Request Flow

When a request arrives, the rate limiter checks the bucket state before processing the request. The flow is:

1. Retrieve the bucket state for the client (e.g., by client_id, api_key, ip_address).
2. Compute the current number of tokens based on the last update time.
3. If tokens ≥ 1, consume one token and proceed.
4. If tokens < 1, return the configured error response.
5. Update the bucket’s last update time and token count.

The following HTTP response is standard when rate limiting is enforced:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
X-RateLimit-Remaining: 3
X-RateLimit-Limit: 10
Retry-After: 60

{
  "error": "RateLimitExceeded",
  "message": "Request limit exceeded",
  "retry_after": 60
}

Clients can use X-RateLimit-Remaining to dynamically adjust their request pacing and Retry-After to delay retries.

Handling Token Bucket State Persistence

Token buckets must be stateful across restarts and deployments. The bucket state includes:

• tokens: current number of tokens (float or integer).
• last_updated: timestamp of the last update (ISO 8601, e.g., 2024-04-05T12:34:56.789Z).
• client_id: identifier for the client (e.g., api-key=abc123).

State is typically stored in a key-value store like Redis or a database.

Redis-based Implementation Example

SETEX rate_limit:api-key:abc123:tokens 3600 25.0
SET rate_limit:api-key:abc123:last_updated "2024-04-05T12:34:56.789Z"

When a request arrives:

# Get current tokens and last update time
GET rate_limit:api-key:abc123:tokens
GET rate_limit:api-key:abc123:last_updated

# Compute elapsed time since last update
# Then calculate new token count
# Update bucket state
MULTI
  INCRBYFLOAT rate_limit:api-key:abc123:tokens 2.5  # Add 2.5 tokens
  SET rate_limit:api-key:abc123:last_updated "2024-04-05T12:37:12.345Z"
EXEC

If the bucket is empty, the client receives 429 with Retry-After set to the time needed for the bucket to refill.

Failure Modes and Edge Cases

Token Overflow During High Load

If the bucket is at capacity and a burst of requests arrives, the first requests consume tokens immediately, while the rest are queued or rejected. The bucket refills over time, allowing for sustained bursts.

For example, with rate=10, burst=50, and window=60, a client sending 100 requests in 10 seconds fills the bucket and processes 50 requests immediately. The remaining 50 requests wait for the bucket to refill.

Clock Drift and Time Synchronization

The algorithm assumes consistent time across service instances. Clock drift between the application server and the storage backend (e.g., Redis) causes incorrect token calculations.

If the Redis server is 5 seconds behind, a request arriving at 12:34:56 on the app server is processed with a last_updated time of 12:34:51 on Redis. This leads to fewer tokens than expected.

Bucket Refill During Request Processing

Requests can take time to process. If the bucket is updated during the processing of a request, the next request may see a different state.

For instance:

• Request 1: consumes a token, updates bucket at t=10.
• Request 2: arrives at t=10.5, reads tokens from t=10.
• But during processing of Request 1, the bucket was updated at t=10.8.
• Request 2 sees an outdated state.

Solutions include:

• Using a transactional update with WATCH/MULTI/EXEC in Redis.
• Applying two-phase token acquisition: first, read the state; second, update it in a single transaction.

Misunderstood Parameters: Rate vs. Window

The rate parameter is often mistaken for the total number of requests per window. However, rate is the rate per second, and window is the duration over which the rate is measured.

A configuration of rate=5, window=60 does not mean 5 requests per minute. It means 5 tokens added per second, so 300 tokens over 60 seconds. The bucket fills at 5 tokens/second, allowing 300 requests in one minute.

To achieve a 5 requests/minute limit, set rate=5/60 ≈ 0.0833 tokens per second, or use rate=1, window=120 to get 1 request every two minutes.

Overlapping Request Streams

When multiple clients use the same bucket (e.g., IP-based rate limiting), a client sending 100 requests in 5 seconds may consume tokens from a bucket shared with other clients.

This leads to interference: a burst from one client affects others. To isolate clients, use a unique bucket per client, identified by:

• client_id (from JWT payload)
• api_key
• ip_address
• user_id
• user_id + endpoint

A common mistake is using a single bucket for all clients, leading to inconsistent limits.

Client-Side Behavior

Clients should handle rate limit errors gracefully.

Retry-After Header

The Retry-After header suggests when to retry a failed request.

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

Clients can:

• Wait 60 seconds before retrying.
• Use exponential backoff with Retry-After as a base.
• Adjust their request pacing based on X-RateLimit-Remaining.

Dynamic Client Throttling

Clients can maintain their own token bucket state and adapt request intervals.

For example, a client that receives X-RateLimit-Remaining: 3 and X-RateLimit-Limit: 10 can:

• Send requests every 10/10 = 1 second if under load.
• Increase interval to 10/3 ≈ 3.3 seconds when X-RateLimit-Remaining drops to 3.

Summary of Key Considerations

• Use rate and burst to define steady and burstable limits.
• Choose window to define the time over which the rate is measured.
• Always persist bucket state with tokens and last_updated.
• Use 429 with JSON body for rate limit errors.
• Set Retry-After to guide clients.
• Handle clock drift and overlapping request streams.
• Use Redis WATCH/MULTI/EXEC for atomic bucket updates.
• Configure route-specific limits using a declarative format.
• Let clients use X-RateLimit-Remaining to tune their behavior.

The token bucket algorithm is not just a rate limiter—it is a foundation for scalable, resilient, and adaptive API systems.

This page was rewritten on 18 October 2026. It replaced a templated version that was not specific to its own title. How these pages are written and checked. If anything here is wrong, tell us at [email protected] and we will correct it.