Reliability & Resilience

Rate-Limiting Algorithms

Rate limiting caps how many requests a client — or the whole system — can make in a time window, protecting downstream capacity and giving predictable, fair pushback instead of an uncontrolled pile-up. Token bucket, leaky bucket, fixed window, and sliding window each make a different precision/memory tradeoff.

Token bucket: tokens refill at a steady rate up to a cap; a request consumes one token — allows bursts up to the bucket size, then throttles to the refill rate
Leaky bucket: requests queue and drain at a fixed rate, smoothing bursts into constant output rather than allowing them through
Fixed window: simplest to implement (a counter reset every window) but can let through nearly 2× the limit right at a window boundary
Sliding window (log or weighted counter) fixes the boundary-burst problem at the cost of more memory or computation per check
Rate limiting is applied per-client (fairness), globally (protect a shared resource), or both — often at multiple layers: an API gateway and the service behind it

Rate-limiting algorithms compared
Algorithm	Allows bursts?	Memory per key	Boundary problem
Fixed window	Yes, within a window	One counter	Up to 2× limit at window edges
Sliding window log	Smoothly limited	One timestamp per request	None, but memory scales with request rate
Sliding window counter	Smoothly limited (approximate)	Two counters	Small approximation error, cheap
Token bucket	Yes, up to bucket size	One counter + timestamp	None — bucket size is the burst allowance
Leaky bucket	No — output is constant-rate	A queue	None, but adds queueing latency

Token bucket

class TokenBucket {
    private final long capacity;
    private final double refillPerMs;
    private double tokens;
    private long lastRefillMs;

    TokenBucket(long capacity, double refillPerSecond) {
        this.capacity = capacity;
        this.refillPerMs = refillPerSecond / 1000.0;
        this.tokens = capacity;
        this.lastRefillMs = System.currentTimeMillis();
    }

    synchronized boolean tryConsume() {
        long now = System.currentTimeMillis();
        tokens = Math.min(capacity, tokens + (now - lastRefillMs) * refillPerMs);
        lastRefillMs = now;
        if (tokens >= 1) {
            tokens -= 1;
            return true;
        }
        return false;    // rate limited
    }
}

Fixed window's boundary-burst problem

A client sending N requests at the end of one window and N more at the start of the next slips past a fixed-window limit