API Rate Limiting & Scalability Patterns · 课时

固定窗口计数器详解

了解固定窗口计数器算法的工作原理、简单性，以及它在处理流量突发时可能存在的不足。

固定窗口计数器详解 是 CoddyKit 上的免费 API Rate Limiting & Scalability Patterns 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 API Rate Limiting & Scalability Patterns 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 API Rate Limiting & Scalability Patterns 课程共包含 4 节课。

本课时的部分内容尚未翻译，以英文显示。

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!

常见问题解答

「固定窗口计数器详解」课时是免费的吗？

是的 — 「固定窗口计数器详解」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 API Rate Limiting & Scalability Patterns 课程的其余内容，请升级到 CoddyKit PRO。 API Rate Limiting & Scalability Patterns 课程共包含 4 节课。

「固定窗口计数器详解」这节课中我会学到什么？

了解固定窗口计数器算法的工作原理、简单性，以及它在处理流量突发时可能存在的不足。你通过在浏览器中直接运行的动手代码来练习 API Rate Limiting & Scalability Patterns，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 API Rate Limiting & Scalability Patterns 需要有经验吗？

无需任何先前经验。CoddyKit 上的 API Rate Limiting & Scalability Patterns 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 1 节课，共 4 节。

「固定窗口计数器详解」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 API Rate Limiting & Scalability Patterns 课中编写并运行代码吗？

能。每节 API Rate Limiting & Scalability Patterns 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 API Rate Limiting & Scalability Patterns