Fast tidsvindu-teller forklart
Oppdag hvordan algoritmen for fast tidsvindu-telling fungerer, hvor enkel den er, og hvilke ulemper den kan ha ved håndtering av trafikkøkninger.
Fast tidsvindu-teller forklart er en gratis leksjon i Mønstre for API-ratebegrensning og skalerbarhet på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Mønstre for API-ratebegrensning og skalerbarhet, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Mønstre for API-ratebegrensning og skalerbarhet inneholder totalt 4 leksjoner.
Hvorfor algoritmer?
Rate limiting handler ikke bare om en kontroll som svarer «ja» eller «nei». Det bygger på smarte algoritmer for å styre trafikken. Algoritmene avgjør hvordan og når forespørsler skal tillates eller avvises, slik at rettferdighet og stabilitet ivaretas.
Vi begynner med en av de enkleste: Fixed Window Counter.
Fixed Window Counter: Ideen
Fixed Window Counter er en enkel algoritme for rate limiting. Den deler tiden inn i faste tidsvinduer som ikke overlapper.
- Hvert tidsvindu har sin egen forespørselsteller.
- Når en forespørsel kommer inn, økes telleren for det gjeldende tidsvinduet.
- Hvis telleren overskrider en forhåndsdefinert grense i tidsvinduet, blokkeres flere forespørsler.
Slik telles forespørslene
Se for deg en klokke. For hvert minutt (det faste tidsvinduet vårt) tillater vi for eksempel 10 forespørsler. Når et nytt minutt begynner, tilbakestilles telleren til null.
- Tidsvindu: En bestemt tidsperiode (for eksempel 60 sekunder).
- Grense: Det maksimale antallet forespørsler som tillates i tidsvinduet.
- Teller: Holder oversikt over forespørslene i det gjeldende tidsvinduet.
Det er som en dørvakt på en klubb som bare slipper inn et bestemt antall personer hver time, før tellingen tilbakestilles for neste time.
Eksempel: Grense på 10 RPS
La oss si at grensen er 10 forespørsler per sekund (RPS).
- Tidsvindu 1 (0–1 s): 7 forespørsler er sendt. 3 forespørsler gjenstår.
- Tidsvindu 2 (1–2 s): 12 forespørsler er sendt. De første 10 tillates, og de neste 2 blokkeres.
- Tidsvindu 3 (2–3 s): 5 forespørsler er sendt. Alle tillates.
Ved starten av hvert nye sekund tilbakestilles telleren, uavhengig av aktiviteten i det foregående sekundet.
Grunnleggende tellerlogikk
Her er en enkel Java-klasse som simulerer en forespørselsteller. Den danner grunnlaget for rate-begrenseren vår og holder oversikt over forespørsler innenfor et definert tidsvindu.
import java.time.Instant;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
class FixedWindowCounter {
private final int limit;
private final long windowSizeMillis; // e.g., 60_000 for 1 minute
private final ConcurrentHashMap<Long, AtomicInteger> counters;
public FixedWindowCounter(int limit, long windowSizeMillis) {
this.limit = limit;
this.windowSizeMillis = windowSizeMillis;
this.counters = new ConcurrentHashMap<>();
}
public boolean allowRequest(String userId) {
long currentWindowKey = Instant.now().toEpochMilli() / windowSizeMillis;
// Get or create counter for the current window
AtomicInteger counter = counters.computeIfAbsent(
currentWindowKey, k -> new AtomicInteger(0)
);
// Increment and check if within limit
return counter.incrementAndGet() <= limit;
}
}
public class Main {
public static void main(String[] args) {
System.out.println("FixedWindowCounter class defined.");
System.out.println("Ready to use in next example.");
}
}Teste tidsvinduet
La oss bruke klassen FixedWindowCounter til å simulere forespørsler og se hvordan den begrenser dem innenfor et tidsvindu på 1 sekund. Legg merke til hvordan forespørslene telles og deretter tilbakestilles for neste tidsvindu.
import java.time.Instant;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
// The FixedWindowCounter class
class FixedWindowCounter {
private final int limit;
private final long windowSizeMillis;
private final ConcurrentHashMap<Long, AtomicInteger> counters;
public FixedWindowCounter(int limit, long windowSizeMillis) {
this.limit = limit;
this.windowSizeMillis = windowSizeMillis;
this.counters = new ConcurrentHashMap<>();
}
public boolean allowRequest(String userId) {
long currentWindowKey = Instant.now().toEpochMilli() / windowSizeMillis;
AtomicInteger counter = counters.computeIfAbsent(
currentWindowKey, k -> new AtomicInteger(0)
);
return counter.incrementAndGet() <= limit;
}
}
public class Main {
public static void main(String[] args) throws InterruptedException {
// Allow 3 requests per 1-second window
FixedWindowCounter limiter = new FixedWindowCounter(3, 1000);
System.out.println("--- First Window ---");
for (int i = 0; i < 5; i++) {
boolean allowed = limiter.allowRequest("user1");
System.out.println("Request " + (i + 1) + ": " + (allowed ? "ALLOWED" : "BLOCKED"));
}
// Wait for next window to start
Thread.sleep(1100);
System.out.println("\n--- Second Window ---");
for (int i = 0; i < 2; i++) {
boolean allowed = limiter.allowRequest("user1");
System.out.println("Request " + (i + 1) + ": " + (allowed ? "ALLOWED" : "BLOCKED"));
}
}
}Fordeler med Fixed Window
Algoritmen Fixed Window Counter er populær på grunn av enkelheten og effektiviteten i bestemte situasjoner.
- Enkel å implementere: Krever minimal logikk og få datastrukturer (bare en teller og et tidsstempel).
- Lavt ressursforbruk: Svært lite minne- og CPU-overhead per tidsvindu.
- Forutsigbar: Tilbakestillingen ved starten av hvert tidsvindu er tydelig og enkel å forstå.
Den er et godt valg for enkel rate limiting der presisjon ikke er avgjørende.
Problemet med trafikkstøt
Til tross for enkelheten har Fixed Window Counter en betydelig ulempe: Den kan tillate dobbelt så høy hastighet som den tiltenkte grensen ved overgangene mellom tidsvinduer.
Se for deg en grense på 10 forespørsler per minutt.
- En bruker sender 10 forespørsler klokken 0:59 (slutten av tidsvindu 1).
- Deretter sender brukeren 10 flere forespørsler klokken 1:01 (begynnelsen av tidsvindu 2).
Det betyr at 20 forespørsler ble sendt innenfor en svært kort periode på 2 minutter, slik at hastigheten i praksis ble doblet i et lite trafikkstøt.
Trafikkstøt ved tidsvinduets grenser
La oss illustrere problemet med trafikkstøt med en grense på 5 forespørsler per minutt.
- Tidsvindu 1 (0:00–0:59): 5 forespørsler sendes klokken 0:58. (Tillatt)
- Tidsvindu 2 (1:00–1:59): 5 forespørsler sendes klokken 1:01. (Tillatt)
I løpet av bare 3 minutter (fra 0:58 til 1:01) ble 10 forespørsler tillatt. Det tilsvarer i praksis 5 forespørsler på omtrent 3 sekunder, ikke 5 forespørsler per minutt, og undergraver hensikten med grensen.
Et slikt «trafikkstøt» kan overbelaste systemet hvis det ikke tas høyde for det.
Kontroll av Fixed Window
Se for deg en rate-begrenser med faste tidsvinduer og en grense på 5 forespørsler per minutt. Klokken er 0:59:30. En bruker har allerede sendt 4 forespørsler i det gjeldende tidsvinduet (0:00:00 til 0:59:59).
Deretter sender brukeren 3 forespørsler til klokken 0:59:45. Rett etterpå, klokken 1:00:05 (5 sekunder inn i neste tidsvindu), sender brukeren 3 forespørsler til.
Oppsummering: Fixed Window
Vi har sett nærmere på algoritmen Fixed Window Counter:
- Den deler tiden inn i tydelige tidsvinduer som ikke overlapper.
- Hvert tidsvindu har en forespørselsteller som tilbakestilles når et nytt tidsvindu begynner.
- Den er enkel å implementere og forstå.
- Den største ulempen er problemet med trafikkstøt, der forespørsler ved grensene mellom tidsvinduer i praksis kan doble hastigheten i løpet av kort tid.
Deretter skal vi se på algoritmer som forsøker å jevne ut slike trafikkstøt.
Lær deg Mønstre for API-ratebegrensning og skalerbarhet med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 12
- Leksjoner
- 48
Ofte stilte spørsmål
Er leksjonen «Fast tidsvindu-teller forklart» gratis?
Ja – hele teksten i «Fast tidsvindu-teller forklart» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Mønstre for API-ratebegrensning og skalerbarhet-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Mønstre for API-ratebegrensning og skalerbarhet inneholder totalt 4 leksjoner.
Hva lærer jeg i «Fast tidsvindu-teller forklart»?
Oppdag hvordan algoritmen for fast tidsvindu-telling fungerer, hvor enkel den er, og hvilke ulemper den kan ha ved håndtering av trafikkøkninger. Du øver på Mønstre for API-ratebegrensning og skalerbarhet med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Mønstre for API-ratebegrensning og skalerbarhet?
Ingen tidligere erfaring er nødvendig. Mønstre for API-ratebegrensning og skalerbarhet på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Fast tidsvindu-teller forklart»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Mønstre for API-ratebegrensning og skalerbarhet-leksjonen?
Ja. Alle Mønstre for API-ratebegrensning og skalerbarhet-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Fast tidsvindu-teller forklart
- Grundig gjennomgang av leaky bucket-algoritmen
- Slik fungerer token bucket-algoritmen
- Velge riktig algoritme