# Rate-limiting algorithms

> Fixed window, sliding log, sliding counter and token bucket, compared on the same traffic.

Concept · Reliability · https://levelcode.org/concepts/rate-limiting-algorithms

A rate limiter caps how many requests a client may make per unit of time. Four algorithms dominate; all allow *limit* requests per *window* in the long run, but behave differently in the short run.

| Algorithm | State per key | Behaviour | Watch out for |
|---|---|---|---|
| Fixed window | One counter per aligned window | Count requests in 12:00:00–12:00:59, reset at the boundary | Up to 2× the limit across a boundary |
| Sliding log | A timestamp per accepted request | Count requests in the last *window* seconds — exact | Memory grows with the limit |
| Sliding window counter | Two counters | `previous × overlap + current` — a close approximation | Slight over-admission right after a boundary |
| Token bucket | Tokens and a timestamp | Bucket of *capacity* tokens refilled at *rate*; each request takes one | Allows bursts up to capacity (by design) |

A **leaky bucket** queues requests and releases them at a constant rate — it smooths output rather than rejecting bursts, and is common in traffic shaping.

Run the same traffic through all four and compare what each lets through:

> **Interactive: Four limiters, one stream of requests.** The token bucket admits a full bucket at once and then follows its refill rate. Switch to window-edge traffic and look at the last column: the fixed window lets twice its limit through around the boundary. Try it: https://levelcode.org/labs/rate-limiter

## Choosing

- **Token bucket** for API rate limits: tolerate short bursts, cap the sustained rate. Two numbers of state.
- **Sliding window counter** for high-volume limits where you want close-to-exact windows cheaply.
- **Sliding log** for low limits that must be exact, such as login attempts.
- **Fixed window** for daily and monthly quotas, where boundary bursts don't matter.

## In a distributed system

Counters must be shared (usually in Redis) and updated **atomically** — a Lua script for read-decide-write logic — or each server must enforce a share of the limit locally. Decide whether to fail open or closed when the store is unreachable, and return `429` with `Retry-After`. The System Design roadmap's rate-limiting lesson builds a Redis token bucket; see also [load shedding](https://levelcode.org/concepts/load-shedding).