En alternativ tilgang til satsbegrænsning

For et par uger siden hos Figma oplevede vi vores første spam-angreb nogensinde. Dette beviste værdien af ​​Figmas takstbegrænser og stoppede til sidst den langvarige vittighed, som jeg havde bygget den forgæves.

Under angrebet sendte spammere uopfordrede invitationer til dokumenter til scoringer af e-mail-adresser. Havde vi ikke opdaget angrebet, kunne vi have haft en enorm stigning i vores leveringsomkostninger og et fald i vores e-mail-afsenders omdømme. Heldigvis fik vi tidligt angrebet af angrebet og undgik dette resultat, fordi vores takstbegrænser opdagede spammernes gnister af anmodninger.

Vores takstbegrænsningssystem er hjemmearbejdet, og jeg vil gerne forklare dets design, hvis det er nyttigt for andre. Det kombinerer et par standardteknikker til at kontrollere den hastighed, hvormed folk sender anmodninger til din server, og den er relativt nøjagtig, enkel og pladseffektiv. Hvis du er en virksomhed, der bygger webapplikationer i forbrugerskala, kan vores takstbegrænser forhindre brugere i at skade dit websteds tilgængelighed med en række anmodninger. Det er også tilfældigt at være god til at stoppe spamangreb, som vi opdagede.

For dem, der ikke er kendte, lukker en takstbegrænser hvor mange anmodninger en afsender - dette kan være en bruger eller en IP-adresse - der kan udsendes i et bestemt tidsvindue (f.eks. 25 anmodninger pr. Minut). I Figmas tilfælde var det også nødvendigt at:

  • gem data eksternt, så de flere maskiner, der kører vores webapplikation, kunne dele dem
  • ikke mærkbart nedsætte webanmodninger
  • skubber ud forældede data effektivt
  • nøjagtigt begrænse overdreven brug af vores webapplikation
  • brug så lidt hukommelse som muligt

De tre første krav var lette at imødekomme. Hos Figma bruger vi to eksterne datalagre - Redis og PostgreSQL - og Redis var det bedre sted at gemme sporingsdata. Redis er en datalager i hukommelsen, der tilbyder ekstremt hurtig læsning og skrivning i forhold til PostgreSQL, en relationsdatabase på disk. Endnu bedre er det nemt at specificere, hvornår Redis skal slette udløbne data.

At finde en måde at opfylde de to sidste krav - nøjagtigt at kontrollere webtrafik og minimere hukommelsesforbruget - var mere en udfordring. Her er de eksisterende implementering af takstbegrænsere, jeg overvejede:

  • Token spand
  • Faste vinduetællere
  • Log med glidende vinduer

Lad os se på, hvordan hver af dem fungerer og sammenligne dem med hensyn til nøjagtighed og hukommelsesforbrug. Dette vil give os en vis kontekst for den endelige tilgang, vi tog for at opbygge den hastighedsbegrænser, der skånede os for spammerne.

Token spand

En simpel Google-søgning efter “rate limit algoritm” peger os på den klassiske token bucket-algoritme (eller lækkende spand som en meteralgoritme). For hver unik bruger registrerer vi deres sidste anmodning's Unix-tidsstempel og tilgængeligt tokenantal inden for en hash i Redis. Vi lagrer disse to værdier i en hash i stedet for som to separate Redis-taster til hukommelseseffektivitet. Et eksempel på hash ser sådan ud:

Bruger 1 har to symboler tilbage i deres token spand og fremsatte deres sidste anmodning torsdag 30. marts 2017 kl 10:00 GMT.

Hver gang en ny anmodning ankommer fra en bruger, skulle takstbegrænseren gøre et antal ting for at spore brugen. Det vil hente hash'en fra Redis og genopfylde de tilgængelige tokens baseret på en valgt påfyldningshastighed og tidspunktet for brugerens sidste anmodning. Derefter vil den opdatere hash med den aktuelle anmodnings tidsstempel og det nye tilgængelige tokenantal. Når det tilgængelige tokenantal falder til nul, ved hastighedsbegrænseren, at brugeren har overskredet grænsen.

Hvis Bruger 1's token-spand tømmes hurtigere, end den genopfylder, og der ikke er nogen tokener tilbage, har Bruger 1 overskredet takstgrænsen.

På trods af token-spandalgoritmens elegance og lille hukommelsesfodaftryk er dens Redis-operationer ikke atomare. I et distribueret miljø skaber adfærd "læse-og-derefter-skriv" en race-betingelse, hvilket betyder, at takstbegrænseren til tider kan være for mild.

Hvis der kun er et enkelt token tilbage, og to serveres Redis-operationer flædes sammen, ville begge anmodninger blive sluppet igennem.

Forestil dig, om der kun var et tilgængeligt token for en bruger, og at brugeren udsendte flere anmodninger. Hvis to separate processer tjente hver af disse anmodninger og samtidig læste det tilgængelige tokenantal, før en af ​​dem opdaterede det, ville hver proces tro, at brugeren havde et enkelt token tilbage, og at de ikke havde ramt hastighedsgrænsen.

Vores token-spandimplementering kunne opnå atomicitet, hvis hver proces skulle hente en Redis-lås under varigheden af ​​dens Redis-operationer. Dette vil dog komme på bekostning af at bremse samtidige anmodninger fra den samme bruger og indføre et andet lag med kompleksitet. Alternativt kan vi lave token spandens Redis-operationer atomiske via Lua-scripting. For enkelheds skyld besluttede jeg dog at undgå de unødvendige komplikationer ved at tilføje et andet sprog til vores codebase.

Faste vinduetællere

Som en anden tilgang overvejede jeg faste vinduetællere. Det er en enkel, hukommelseseffektiv algoritme, der registrerer antallet af anmodninger fra en afsender, der forekommer i hastighedsgrænsens tidsinterval. I modsætning til token-spand-algoritmen, er denne tilgangs Redis-operationer atomære. Hver anmodning ville øge en Redis-nøgle, der indeholdt anmodningens tidsstempel. En given Redis-nøgle kan se sådan ud:

Bruger 1 har fremsat 1 anmodning mellem 10:00:00 GMT og 10:00:59 GMT torsdag 30. marts 2017.

Når vi øger antallet af anmodninger for en given tidsstempel, sammenligner vi dens værdi med vores kursgrænse for at beslutte, om anmodningen skal afvises. Vi vil også bede Redis om at udløbe nøglen, når det aktuelle minut gik for at sikre, at uaktuelle tællere ikke holder sig for evigt.

Når værdien af ​​den seneste Redis-nøgle overstiger anmodningstærsklen, har Bruger 1 overskredet takstgrænsen.

Selvom den faste vinduesmetode tilbyder en ligetil mental model, kan den undertiden slippe dobbelt så mange tilladte anmodninger pr. Minut. For eksempel, hvis vores kursgrænse var 5 anmodninger pr. Minut, og en bruger fremsatte 5 anmodninger kl. 11:00:59, kunne de fremsætte yderligere 5 anmodninger kl. 11:01:00, fordi en ny tæller begynder i starten af ​​hvert minut. På trods af en takstgrænse på 5 anmodninger pr. Minut, har vi nu tilladt 10 anmodninger på mindre end et minut!

Hvis vi tæller anmodninger i faste minutvinduer, kan vi slippe op til dobbelt så mange tilladte anmodninger pr. Minut.

Vi kunne undgå dette problem ved at tilføje en anden satsgrænse med en mindre tærskel og kortere håndhævelsesvindue - f.eks. 2 anmodninger pr. Sekund ud over 5 anmodninger pr. Minut - men dette ville overkomplicere takstgrænsen. Det ville sandsynligvis også pålægge en for streng restriktion for, hvor ofte brugeren kunne fremsætte anmodninger.

Log med glidende vinduer

Den endelige takstbegrænserimplementering overvejede jeg som optimeret for nøjagtighed - den gemmer bare et tidsstempel for hver anmodning. Som Peter Hayes beskriver, kunne vi effektivt spore alle brugernes anmodninger i et enkelt sorteret sæt.

Bruger 1's tre anmodninger torsdag 30. marts 2017 kl. 10:00:00, 10:00:54 og 10:01:38 GMT er sorteret efter Unix-mikrosekundets tidsstempel.

Når webapplikationen behandler en anmodning, vil den indsætte et nyt medlem i det sorterede sæt med en sorteringsværdi af Unix-mikrosekundets tidsstempel. Dette vil give os mulighed for effektivt at fjerne alle sættets medlemmer med forældede tidsstempler og tælle størrelsen på sættet bagefter. Størrelsen på det sorterede sæt vil derefter være lig med antallet af anmodninger i det seneste glidende tidsvindue.

Når størrelsen på bruger 1's sorterede sæt overskrider anmodningstærsklen, har bruger 1 overskredet takstgrænsen.

Både denne algoritme og den faste vinduetæller-tilgang deler en atomisk "skriv-og-derefter-læst" -redis-operationssekvens, men førstnævnte giver en bemærkelsesværdig bivirkning. Navnlig fortsætter takstbegrænseren med at tælle anmodninger, selv efter at brugeren har overskredet takstgrænsen. Jeg var tilpas med denne opførsel, da det bare ville udvide et forbud mod en ondsindet bruger snarere end at lade deres anmodninger komme igennem, så snart tidsvinduet var gået.

Mens præcisionen i glidevindelog-tilgangen kan være nyttig for en udvikler-API, efterlader den et betydeligt stort hukommelsesfodaftryk, fordi det gemmer en værdi for enhver anmodning. Dette var ikke ideelt for Figma. En enkelt taksegrænse på 500 anmodninger pr. Dag pr. Bruger på et websted med 10.000 aktive brugere om dagen kunne hypotetisk betyde, at 5.000.000 værdier lagres i Redis. Hvis hver gemt tidsstempelværdi i Redis endda var et 4-bytes heltal, ville dette tage ~ 20 MB (4 byte pr. Tidsstempel * 10.000 brugere * 500 anmodninger / bruger = 20.000.000 byte).

Skydevinduer

I sidste ende nærmet de sidste to hastighedsbegrænsere - faste vinduetællere og glidende vindueslog - algoritmen, der stoppede spammerne. Vi tæller anmodninger fra hver afsender ved hjælp af flere faste tidsvinduer 1 / 60. størrelsen på vores takstgræns tidsvindue.

For eksempel, hvis vi har en timeprisgrænse, øger vi tællere, der er specifikke for det aktuelle Unix-minutstempel og beregner summen af ​​alle tællere i den sidste time, når vi modtager en ny anmodning. For at reducere vores hukommelsesfodaftryk gemmer vi vores tællere i en Redis-hash - de tilbyder ekstremt effektiv opbevaring, når de har færre end 100 nøgler. Når hver anmodning øger en tæller i hash, indstiller den også hash'en til at udløbe en time senere. I tilfælde af at en bruger fremsætter anmodninger hvert minut, kan brugerens hash blive stort fra at holde fast i tællere til svundne tidsstempler. Vi forhindrer dette ved regelmæssigt at fjerne disse tællere, når der er et betydeligt antal af dem.

Når summen af ​​tællere med tidsstempler i den sidste time overstiger anmodningstærsklen, har Bruger 1 overskredet takstgrænsen.

Lad os sammenligne hukommelsesanvendelsen af ​​denne algoritme med vores beregning fra loggealgoritmen til skydevinduet. Hvis vi har en takstgrænse på 500 anmodninger pr. Dag pr. Bruger på et websted med 10.000 aktive brugere, er vi højst nødt til at gemme ~ 600.000 værdier i Redis. Det kommer ud til et hukommelsesfodaftryk på ~ 2,4 MB (4 byte pr. Tæller * 60 tællere * 10.000 brugere = 2.400.000 byte). Dette er lidt mere skalerbart.

Praktiske overvejelser

Ved hjælp af faste vinduetællere med 1:60-forholdet mellem tællerens tidsvindue og hastighedsgrænsen for håndhævelsestidsvindue, var vores takstbegrænser nøjagtigt ned til det andet og minimerede hukommelsesbruget markant. I praksis er et stort håndhævelsestidsvindue - f.eks. en time - reduceret lidt nøjagtigheden af ​​hastighedsbegrænseren. Dette illustreres bedst ved hjælp af et eksempel: For en timeprisgrænse, når takstbegrænseren kontrollerer brugen kl. 11:00:35, ignorerer den anmodningerne, der opstod mellem 10:00:00 og 10:00:59.

Hvis vi tæller forespørgsler i 60 faste minutvinduer og kontrollerer antallet af forespørgsler, når vi befinder os inden for et fast minutvindue, kan vi muligvis undertone det samlede antal anmodninger inden for den sidste time. Ovenfor ignorerer takstbegrænseren de tre anmodninger, der opstod mellem 10:00:00 og 10:00:59.

Denne lette grad af variabel lempelse - op til 59 sekunder - kan være acceptabel afhængigt af dit brugssag. I vores situation foretrækkede vi dog, at vores takstbegrænser undertiden var en smule hårdere i stedet for lidt mildere, så jeg beregnet summen af ​​alle tællere i den sidste time og et minut, hver gang den aktuelle tidsstempel ikke kunne deles med 60. Variabel restriktivitet kan endda være nyttigt til at afskrække programmatiske scripting mod webstedet.

Til sidst måtte vi reflektere over, hvordan vi skulle svare på brugere, der overskred takstgrænsen. Traditionelt svarer webapplikationer på anmodninger fra brugere, der overskrider takstgrænsen med en HTTP-svarskode på 429. Vores takstbegrænser gjorde det oprindeligt også. Men i tilfælde af Figmas spamangreb, så vores angribere responskoden ændre sig fra 200 til 429 og oprettede simpelthen nye konti for at omgå takstbegrænsningen på deres blokerede konti. Som svar implementerede vi et skyggeforbud: På overfladen fortsatte angriberne med at modtage en 200 HTTP-svarskode, men bag kulisserne stoppede vi simpelthen med at sende dokumentinvitationer, efter at de overskred satsgrænsen.

Mens spam-angrebet er forbi i øjeblikket, kan og vil nye typer hændelser ske i fremtiden, og vi vil fortsætte med at justere vores takstbegrænser efter behov.

Kan du lide at tackle hårde tekniske problemer som dette? Figma bygger et browserbaseret samarbejdsdesignværktøj, og vi ansætter! Hvis du kan lide denne historie, kan du abonnere her for at få opdateringer, når vi udgiver nyt redaktionelt indhold.