Fixed Window Rate Limiting Algorithm

The Fixed Window Rate Limiting algorithm divides time into fixed windows of a specified duration, with each window having a predetermined request limit. Requests are counted against this limit, and once the maximum number of requests for a window is reached, additional requests are rejected until the next window starts. The request count is reset at the beginning of each new window.

In the figure above, the rate limit is set to one request per two seconds. The initial timeframe starts when request A arrives, bringing the request count to 1. Request B is dropped because it causes the request count to reach 2 within the current two-second window. Shortly after two seconds, request C arrives. This marks the start of a new window and resets the request count, allowing Request C to be processed. Request D is subsequently dropped for the same reason as Request B.

Implementation Details

The Fixed Window Rate Limiting algorithm is initialized with two key properties: the maximum number of requests allowed per window and the length of each window. As illustrated in the flow diagram below, a request is successfully processed if the current request count within the ongoing window does not exceed the maximum limit. If the limit is exceeded, the request is either rejected or delayed. A new window is initiated, and the request count is reset, when the request’s timestamp falls outside the current window.

Typically, rate limits are applied per user. To track user-specific request counts and windows, you may use a dictionary with user ID as the key and a pair of the window timestamp and request count as the value, represented as Map<String, FixedWindow>. Below is a Java implementation of the Fixed Window Rate Limiting algorithm:

import java.time.Clock;
import java.util.HashMap;
import java.util.Map;

public class FixedWindowRateLimiter {

  private final int maxCount;
  private final long windowLengthMillis;
  private final Clock clock;
  private final Map<String, FixedWindow> userFixedWindow = new HashMap<>();

  FixedWindowRateLimiter(int maxCount, long windowLengthMillis, Clock clock) {
    this.maxCount = maxCount;
    this.windowLengthMillis = windowLengthMillis;
    this.clock = clock;
  }

  boolean allowed(String userId) {
    long now = clock.millis();
    FixedWindow fixedWindow = userFixedWindow.get(userId);

    // If there is a new user OR it is time to start a new window,
    // initialize a new fixed window with the current request timestamp.
    if (fixedWindow == null
        || fixedWindow.timestamp() + windowLengthMillis < now) {
      fixedWindow = new FixedWindow(now, 0);
    }

    // If a number of requests within the window exceeds the limit,
    // disallow this request. Otherwise, update the current request count
    // and allow the request.
    if (fixedWindow.count() >= maxCount) {
      return false;
    } else {
      FixedWindow updatedWindow = new FixedWindow(fixedWindow.timestamp(),
          fixedWindow.count() + 1);
      userFixedWindow.put(userId, updatedWindow);
      return true;
    }
  }

  private record FixedWindow(long timestamp, int count) {
  }
}

The allowed method checks whether a user’s request is within the limits. If a user’s current window does not exist or has expired, a new window is created. Once the maximum number of requests in a window is reached, subsequent requests are rejected until the next window starts.

The following Java tests demonstrates the usage of this limiter:

import org.junit.jupiter.api.Test;

import java.time.Clock;

import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.mockito.Mockito.mock;
import static org.mockito.Mockito.when;

public class FixedWindowRateLimiterTest {

  private static final String BOB = "Bob";
  private static final String ALICE = "Alice";

  @Test
  void allowed_requestsFromMultipleUsers_ensuresIndividualRateLimiters() {
    Clock clock = mock(Clock.class);
    when(clock.millis()).thenReturn(0L, 999L, 1000L, 1000L, 1001L,
        2001L, 2001L, 2001L, 3002L, 3003L);

    FixedWindowRateLimiter limiter = new FixedWindowRateLimiter(1, 2000, clock);

    // 0 seconds passed
    assertTrue(limiter.allowed(BOB),
        "Bob's request 1 at timestamp=0 must pass");
    assertFalse(limiter.allowed(BOB),
        "Bob's request 2 at timestamp=999 must not be allowed");

    // 1 second passed
    assertFalse(limiter.allowed(BOB),
        "Bob's request 3 at timestamp=1000 must not be allowed");
    assertTrue(limiter.allowed(ALICE),
        "Alice's request 1 at timestamp=1000 must pass");
    assertFalse(limiter.allowed(ALICE),
        "Alice's request 2 at timestamp=1001 must not be allowed");

    // 2 seconds passed
    assertFalse(limiter.allowed(ALICE),
        "Alice's request 3 at timestamp=2001 must not be allowed");
    assertTrue(limiter.allowed(BOB),
        "Bob's request 4 at timestamp=2001 must pass, because a new" +
            " fixed window [2001; 3001] is started with reset counts");
    assertFalse(limiter.allowed(BOB),
        "Bob's request 5 at timestamp=2001 must not be allowed");

    // 3 seconds passed
    assertTrue(limiter.allowed(ALICE),
        "Alice's request 4 at timestamp=3002 must pass, because a new" +
            " fixed window [3002; 4002] is started with reset counts");
    assertFalse(limiter.allowed(ALICE),
        "Alice's request 5 at timestamp=3003 must not be allowed");
  }
}

This test simulates scenarios for different users and varying time intervals to ensure the rate limiter functions as expected. More tests and latest source code can be found in the rate-limiting GitHub repository.

For additional implementations and perspectives, you can explore open-source resources such as:

• Fixed window rate limiting middleware for GraphQL
• Fixed window rate limiter based on Redis

Pros and Cons

Pros

Simplicity: The fixed window rate limiter is relatively straightforward to implement. It doesn’t require complex algorithm theory or data structures, making it a good choice for small applications or for engineers who need a quick solution. Additionally, this algorithm can be adapted for distributed rate limiting using Redis, which supports atomic execution of operations.

Efficiency: Due to its simplicity, a fixed window rate limiter often requires less computational overhead compared to more complex algorithms such as the sliding window rate limiting algorithm. This makes it suitable for high-performance environments where processing speed is crucial.

Fairness: This algorithm ensures that recent requests are processed without being delayed by older ones. It facilitates the execution of more new requests as the system resets the request count at the end of each window.

Cons

Bursty Traffic: Fixed window rate limiters can lead to traffic spikes, potentially allowing the number of requests to be twice the set limit. This occurs if a large number of requests arrive at the end of one window and the start of the next, temporarily overloading the system despite the average rate of requests being within the set limits. Although adding a secondary rate limit with a smaller threshold and shorter window (e.g., 5 requests per second, in addition to 100 requests per minute) could mitigate this, it complicates the rate limiting and may impose excessively strict restrictions on user requests.

Inflexibility: This approach does not differentiate between various types of requests or users, treating lightweight and resource-intensive requests equally. Consequently, it might not be suitable for scenarios requiring traffic prioritization or tailored handling of different request types.

Uneven Usage: With longer window durations (e.g., 10 requests per hour), users who rapidly reach the limit may experience prolonged waiting times. For instance, a user could make 10 requests in the first minute, but would have to wait nearly an hour to make the 11th request, leading to uneven and potentially frustrating user experiences.

Common Use Cases

This algorithm is frequently applied in scenarios where rate limits need to be enforced within specific time intervals, such as in API rate limiting and user authentication processes.

Thanks to its simplicity and low memory requirements, the Fixed Window algorithm is well-suited for environments with limited resources, such as IoT devices and embedded software systems.

The Fixed Window algorithm does not require complex coordination in a distributed environment. The update operations within the algorithm can be executed atomically, enhancing its suitability for distributed systems. This characteristic makes it an advantageous choice in scenarios where a rate limiter needs to be shared between multiple instances of the same service.

Summary

The beauty of the fixed window algorithm is its simplicity and resource efficiency both in local and distributed environments. Depending on your system requirements it can serve as an excellent initial choice, suitable for prototyping or as a primary layer of defense against abusive traffic.

This algorithm is particularly advantageous for new systems that need to monitor traffic patterns to determine future adaptations or to consider moving to a different algorithm. By implementing the fixed window approach, you can safeguard system availability and maintain a positive user experience without compromising on performance during the early stages of traffic pattern analysis.