Token Bucket: Bursts Without Losing Control

The failure mode it solves

Bursty traffic is normal for APIs. A client can pause for 30 seconds, then send a short spike of requests. Fixed window counters either reject the spike or allow too much if the burst crosses a window boundary. Token Bucket solves that by letting short bursts through while still enforcing a long-term average.

If you want a quick mental model: think of tokens as prepaid requests. They accumulate at a steady rate and get spent on demand. Once that image lands, the rest is just bookkeeping.

How the algorithm works in this service

Each client and endpoint pair has a bucket stored in Redis. The bucket holds a floating token count and the last refill timestamp. On every request, the Lua script refills tokens based on elapsed time using Redis server time, then decides allow or reject.

Step-by-step flow:

Read tokens and last_refill from Redis for the key rate-limit:{ip}:{endpoint}.
Compute new tokens: tokens = min(capacity, tokens + elapsed_seconds * refillRate).
If tokens >= 1, allow the request and decrement by 1. Otherwise reject.
Store the updated tokens and last_refill back to Redis with the configured TTL.

Diagram

Token bucket

The diagram shows the two moving parts: a steady refill and a request drain. The important detail is that refill happens on demand during the request, not on a background timer.

Worked example: burst, then steady

At t=0, the bucket has capacity 100 and refillRate 10 tokens/sec. A client sends 20 requests at once. All 20 are allowed, leaving 80 tokens. Over the next 5 seconds, 50 tokens refill, taking the bucket back to 100. If the client keeps sending 10 requests per second, the bucket stays near full and every request is allowed. If the client sends 200 requests in one second, the first 100 pass and the rest are rejected until tokens refill.

Where it fits versus the other algorithms

Algorithm	Strength	Weakness	Best fit
Token Bucket	Allows bursts without losing average control	Not perfectly uniform spacing	Public APIs and user traffic
Leaky Bucket	Smooths output rate	Adds queueing latency	Protecting slow backends
Fixed Counter	Fast and simple	Boundary spikes	Internal or low-risk endpoints
Sliding Window	Most accurate enforcement	Higher Redis cost	Billing and security-sensitive flows

Configuration in this project

yaml

rate-limit:
  fallback:
    algorithm: TOKEN_BUCKET
    capacity: 100
    refillRate: 10

This config enforces an average of 10 requests/second with bursts up to 100 requests. capacity is the maximum burst size. refillRate controls how quickly the bucket recovers. If you set refillRate to 0, the bucket becomes a one-time allowance until the TTL expires. If you raise capacity without raising refillRate, you allow larger spikes without changing the long-term average.

Redis state and TTL

Token Bucket uses a Redis hash with two fields:

text

key: rate-limit:{ip}:{endpoint}
tokens: float
last_refill: unix_ms

The TTL comes from rate-limit.redis.ttl. Keep it longer than your expected idle period so a quiet client does not lose its accumulated state too early, but avoid extremely long TTLs if you have high cardinality keys.