Fixed window algorithm in Rest API - Step-by-Step Execution

Concept Flow - Fixed window algorithm

Start

↓

Request arrives

↓

Check current window timestamp

↓

Is current time inside window?

No→Reset window start time and count

↓

Increment request count

↓

Reject request

No↓

Allow request

↓

End

This flow shows how each request is checked against a fixed time window and a request limit to decide if it is allowed or rejected.

Execution Sample

Rest API

window_start = 0
limit = 3
count = 0
current_time = 1
if current_time >= window_start + 10:
    window_start = current_time
    count = 0
count += 1
if count > limit:
    print('Reject')
else:
    print('Allow')

This code checks if a request fits in the current fixed window and allows or rejects it based on the count limit.

Execution Table

Step	current_time	window_start	count before	Condition (current_time >= window_start + 10)	Action	count after	Decision	Output
1	1	0	0	1 >= 0 + 10 -> False	No reset	1	count=1 <= 3	Allow
2	2	0	1	2 >= 0 + 10 -> False	No reset	2	count=2 <= 3	Allow
3	3	0	2	3 >= 0 + 10 -> False	No reset	3	count=3 <= 3	Allow
4	4	0	3	4 >= 0 + 10 -> False	No reset	4	count=4 > 3	Reject
5	11	0	4	11 >= 0 + 10 -> True	Reset window_start=11, count=0	1	count=1 <= 3	Allow
6	12	11	1	12 >= 11 + 10 -> False	No reset	2	count=2 <= 3	Allow
7	21	11	2	21 >= 11 + 10 -> True	Reset window_start=21, count=0	1	count=1 <= 3	Allow

💡 Execution stops after processing all requests in the example.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7
current_time	-	1	2	3	4	11	12	21
window_start	0	0	0	0	0	11	11	21
count	0	1	2	3	4	1	2	1

Key Moments - 3 Insights

Why do we reset the window_start and count when current_time >= window_start + window_size?

Because the fixed window has ended, so we start a new window from the current time and reset the count to track requests in the new window. See execution_table row 5.

Why does the count increase even if the request is rejected?

The count increments before checking the limit to track all requests in the window. If count exceeds limit, the request is rejected. See execution_table row 4.

What happens if requests come after the window resets?

The window_start updates to the new time, count resets to zero, and counting starts fresh. Requests are allowed until the limit is reached again. See execution_table rows 5 and 7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the count after incrementing?

A 1

B 4

C 3

D 0

💡 Hint

Check the 'count after' column in execution_table row 4.

At which step does the window_start reset to 11?

A Step 6

B Step 3

C Step 5

D Step 7

💡 Hint

Look at the 'Action' column in execution_table for when reset happens.

If the limit was increased to 5, what would be the decision at step 4?

A Allow

B Reject

C Reset window

D Error

💡 Hint

Check the 'Decision' column and compare count to limit in execution_table row 4.

Concept Snapshot

Fixed window algorithm limits requests in fixed time windows.
Track window start time and count requests.
If current time exceeds window, reset count and start time.
Increment count for each request.
Reject if count exceeds limit.
Allows simple rate limiting per fixed interval.

Full Transcript

The fixed window algorithm controls how many requests are allowed in a fixed time period. When a request comes, the system checks if the current time is still inside the current window. If not, it resets the window start time and count. Then it increments the count for the new request. If the count goes over the allowed limit, the request is rejected. Otherwise, it is allowed. This process repeats for each request, ensuring no more than the limit number of requests happen in each fixed window period.

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