Versuche in einem Zeitfenster zählen

Kapitel 3 hat dafür gesorgt, dass jeder Passwortversuch den Server einen scrypt-Aufruf kostet. Einen Versuch kostet es den Ratenden immer noch fast nichts, und nichts zählt die Versuche. bens Anmeldung aus der letzten Lektion lässt sich eine Million Mal versuchen.

In Python in der Praxis hast du den Status 429 von der Seite des Clients kennengelernt: ein Server, der deinem Programm sagt, es solle langsamer machen. Diese Lektion und die nächste sind die Seite des Servers. Heute schreibst du den Zähler allein, in einer neuen Datei, limits.py. Noch fragt ihn keine Route.

Ein Fenster, das gleitet

Der Begrenzer hält für jeden Schlüssel die Zeitpunkte der letzten Versuche dieses Schlüssels fest. Ein Schlüssel ist ein Stück Text, das sagt, wessen Versuche das sind. Ein Versuch ist aktuell, solange now - stamp < window gilt. Die Zeitpunkte heißen Stempel (stamps), und attempts ist ein Dictionary von jedem Schlüssel zu seiner Liste von Stempeln.

Nimm limit=3 und window=60 und Versuche bei den Sekunden 0, 10 und 20. Ein vierter Versuch kommt bei Sekunde 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

Wenn schon limit Stempel im Fenster sind, wird der nächste Versuch abgelehnt. Die Wartezeit ist die Zeit, bis der älteste Stempel herausfällt: oldest + window - now. Bei Sekunde 60 ist der Stempel von Sekunde 0 genau window Sekunden alt, also nicht mehr aktuell, und es ist wieder Platz. Das Fenster ist kein fester Block auf der Uhr. Es endet bei now und bewegt sich mit jedem Aufruf.

Die Funktion gibt für einen Versuch, den sie erlaubt, 0 zurück und für einen, den sie ablehnt, die Sekunden, die zu warten sind. Das mitgelieferte whole_seconds(wait) rundet eine Wartezeit auf eine ganze Zahl auf und gibt nie weniger als 1 zurück. Beides zählt für die nächste Lektion: Der Header Retry-After nimmt ganze Sekunden, und eine Ablehnung, die 0 sagt, sähe wie eine Erlaubnis aus.

Ein abgelehnter Versuch wird nicht festgehalten

Wenn die Funktion ablehnt, fügt sie der Liste nichts hinzu. Angenommen, sie täte es. Ein Client, der es weiter versucht, würde seine eigene Wartezeit mit jedem Versuch nach hinten schieben und nie hineinkommen. Schlimmer noch, jeder könnte das mit dem Schlüssel eines anderen tun. Ein abgelehnter Versuch ändert also nichts für die Versuche danach.

Ein Fremder wählt die Schlüssel

Bei einer Anmeldung wird der Schlüssel ein Benutzername sein, und ein Anmeldeformular akzeptiert jeden Text als Namen. Die Schlüssel von attempts wählt also, wer Anfragen sendet. Ein Dictionary, dessen Schlüssel Fremde eintippen, wächst ohne Grenze, bis dem Server der Speicher ausgeht.

Zwei Regeln halten es klein.

Erstens: Vergiss einen Schlüssel, wenn sein letzter Stempel aus dem Fenster fällt. Das ist die Aufgabe von forget_old(attempts, now, window): Behalte für jeden Schlüssel nur die aktuellen Stempel und entferne den Schlüssel, wenn keiner übrig ist. Ein Dictionary darf seine Größe nicht ändern, während eine Schleife es liest. Sammle also die zu entfernenden Schlüssel zuerst in einer Liste und entferne sie in einer zweiten Schleife, wie beim Aufräumen in Kapitel 4.

Zweitens: Lehne es ab, einen neuen Schlüssel zu verfolgen, wenn das Dictionary schon MAX_KEYS Schlüssel enthält. Ein Schlüssel, den das Dictionary schon enthält, wird weiter gezählt. Dem neuen Schlüssel wird gesagt, er solle whole_seconds(window) warten. Wenn kein gespeicherter Schlüssel erneut versucht wird, ist spätestens nach einem Fenster ein Platz frei.

Eine volle Tabelle ist selbst ein Weg, neue Leute auszusperren, und du solltest wissen, dass es ihn gibt. Die nächste Lektion richtet die Anmeldung so ein, dass ihre Tabelle weit unter MAX_KEYS bleibt.

Die Zeit ist wieder ein Argument

now ist eine Zahl, die der Aufrufer übergibt. Nichts in limits.py importiert eine Uhr, und nichts darin wartet. Das ist die Regel aus Kapitel 4, und sie zahlt sich genauso aus: Du kannst ein Fenster von fünf Minuten im Nu testen, indem du die Zahlen übergibst, die du willst.

forget_old wendet das eine window, das es bekommt, auf jeden Schlüssel in der Tabelle an. Die Anmeldung in der nächsten Lektion verwendet für ihre beiden Limits dasselbe WINDOW, also ist das sicher. Zwei Limits mit verschiedenen Fenstern bräuchten jeweils eine eigene Tabelle.

allow_attempt ruft bei jedem Aufruf zuerst forget_old auf. Es sieht sich jedes Mal jeden Schlüssel an. Für eine Tabelle mit höchstens 1000 kurzen Listen ist das in Ordnung. Es ist eine Entscheidung für einfachen Code, nicht für Geschwindigkeit.

Deine Aufgabe

In limits.py:

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

2. Schreib allow_attempt(attempts, key, now, *, limit, window). Ruf zuerst forget_old auf. Wenn der Schlüssel schon limit Stempel hat, gib whole_seconds(oldest + window - now) zurück und halte nichts fest. Wenn der Schlüssel neu ist und das Dictionary schon MAX_KEYS Schlüssel enthält, gib whole_seconds(window) zurück und halte nichts fest. Andernfalls füge now zur Liste des Schlüssels hinzu und gib 0 zurück.

Probier es dann von Hand aus:

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)"

Es gibt aus:

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

Zwei Versuche sind erlaubt. Der dritte, bei Sekunde 20, muss 40 Sekunden warten. Bei Sekunde 60 ist der erste Stempel herausgefallen, also wird der Versuch erlaubt und festgehalten, und das Dictionary enthält die zwei Stempel, die noch aktuell sind.

Der Zähler funktioniert, und die Anmeldung fragt ihn immer noch nie. Die nächste Lektion setzt ihn vor die Passwortprüfung.