​
Fixed Window

This algorithm divides time into fixed durations/windows. For example each window is 10 seconds long. When a new request comes in, the current time is used to determine the window and a counter is increased. If the counter is larger than the set limit, the request is rejected.

​
Pros

  • Very cheap in terms of data size and computation
  • Newer requests are not starved due to a high burst in the past

​
Cons

  • Can cause high bursts at the window boundaries to leak through
  • Causes request stampedes if many users are trying to access your server, whenever a new window begins

​
Usage

from upstash_ratelimit import Ratelimit, FixedWindow
from upstash_redis import Redis

ratelimit = Ratelimit(
    redis=Redis.from_env(),
    limiter=FixedWindow(max_requests=10, window=10),
)

​
Sliding Window

Builds on top of fixed window but instead of a fixed window, we use a rolling window. Take this example: We have a rate limit of 10 requests per 1 minute. We divide time into 1 minute slices, just like in the fixed window algorithm. Window 1 will be from 00:00:00 to 00:01:00 (HH:MM:SS). Let’s assume it is currently 00:01:15 and we have received 4 requests in the first window and 5 requests so far in the current window. The approximation to determine if the request should pass works like this: 
limit = 10

# 4 request from the old window, weighted + requests in current window
rate = 4 * ((60 - 15) / 60) + 5 = 8

return rate < limit # True means we should allow the request

​
Pros

  • Solves the issue near boundary from fixed window.

​
Cons

  • More expensive in terms of storage and computation
  • It’s only an approximation because it assumes a uniform request flow in the previous window

​
Usage

from upstash_ratelimit import Ratelimit, SlidingWindow
from upstash_redis import Redis

ratelimit = Ratelimit(
    redis=Redis.from_env(),
    limiter=SlidingWindow(max_requests=10, window=10),
)

​
Token Bucket

Consider a bucket filled with maximum number of tokens that refills constantly at a rate per interval. Every request will remove one token from the bucket and if there is no token to take, the request is rejected.

​
Pros

  • Bursts of requests are smoothed out and you can process them at a constant rate.
  • Allows setting a higher initial burst limit by setting maximum number of tokens higher than the refill rate

​
Cons

  • Expensive in terms of computation

​
Usage

from upstash_ratelimit import Ratelimit, TokenBucket
from upstash_redis import Redis

ratelimit = Ratelimit(
    redis=Redis.from_env(),
    limiter=TokenBucket(max_tokens=10, refill_rate=5, interval=10),
)