Een alternatieve benadering voor snelheidsbeperking

Een paar weken geleden ondervonden we bij Figma onze allereerste spam-aanval. Dit bewees de waarde van Figma's snelheidsbegrenzer en maakte eindelijk een einde aan de al lang bestaande grap dat ik het tevergeefs had gebouwd.

Tijdens de aanval stuurden de spammers ongevraagde uitnodigingen voor documenten naar tientallen e-mailadressen. Als we de aanval niet hadden ontdekt, hadden we mogelijk een enorme stijging van onze bezorgkosten en een achteruitgang van de reputatie van onze afzender van de e-mail kunnen meemaken. Gelukkig kregen we al vroeg de aanval te pakken en vermeden we deze uitkomst omdat onze snelheidsbegrenzer de vlaag van verzoeken van spammers detecteerde.

Ons tariefbeperkingssysteem is van eigen bodem en ik wil het ontwerp graag uitleggen voor het geval het voor anderen nuttig is. Het combineert een paar standaardtechnieken om de snelheid te bepalen waarmee mensen verzoeken naar uw server verzenden, en het is relatief nauwkeurig, eenvoudig en ruimtebesparend. Als u een bedrijf bent dat webapplicaties op consumentenschaal bouwt, kan onze tariefbeperking voorkomen dat gebruikers de beschikbaarheid van uw website schaden met een groot aantal verzoeken. Het is ook geweldig in het stoppen van spam-aanvallen, zoals we hebben ontdekt.

Voor degenen die niet vertrouwd zijn, beperkt een snelheidsbegrenzer hoeveel verzoeken een afzender - dit kan een gebruiker of een IP-adres zijn - in een specifiek tijdvenster (bijvoorbeeld 25 verzoeken per minuut) kunnen worden uitgegeven. In het geval van Figma moest het ook:

  • gegevens extern opslaan, zodat de meerdere machines waarop onze webtoepassing draait deze kunnen delen
  • Webaanvragen niet aanzienlijk vertragen
  • verouderde gegevens efficiënt uitwerpen
  • overmatig gebruik van onze webapplicatie nauwkeurig beperken
  • gebruik zo weinig mogelijk geheugen

Aan de eerste drie vereisten was eenvoudig te voldoen. Bij Figma gebruiken we twee externe datastores - Redis en PostgreSQL - en Redis was de betere locatie om trackinggegevens op te slaan. Redis is een gegevensopslag in het geheugen die extreem snel leest en schrijft ten opzichte van PostgreSQL, een relationele database op schijf. Nog beter, het is eenvoudig om aan te geven wanneer Redis verlopen gegevens moet verwijderen.

Een manier vinden om aan de laatste twee vereisten te voldoen - het webverkeer nauwkeurig beheersen en het geheugengebruik minimaliseren - was een grotere uitdaging. Hier zijn de bestaande snelheidsbegrenzerimplementaties die ik heb overwogen:

  • Token emmer
  • Vaste venstertellers
  • Schuifraam log

Laten we eens kijken hoe elk van hen werkt en ze vergelijken op het gebied van nauwkeurigheid en geheugengebruik. Dit geeft ons enige context voor de uiteindelijke aanpak die we hebben gevolgd om de snelheidsbegrenzer te bouwen die ons van de spammers heeft gespaard.

Token emmer

Een eenvoudige Google-zoekopdracht naar "tarieflimietalgoritme" wijst ons op het klassieke token bucket-algoritme (of lekkende bucket als meteralgoritme). Voor elke unieke gebruiker zouden we het Unix-tijdstempel van hun laatste verzoek en het aantal tokens registreren binnen een hash in Redis. We zouden deze twee waarden opslaan in een hash in plaats van als twee afzonderlijke Redis-sleutels voor geheugenefficiëntie. Een voorbeeld van een hash ziet er zo uit:

Gebruiker 1 heeft nog twee tokens in zijn tokenemmer en heeft zijn laatste verzoek gedaan op donderdag 30 maart 2017 om 10:00 GMT.

Wanneer een nieuw verzoek van een gebruiker binnenkomt, moet de snelheidsbegrenzer een aantal dingen doen om het gebruik bij te houden. Het zou de hash van Redis halen en de beschikbare tokens opnieuw vullen op basis van een gekozen navulsnelheid en de tijd van het laatste verzoek van de gebruiker. Vervolgens wordt de hash bijgewerkt met de tijdstempel van het huidige verzoek en het nieuwe aantal beschikbare tokens. Wanneer het aantal beschikbare tokens tot nul daalt, weet de snelheidsbegrenzer dat de gebruiker de limiet heeft overschreden.

Als de token-emmer van gebruiker 1 sneller leegloopt dan deze wordt bijgevuld en er geen tokens meer zijn, heeft gebruiker 1 de snelheidslimiet overschreden.

Ondanks de elegantie en de kleine geheugenafdruk van het token bucket-algoritme zijn de bewerkingen van Redis niet atomair. In een gedistribueerde omgeving creëert het "lezen en schrijven" -gedrag een race-situatie, wat betekent dat de snelheidsbegrenzer soms te soepel kan zijn.

Als er nog maar één token over is en de redisactiviteiten van twee servers doorschieten, worden beide verzoeken doorgelaten.

Stel je voor dat er slechts één beschikbaar token voor een gebruiker was en dat die gebruiker meerdere verzoeken had gedaan. Als twee afzonderlijke processen aan elk van deze verzoeken zouden voldoen en tegelijkertijd het beschikbare tokenaantal zouden lezen voordat een van hen het zou bijwerken, zou elk proces denken dat de gebruiker nog een enkel token over had en dat ze de snelheidslimiet niet hadden bereikt.

Onze token bucket-implementatie zou atomiciteit kunnen bereiken als elk proces een Redis-slot zou halen voor de duur van zijn Redis-activiteiten. Dit zou echter ten koste gaan van het gelijktijdig vertragen van aanvragen van dezelfde gebruiker en het introduceren van een andere laag van complexiteit. Als alternatief kunnen we de Redis-bewerkingen van de token-emmer atoom maken via Lua-scripts. Voor de eenvoud besloot ik echter de onnodige complicaties van het toevoegen van een andere taal aan onze codebase te vermijden.

Vaste venstertellers

Als tweede benadering overwoog ik vaste venstertellers. Het is een eenvoudig, geheugenefficiënt algoritme dat het aantal verzoeken van een afzender registreert dat zich binnen het tijdsinterval van de snelheidslimiet voordoet. In tegenstelling tot het token bucket-algoritme zijn de Redis-bewerkingen van deze aanpak atomair. Elk verzoek verhoogt een Redis-sleutel met de tijdstempel van het verzoek. Een gegeven Redis-sleutel kan er zo uitzien:

Gebruiker 1 heeft 1 verzoek gedaan tussen 10:00:00 GMT en 10:00:59 GMT op donderdag 30 maart 2017.

Wanneer we het aantal aanvragen voor een bepaalde tijdstempel verhogen, vergelijken we de waarde ervan met onze tarieflimiet om te beslissen of we het verzoek weigeren. We zouden Redis ook vertellen de sleutel te laten vervallen wanneer de huidige minuut voorbij is om ervoor te zorgen dat de oude tellers niet voor altijd blijven bestaan.

Wanneer de waarde van de laatste Redis-sleutel de verzoekdrempel overschrijdt, heeft gebruiker 1 de snelheidslimiet overschreden.

Hoewel de fixed window-benadering een eenvoudig mentaal model biedt, kan het soms het dubbele aantal toegestane aanvragen per minuut doorlaten. Als onze tarieflimiet bijvoorbeeld 5 verzoeken per minuut zou zijn en een gebruiker 5 verzoeken om 11:00:59 heeft gedaan, kunnen ze 5 meer verzoeken doen om 11:01:00 omdat een nieuwe teller begint aan het begin van elke minuut. Ondanks een limiet van 5 aanvragen per minuut, hebben we nu 10 aanvragen in minder dan een minuut toegestaan!

Als we verzoeken in vaste minutenvensters tellen, kunnen we tot twee keer het aantal toegestane aanvragen per minuut doorlaten.

We kunnen dit probleem voorkomen door een andere tarieflimiet toe te voegen met een kleinere drempel en een kortere handhavingsperiode - bijv. 2 verzoeken per seconde naast 5 verzoeken per minuut - maar dit zou de snelheidslimiet te ingewikkeld maken. Ongetwijfeld zou het ook een te zware beperking opleggen aan hoe vaak de gebruiker verzoeken kan doen.

Schuifraam log

De uiteindelijke implementatie van de snelheidsbegrenzer die ik overwoog, optimaliseert voor nauwkeurigheid - het slaat gewoon een tijdstempel op voor elk verzoek. Zoals Peter Hayes beschrijft, konden we alle verzoeken van een gebruiker efficiënt volgen in een enkele gesorteerde set.

De drie verzoeken van gebruiker 1 op donderdag 30 maart 2017 om 10:00:00, 10:00:54 en 10:01:38 GMT worden gesorteerd op microtijd van Unix.

Wanneer de webtoepassing een aanvraag verwerkt, wordt een nieuw lid in de gesorteerde set ingevoegd met een sorteerwaarde van de tijdstempel van de microseconde Unix. Hiermee kunnen we alle leden van de set met verouderde tijdstempels efficiënt verwijderen en daarna de grootte van de set tellen. De grootte van de gesorteerde set is dan gelijk aan het aantal aanvragen in het meest recente schuifvenster.

Wanneer de grootte van de gesorteerde set van gebruiker 1 de verzoekdrempel overschrijdt, heeft gebruiker 1 de snelheidslimiet overschreden.

Zowel dit algoritme als de vaste venstertellers benaderen een atomaire "schrijf-en-dan-lees" Redis-bewerkingsvolgorde, maar de eerste produceert een opmerkelijk neveneffect. De snelheidsbegrenzer blijft namelijk verzoeken tellen, zelfs nadat de gebruiker de snelheidslimiet overschrijdt. Ik voelde me op mijn gemak met dit gedrag, omdat het een verbod op een kwaadwillende gebruiker zou verlengen in plaats van hun verzoeken door te laten zodra het tijdvenster was verstreken.

Hoewel de precisie van de logboekbenadering van het schuifvenster nuttig kan zijn voor een API voor ontwikkelaars, laat het een aanzienlijk grote geheugenvoetafdruk achter omdat het voor elke aanvraag een waarde opslaat. Dit was niet ideaal voor Figma. Een enkele tarieflimiet van 500 verzoeken per dag per gebruiker op een website met 10.000 actieve gebruikers per dag zou hypothetisch kunnen betekenen dat er 5.000.000 waarden worden opgeslagen in Redis. Als elke opgeslagen tijdstempelwaarde in Redis zelfs een geheel getal van 4 bytes zou zijn, zou dit ~ 20 MB kosten (4 bytes per tijdstempel * 10.000 gebruikers * 500 aanvragen / gebruiker = 20.000.000 bytes).

Schuifraam tellers

Uiteindelijk hebben de laatste twee snelheidslimiterbenaderingen - vaste venstertellers en glijdend vensterlogboek - het algoritme geïnspireerd dat de spammers tegenhield. We tellen verzoeken van elke afzender met behulp van meerdere vaste tijdvensters 1/60 van de grootte van het tijdvenster van onze tarieflimiet.

Als we bijvoorbeeld een uurtarieflimiet hebben, verhogen we tellers die specifiek zijn voor de huidige Unix-minutentijdstempel en berekenen we de som van alle tellers in het afgelopen uur wanneer we een nieuw verzoek ontvangen. Om onze geheugenvoetafdruk te verkleinen, slaan we onze tellers op in een Redis-hash - ze bieden een uiterst efficiënte opslag wanneer ze minder dan 100 sleutels hebben. Wanneer elk verzoek een teller in de hash verhoogt, stelt deze ook in dat de hash een uur later vervalt. In het geval dat een gebruiker elke minuut een verzoek indient, kan de hash van de gebruiker groot worden van vasthouden aan tellers voor voorbije tijdstempels. We voorkomen dit door deze tellers regelmatig te verwijderen wanneer er een aanzienlijk aantal is.

Wanneer de som van de tellers met tijdstempels in het afgelopen uur de verzoekdrempel overschrijdt, heeft gebruiker 1 de snelheidslimiet overschreden.

Laten we het geheugengebruik van dit algoritme vergelijken met onze berekening van het logboekalgoritme van het schuifvenster. Als we een tarieflimiet van 500 verzoeken per dag per gebruiker op een website met 10.000 actieve gebruikers hebben, zouden we hoogstens ~ 600.000 waarden in Redis moeten opslaan. Dat komt uit op een geheugenvoetafdruk van ~ 2,4 MB (4 bytes per teller * 60 tellers * 10.000 gebruikers = 2.400.000 bytes). Dit is een beetje meer schaalbaar.

Praktische overwegingen

Met behulp van vaste venstertellers met een 1:60 verhouding tussen het tijdvenster van de teller en het handhavingstijdvenster van de snelheidslimiet, was onze snelheidsbegrenzer tot op de seconde nauwkeurig en minimaliseerde het geheugengebruik aanzienlijk. In de praktijk echter, een groot handhavingstijdvenster - b.v. één uur - verminderde de precisie van de snelheidsbegrenzer enigszins. Dit wordt het best geïllustreerd aan de hand van een voorbeeld: voor een tarieflimiet per uur, wanneer de tariefbegrenzer het gebruik om 11:00:35 controleert, negeert het de verzoeken die plaatsvonden tussen 10:00:00 en 10:00:59.

Als we verzoeken tellen in 60 vensters met een vaste minuut en het aantal verzoeken controleren wanneer we ons binnen een venster met een vaste minuut bevinden, kunnen we het totale aantal verzoeken in het afgelopen uur onderschatten. Hierboven negeert de snelheidsbegrenzer de drie verzoeken die plaatsvonden tussen 10:00:00 en 10:00:59.

Deze lichte mate van variabele clementie - tot 59 seconden - kan acceptabel zijn, afhankelijk van uw gebruik. In onze situatie gaven we er echter de voorkeur aan dat onze tariefbegrenzer soms een beetje ruwer was in plaats van enigszins soepel, dus ik berekende de som van alle tellers in het laatste uur en één minuut wanneer de huidige tijdstempel niet deelbaar was door 60. Variabel restrictiviteit zou zelfs nuttig kunnen zijn om programmatische scripting tegen de site te ontmoedigen.

Ten slotte moesten we nadenken over hoe te reageren op gebruikers die de tarieflimiet overschreden. Traditioneel reageren webapplicaties op verzoeken van gebruikers die de snelheidslimiet overschrijden met een HTTP-antwoordcode van 429. Onze snelheidsbegrenzer deed dat aanvankelijk ook. Maar in het geval van de spamaanval van Figma, zagen onze aanvallers de reactiecode veranderen van 200 naar 429 en creëerden eenvoudig nieuwe accounts om de snelheidsbeperking op hun geblokkeerde accounts te omzeilen. In reactie daarop hebben we een schaduwverbod geïmplementeerd: aan het oppervlak bleven de aanvallers een HTTP HTTP-antwoordcode ontvangen, maar achter de schermen stopten we gewoon met het verzenden van documentuitnodigingen nadat ze de snelheidslimiet hadden overschreden.

Hoewel de spamaanval vooralsnog voorbij is, kunnen en zullen nieuwe soorten incidenten in de toekomst plaatsvinden en we zullen onze snelheidsbegrenzer blijven aanpassen als dat nodig is.

Zoals moeilijke technische problemen zoals deze aanpakken? Figma bouwt een browsergebaseerd samenwerkingsontwerpgereedschap en we zijn aan het inhuren! Als je dit verhaal leuk vindt, abonneer je dan hier om updates te ontvangen wanneer we nieuwe redactionele inhoud publiceren.