O abordare alternativă a limitării ratelor

Cu câteva săptămâni în urmă, la Figma, am experimentat primul nostru atac de spam. Aceasta a dovedit valoarea limitatorului de viteză al lui Figma și, în cele din urmă, a pus capăt glumii de lungă durată pe care am construit-o în zadar.

În timpul atacului, spammerii au trimis invitații nesolicitate pentru documente la sute de adrese de e-mail. Dacă n-am fi descoperit atacul, am fi putut face față unei creșteri uriașe a costurilor noastre de livrare și a unei scăderi a reputației expeditorului de e-mail. Din fericire, am obținut atentia de la început și am evitat acest rezultat, deoarece limitatorul nostru de rate a detectat flamry-ul solicitărilor de către spammeri.

Sistemul nostru de limitare a ratelor este de natură casnică și aș dori să explic designul său în cazul în care este util pentru alții. Acesta combină câteva tehnici standard pentru a controla viteza cu care persoanele emit cereri către serverul dvs. și este relativ precisă, simplă și eficientă în spațiu. Dacă sunteți o companie care creează aplicații web la scara consumatorului, limitatorul nostru de rate poate împiedica utilizatorii să afecteze disponibilitatea site-ului dvs. web cu o serie de solicitări. De asemenea, se întâmplă să fie excelent la oprirea atacurilor de spam, așa cum am descoperit.

Pentru cei care nu sunt familiarizați, un limitator de viteză stabilește câte solicitări ale unui expeditor - acesta ar putea fi un utilizator sau o adresă IP - poate fi emis într-o fereastră specifică de timp (de exemplu, 25 de solicitări pe minut). În cazul lui Figma, trebuia să:

  • stocați datele extern, astfel încât mai multe mașini care rulează aplicația noastră web să le poată partaja
  • nu încetinește considerabil cererile web
  • ejectează eficient date depășite
  • limitează cu exactitate utilizarea excesivă a aplicației noastre web
  • folosiți cât mai puțină memorie posibilă

Primele trei cerințe au fost ușor de îndeplinit. La Figma, folosim două magazine de date externe - Redis și PostgreSQL - iar Redis a fost locația mai bună pentru a salva datele de urmărire. Redis este un depozit de date în memorie care oferă lecturi și scrieri extrem de rapide relativ la PostgreSQL, o bază de date relațională pe disc. Și mai bine, este simplu să specifici când Redis ar trebui să șteargă datele expirate.

Găsirea unei modalități de a satisface ultimele două cerințe - controlul precis al traficului web și minimizarea utilizării memoriei - a fost mai mult o provocare. Iată implementările limitate de viteză existente pe care le-am avut în vedere:

  • Găleată cu jetoane
  • Contoare de ferestre fixe
  • Jurnalul ferestrei glisante

Să ne uităm la modul în care fiecare dintre ele funcționează și să le comparăm în ceea ce privește precizia și utilizarea memoriei. Acest lucru ne va oferi un context pentru abordarea finală pe care am luat-o pentru a construi limitatorul de viteză care ne-a scutit de spameri.

Găleată cu jetoane

O simplă căutare pe Google pentru „algoritmul limită de viteză” ne indică spre algoritmul clasic de cupă de jeton (sau găleată scurgeră ca algoritm de contor). Pentru fiecare utilizator unic, am înregistra ultima sa solicitare a mărcii de timp Unix și numărul de jetoane disponibile într-un haș în Redis. Am depozita aceste două valori într-un hash, mai degrabă decât două taste Redis separate pentru eficiența memoriei. Un exemplu de haș ar arăta astfel:

Utilizatorul 1 a rămas două jetoane în găleata de jeton și și-a făcut ultima solicitare joi, 30 martie 2017, la ora 10:00 GMT.

Ori de câte ori o nouă solicitare ajunge de la un utilizator, limitatorul de viteză ar trebui să facă o serie de lucruri pentru a urmări utilizarea. Ar preveni hașul de la Redis și ar reumple token-urile disponibile pe baza unei rate de reumplere alese și a timpului ultimei solicitări a utilizatorului. Apoi, va actualiza hash-ul cu ora actuală a cererii curente și cu noul număr de jetoane disponibil. Când numărul de jetoane disponibil scade la zero, limitatorul de viteză știe că utilizatorul a depășit limita.

Dacă galeata cu jetonul utilizatorului 1 se golește mai repede decât se reumple și nu se lasă jetoane, utilizatorul 1 a depășit limita de viteză.

În ciuda eleganței și algoritmului mic de memorie al algoritmului de galeată, operațiile sale Redis nu sunt atomice. Într-un mediu distribuit, comportamentul de „citire și apoi scriere” creează o condiție de cursă, ceea ce înseamnă că limitatorul de viteză poate fi uneori prea indulgent.

Dacă rămâne doar un singur token și operațiile Redis ale două servere se întrepătrund, ambele solicitări ar fi acceptate.

Imaginați-vă dacă a fost un singur jeton disponibil pentru un utilizator și acel utilizator a emis mai multe solicitări. Dacă două procese separate au servit fiecare din aceste solicitări și au citit concomitent numărul de jetoane disponibile înainte ca oricare dintre ele să-l actualizeze, fiecare proces ar crede că utilizatorul a avut un singur simbol stânga și că nu au atins limita de rată.

Punerea în aplicare a găleții noastre jetoane ar putea atinge atomicitatea dacă fiecare proces ar obține un blocaj Redis pe durata operațiunilor sale Redis. Totuși, acest lucru ar veni în detrimentul încetinirii cererilor simultane din partea aceluiași utilizator și a introducerii unui alt strat de complexitate. În mod alternativ, am putea face ca operațiunile Redis ale găleții token să fie atomice prin scripturi Lua. Pentru simplitate, însă, am decis să evit complicațiile inutile de a adăuga o altă limbă la baza noastră de coduri.

Contoare de ferestre fixe

Ca o a doua abordare, am considerat contoare de ferestre fixe. Este un algoritm simplu, eficient în memorie, care înregistrează numărul de solicitări ale unui expeditor care au apărut în intervalul de timp limită de rată. Spre deosebire de algoritmul bucket token, operațiunile Redis ale acestei abordări sunt atomice. Fiecare solicitare va crește o cheie Redis care includea ora de timp a cererii. O cheie Redis dată ar putea arăta astfel:

Utilizatorul 1 a făcut 1 cerere între 10:00:00 GMT și 10:00:59 GMT joi, 30 martie 2017.

La creșterea numărului de cereri pentru un moment dat, am compara valoarea acesteia cu limita noastră de rată pentru a decide dacă respingem cererea. De asemenea, i-am spune lui Redis să expire cheia atunci când a trecut minutul curent pentru a ne asigura că contoarele neperformante nu vor rămâne pentru totdeauna.

Când valoarea ultimei chei Redis depășește pragul solicitării, utilizatorul 1 a depășit limita de rată.

Deși abordarea ferestrei fixe oferă un model mental simplu, poate uneori să dubleze de două ori numărul de solicitări permise pe minut. De exemplu, dacă limita noastră de rată a fost de 5 solicitări pe minut și un utilizator a făcut 5 solicitări la 11:00:59, ar putea face încă 5 solicitări la 11:01:00, deoarece un contor nou începe la începutul fiecărui minut. În pofida unei limite de 5 solicitări pe minut, acum am permis 10 solicitări în mai puțin de un minut!

Dacă numărăm cererile în ferestrele de minute fixe, am putea trece până la de două ori numărul de solicitări permise pe minut.

Am putea evita această problemă adăugând o altă limită de rată cu un prag mai mic și o fereastră de executare mai scurtă - de ex. 2 cereri pe secundă, în plus, 5 solicitări pe minut, dar acest lucru ar complica limita de tarif. În mod evident, aceasta ar impune, de asemenea, o restricție prea severă cu privire la cât de des utilizatorul ar putea face solicitări.

Jurnalul ferestrei glisante

Ultima implementare a limitatorului de viteză pe care am considerat că este optimizată pentru acuratețe - doar stochează o marcă de timp pentru fiecare cerere. După cum descrie Peter Hayes, am putea urmări eficient toate solicitările utilizatorului într-un singur set sortat.

Cele trei solicitări ale utilizatorului 1, joi, 30 martie 2017, la ora 10:00:00, 10:00:54 și 10:01:38 GMT sunt sortate după ora de timp microsecundă Unix.

Când aplicația web prelucrează o solicitare, aceasta ar insera un nou membru în setul sortat cu o valoare de sortare a momentului de timp microsecund Unix. Acest lucru ne-ar permite să ștergem în mod eficient toți membrii setului cu timpe-date depășite și să numărăm după aceea dimensiunea setului. Mărimea setului sortat ar fi apoi egală cu numărul de solicitări din cea mai recentă fereastră glisantă a timpului.

Când dimensiunea setului utilizatorului 1 sortat depășește pragul solicitării, utilizatorul 1 a depășit limita de rată.

Atât acest algoritm, cât și abordarea contoarelor de ferestre fixe împărtășesc o secvență de operare Redis atomică „scrie-și-apoi-citită”, dar prima produce un efect secundar notabil. Anume, limitatorul de rate continuă să numere solicitările chiar și după ce utilizatorul depășește limita de tarif. Am fost confortabil cu acest comportament, întrucât ar extinde pur și simplu interdicția unui utilizator rău intenționat, decât să-i trimit cererile imediat ce trece timpul.

Deși precizia abordării jurnalului ferestrei glisante poate fi utilă pentru un API pentru dezvoltatori, lasă o amprentă de memorie considerabil de mare, deoarece stochează o valoare pentru fiecare solicitare. Acest lucru nu a fost ideal pentru Figma. O limită unică de 500 de solicitări pe zi pe utilizator pe un site web cu 10.000 de utilizatori activi pe zi ar putea însemna, ipotetic, stocarea a 5.000.000 de valori în Redis. Dacă fiecare valoare de timp memorată stocată în Redis ar fi chiar un număr întreg de 4 biți, aceasta ar lua ~ 20 MB (4 octeți pe timestamp * 10.000 utilizatori * 500 solicitări / utilizator = 20.000.000 octeți).

Contoare pentru geamuri glisante

În cele din urmă, ultimele două abordări ale limitatorului de viteză - contoare de ferestre fixe și jurnal de ferestre glisante - au inspirat algoritmul care a oprit spamerii. Numărăm cererile de la fiecare expeditor folosind mai multe ferestre de timp fix 1/60 de dimensiunea ferestrei de timp a limitei noastre de rată.

De exemplu, dacă avem o limită de viteză pe oră, creștem contoarele specifice momentului de marcare minut Unix și calculăm suma tuturor contoarelor din ultima oră când primim o nouă solicitare. Pentru a ne reduce amprenta de memorie, stocăm contoarele noastre într-un hash Redis - acestea oferă o stocare extrem de eficientă atunci când au mai puțin de 100 de taste. Când fiecare cerere crește un contor în hash, setează și hașa să expire o oră mai târziu. În cazul în care un utilizator face solicitări în fiecare minut, hașa utilizatorului poate crește de la a ține la contoare pentru marci de timp trecute. Îl prevenim prin eliminarea regulată a acestor contoare atunci când există un număr considerabil de ele.

Atunci când suma contoarelor cu timestampe din ultima oră depășește pragul solicitării, utilizatorul 1 a depășit limita ratei.

Să comparăm utilizarea memoriei acestui algoritm cu calculul nostru din algoritmul de jurnal al ferestrei glisante. Dacă avem o limită de rată de 500 de solicitări pe zi pe utilizator pe un site web cu 10.000 de utilizatori activi, cel mult ar trebui să stocăm ~ 600.000 de valori în Redis. Aceasta se datorează unei amprente de memorie de ~ 2,4 MB (4 octeți pe contor * 60 contoare * 10 000 utilizatori = 2,400,000 octeți). Acest lucru este ceva mai scalabil.

Consideratii practice

Utilizând contoare de ferestre fixe, cu un raport de 1:60 între fereastra de timp a contorului și fereastra de timp de aplicare a limitei de rată, limitatorul nostru de viteză a fost exact până la al doilea și a redus în mod semnificativ utilizarea memoriei. În practică, însă, o fereastră mare de timp de aplicare - de ex. o oră - a redus ușor precizia limitatorului de viteză. Acest lucru este ilustrat cel mai bine printr-un exemplu: pentru o limită de oră, când limitatorul de viteză verifică utilizarea la 11:00:35, ignoră solicitările care au avut loc între 10:00:00 și 10:00:59.

Dacă numărăm solicitări în 60 de ferestre minute fixe și verificăm numărul de solicitări atunci când ne aflăm într-o fereastră de un minut fix, este posibil să subcontestăm numărul total de solicitări în ultima oră. Mai sus, limitatorul de rate ignoră cele trei solicitări apărute între orele 10:00:00 și 10:00:59.

Acest grad ușor de clemență variabilă - până la 59 de secunde - poate fi acceptat în funcție de cazul dvs. de utilizare. Cu toate acestea, în situația noastră, am preferat ca limitatorul nostru de viteză să fie uneori mai dur, în loc de ușor indulgent, așa că am calculat suma tuturor contoarelor în ultima oră și un minut, ori de câte ori intervalul de timp actual nu era divizibil cu 60. Variabilă restrictivitatea ar putea fi chiar utilă pentru a descuraja scripturile programatice împotriva site-ului.

În cele din urmă, a trebuit să reflectăm cum să răspundem utilizatorilor care au depășit limita de tarif. În mod tradițional, aplicațiile web răspund la solicitările utilizatorilor care depășesc limita ratei cu un cod de răspuns HTTP de 429. Limitatorul nostru de rate a făcut-o inițial. Dar în cazul atacului de spam al Figma, atacatorii noștri au văzut că codul de răspuns se schimbă de la 200 la 429 și au creat pur și simplu noi conturi pentru a evita limitarea ratei conturilor blocate. Drept răspuns, am implementat o interdicție de umbră: La suprafață, atacatorii au continuat să primească un cod de răspuns HTTP de 200, dar în culise am oprit pur și simplu să trimitem invitații la documente după ce au depășit limita ratei.

În timp ce atacul de spam a luat sfârșit deocamdată, noi tipuri de incidente pot și se vor întâmpla în viitor și vom continua să ne ajustăm limitatorul de viteză, după cum este necesar.

Vrei să abordezi probleme dificile de inginerie ca asta? Figma construiește un instrument de design colaborativ bazat pe browser și angajăm! Dacă vă place această poveste, abonați-vă aici pentru a primi actualizări atunci când publicăm conținut editorial nou.