Pogingen tellen in een venster

Hoofdstuk 3 liet elke wachtwoordgok de server één scrypt-aanroep kosten. Een gok kost de rader nog steeds bijna niets, en niets telt de gokken. De login van ben uit de vorige les kan een miljoen keer geprobeerd worden.

In Python in Practice kwam je status 429 tegen vanaf de kant van de client: een server die je programma zegt rustiger aan te doen. Deze les en de volgende zijn de kant van de server. Vandaag schrijf je alleen de teller, in een nieuw bestand, limits.py. Er is nog geen route die hem iets vraagt.

Een venster dat schuift

De begrenzer houdt per sleutel de tijden bij van de recente pogingen van die sleutel. Een sleutel is een stukje tekst dat zegt van wie deze pogingen zijn. Een poging is recent zolang now - stamp < window. De tijden heten stempels, en attempts is een dict van elke sleutel naar zijn lijst stempels.

Neem limit=3 en window=60, en pogingen op seconde 0, 10 en 20. Een vierde poging komt op seconde 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

Met al limit stempels in het venster wordt de volgende poging geweigerd. De wachttijd is de tijd tot de oudste stempel vertrekt: oldest + window - now. Op seconde 60 is de stempel van seconde 0 precies window seconden oud, dus hij is niet meer recent, en er is weer ruimte. Het venster is geen vast blok op de klok. Het eindigt bij now en schuift bij elke aanroep mee.

De functie geeft 0 terug voor een poging die ze toestaat, en het aantal seconden wachten voor een poging die ze weigert. De meegeleverde whole_seconds(wait) rondt een wachttijd naar boven af op een heel getal en geeft nooit minder dan 1 terug. Beide doen ertoe voor de volgende les: de header Retry-After neemt hele seconden, en een weigering die 0 zei, zou op toestemming lijken.

Een geweigerde poging wordt niet vastgelegd

Als de functie weigert, voegt ze niets aan de lijst toe. Stel dat ze dat wel deed. Een client die blijft proberen, zou dan met elke poging zijn eigen wachttijd vooruitschuiven en nooit binnenkomen. Erger nog, iedereen zou dat met de sleutel van een ander kunnen doen. Een geweigerde poging verandert dus niets voor de pogingen erna.

Een vreemde kiest de sleutels

Bij een login wordt de sleutel een gebruikersnaam, en een loginformulier accepteert elke tekst als naam. De sleutels van attempts worden dus gekozen door wie de verzoeken stuurt. Een dict met als sleutels wat vreemden intypen, groeit zonder grens, tot de server geen geheugen meer heeft.

Twee regels houden hem klein.

Ten eerste: vergeet een sleutel als zijn laatste stempel het venster verlaat. Dat is de taak van forget_old(attempts, now, window): houd voor elke sleutel alleen de recente stempels, en verwijder de sleutel als er geen over is. Een dict kan niet van grootte veranderen terwijl een lus hem leest. Verzamel dus eerst de te verwijderen sleutels in een lijst en verwijder ze in een tweede lus, zoals bij het opruimen in hoofdstuk 4.

Ten tweede: weiger een nieuwe sleutel bij te houden als de dict al MAX_KEYS sleutels bevat. Een sleutel die de dict al heeft, wordt nog steeds geteld. De nieuwe sleutel krijgt te horen dat hij whole_seconds(window) moet wachten. Als geen opgeslagen sleutel opnieuw geprobeerd wordt, is er uiterlijk na één venster een plek vrij.

Een volle tabel is zelf een manier om nieuwe mensen buiten te houden, en je moet weten dat die er is. De volgende les richt de login zo in dat zijn tabel ver onder MAX_KEYS blijft.

Tijd is weer een argument

now is een getal dat de aanroeper meegeeft. Niets in limits.py importeert een klok, en niets erin wacht. Dat is de regel uit hoofdstuk 4, en die betaalt zich op dezelfde manier uit: je kunt een venster van vijf minuten in een mum van tijd testen, door de getallen mee te geven die je wilt.

forget_old past het ene window dat hij krijgt toe op elke sleutel in de tabel. De login in de volgende les gebruikt hetzelfde WINDOW voor zijn beide limieten, dus dat is veilig. Twee limieten met verschillende vensters zouden elk een eigen tabel nodig hebben.

allow_attempt roept bij elke aanroep eerst forget_old aan. Die bekijkt elke keer elke sleutel. Voor een tabel van hoogstens 1000 korte lijsten is dat prima. Het is een keuze voor eenvoudige code, niet voor snelheid.

Je opdracht

In limits.py:

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

2. Schrijf allow_attempt(attempts, key, now, *, limit, window). Roep eerst forget_old aan. Als de sleutel al limit stempels heeft, geef whole_seconds(oldest + window - now) terug en leg niets vast. Als de sleutel nieuw is en de dict al MAX_KEYS sleutels bevat, geef whole_seconds(window) terug en leg niets vast. Voeg anders now toe aan de lijst van de sleutel en geef 0 terug.

Probeer het daarna met de 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)"

Het drukt af:

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

Twee pogingen worden toegestaan. De derde, op seconde 20, moet 40 seconden wachten. Op seconde 60 is de eerste stempel vertrokken, dus de poging wordt toegestaan en vastgelegd, en de dict bevat de twee stempels die nog recent zijn.

De teller werkt, en de login vraagt hem nog steeds nooit iets. De volgende les zet hem vóór de wachtwoordcontrole.