Fixed Window Algorithm — Simple Rate Limiting with Periodic Resets

In this tutorial, you will learn about Fixed Window Algorithm. We cover key concepts, practical examples, and best practices to help you master this topic.

The fixed window algorithm tracks request counts in discrete time windows (every 60 seconds, every hour), resetting the counter to zero at the start of each new window for simple Rate Limiting with minimal memory overhead.

What You'll Learn

• How fixed window rate limiting works
• The boundary problem and when it matters
• Simple implementation with Redis

Why It Matters

Fixed window is the simplest rate limiting algorithm and a good starting point. Many APIs use it because it is easy to understand, implement, and explain to users. However, the boundary problem can allow up to 2x the intended rate.

Real-World Use

Durga Antivirus Pro's free API tier uses fixed window with a 100 req/hour limit. The simplicity makes it easy to communicate to partners. Most partners never hit the boundary problem, and the simplicity is worth the slight inaccuracy.

flowchart LR
    subgraph "Fixed Window (60s)"
        W1["Window 1\n0:00 - 1:00\nCount: 100"]
        W2["Window 2\n1:00 - 2:00\nCount: 100"]
        W3["Window 3\n2:00 - 3:00\nCount: 100"]
    end
    Boundary["Boundary Problem\n100 req at 0:59 + 100 req at 1:01\n= 200 req in 2 seconds"]
    style W1 fill:#dbeafe,stroke:#2563eb
    style W2 fill:#dbeafe,stroke:#2563eb
    style W3 fill:#dbeafe,stroke:#2563eb
    style Boundary fill:#fef3c7,stroke:#d97706

Simple In-Memory Fixed Window

import time
import threading

class FixedWindow:
    def __init__(self, limit, window_seconds):
        self.limit = limit
        self.window_seconds = window_seconds
        self.count = 0
        self.window_start = time.monotonic()
        self.lock = threading.Lock()

    def allow_request(self):
        with self.lock:
            now = time.monotonic()
            if now - self.window_start >= self.window_seconds:
                self.count = 0
                self.window_start = now
            if self.count < self.limit:
                self.count += 1
                return True
            return False

    def remaining(self):
        with self.lock:
            return max(0, self.limit - self.count)

    def reset_time(self):
        with self.lock:
            return int(self.window_start + self.window_seconds)

Redis Fixed Window (Distributed)

import redis
import time

class RedisFixedWindow:
    def __init__(self, redis_client):
        self.redis = redis_client

    def allow_request(self, client_id, limit, window_seconds):
        now = int(time.time())
        window_key = now - (now % window_seconds)
        key = f"fw:{client_id}:{window_key}"

        count = self.redis.incr(key)
        if count == 1:
            self.redis.expire(key, window_seconds * 2)

        if count > limit:
            return False, 0, window_key + window_seconds
        return True, limit - count, window_key + window_seconds

# Usage
rl = RedisFixedWindow(redis_client)
for i in range(105):
    allowed, remaining, reset = rl.allow_request("user-1", 100, 60)
    if not allowed:
        print(f"Rate limited. Reset at: {reset}")
        break

The Boundary Problem

# Demonstrating the boundary problem
window = FixedWindow(limit=10, window_seconds=60)

# First window: use all 10 requests at 0:59
for i in range(10):
    assert window.allow_request()

# Simulate a new window starting immediately
window.window_start -= 60
window.count = 0

# Second window: use all 10 requests at 1:01
for i in range(10):
    assert window.allow_request()

# In 2 real seconds, 20 requests processed (2x the intended rate)

The boundary problem allows up to 2x the limit in a small time window around the boundary.

Mitigating the Boundary Problem

Add a small randomized delay or use a Sliding Window:

import random

class FixedWindowWithJitter:
    def __init__(self, limit, window_seconds, jitter_percent=0.1):
        self.window = FixedWindow(limit, window_seconds)
        self.jitter = jitter_percent

    def allow_request(self):
        # Add jitter to boundary decisions
        if random.random() < self.jitter:
            time.sleep(random.uniform(0.1, 1.0))
        return self.window.allow_request()

Common Mistakes

1. Not Considering the Boundary Problem

Design your limits so that 2x the limit is still acceptable, or use sliding window for stricter enforcement.

2. Using Client Timestamps for Window Calculation

Clients may have incorrect clocks. Always use the server time for window calculation.

3. Off-by-One in Window Alignment

If windows align to natural time boundaries (every hour on the hour), all users reset at the same time, causing thundering herd. Stagger windows per client.

4. Not Setting TTL on Redis Keys

Without TTL, stale keys accumulate in Redis forever. Set TTL to 2x the window for safety.

5. Counting Every Request Including Errors

Rate limits should count all requests that reach the server, not just successful ones. Errors still consume resources.

Practice Questions

1. How does the fixed window algorithm track request counts?
2. What is the boundary problem in fixed window rate limiting?
3. Why is fixed window simpler than sliding window to implement?
4. How can you mitigate the boundary problem?
5. When is fixed window acceptable despite the boundary problem?

Answers:

1. It divides time into fixed intervals (e.g., every 60 seconds) and counts requests within each interval, resetting at the start.
2. At the boundary between windows, a client can exhaust one window's limit and immediately start the next, doubling the effective rate.
3. Fixed window uses a single counter per window that resets at the boundary. Sliding window needs timestamps or sliding counters.
4. Use sliding window, add jitter, or design limits conservatively (set limit to half of actual capacity).
5. When the limit is generous enough that 2x is still safe, or when users rarely burst at window boundaries.

Challenge: Implement a fixed window rate limiter with Redis that uses client-specific window alignment (each client's window starts when they make their first request) instead of global clock alignment.

FAQ

Mini Project

Build a fixed window rate limiter with Redis that uses natural clock alignment (every minute on the minute). Implement per-IP rate limits of 30 req/min. Add jitter to mitigate boundary issues. Return X-RateLimit-* headers.

What's Next

Continue with Sliding Window Algorithm for more accurate rate limiting without boundary problems, or explore Token Bucket Algorithm for burst-friendly rate limiting.