Sliding window rate limiter in Python

Why this matters

A web service often limits how fast one user can call it. A login page might allow 5 tries per minute. An API might allow 100 calls per hour for each API key. Without a limit, one script can send a million tries in a minute and slow the service down for everyone else.

A rate limiter is the code that makes this decision. For each request, it answers one question: is this user already at the limit, or may this request go through?

This lesson builds a limiter that uses a sliding window. A window is a stretch of time that moves forward with the clock. The limiter looks at the last few seconds, not at fixed blocks such as "minute 1" or "minute 2". The earlier lessons in this module covered sliding windows over lists, where the window holds positions. Here the window holds points in time, and each stored point is one request.

The rule in plain words

Two numbers define the rule.

• The limit is the most requests a user may make inside one window. Here it is 3.
• The window is the length of time that counts. Here it is 10 seconds, or 10,000 milliseconds.

A request counts for exactly one window after it happens. A request made at second 0 counts until the clock reaches second 10. From second 10 onward it no longer counts, because it is exactly one window old.

Take one user with a limit of 3 and a window of 10 seconds. The user sends requests at these times, in seconds.

The row for second 10 needs a closer look. Before the check, the request from second 0 is removed, because 10 minus 0 equals the window. Two requests are left, at seconds 1 and 2. That is below the limit of 3, so the request at second 10 is allowed. The rejected request at second 3 never counted, so it does not appear in the list of counting requests.

Working a small case by hand is a good way to check the rule before writing code. Each row is a question the code must answer the same way.

The data structure: a queue of times

The useful fact is that the oldest request always leaves the window first. If the request at second 1 is still counting, then the request at second 0 has either left already or is about to. The stored times are always in increasing order, and the code only ever removes from the front.

A queue is a list where you add at one end and remove at the other. The first item in is the first item out. Python's collections.deque is a double-ended queue. It adds and removes at either end in a fixed amount of work. The code in this lesson uses three of its operations.

• append(x) adds x at the back, which is the newest end.
• times[0] reads the front item, which is the oldest, without removing it.
• popleft() removes the front item and returns it.

A Python list could hold the times too, and list.pop(0) removes the front. But removing from the front of a list moves every other item one place forward. A long list makes each request slower. deque.popleft() removes from the front in the same amount of work no matter how long the queue is.

Step 1: one user, one queue

Start with a single user. The queue holds the times of that user's requests that still count. Every request does two things.

1. Remove the times at the front that are one window old or older.
2. If fewer than LIMIT times are left, add this time at the back and allow the request. Otherwise reject it.

t=0 allowed queue=[0]
t=1000 allowed queue=[0, 1000]
t=2000 rejected queue=[0, 1000]
t=4000 rejected queue=[0, 1000]
t=5000 allowed queue=[1000, 5000]
t=6000 allowed queue=[5000, 6000]
t=9000 rejected queue=[5000, 6000]

The time is in milliseconds, so 5000 means 5 seconds. The loop at the bottom sends seven requests and prints the decision and the queue after each one. list(times) copies the deque into a list for printing, so the output looks like the queue's contents.

Check the line for t=5000 against the rule. The time 0 is 5000 milliseconds old, which equals the window, so it leaves the queue. The time 1000 is 4000 milliseconds old and stays. The queue has one item, so the request is allowed and 5000 joins the back.

The rejected requests at 2000 and 4000 do not appear in the queue. They are refused, and the code returns before it adds them. That detail matters, and the mistakes section shows what happens when it is wrong.

Step 2: many users, one dict

A real service has many users. Each user needs a separate queue, so the code keeps a dict from the user's id to that user's queue. The dict's values are deques.

When a request arrives, the code needs the queue for that user. If the user has never called before, the code must create an empty queue. A defaultdict(deque) does this on its own. When you read a key that is missing, it calls deque(), stores the result, and returns it. This is the same job that computeIfAbsent does in Java.

times = recent_times[user_id]

For a user who already has a queue, the read just returns that queue. For a new user, the read creates an empty queue first.

The full class is below. It has the same queue logic as Step 1, moved into a helper method, and it keeps one queue per user.

The method computes window_start as now - window_millis. A time is removed when it is less than or equal to window_start. That is the same as saying now - time >= window_millis, which is the rule from Step 1 written in the other direction. Either form works. The one used here reads well when the window start is named.

The allow method takes now as a parameter instead of reading the clock itself. The reason is testing. A test can pass the exact times it wants, and the result is the same every run. A production service would pass the current time, as explained in the section on time sources below.

The remove_idle_users method loops over list(self.recent_times), which is a copy of the keys. It deletes entries while it walks the copy, so the dict itself is not changed during the loop. Lesson 11 explained why changing a dict while looping over it raises an error.

Step 3: a worked run with two users

The code below uses the class above. It sends requests for two users, with a limit of 3 and a window of 10 seconds. It also runs the cleanup method at the end.

ana  t=0      allowed
ana  t=1000   allowed
ana  t=2000   allowed
ana  t=3000   rejected
bo   t=3000   allowed
ana  t=10000  allowed
ana  t=10500  rejected
ana  t=11000  allowed
ana  t=11500  rejected
tracked users: 2
tracked users after cleanup: 0

Look at the rows for ana. The first three requests fill the limit. The request at 3000 is rejected. At 10000, the request from time 0 has left the window, so there is room, and the request is allowed. At 10500, the times 1000, 2000 and 10000 are all still counting, so the limit is reached again. At 11000, the time 1000 leaves, so the request is allowed. At 11500, the times 2000, 10000 and 11000 count, so it is rejected.

The request for bo at 3000 is allowed even though ana was rejected at the same moment. Each user has a separate queue, so one user's requests never use up another user's limit.

After the first pass, ana and bo both have entries in the dict. The cleanup at time 30000 removes every time that is 10 seconds old or more. Both queues become empty, and the code deletes both entries from the dict.

Why cleanup matters

Without the cleanup method, the dict keeps an entry for every user who has ever made a request. A user who stops calling still has a queue, and that queue is empty after the old times leave. An empty queue takes up a little memory. If a service sees millions of different users over a year, the dict grows with all of them, even though only a few are active at any moment.

The cleanup function clears the old times from each queue, then deletes the entry when the queue is empty. A real service calls a cleanup like this on a timer, for example once a minute. It does not have to run before every request.

Choosing the time source

The examples pass times in milliseconds that the caller writes by hand. A running service needs a real clock. Python's time module gives two common choices.

• time.time_ns() returns the wall-clock time in nanoseconds since 1970. It matches the calendar, but the operating system can change it, for example when a clock is corrected over the network. A change like that could make a window look longer or shorter than it is.
• time.monotonic_ns() returns a counter in nanoseconds that only moves forward. Its starting point is arbitrary, so the value means nothing on its own. Only the difference between two values is meaningful. It does not jump when the wall clock is corrected, so it is the usual choice for measuring a window.

time.monotonic() is the same clock as a float in seconds. Its starting point is arbitrary too, so only the difference between two readings matters.

If you use time.monotonic_ns(), the window and the stored values must both be in nanoseconds. A window of 10 seconds becomes 10_000_000_000. Python allows underscores in long numbers to make them easier to read.

Common mistakes

Storing rejected requests

The most common mistake is adding the new time to the queue before the check. Then a rejected request still takes up space in the window. The user is blocked for longer than the rule says.

The table below comes from running the correct limiter and a buggy one side by side. Both have a limit of 2 and a window of 10 seconds, and they get the same requests. The buggy version adds now first and checks the size after that.

class BuggyLimiter(RateLimiter):
    def allow(self, user_id, now):
        times = self.recent_times[user_id]
        times.append(now)
        window_start = now - self.window_millis
        while times and times[0] <= window_start:
            times.popleft()
        return len(times) <= self.limit

Output:

time    correct   buggy
0       allowed   allowed
1000    allowed   allowed
2000    rejected  rejected
3000    rejected  rejected
10500   allowed   rejected
11000   allowed   rejected

At time 10500, the correct version has only the request at 1000 still counting, so the user may go. The buggy version has also stored the requests at 2000 and 3000, which were refused. They are still in the window, so the user stays blocked. Every refused call makes the wait longer. A client that keeps retrying would keep getting refused.

The fix is to check first and add only when the request is allowed, as Step 1 and the full class do.

Reading a missing key from a plain dict

A plain dict returns None from get for a key that is not there. If the code then uses that None as a queue, Python stops with a TypeError. This happens when the author uses get instead of the defaultdict for a user who has not called yet.

from collections import deque
 
recent_times = {"ana": deque()}
times = recent_times.get("bo")
print(len(times))

TypeError: object of type 'NoneType' has no len()

The message names the operation (len) and the type that was used (NoneType). The fix is to use the defaultdict(deque) from the class, or to write times = recent_times.setdefault("bo", deque()), which creates the queue when it is missing.

The eviction loop in _evict_old does not fail on None, because while times and ... stops at once. The len call in allow after it does fail, with the same error. That is one more reason to make sure every user has a real queue.

Off by one at the window edge

A request must leave the window exactly one window after it happened. If the code removes times only when they are strictly older than the window, a request stays one extra tick. The check becomes now - time > window_millis instead of >=, or time < window_start instead of <=.

The hand trace in the first section shows the expected behaviour. At second 10 with a 10-second window, the request from second 0 must be gone. If your code still counts it, check the comparison operator first.

Using a list and removing from the front

A Python list also works for the queue if you remove from index 0 with pop(0). The output is the same, but each removal moves the rest of the list. With many requests per user, the limiter slows down. collections.deque with popleft() avoids the moving.

Expecting a fixed reset time

Some people expect a limit to reset at fixed times, such as the start of each minute. A sliding window does not do that. Each user's window moves with that user's own requests. A user who made 3 requests at second 58 gets room again at second 68 in a 10-second window, not at second 60.

Practice

Exercise 1. A limiter allows 2 requests per 3000 milliseconds. The requests arrive at times 0, 1000, 2999, 3000 and 4000. For each one, say whether it is allowed. Then check your answer by calling allow on a RateLimiter(2, 3000) with the same times.

Show the answer

The queue before each request is shown in brackets. At 0, the queue is empty, so the request is allowed [0]. At 1000, one time is in the queue, so it is allowed [0, 1000]. At 2999, both times are younger than 3000, so the limit is reached and the request is rejected. At 3000, the time 0 is exactly 3000 old and leaves, so the request is allowed [1000, 3000]. At 4000, the time 1000 leaves, so the request is allowed [3000, 4000]. The results are allowed, allowed, rejected, allowed, allowed.

['allowed', 'allowed', 'rejected', 'allowed', 'allowed']

Exercise 2. A limiter is built with a limit of 0. What does allow return for any request, and why?

Show the answer

It always returns False. The check len(times) < limit becomes len(times) < 0, and a length can never be below 0. So no request is ever added, and every request is rejected. A limit of 0 is a way to block a user completely, and the code handles it without a special case.

Exercise 3. Someone rewrites allow like this, to avoid the defaultdict:

times = recent_times.get(user_id)
evict_old(times, now)
if len(times) < limit:
    times.append(now)

The first call with a new user id fails. What is the exception, and what is the smallest fix?

Show the answer

The exception is a TypeError, because get returns None for a user who is not in the dict, and len cannot take None. The smallest fix is to replace get with recent_times[user_id] on a defaultdict(deque), which creates the queue on the first request. The setdefault(user_id, deque()) call works too.

Exercise 4. Change the class so that a user may make 3 requests in any one second, and the times are measured in nanoseconds with time.monotonic_ns(). Which two numbers change, and which code stays the same?

Show the answer

Two numbers change in the constructor call. The limit becomes 3, and the window becomes 1_000_000_000, which is one second in nanoseconds. The times passed in must come from time.monotonic_ns(). The allow, _evict_old and remove_idle_users methods stay the same, because they only compare numbers and do not care what unit those numbers use.

Exercise 5. A user's last request was at time 5000. The window is 10000. Is the user's queue empty after remove_idle_users(15000), and is the user removed from the dict?

Show the answer

Yes to both. At 15000, the window start is 5000. The time 5000 is less than or equal to 5000, so _evict_old removes it. The queue is empty, so the cleanup deletes the entry from the dict. If the cleanup ran at 14999 instead, the window start would be 4999, the time 5000 would stay, and the user would remain in the dict.

Summary

• A sliding window rate limiter counts only the requests made within the last window, so the window moves with the clock.
• Store the times of counting requests in a deque, remove old times from the front, and add a new time only when the request is allowed.
• Keep one queue per user in a dict, and use a defaultdict(deque) so that a new user works on the first call.
• Pass now as a parameter so tests can use fixed times, and use time.monotonic_ns() in a real service to measure intervals.
• Clean up idle users on a timer, so the dict does not grow without limit.
• Check the limit before storing a request. Storing refused requests blocks a user for longer than the rule allows.