Räknare med fast fönster förklarad
Upptäck hur algoritmen med räknare för fasta fönster fungerar, hur enkel den är och vilka nackdelar den kan ha vid hantering av trafiktoppar.
Räknare med fast fönster förklarad är en gratis lektion i API-begränsning och skalbarhetsmönster på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för API-begränsning och skalbarhetsmönster, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i API-begränsning och skalbarhetsmönster innehåller totalt 4 lektioner.
Varför algoritmer?
Rate limiting är inte bara en kontroll med svaret ”ja” eller ”nej”. Det bygger på smarta algoritmer för att hantera trafik. Algoritmerna avgör hur och när förfrågningar ska tillåtas eller nekas, vilket säkerställer rättvisa och stabilitet.
Vi börjar med en av de enklaste: Fixed Window Counter.
Fixed Window Counter: Idén
Fixed Window Counter är en enkel algoritm för rate limiting. Den delar upp tiden i fasta, icke-överlappande tidsfönster.
- Varje tidsfönster har sin egen räknare för förfrågningar.
- När en förfrågan kommer in ökas räknaren för det aktuella tidsfönstret.
- Om räknaren överskrider en förutbestämd gräns inom tidsfönstret blockeras ytterligare förfrågningar.
Så räknar den
Föreställ er en klocka. Under varje minut (vårt fasta tidsfönster) tillåter vi exempelvis 10 förfrågningar. När en ny minut börjar återställs räknaren till noll.
- Tidsfönster: En specifik tidsperiod (t.ex. 60 sekunder).
- Gräns: Högsta antal förfrågningar som tillåts under tidsfönstret.
- Räknare: Håller reda på förfrågningar under det aktuella tidsfönstret.
Det fungerar ungefär som en dörrvakt på en klubb som bara släpper in ett visst antal personer varje timme och sedan återställer räkningen inför nästa timme.
Exempel: 10 RPS-gräns
Anta att vår gräns är 10 förfrågningar per sekund (RPS).
- Tidsfönster 1 (0–1 s): 7 förfrågningar skickas. 3 förfrågningar återstår.
- Tidsfönster 2 (1–2 s): 12 förfrågningar skickas. De första 10 tillåts, de nästa 2 blockeras.
- Tidsfönster 3 (2–3 s): 5 förfrågningar skickas. Alla tillåts.
I början av varje ny sekund återställs räknaren, oavsett aktiviteten under föregående sekund.
Grundläggande räknarlogik
Här är en enkel Java-klass som simulerar en räknare för förfrågningar. Den utgör grunden för vår rate limiter. Den håller reda på förfrågningar inom ett definierat tidsfönster.
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.");
}
}Testa tidsfönstret
Vi använder klassen FixedWindowCounter för att simulera förfrågningar och se hur den begränsar dem inom ett tidsfönster på 1 sekund. Observera hur förfrågningarna räknas och sedan återställs inför nästa tidsfönster.
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"));
}
}
}Fixed Window: Fördelar
Algoritmen Fixed Window Counter är populär tack vare sin enkelhet och effektivitet i vissa situationer.
- Enkel att implementera: Kräver minimal logik och enkla datastrukturer (bara en räknare och en tidsstämpel).
- Låg resursanvändning: Mycket liten minnes- och CPU-belastning per tidsfönster.
- Förutsägbar: Återställningen i början av varje tidsfönster är tydlig och lätt att förstå.
Det är ett bra val för enkel rate limiting där precision inte är avgörande.
Burst-problemet
Trots sin enkelhet har Fixed Window Counter en betydande nackdel: den kan tillåta dubbelt så hög takt som den avsedda gränsen vid tidsfönstrens gränser.
Föreställ er en gräns på 10 förfrågningar per minut.
- En användare skickar 10 förfrågningar kl. 0:59 (i slutet av tidsfönster 1).
- Därefter skickar användaren 10 förfrågningar till kl. 1:01 (i början av tidsfönster 2).
Det innebär att 20 förfrågningar skickades under en mycket kort period på 2 minuter, vilket i praktiken fördubblar takten i en liten burst.
Bursts vid tidsgränser
Vi illustrerar burst-problemet med en gräns på 5 förfrågningar per minut.
- Tidsfönster 1 (0:00–0:59): 5 förfrågningar skickas kl. 0:58. (Tillåts)
- Tidsfönster 2 (1:00–1:59): 5 förfrågningar skickas kl. 1:01. (Tillåts)
På bara 3 minuter (0:58 till 1:01) tilläts 10 förfrågningar. Det motsvarar i praktiken 5 förfrågningar på cirka 3 sekunder, inte 5 förfrågningar per minut, vilket motverkar syftet med gränsen.
Den här burst-trafiken kan överbelasta ert system om ni inte tar hänsyn till den.
Kontroll av Fixed Window
Föreställ er en rate limiter med fasta tidsfönster och gränsen 5 förfrågningar per minut. Klockan är 0:59:30. En användare har redan skickat 4 förfrågningar under det aktuella tidsfönstret (0:00:00 till 0:59:59).
Därefter skickar användaren ytterligare 3 förfrågningar kl. 0:59:45. Omedelbart efter, kl. 1:00:05 (5 sekunder in i nästa tidsfönster), skickar användaren 3 förfrågningar till.
Repetition: Fixed Window
Vi har gått igenom algoritmen Fixed Window Counter:
- Den delar upp tiden i tydliga, icke-överlappande tidsfönster.
- Varje tidsfönster har en räknare för förfrågningar som återställs när ett nytt tidsfönster börjar.
- Den är enkel att implementera och förstå.
- Dess främsta nackdel är burst-problemet, där förfrågningar vid tidsfönstrens gränser i praktiken kan fördubbla takten under en kort period.
Härnäst tittar vi på algoritmer som försöker jämna ut dessa bursts!
Lär dig API-begränsning och skalbarhetsmönster med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 12
- Lektioner
- 48
Vanliga frågor
Är lektionen ”Räknare med fast fönster förklarad” gratis?
Ja – hela texten till ”Räknare med fast fönster förklarad” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i API-begränsning och skalbarhetsmönster, kan Ni uppgradera till CoddyKit PRO. Kursen i API-begränsning och skalbarhetsmönster innehåller totalt 4 lektioner.
Vad lär jag mig i ”Räknare med fast fönster förklarad”?
Upptäck hur algoritmen med räknare för fasta fönster fungerar, hur enkel den är och vilka nackdelar den kan ha vid hantering av trafiktoppar. Ni övar på API-begränsning och skalbarhetsmönster med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig API-begränsning och skalbarhetsmönster?
Du behöver inga förkunskaper. Utbildningen i API-begränsning och skalbarhetsmönster på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Räknare med fast fönster förklarad”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här API-begränsning och skalbarhetsmönster-lektionen?
Ja. Varje API-begränsning och skalbarhetsmönster-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Räknare med fast fönster förklarad
- Leaky bucket-algoritmen på djupet
- Token bucket-algoritmens mekanik
- Välj rätt algoritm