Fixed window algorithm in Rest API - Mini Project: Build & Apply

Implementing Fixed Window Rate Limiting Algorithm

📖 Scenario: You are building a simple REST API server that limits how many requests a user can make in a fixed time window. This helps prevent abuse and keeps the server stable.

🎯 Goal: Build a fixed window rate limiter that counts requests per user in a 60-second window and blocks requests exceeding the limit.

📋 What You'll Learn

Create a dictionary to store request counts per user

Add a variable for the fixed window duration in seconds

Implement the fixed window logic to count requests and reset counts after the window expires

Print whether a request is allowed or blocked based on the rate limit

💡 Why This Matters

🌍 Real World

Rate limiting is used in APIs to prevent too many requests from one user, protecting servers from overload and abuse.

💼 Career

Understanding rate limiting algorithms is important for backend developers and API designers to build reliable and secure services.

1

Create the request count storage

Create a dictionary called request_counts to store the number of requests per user. Initialize it as an empty dictionary.

Rest API

# Create a dictionary called request_counts to store user request counts
# Your code here

Hint

Use curly braces {} to create an empty dictionary in Python.

2

Set the fixed window duration

Create a variable called window_duration and set it to 60 to represent the fixed window length in seconds.

Rest API

request_counts = {}
# Create a variable window_duration and set it to 60
# Your code here

Hint

Just assign the number 60 to the variable window_duration.

3

Implement the fixed window logic

Write a function called is_request_allowed(user_id, current_time) that uses request_counts and window_duration to count requests per user. If the user has made fewer than 5 requests in the current window, increase the count and return True. Otherwise, return False. Use a dictionary value as a tuple (window_start_time, count) to track the window start and count.

Rest API

request_counts = {}
window_duration = 60
# Write the function is_request_allowed(user_id, current_time) below
# Your code here

Hint

Use the current time to check if the window expired. Reset count if expired, else increment if under limit.

4

Test and print the rate limiter result

Call is_request_allowed('user1', 100) five times and print the result each time. Then call it a sixth time and print the result. This shows the limiter blocking the sixth request.

Rest API

request_counts = {}
window_duration = 60

def is_request_allowed(user_id, current_time):
    if user_id not in request_counts:
        request_counts[user_id] = (current_time, 1)
        return True
    window_start, count = request_counts[user_id]
    if current_time - window_start < window_duration:
        if count < 5:
            request_counts[user_id] = (window_start, count + 1)
            return True
        else:
            return False
    else:
        request_counts[user_id] = (current_time, 1)
        return True

# Call is_request_allowed 6 times for 'user1' at time 100 and print results
# Your code here

Hint

Use a for loop to call the function 6 times and print the results with the request number.

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