API Rate Limiting & Scalability Patterns · Leçon

Explication du compteur à fenêtre fixe

Découvrez le fonctionnement de l’algorithme du compteur à fenêtre fixe, sa simplicité et ses inconvénients potentiels pour gérer les pics de trafic.

Explication du compteur à fenêtre fixe est une leçon API Rate Limiting & Scalability Patterns gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage API Rate Limiting & Scalability Patterns, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours API Rate Limiting & Scalability Patterns comprend 4 leçons au total.

Certaines parties de cette leçon n'ont pas encore été traduites et s'affichent en anglais.

Why Algorithms?

Rate limiting isn't just a 'yes' or 'no' check. It relies on smart algorithms to manage traffic. These algorithms decide how and when to allow or deny requests, ensuring fairness and stability.

We'll start with one of the simplest: the Fixed Window Counter.

Fixed Window Counter: The Idea

The Fixed Window Counter is a straightforward rate limiting algorithm. It works by dividing time into fixed, non-overlapping windows.

Each window has its own request counter.
Once a request comes in, the counter for the current window increments.
If the counter exceeds a predefined limit within that window, further requests are blocked.

How It Counts

Imagine a clock. For every minute (our fixed window), we allow, say, 10 requests. When a new minute starts, the counter resets to zero.

Window: A specific time period (e.g., 60 seconds).
Limit: Maximum requests allowed in that window.
Counter: Tracks requests within the current window.

It's like a bouncer at a club, letting in only a set number of people each hour, then resetting the count for the next hour.

Example: 10 RPS Limit

Let's say our limit is 10 requests per second (RPS).

Window 1 (0-1s): 7 requests made. 3 requests remaining.
Window 2 (1-2s): 12 requests made. First 10 allowed, next 2 blocked.
Window 3 (2-3s): 5 requests made. All allowed.

At the start of each new second, the counter resets, regardless of activity in the previous second.

Basic Counter Logic

Here's a simple Java class simulating a request counter. This forms the foundation of our rate limiter. It keeps track of requests within a defined window.

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.");
    }
}

Testing the Window

Let's use our FixedWindowCounter class to simulate requests and see how it limits them within a 1-second window. Observe how requests are counted and then reset for the next window.

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: Pros

The Fixed Window Counter algorithm is popular for its simplicity and efficiency in certain scenarios.

Easy to Implement: Requires minimal logic and data structures (just a counter and a timestamp).
Low Resource Usage: Very little memory and CPU overhead per window.
Predictable: The reset at the start of each window is clear and easy to understand.

It's a good choice for basic rate limiting where precision isn't paramount.

The Burst Problem

Despite its simplicity, the Fixed Window Counter has a significant drawback: it can allow twice the intended rate limit at the window boundaries.

Imagine a limit of 10 requests per minute.

A user makes 10 requests at 0:59 (end of window 1).
They then make 10 more requests at 1:01 (start of window 2).

This means 20 requests were made within a very short 2-minute period, effectively doubling the rate in a small burst.

Boundary Bursts

Let's visualize the burst issue with a 5 requests/minute limit.

Window 1 (0:00 - 0:59): 5 requests sent at 0:58. (Allowed)
Window 2 (1:00 - 1:59): 5 requests sent at 1:01. (Allowed)

In just 3 minutes (0:58 to 1:01), 10 requests were allowed. This is effectively 5 requests in ~3 seconds, not 5 requests per minute, defeating the purpose of the limit.

This 'burst' can overwhelm your system if not accounted for.

Fixed Window Check

Consider a fixed window rate limiter set to 5 requests per minute. The current time is 0:59:30. A user has already made 4 requests in the current window (0:00:00 to 0:59:59).

They then make another 3 requests at 0:59:45. Immediately after, at 1:00:05 (5 seconds into the next window), they make 3 more requests.

Recap: Fixed Window

We've explored the Fixed Window Counter algorithm:

It divides time into distinct, non-overlapping windows.
Each window has a request counter that resets at the start of a new window.
It's simple to implement and understand.
Its main drawback is the burst problem, where requests at window boundaries can effectively double the rate in a short period.

Next, we'll look at algorithms that try to smooth out these bursts!

Questions Fréquemment Posées

La leçon « Explication du compteur à fenêtre fixe » est-elle gratuite ?

Oui — le texte complet de « Explication du compteur à fenêtre fixe » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours API Rate Limiting & Scalability Patterns, passe à CoddyKit PRO. Le cours API Rate Limiting & Scalability Patterns comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Explication du compteur à fenêtre fixe » ?

Découvrez le fonctionnement de l’algorithme du compteur à fenêtre fixe, sa simplicité et ses inconvénients potentiels pour gérer les pics de trafic. Tu pratiques API Rate Limiting & Scalability Patterns avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer API Rate Limiting & Scalability Patterns ?

Aucune expérience préalable n'est requise. API Rate Limiting & Scalability Patterns sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Explication du compteur à fenêtre fixe » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon API Rate Limiting & Scalability Patterns ?

Oui. Chaque leçon API Rate Limiting & Scalability Patterns inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

Explication du compteur à fenêtre fixe
Approfondissement de l’algorithme du seau percé
Mécanismes de l’algorithme du seau à jetons
Choisir le bon algorithme

← Retour à API Rate Limiting & Scalability Patterns