Rate limiting and back-pressure

Token bucket or leaky bucket: which one should I use?

A token bucket answers yes or no right now and lets a burst through up to its capacity, so it suits an API that should tolerate a client opening with a handful of calls. A leaky bucket holds requests and releases them at a fixed pace, so what reaches the other side is smooth, at the cost of added delay. Pick the token bucket when the caller can take a 429 and retry, and the leaky bucket when the work must be done and the thing downstream cannot take bursts. Both keep O(1) state per key.

Why does a fixed window let through twice the limit?

A fixed window resets its count on the clock boundary, so a client can send the whole limit in the last second of one window and the whole limit again in the first second of the next. That is twice the limit inside two seconds. A sliding log fixes it exactly by keeping every allowed time, and a sliding window counter fixes it approximately by weighing the previous window by how much of it still overlaps. The counter keeps two numbers per key instead of a list.

Where should the rate limiter live?

At the edge of the service, in the gateway or in a small library every server calls before doing any work, so a refusal costs almost nothing. If each server keeps its own counters, a client spread over n servers by the balancer gets n times the limit, so a limit that must hold across servers keeps its counters in a shared store. That costs one network round trip per request, and two servers updating the same counter at once is why the limiter should use one atomic increment rather than a read followed by a write.

What should the API return when it limits a request?

HTTP 429, Too Many Requests, with a Retry-After header saying when a retry can succeed. A token bucket can compute that exactly: the missing fraction of a token divided by the refill rate. Returning it lets well-behaved clients wait the right amount instead of retrying at once, which would only add load. Many APIs also return the limit and the remaining allowance on every response so clients can pace themselves.

Is rate limiting the same as back-pressure?

No, though they work together. A rate limit caps what each client may send, which gives fairness between clients. Back-pressure caps what the service accepts in total, by bounding its queues or the work in flight, so the whole service stays inside its capacity even when every client is within its own limit. A few clients each at their limit can still fill a service, so you want both.