Abstract

Rate limiting at the API gateway is one of the most consequential pieces of infrastructure in any platform serving multiple tenants or external consumers. The choice of algorithm - fixed window, sliding window, leaky bucket, or token bucket - determines both the protection guarantees and the user experience for legitimate traffic. Token bucket is the dominant choice for API rate limiting because it absorbs short bursts while bounding sustained throughput, and its semantics map directly to the concepts API consumers already reason about: capacity, refill rate, and current balance. Implementing it correctly in a distributed gateway requires careful attention to state synchronization.

Token Bucket Mechanics

A token bucket is defined by two parameters: bucket capacity (the maximum burst size) and refill rate (tokens added per unit time). Each incoming request consumes one or more tokens. If the bucket has sufficient tokens, the request proceeds and the token count decrements. If not, the request is rejected or queued. The bucket refills continuously at the refill rate, up to its capacity.

This model gives clients predictable behavior. A client with a 100-request-per-minute rate limit and a burst capacity of 20 can fire 20 requests instantly after a period of inactivity, then sustain 100 per minute thereafter. Compare this to fixed-window limiting, where a client can legally fire 100 requests at 11:59:59 and another 100 at 12:00:00, creating a 200-request burst that downstream services must absorb. Token bucket prevents this because the bucket is the shared state, not the window boundary.

Distributed State and Redis

In a horizontally scaled gateway - Envoy, Kong, or a custom Go service - token bucket state cannot live in process memory without per-instance drift producing inconsistent enforcement across the fleet. Redis is the standard backing store. The INCRBY + TTL approach is common but racy; the correct implementation uses a Lua script evaluated atomically in Redis, which reads the current token count and last-refill timestamp, computes elapsed time to calculate refill, applies the delta, decrements for the request, and writes the new state in a single atomic operation.

Redis cluster latency at the rate-limiting hot path adds 0.5 to 2 milliseconds in typical deployments. For latency-sensitive workloads, local token buckets with periodic reconciliation against Redis provide a compromise: each gateway instance maintains a local bucket and asynchronously syncs with Redis every few hundred milliseconds. This allows brief over-limit events but bounds them to one reconciliation window.

Per-Client and Composite Limits

Production API rate limiting nearly always involves multiple limit dimensions: per-client limits, per-endpoint limits, global limits, and tenant-level aggregate limits. Storing a separate token bucket per (client, endpoint) pair in Redis is straightforward but multiplies key count. Composite rate limiting - where a single request decrements from both a per-client bucket and a global endpoint bucket, rejecting if either is empty - requires two atomic operations or a more complex Lua script, but it accurately models quota hierarchies.

Envoy’s rate limit service (ratelimit, maintained by Envoy Proxy) implements this model via a gRPC service that gateways call per request. Kong’s Rate Limiting Advanced plugin provides Redis-backed token bucket limiting with sliding window options. Both expose Prometheus metrics for current bucket fill levels, rejection rates, and Redis latency, which are the key signals for tuning bucket sizes to actual traffic patterns.