Fixed Window Counter with ConcurrentHashMap

Your learning outcome for this lesson:

By the end of this lesson, you will be able to implement a basic in-memory fixed window counter using ConcurrentHashMap.

1. The Fixed Window Counter Algorithm

The Fixed Window Counter is a straightforward rate-limiting algorithm. It works by dividing time into fixed-size intervals (or "windows") and limiting the number of requests allowed from a single client within each window.

• Example: If the limit is 100 requests per hour, a client can make 100 requests between 2:00 PM and 3:00 PM. At 3:00 PM, the window resets, and the client can make another 100 requests.

For a more detailed explanation of the algorithm and its primary drawback (the potential for a "burst" of traffic at the window boundary), let's watch a short video.

To implement this, for each client key, we need to store two pieces of information:

1. The number of requests made in the current window.
2. The start time of that window.

When a new request comes in, we check if it falls within the current window. If it does, we increment the count. If it falls into a new window, we reset the count and update the window's start time.

2. The Critical Challenge: Concurrency

Since our rate limiter will serve a web application, it will inherently be multi-threaded. Many requests from different clients (and even the same client) could arrive simultaneously. This poses a significant challenge.

If we use a standard java.util.HashMap, we risk running into major issues:

• Race Conditions: Two threads might try to update the count for the same client at the same time, leading to an incorrect final count.
• Data Corruption: In the worst case, concurrent modifications can corrupt the internal structure of the HashMap, potentially causing infinite loops.

The solution is to use data structures designed for concurrent access. Given your background, you'll recognize the importance of thread safety in shared-memory systems.

Introducing ConcurrentHashMap

java.util.concurrent.ConcurrentHashMap is a high-performance, thread-safe implementation of the Map interface. It's the ideal tool for our use case.

Avoiding "Slipped Conditions" with Atomic Operations

Even with ConcurrentHashMap, a naive check-then-act pattern can still fail. Consider this logic for adding a new client to our map:

// Anti-pattern: This is NOT thread-safe!
if (!requestCounts.containsKey(clientKey)) {
    requestCounts.put(clientKey, 1);
}

A "slipped condition" or race condition can occur here. Two threads could execute the containsKey check simultaneously, both find it false, and both proceed to put a new value, with one overwriting the other.

To solve this, ConcurrentHashMap provides atomic operations that combine the check and the action into a single, indivisible step. The most useful one for us is computeIfAbsent. This method guarantees that the function to create a new value is only called once per key.

3. Implementing the FixedWindowCounter

Now, let's bring these concepts together to build our FixedWindowCounter class. It will implement the RateLimiter interface we designed earlier.

A simple ConcurrentHashMap<String, Integer> isn't sufficient because we also need to store the window's start time for each key. A clean way to manage this is with a small, private inner class.

Here is the complete implementation. It uses ConcurrentHashMap to store client data, AtomicInteger for thread-safe counting within each window, and computeIfAbsent to safely initialize new clients.

import java.time.Duration;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * An in-memory implementation of the Fixed Window Counter rate-limiting algorithm.
 * This implementation is thread-safe.
 */
public class FixedWindowCounter implements RateLimiter {

    private final int capacity;
    private final Duration windowSize;
    private final Map<String, Window> windows = new ConcurrentHashMap<>();

    /**
     * A helper class to store the request count and start time for a window.
     */
    private static class Window {
        private final AtomicInteger count;
        private final long startTime;

        Window(long startTime) {
            this.count = new AtomicInteger(0);
            this.startTime = startTime;
        }
    }

    public FixedWindowCounter(int capacity, Duration windowSize) {
        this.capacity = capacity;
        this.windowSize = windowSize;
    }

    @Override
    public boolean allowRequest(String key) {
        long currentTime = System.currentTimeMillis();
        long windowSizeMillis = windowSize.toMillis();

        // Atomically get or create a window for the given key.
        Window currentWindow = windows.computeIfAbsent(key, k -> new Window(currentTime));

        // Check if the window has expired.
        if (currentTime - currentWindow.startTime > windowSizeMillis) {
            // This is a simplified reset. In a highly contented environment,
            // this could lead to a thundering herd problem where many threads try to reset at once.
            // A synchronized block or a more advanced CAS loop would make this more robust,
            // but for a basic implementation, this is a good starting point.
            windows.put(key, new Window(currentTime));
            currentWindow = windows.get(key);
        }

        // Increment count and check against capacity.
        return currentWindow.count.incrementAndGet() <= capacity;
    }
}

Dissecting the Code:

1. FixedWindowCounter(capacity, windowSize): The constructor takes the maximum number of requests (capacity) and the time window duration (windowSize), which will be configured later.
2. private static class Window: This inner class neatly bundles the two pieces of data we need for each key: an AtomicInteger for the counter and a long for the window's start time. Using AtomicInteger ensures that incrementing the count is itself a thread-safe operation.
3. windows.computeIfAbsent(...): This is the atomic operation we discussed. It ensures that when a new client makes their first-ever request, a Window object is created and inserted into the map exactly once.
4. Window Expiration Check: The if (currentTime - currentWindow.startTime > windowSizeMillis) logic checks if the request belongs to a new window. If so, it replaces the old window with a new one.
5. currentWindow.count.incrementAndGet(): This atomically increments the request count for the current window and returns the new value, which we then compare against the capacity.

You have now built your first rate-limiting algorithm! This class is a self-contained, thread-safe component ready to be plugged into our Spring Boot application.

Key Takeaways

• The Fixed Window Counter algorithm limits requests within discrete time intervals.
• Implementing services for concurrent environments requires thread-safe data structures like ConcurrentHashMap and AtomicInteger.
• Naive "check-then-act" logic is prone to race conditions ("slipped conditions").
• Atomic operations like computeIfAbsent are essential for writing correct and robust concurrent code.
• We have a concrete FixedWindowCounter class that fulfills the RateLimiter contract.

Next Steps

With our first algorithm implemented, the next step is to integrate it into our Spring Boot application. In the following lessons, we will:

1. Implement the IpAddressKeyResolver to get a key from incoming requests.
2. Create a Spring HandlerInterceptor that uses the key resolver and our new FixedWindowCounter.
3. Ensure that when a request is denied, our API returns the standard HTTP 429 (Too Many Requests) status code.