Java Sliding Window Rate Limiter Algorithm

The Sliding Window Algorithm is an improvement over the Fixed Window Algorithm. It maintains a sliding window of fixed size and counts the number of requests made within that window. If the number of requests exceeds the limit, then any subsequent requests are blocked until the start of the next window. Unlike the Fixed Window Algorithm, the Sliding Window Algorithm can handle bursts of requests by gradually reducing the limit as the number of requests increases.

Java Code for Sliding Window Algorithm:

import java.time.Instant;
import java.util.ArrayDeque;
import java.util.Queue;

public class SlidingWindowRateLimiter {
    private final int limit; // Maximum number of requests allowed within the time window
    private final int windowSeconds; // Duration of the time window in seconds
    private final Queue<Instant> requestQueue; // Queue to store request timestamps

    public SlidingWindowRateLimiter(int limit, int windowSeconds) {
        this.limit = limit;
        this.windowSeconds = windowSeconds;
        this.requestQueue = new ArrayDeque<>();
    }

    public synchronized boolean allowRequest() {
        clearExpiredRequests(); // Clear expired requests from the queue

        if (requestQueue.size() < limit) {
            requestQueue.offer(Instant.now()); // Add current request timestamp to the queue
            return true; // Request is allowed
        } else {
            return false; // Request is not allowed
        }
    }

    private void clearExpiredRequests() {
        Instant now = Instant.now();
        Instant windowStart = now.minusSeconds(windowSeconds);

        while (!requestQueue.isEmpty() && requestQueue.peek().isBefore(windowStart)) {
            requestQueue.poll(); // Remove expired requests from the queue
        }
    }
}

In the above code, we have a SlidingWindowRateLimiter class that implements the Sliding Window Algorithm for rate limiting. It takes the maximum number of requests allowed within a time window (limit) and the duration of the time window in seconds (windowSeconds) as parameters in the constructor.

The allowRequest() method is used to check if a request is allowed or not. It synchronizes the method to ensure thread safety.

The clearExpiredRequests() method is called before checking the request queue for the number of requests. It clears any expired requests from the queue based on the current time and the window duration. The expired requests are removed from the queue to keep track of only the requests within the defined time window.

You can create an instance of SlidingWindowRateLimiter and use the allowRequest() method to control the rate at which requests are allowed within the sliding window.

The Sliding Window Algorithm maintains a rolling window of requests over time and allows the rate limit to be more evenly distributed. Requests are tracked not only within the fixed time window but also across the previous windows. This allows for more flexibility and a smoother distribution of requests compared to the Fixed Window Algorithm.