Count Attempts in a Window

Chapter 3 made every password guess cost the server one scrypt call. A guess still costs the guesser almost nothing, and nothing counts the guesses. ben’s login from the last lesson can be tried a million times.

In Python in Practice you met status 429 from the client’s side: a server telling your program to slow down. This lesson and the next are the server’s side. Today you write the counter alone, in a new file, limits.py. No route asks it yet.

A window that slides

The limiter keeps, for each key, the times of that key’s recent attempts. A key is a piece of text that says whose attempts these are. An attempt is recent while now - stamp < window. The times are called stamps, and attempts is a dict from each key to its list of stamps.

Take limit=3 and window=60, and attempts at seconds 0, 10, and 20. A fourth attempt arrives at second 30:

second      0     10     20     30                    60
attempt     x      x      x      ?                     |
                                 now                   the stamp from
                                                       second 0 leaves

in the window at second 30: the stamps 0, 10, 20. That is 3, the limit.
the oldest stamp, 0, leaves at 0 + 60 = 60
the wait is 60 - 30 = 30 seconds

With limit stamps already in the window, the next attempt is refused. The wait is the time until the oldest stamp leaves: oldest + window - now. At second 60 the stamp from second 0 is exactly window seconds old, so it is no longer recent, and there is room again. The window is not a fixed block of the clock. It ends at now and moves with every call.

The function returns 0 for an attempt it allows, and the seconds to wait for one it refuses. The supplied whole_seconds(wait) rounds a wait up to a whole number and never returns less than 1. Both matter for the next lesson: the Retry-After header takes whole seconds, and a refusal that said 0 would look like permission.

A refused attempt is not recorded

When the function refuses, it adds nothing to the list. Suppose it did. A client that keeps trying would push its own wait forward with every try and never get in. Worse, anyone could do that to someone else’s key. So a refused attempt changes nothing for the attempts after it.

A stranger chooses the keys

At a login the key will be a user name, and a login form accepts any text as a name. So the keys of attempts are chosen by whoever sends requests. A dict keyed by what strangers type grows without bound, until the server runs out of memory.

Two rules keep it small.

First, forget a key when its last stamp leaves the window. That is the job of forget_old(attempts, now, window): for every key, keep only the recent stamps, and remove the key when none is left. A dict cannot change size while a loop reads it. So collect the keys to remove in a list first and remove them in a second loop, as in the sweep of Chapter 4.

Second, refuse to track a new key when the dict already holds MAX_KEYS keys. A key the dict already holds is still counted. The new key is told to wait whole_seconds(window). If no stored key is tried again, a slot is free after one window at the latest.

A full table is itself a way to keep new people out, and you should know that it is there. The next lesson arranges the login so that its table stays far below MAX_KEYS.

Time is an argument, again

now is a number the caller passes in. Nothing in limits.py imports a clock, and nothing in it waits. That is the rule from Chapter 4, and it pays the same way: you can test a five-minute window in no time at all, by passing the numbers you want.

forget_old applies the one window it is given to every key in the table. The login in the next lesson uses the same WINDOW for both of its limits, so that is safe. Two limits with different windows would each need a table of their own.

allow_attempt calls forget_old first, on every call. It looks at every key each time. For a table of at most 1000 short lists that is fine. It is a choice for plain code, not for speed.

Your task

In limits.py:

1. Write forget_old(attempts, now, window).

2. Write allow_attempt(attempts, key, now, *, limit, window). Call forget_old first. When the key already has limit stamps, return whole_seconds(oldest + window - now) and record nothing. When the key is new and the dict already holds MAX_KEYS keys, return whole_seconds(window) and record nothing. Otherwise add now to the key’s list and return 0.

Then try it by hand:

python -c "import limits; a = {}; print(limits.allow_attempt(a, 'k', 0, limit=2, window=60), limits.allow_attempt(a, 'k', 10, limit=2, window=60), limits.allow_attempt(a, 'k', 20, limit=2, window=60), limits.allow_attempt(a, 'k', 60, limit=2, window=60)); print(a)"

It prints:

0 0 40 0
{'k': [10, 60]}

Two attempts are allowed. The third, at second 20, must wait 40 seconds. At second 60 the first stamp has left, so the attempt is allowed and recorded, and the dict holds the two stamps that are still recent.

The counter works, and the login still never asks it. The next lesson puts it in front of the password check.