Skip to content

Algorithms

A limiter counts requests with one of three algorithms. Each one is a single Lua script that Redis runs atomically, so any number of processes can race for the same bucket and exactly the allowed number of requests get through.

from ratelimit_io import Algorithm, Limit, RateLimiter

limiter = RateLimiter(client, limit=Limit(100, minutes=1), algorithm=Algorithm.SLIDING_WINDOW)

Algorithm.FIXED_WINDOW is the default. To read the choice from configuration, convert the string: Algorithm(settings.rate_limit_algorithm) accepts 'fixed_window', 'sliding_window' and 'gcra'.

At a glance

Fixed window Sliding window GCRA
Guarantee at most N per window, up to 2N around a window boundary at most N in any period-long interval a burst of at most N, then N per period on average
Memory per bucket two numbers one entry per slot handed out in the last period two numbers
retry_after on refusal until the window ends until the oldest request leaves the window until the next request conforms
Pick it for per-user or per-IP limits strict quotas of someone else's API smooth traffic, token-bucket semantics

These rules hold for every algorithm:

  • A refused request is not recorded. A client that keeps knocking while blocked does not push its own unblocking further away.
  • A waiting request reserves its slot. With a wait budget, a request that finds the bucket full takes the next free slot in advance and sleeps until it. Waiters are served in arrival order; see Waiting for a slot.
  • Time comes from Redis. Every script reads the server's TIME, to the microsecond. Clock skew between application hosts cannot bend a limit, and a bucket that loses its expiry still counts correctly, because expiry only removes buckets nobody uses.

Fixed window

The first request opens a window one period long with N slots. Requests take the slots of the current window; once they are gone, a request is refused until the window ends, or with a wait budget reserves a slot in the next window, which starts the moment the current one ends.

It is the simplest algorithm, and its weakness is the boundary: N requests at the end of one window and N more at the start of the next pass within a very short time. When that burst is harmless, which it is for most per-user limits, the fixed window is the right default.

Sliding window

A log of the slots handed out per bucket, kept in a sorted set. A request is allowed when fewer than N slots fall within the last period, so no period-long interval ever holds more than N. A waiting request is logged at the slot it reserves, one period after the slot N places before it.

The price is memory: a bucket holds one entry per slot handed out in the last period, plus one per waiting request. For 100 requests a minute that is nothing. For a million requests a day per key, choose GCRA.

Pick the sliding window when exceeding the limit has a cost you cannot absorb, typically an external API that bans clients for going over its quota. Set the limit a little below that quota all the same: the limiter counts a request when it takes its slot, and the network delays each request by a different amount on its way to the provider.

GCRA

The generic cell rate algorithm is a token bucket in constant memory: per bucket it keeps how far ahead the theoretical arrival time of the next request lies. A full bucket allows a burst of N requests; after that it refills one request every period / N.

GCRA limits the rate, not the count per window. Over a long run the average is exactly N per period, and traffic comes out evenly spread. Within one period-long interval, though, a full burst plus a period of refills can add up to 2N − 1 requests.

retry_after is exact and usually short: after a burst against Limit(60, minutes=1) the next request conforms one second later.

Switching algorithms

The algorithm is part of the bucket name, so a limiter with a different algorithm starts with empty buckets instead of misreading the old ones. Switching in a deploy resets every counter once.