Rate Limiting Algorithms

Overview

The token bucket is the algorithm behind most production rate limiters, including API Gateway's: tokens are added to a bucket at a configured rate (the sustained, steady-state throughput), the bucket has a maximum capacity (the burst limit), and each request consumes one token, proceeding immediately if one's available and getting rejected (typically a 429) only once the bucket is genuinely empty. This is why a short traffic spike doesn't fail instantly even though it exceeds the configured rate, unused tokens accumulated during quieter periods absorb the burst, up to the bucket's capacity, before rejection ever starts. A fixed-window counter (a simple "N requests per minute" reset on the clock) has a real, documented flaw a token bucket and sliding-window approaches both avoid: a client can send a full window's worth of requests at the very end of one window and another full window's worth at the start of the next, doubling the effective rate right at the boundary.

Quick Reference

Syntax

# API Gateway usage plan - rate is tokens/sec added, burst is bucket capacity
throttle:
  rateLimit: 100   # steady-state requests per second
  burstLimit: 200  # max concurrent burst the bucket can absorb

Examples

# A minimal token bucket - request proceeds if a token is
# available, rejected once the bucket is actually empty.
import time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.rate, self.capacity = rate, capacity
        self.tokens, self.last = capacity, time.time()

    def allow(self):
        now = time.time()
        self.tokens = min(self.capacity, self.tokens + (now - self.last) * self.rate)
        self.last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Visual Diagram

Common Mistakes

• Using a naive fixed-window counter and not accounting for its documented boundary-doubling flaw, where a client can effectively double the intended rate right at a window edge.
• Setting burst capacity far higher than any legitimate traffic pattern needs, defeating the purpose of having a steady-state rate limit at all.
• Rejecting requests based on average rate alone instead of actual token availability, penalizing legitimate short bursts a properly-sized bucket would have absorbed.
• Applying one single rate limit account-wide when different clients or endpoints have genuinely different legitimate traffic patterns, instead of layering per-client and per-method limits.

Performance

• A token bucket's per-request check is O(1), a simple arithmetic update and comparison, negligible overhead compared to the request it's gating.
• Sliding window implementations generally track more state (recent request timestamps or sub-window counters) than a token bucket's single counter, a real memory/complexity trade for avoiding the fixed-window boundary flaw.

Best Practices

• Configure rate and burst as two deliberate, independent values based on real observed traffic, not a single guessed number.
• Prefer token bucket or true sliding-window algorithms over a naive fixed-window counter, given its documented boundary-doubling flaw.
• Layer throttling at multiple levels (account, API, per-client) when different consumers legitimately need different limits, rather than one blanket setting.
• Return a clear, standard rejection response (429, with retry-after guidance where possible) so well-behaved clients can back off correctly.