Fixed window algorithm in Rest API - Deep Dive

Overview - Fixed window algorithm

What is it?

The fixed window algorithm is a way to control how many times a user or system can do something in a set time period. It divides time into equal chunks or windows, and counts actions within each window. If the count goes over a limit, new actions are blocked until the next window starts. This helps prevent too many requests or actions happening too fast.

Why it matters

Without this algorithm, systems can get overwhelmed by too many requests at once, causing slowdowns or crashes. It protects servers and services by limiting how much work they do in a short time. This keeps apps reliable and fair for everyone using them.

Where it fits

Learners should first understand basic programming concepts and how APIs work. After this, they can learn about other rate limiting methods like sliding window or token bucket algorithms to compare and choose the best fit.

Mental Model

Core Idea

The fixed window algorithm counts actions in fixed time blocks and blocks excess actions until the next block starts.

Think of it like...

Imagine a parking lot that resets its available spots every hour. Once all spots are taken in that hour, no more cars can enter until the next hour when spots reset.

┌───────────────┐
│ Time Window 1 │
│ Count: 0 → N │
│ Limit reached │
└───────────────┘
       ↓ resets
┌───────────────┐
│ Time Window 2 │
│ Count: 0 → N │
│ Limit reached │
└───────────────┘

Build-Up - 6 Steps

1

Foundation

Understanding Rate Limiting Basics

Concept: Rate limiting controls how often an action can happen in a time frame.

Rate limiting is like setting a speed limit for requests to a server. It stops too many requests from happening too fast, which can crash or slow down the system. The fixed window algorithm is one way to do this by counting requests in fixed time blocks.

Result

You know why limiting requests is important to keep systems stable.

Understanding the need for rate limiting helps you see why algorithms like fixed window exist.

2

Foundation

Time Windows and Counting Actions

Concept: Time is split into equal windows, and actions are counted per window.

Imagine dividing time into chunks, like 1-minute blocks. For each block, you count how many requests happen. If the count hits a limit, new requests are blocked until the next block starts and the count resets.

Result

You grasp how fixed windows organize time and count actions.

Knowing how time windows work is key to understanding how the algorithm limits actions.

3

Intermediate

Implementing Fixed Window Counting

🤔Before reading on: do you think the count resets exactly at the window boundary or gradually? Commit to your answer.

Concept: The count resets exactly at the end of each fixed window.

In code, you track the start time of the current window and the count of actions. When a request comes in, check if it's still in the current window. If yes, increase count and compare to limit. If the window ended, reset count and start time.

Result

You can write code that counts requests per fixed window and blocks excess.

Understanding the exact reset timing helps avoid bugs where counts leak between windows.

4

Intermediate

Handling Edge Cases and Limits

🤔Before reading on: do you think requests arriving exactly at the window boundary belong to the old or new window? Commit to your answer.

Concept: Requests at the boundary belong to the new window after reset.

Requests that arrive exactly when a window ends are counted in the new window. This means the count resets before counting that request. Also, if many requests come at once, the algorithm blocks those exceeding the limit.

Result

You know how to handle tricky timing cases to keep counting accurate.

Handling boundaries correctly prevents unfair blocking or allowing too many requests.

5

Advanced

Limitations of Fixed Window Algorithm

🤔Before reading on: do you think fixed window can allow bursts of requests at window edges? Commit to your answer.

Concept: Fixed window can allow bursts of requests at the edges of windows.

Because counts reset only at fixed times, a user can send many requests at the end of one window and again at the start of the next. This can double the allowed requests in a short time, causing bursts that may overload the system.

Result

You understand why fixed window is simple but can cause uneven request bursts.

Knowing this limitation helps you decide when fixed window is or isn't suitable.

6

Expert

Optimizing Fixed Window in Distributed Systems

🤔Before reading on: do you think fixed window counting is easy or hard to implement across multiple servers? Commit to your answer.

Concept: Implementing fixed window counting across servers requires synchronization or shared storage.

In real systems with many servers, each may count requests separately. To enforce a global limit, counts must be stored in a shared place like a database or cache. This adds complexity and latency. Some systems use approximate counting or combine fixed window with other algorithms to improve accuracy and performance.

Result

You see the challenges and solutions for using fixed window in real-world, large-scale systems.

Understanding distributed challenges prepares you for building scalable rate limiting.

Under the Hood

The fixed window algorithm works by tracking a timestamp marking the start of the current window and a counter for actions within that window. When a new action arrives, the system checks if the current time is still within the window. If yes, it increments the counter; if the counter exceeds the limit, the action is blocked. If the time has passed the window, the counter resets to zero and the window start time updates. This simple mechanism relies on time comparisons and counters stored in memory or shared storage.

Why designed this way?

Fixed window was designed for simplicity and efficiency. It uses minimal state and easy time checks, making it fast and easy to implement. Alternatives like sliding window or token bucket are more complex but handle bursts better. Fixed window trades off burst control for simplicity, which was suitable for early systems and many practical cases.

┌───────────────┐       ┌───────────────┐
│ Current Time  │──────▶│ Check Window  │
└───────────────┘       └───────────────┘
                              │
               ┌──────────────┴──────────────┐
               │                             │
       ┌───────────────┐             ┌───────────────┐
       │ Inside Window │             │ Window Passed │
       └───────────────┘             └───────────────┘
               │                             │
       ┌───────────────┐             ┌───────────────┐
       │ Increment    │             │ Reset Counter │
       │ Counter      │             │ and Time      │
       └───────────────┘             └───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does fixed window prevent all bursts of requests? Commit yes or no.

Common Belief: Fixed window completely stops bursts of requests at any time.

Reality: Fixed window allows bursts at the edges of windows because counts reset only at fixed times.

Why it matters: Believing it stops all bursts can lead to overloads and system crashes during window transitions.

Quick: Is fixed window counting always accurate in distributed systems? Commit yes or no.

Common Belief: Fixed window counting is perfectly accurate across multiple servers without extra work.

Reality: Distributed fixed window counting requires shared storage or synchronization; otherwise counts can be inconsistent.

Why it matters: Ignoring this causes incorrect rate limiting, letting some users bypass limits or blocking others unfairly.

Quick: Does fixed window reset counts gradually over time? Commit yes or no.

Common Belief: The count resets gradually as time passes within the window.

Reality: The count resets all at once exactly at the window boundary, not gradually.

Why it matters: Misunderstanding reset timing can cause bugs where requests are blocked or allowed incorrectly.

Quick: Can fixed window algorithm be used for all rate limiting needs? Commit yes or no.

Common Belief: Fixed window is the best choice for all rate limiting scenarios.

Reality: Fixed window is simple but not always best; other algorithms handle bursts and fairness better.

Why it matters: Using fixed window blindly can cause poor user experience or system overload in complex cases.

Expert Zone

1

Fixed window counting can be combined with sliding window techniques to smooth out bursts while keeping implementation simple.

2

In distributed systems, using atomic increment operations in shared caches like Redis helps maintain accurate counts with minimal latency.

3

Choosing window size affects user experience: too short windows may block legitimate bursts, too long windows reduce responsiveness.

When NOT to use

Avoid fixed window when you need smooth rate limiting without bursts, or when you require precise fairness over sliding time. Use sliding window or token bucket algorithms instead.

Production Patterns

In production, fixed window is often used for simple API rate limits with moderate traffic. It is implemented with Redis counters and TTLs for efficiency. For high-scale systems, it is combined with other algorithms or approximations to balance accuracy and performance.

Connections

Sliding Window Algorithm

Builds on and improves fixed window by smoothing counts over time.

Understanding fixed window helps grasp sliding window, which solves burst problems by tracking partial windows.

Token Bucket Algorithm

Alternative rate limiting method with a different approach to controlling bursts.

Knowing fixed window clarifies why token bucket uses tokens to allow bursts while enforcing average limits.

Traffic Light Control Systems

Shares the idea of fixed time intervals controlling flow.

Seeing how traffic lights manage cars in fixed cycles helps understand how fixed window controls request flow.

Common Pitfalls

#1 Allowing request counts to leak between windows causing inaccurate limits.

Wrong approach:

if current_time > window_start + window_size:
count = 0 # but forgetting to update window_start
count += 1

Correct approach:

if current_time > window_start + window_size:
count = 0
window_start = current_time
count += 1

Root cause:

Not resetting the window start time causes counts to accumulate incorrectly across windows.

#2 Blocking requests that arrive exactly at the window boundary incorrectly.

Wrong approach:

if current_time >= window_start + window_size:
# count not reset before checking
if count >= limit:
block_request()

Correct approach:

if current_time >= window_start + window_size:
count = 0
window_start = current_time
if count >= limit:
block_request()

Root cause:

Failing to reset count before checking limit causes boundary requests to be blocked unfairly.

#3 Implementing fixed window counting separately on multiple servers without synchronization.

Wrong approach:

# Each server has its own count and window_start
count += 1
if count > limit:
block_request()

Correct approach:

# Use shared storage like Redis with atomic increment and expiry
count = redis.incr(key)
if count == 1:
redis.expire(key, window_size)
if count > limit:
block_request()

Root cause:

Not sharing counts leads to inconsistent limits and allows users to bypass rate limits.

Key Takeaways

The fixed window algorithm limits actions by counting them in fixed time blocks and resetting counts at block boundaries.

It is simple and efficient but can allow bursts of actions at window edges, which may overload systems.

Correct handling of window boundaries and resets is crucial to avoid unfair blocking or allowing too many actions.

In distributed systems, shared storage and atomic operations are needed to keep counts accurate across servers.

Understanding fixed window helps you learn more advanced rate limiting algorithms that improve fairness and burst control.

Practice

1.

What is the main idea behind the Fixed window algorithm in rate limiting?

easy

A. Count requests in fixed time intervals and block if limit exceeded

B. Allow unlimited requests without any restrictions

C. Count requests over a sliding time window for smooth limiting

D. Block all requests after the first one

Solution

1. Step 1: Understand fixed window concept

   The fixed window algorithm divides time into fixed intervals (windows) and counts requests in each interval.

2. Step 2: Identify how blocking works

   If the number of requests in the current window exceeds the limit, further requests are blocked until the next window.

3. Final Answer:

   Count requests in fixed time intervals and block if limit exceeded -> Option A

4. Quick Check:

   Fixed window = count + block in fixed intervals [OK]

Hint: Fixed window counts requests per fixed time block [OK]

Common Mistakes:

• Confusing fixed window with sliding window algorithm
• Thinking it allows unlimited requests
• Assuming it blocks all requests immediately

2.

Which of the following is the correct way to check the current window start time in a fixed window algorithm using Python?

import time
window_size = 60  # seconds
current_time = int(time.time())
window_start = ?

easy

A. current_time - (current_time % window_size)

B. current_time % window_size

C. current_time + window_size

D. window_size - current_time

Solution

1. Step 1: Calculate window start using modulo

   The window start is the current time minus the remainder when divided by window size, to align to window boundary.

2. Step 2: Apply formula

   Using current_time - (current_time % window_size) gives the start of the current fixed window.

3. Final Answer:

   current_time - (current_time % window_size) -> Option A

4. Quick Check:

   Window start = current_time - remainder [OK]

Hint: Use modulo to find window start time [OK]

Common Mistakes:

• Using modulo alone without subtraction
• Adding window size instead of subtracting remainder
• Confusing window start with window end

3.

Given the following Python code snippet implementing a fixed window rate limiter, what will be the output?

requests = [1, 1, 1, 1, 1]
limit = 3
window_start = 0
count = 0
for req in requests:
    if count < limit:
        count += req
        print("Allowed")
    else:
        print("Blocked")

medium

A. Allowed Allowed Allowed Allowed Allowed

B. Blocked Blocked Blocked Blocked Blocked

C. Allowed Allowed Allowed Blocked Blocked

D. Allowed Allowed Blocked Allowed Blocked

Solution

1. Step 1: Trace request counts

   Count starts at 0. For each request (value 1), count increases until it reaches limit 3.

2. Step 2: Determine allowed or blocked

   First 3 requests increase count to 3 and print "Allowed". Next requests exceed limit, so print "Blocked".

3. Final Answer:

   Allowed Allowed Allowed Blocked Blocked -> Option C

4. Quick Check:

   Count ≤ 3 allowed, else blocked [OK]

Hint: Count requests and block after limit reached [OK]

Common Mistakes:

• Assuming all requests allowed
• Resetting count incorrectly
• Confusing count comparison operator

4.

Identify the bug in this fixed window rate limiter code snippet and select the fix:

limit = 5
window_size = 60
count = 0
window_start = int(time.time())

if int(time.time()) - window_start > window_size:
    count = 0

count += 1
if count > limit:
    print("Blocked")
else:
    print("Allowed")

medium

A. Increase limit to 10

B. Change count += 1 to count = 1

C. Remove the if condition checking time difference

D. Move window_start update inside the if block to reset window

Solution

1. Step 1: Identify window reset logic

   The code resets count when window expires but does not update window_start, so window never moves forward.

2. Step 2: Fix by updating window start time

   Inside the if block, update window_start = int(time.time()) to start a new window correctly.

3. Final Answer:

   Move window_start update inside the if block to reset window -> Option D

4. Quick Check:

   Reset count and window start together [OK]

Hint: Update window start when resetting count [OK]

Common Mistakes:

• Not updating window start time
• Resetting count incorrectly
• Ignoring time difference condition

5.

You want to implement a fixed window rate limiter that allows 10 requests per minute per user. Which approach correctly handles multiple users without mixing counts?

hard

A. Store counts in a list without user identification

B. Use a dictionary with user IDs as keys and counts as values, reset counts per user each window

C. Use a single global count for all users and reset every minute

D. Allow unlimited requests for all users

Solution

1. Step 1: Understand per-user counting

   Each user must have a separate count to avoid mixing requests between users.

2. Step 2: Use dictionary keyed by user ID

   A dictionary with user IDs as keys and counts as values allows tracking each user's requests independently and resetting counts per window.

3. Final Answer:

   Use a dictionary with user IDs as keys and counts as values, reset counts per user each window -> Option B

4. Quick Check:

   Separate counts per user = dictionary keyed by user [OK]

Hint: Track counts per user with dictionary keys [OK]

Common Mistakes:

• Using a single global count for all users
• Not resetting counts per user
• Ignoring user identification in counting