Rate Limiter The Token Bucket

​

How it works

• Each user (or client) has a bucket that holds up to 100 tokens.
• Each API request consumes one token (or a configurable cost).
• The bucket refills continuously at 100 tokens per minute (100 / 60 ≈ 1.67 tokens/s).
• Tokens stop accumulating once the bucket reaches its capacity (100 tokens).
• If the bucket has insufficient tokens when a request arrives, the request is rejected with HTTP 429 (Too Many Requests).

​

Example behavior

• If Alan makes 100 requests back-to-back, he can drain the bucket almost instantly.
• Immediately after the burst, tokens will replenish at ≈1.67 tokens/sec, allowing him to continue making requests at the sustained rate (roughly 1–2 calls/sec).
• The token bucket never fully locks a user out — tokens keep replenishing, and requests can resume as soon as enough tokens accumulate.

​

Properties and guarantees

• The token bucket does not enforce a strict ceiling of 100 requests per rolling 60-second window. If a bucket is full, a user can spend all 100 tokens at once (explicit burst).
• It guarantees a sustained refill rate of 100 tokens/minute.
• Burst capacity is explicit and configurable via the bucket size (e.g., reduce capacity to 20 tokens for a smaller allowed burst while keeping the same refill rate).
• For each user we store the minimal state needed to compute token availability at any moment — the current token count and the timestamp of the last refill.

​

What we store per user

​

Comparison to other approaches

​

Responses and headers

• When a user exceeds available tokens, return:
  • HTTP 429 (Too Many Requests)
  • Retry-After header with seconds to wait (or an estimated time until tokens are available)
  • Optionally: X-RateLimit-Remaining to show available tokens

• If tokens >= 1, allow immediately.
• Otherwise: seconds = ceil((1 - tokens) / REFILL_PER_SEC).

​

Basic refill/check logic (Python example)

import time
import math

CAPACITY = 100.0                 # max tokens in bucket
REFILL_PER_SEC = 100.0 / 60.0    # tokens added per second

class TokenBucket:
    def __init__(self, tokens=CAPACITY, last_refill=None):
        self.tokens = float(tokens)
        self.last_refill = last_refill or time.time()

    def _refill(self):
        now = time.time()
        elapsed = now - self.last_refill
        if elapsed <= 0:
            return
        added = elapsed * REFILL_PER_SEC
        self.tokens = min(CAPACITY, self.tokens + added)
        self.last_refill = now

    def allow_request(self, cost=1.0):
        """Return (allowed: bool, remaining_tokens: float)."""
        self._refill()
        if self.tokens >= cost:
            self.tokens -= cost
            return True, self.tokens
        return False, self.tokens

    def retry_after_seconds(self, cost=1.0):
        """Estimate seconds until `cost` tokens are available."""
        self._refill()
        if self.tokens >= cost:
            return 0
        needed = cost - self.tokens
        return math.ceil(needed / REFILL_PER_SEC)

• Uses fractional tokens so refills are continuous.
• Updates last_refill only on refill/check to minimize write churn.
• Exposes a retry_after_seconds helper to populate Retry-After headers.

​

Deployment notes and distributed considerations

• Single gateway: token-bucket state can be stored in memory on one instance.
• Horizontally scaled gateways: when requests for the same user hit different instances, you must keep state consistent. Common strategies:
  • Centralized store (e.g., Redis) to store tokens and timestamps atomically.
  • Sticky routing (consistent hashing) so a user is routed to the same gateway instance.
  • Best-effort synchronization or probabilistic algorithms (less strict, but simpler and faster).
• When using Redis, prefer commands that perform read-modify-write atomically (e.g., Lua scripts or Redis tokens implementation) to avoid race conditions.

​

Practical headers and client guidance

• Return these headers to help clients:
  • X-RateLimit-Limit: 100 (configured capacity or sustained rate)
  • X-RateLimit-Remaining: <tokens> (fractional value is acceptable)
  • Retry-After: <seconds> when returning 429
• Encourage clients to back off (exponential or jittered) when they receive 429 and to use X-RateLimit-Remaining to pace requests.

​

Summary

• Implement rate limiting at the API gateway (front door).
• For authenticated users, rate-limit per-account; for unauthenticated traffic, consider per-IP limits.
• Each user/account receives a token bucket that enforces a sustained rate of 100 requests/minute and allows bursts up to the bucket capacity (100 tokens).
• When tokens are exhausted, return 429 with helpful headers (Retry-After, X-RateLimit-Remaining).

​

Next topic

​

Links and references

• Redis — common choice for centralized counters and token buckets
• RFC 6585 — 429 Too Many Requests
• Rate Limiting Patterns and Practices