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.