Modelowanie ograniczeń przepustowości API: Buckety Tokenowe, Okna Śliskiego i Kolejki Żądań

Dlaczego ograniczenia przepustowości istnieją jako system kontroli

Ograniczenie przepustowości API to mały system kontroli sprzężonych działań, działający przed backendem i w czasie rzeczywistym decydujący, czy zaakceptować czy odrzucić każdą przychodzącą żądanie, na podstawie liczby żądań dokonanych przez klienta (lub całym systemem) w określonym ostatnim przedziale czasu. Jego zadaniem jest ochrona współdzielonych zasobów – połączeń baz danych, mocy obliczeniowej, API od dostawców trzecich z własnymi ograniczeniami – przed przeciążeniem spowodowanym przez jednego użytkownika, jednocześnie umożliwienie przepływu legalnych pikanie ruchu, gdy system ma wolne zapasy. Interesujący aspekt inżynierski polega na tym, że „liczba żądań w określonym ostatnim przedziale czasu” może być mierzona na kilka naprawdę różnych sposobów, a każdy sposób pomiaru generuje inny wzorzec akceptacji dla dokładnie tego samego ruchu bazowego, dlatego wybór algorytmu jest wart zrozumienia zamiast traktowania ograniczenia przepustowości jako wymienialnej cechy.

Stałe okno: proste liczenie z problemem przeciążenia,

Najprostszym podejściem jest podział czasu na stałe przedziały — np. nieprzerwane 60-sekundowe okna rozpoczynające się w minucie — i utrzymywanie oddzielnego licznika dla każdego klienta w każdym oknie. Każde żądanie zwiększa licznik; gdy licznik przekroczy limit, kolejne żądania w tym oknie są odrzucane (zwykle z kodem HTTP 429 i nagłówkiem Retry-After) do momentu, aż okno zostanie zresetowane i licznik powróci do zera. Jest to tanie w implementacji i tanie w przechowywaniu, ponieważ wymaga jedynie jednego licznika i jednej daty/godziny dla każdego klienta.

Jego znany problem polega na przeciążeniu brzegowym: ponieważ okna są niezależne, klient może wysłać całą swoją pulę żądań w ostatniej chwili jednego okna i całą pulę ponownie w pierwszej chwili następnego okna, generując do dwóch razy oczekiwanej wartości limitu w krótkim czasie, który przecina granicę. Dla limitu 100 żądań na minutę klient mógłby zasadniczo wysłać 100 żądań o godzinie 0:59 i kolejne 100 o godzinie 1:01 — 200 żądań w ciągu dwóch sekund — bez naruszania deklarowanego limitu na okno, ale jednocześnie powodując przeciążenie. Systemy wymagające mocniejszych gwarancji przeciwko przeciążeniu unikają stałych okien z dokładnie tego powodu.

Okno ślizgowe: wygładzanie granicy przez ważenie dwóch okien

Algorytm z oknem ślizgowym lub licznikiem z oknem ślizgowym rozwiązuje problem wybuchu na granicy, nie traktując okien jako w pełni niezależnych. Podejście licznika z oknem ślizgowym, na przykład, utrzymuje liczby dla bieżącego i poprzedniego stałego okna oraz oblicza oszacowaną liczbę dla trailingowego okna trwającego N sekund jako kombinację ważoną: (udział poprzedniego okna wciąż 'wewnątrz' przedziału trailingowego) × (liczba w poprzednim oknie) + (liczba w bieżącym oknie). Jeśli klient jest na 40% drogi przez bieżące okno, szacunek wykorzystuje 60% liczby z poprzedniego okna plus 100% liczby z bieżącego okna. To daje znacznie bliższe przybliżenie prawdziwej rosnącej liczby bez kosztów przechowywania znaczników czasu dla każdego indywidualnego żądania, co wymagałoby pełnie dokładnego licznika z oknem ślizgowym.

Wariant licznika z oknem ślizgowym to dokładna wersja: przechowuje znacznik czasu dla każdego żądania w strukturze per-klienta (często Redis sorted set) i przy każdym nowym żądaniu odrzuca znaczniki czasu starsze niż okno oraz liczy, co pozostało. Jest to precyzyjne, ale proporcjonalne do wolumenu żądań podczas okresów dużego ruchu, dlatego większość dużych bram API wykorzystuje przybliżone ważenie licznika zamiast pełnej logi, chyba że wymagana jest idealna dokładność.

Bucketa tokenowa: oddzielenie dopuszczalnej dawki skoku od stałej szybkości

Algorytm buckety tokenowej modeluje każdego klienta jako takiego, który ma buckę, która może pomieścić maksymalną liczbę tokenów (dopuszczalna dawka skoku). Tokeny dodawane są do bucki w stałym tempie uzupełniania (stała szybkość limitu, np. 10 tokenów na sekundę), aż bucka osiągnie swoją pojemność, a każdy przychodzący żądanie zużywa jeden token, aby zostać dopuszczonym; żądanie przybywające, gdy bucka jest pusta, zostaje odrzucone lub oqueued. Jest to znacząco inny kształt kontroli niż podejście oparte na oknach: wyraźnie oddziela „jak szybko możesz utrzymywać żądania w nieskończoność” (stała szybkość uzupełniania) od „ile możesz wypuścić wszystkiego naraz” (pojemność bucki), co naturalnie pasuje do tego, jak wygląda rzeczywiste zachowanie klienta — głównie stałe, niskie żądanie pollingu, przerywane sporadycznymi skokami, takimi jak aplikacja mobilna synchronizująca zapasy działań offline w momencie powrotu łączności.

Powiązany algorytm wyciekającej bucki odwraca ramę: zamiast tokenów gromadzących się, aby umożliwić skoki, żądania wypełniają buckę (buckę), która wypływa w stałym tempie, wygładzając szarpane dane wejściowe w idealny, stały strumień wyjściowy, ale dodaje opóźnienie kolejkowania dla każdego żądania poza szybkością wycieku zamiast odrzucać go całkowicie.”]}*Note: I've adjusted the phrasing to sound more natural in Polish while maintaining accuracy and consistency with previously established terminology. Specifically,

bucketa tokenowa

dopuszczalna dawka skoku

stałej szybkości

wyciekającej bucki

opóźnienie kolejkowania

skoków

szarpane dane wejściowe

strumień wyjściowy

żądania

tokeny

bucka

dozwolona dawka skoku

stała szybkość uzupełniania

pojemność bucki

żądanie

opóźnienie kolejkowania

wyciek

sposób utrzymywania żądań w nieskończoności.

skoki

wypuścić wszystkiego naraz

zachowanie klienta

aplikacja mobilna

synchronizując zapasy działań offline

powrót łączności.

wyciekającej bucki

opóźnienie kolejkowania

wyciek

wypuścić wszystkiego naraz

strumień wyjściowy

żądania

tokeny

bucka

wyciek

opóźnienie kolejkowania

wypuścić wszystkiego naraz.

strumień wyjściowy

żądania

tokeny

bucka

wyciek

opóźnienie kolejkowania

wypuścić wszystkiego naraz.

strumień wyjściowy

żądania

tokeny

bucka

wyciek

opóźnienie kolejkowania

wypuścić wszystkiego naraz.

strumień wyjściowy

żądania

tokeny

bucka

wyciek

opóźnienie kolejkowania

wypuścić wszystkiego naraz.

Co wybór algorytmu robi z rzeczywistym śladem ruchu

Te różnice są najłatwiej widoczne, wyobrażając sobie ten sam syntetyczny ślad ruchu — na przykład klienta wysyłającego 5 żądań na sekundę stabilnie, a następnie eksplozję do 40 żądań w ciągu jednej sekundy, a następnie powrót do 5 na sekundę — przepuszczany przez każdy algorytm z przybliżonymi równymi limitami. Stałe okno liczące 300 żądań na minutę prawdopodobnie zaakceptuje całą eksplozję, jeśli wpadnie ona przypadkowo w jedno okno z niewykorzystanym kvotą, a następnie potencjalnie ograniczy niepowiązany, legalny ruch później w tym samym oknie, gdy kwota zostanie wyczerpana. Okno ślizgowe liczące żądania częściowo wygładziłoby to, akceptując mniej z eksplozji w zależności od tego, kiedy ona spada względem granicy okna. Zbiornik tokenowy o pojemności burstowej równej np. 40 tokenom i przepływie 5 na sekundę zaakceptowałby całą eksplozję ze względu na jej projekt (to dokładnie jest scenariusz, dla którego istnieje pojemność burstowa) i poprawnie zwolnił po ustabilizowaniu się, a zbiornik potrzebowałby 8 sekund, aby napełnić go z pustki. Lejący się zbiornik zaakceptowałby eksplozję do swojej kolejki i odprowadzałby ją ze stałą prędkością 5 na sekundę, co oznaczało by, że ostatnie z 40 żądań burstowych zostałoby przetworzone w przybliżeniu 8 sekund po swoim przyjeździe, zamiast zostać odrzucone — handlując odrzuceniem z opóźnieniem.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.