Rate limiting with sliding window in Redis - Step-by-Step Execution

Concept Flow - Rate limiting with sliding window

Request arrives

↓

Get current timestamp

↓

Calculate window start time

↓

Remove timestamps older than window start

↓

Count remaining timestamps

↓

If count < limit?

No→Reject request

Yes↓

Add current timestamp

↓

Allow request

Each request is checked against recent requests in a time window. Old requests are removed, and if the count is below the limit, the request is allowed and timestamp recorded.

Execution Sample

Redis

local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local window_start = now - window
redis.call('ZREMRANGEBYSCORE', key, 0, window_start)
local count = redis.call('ZCARD', key)
if count < limit then
  redis.call('ZADD', key, now, tostring(now))
  return 1
else
  return 0
end

This Lua script in Redis implements sliding window rate limiting by removing old timestamps, counting current ones, and deciding to allow or reject the request.

Execution Table

Step	Action	Timestamp	Window Start	Old Timestamps Removed	Count After Removal	Decision	New Timestamp Added	Result
1	Request arrives	1000	940	Remove timestamps <= 940	3	3 < 5? Yes	Add 1000	Allow (1)
2	Request arrives	1010	950	Remove timestamps <= 950	4	4 < 5? Yes	Add 1010	Allow (1)
3	Request arrives	1020	960	Remove timestamps <= 960	5	5 < 5? No	No add	Reject (0)
4	Request arrives	1030	970	Remove timestamps <= 970	4	4 < 5? Yes	Add 1030	Allow (1)
5	Request arrives	1040	980	Remove timestamps <= 980	5	5 < 5? No	No add	Reject (0)

💡 Execution stops after each request is processed with decision to allow or reject based on count vs limit.

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5
now (timestamp)	N/A	1000	1010	1020	1030	1040
window_start	N/A	940	950	960	970	980
count	N/A	3	4	5	4	5
timestamps in sorted set	[]	[960,970,980]	[970,980,990,1000]	[980,990,1000,1010,1020]	[990,1000,1010,1030]	[1000,1010,1030,1040]

Key Moments - 3 Insights

Why do we remove timestamps older than the window start before counting?

Because only requests within the current sliding window count towards the limit. Removing old timestamps ensures we count only recent requests, as shown in execution_table rows where old timestamps are removed before counting.

What happens if the count equals the limit exactly?

The request is rejected because the limit is reached. In execution_table row 3 and 5, count is 5 which equals limit 5, so the decision is No and request is rejected.

Why do we add the current timestamp only if the request is allowed?

Adding the timestamp represents recording the allowed request. If rejected, we don't add it to avoid counting it in future windows. This is shown in execution_table where 'New Timestamp Added' is only Yes when decision is allow.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3. What is the count after removing old timestamps?

A 5

B 4

C 3

D 6

💡 Hint

Check the 'Count After Removal' column in execution_table row 3.

At which step does the request get rejected because the count equals the limit?

A Step 4

B Step 2

C Step 3

D Step 1

💡 Hint

Look for 'Decision' column where count < limit is No and result is Reject.

If the window size was increased, how would the 'Old Timestamps Removed' column change?

A More timestamps would be removed

B Fewer timestamps would be removed

C No timestamps would be removed

D All timestamps would be removed

💡 Hint

Increasing window means window_start is smaller, so fewer timestamps fall outside the window.

Concept Snapshot

Rate limiting with sliding window in Redis:
- Use sorted set to store request timestamps
- Remove timestamps older than (now - window)
- Count remaining timestamps
- If count < limit, allow and add current timestamp
- Else reject request
This ensures smooth rate limiting over time.

Full Transcript

This visual execution shows how sliding window rate limiting works in Redis. Each request gets the current time and calculates the window start by subtracting the window size. Old timestamps outside the window are removed from the sorted set. Then the count of timestamps inside the window is checked. If the count is less than the limit, the request is allowed and the current timestamp is added to the sorted set. Otherwise, the request is rejected. The execution table traces five requests with timestamps, showing removal of old timestamps, counts, decisions, and additions. The variable tracker shows how timestamps and counts change after each request. Key moments clarify why old timestamps are removed, what happens when count equals limit, and why timestamps are added only on allowed requests. The quiz tests understanding of counts, rejection steps, and window size effects. The snapshot summarizes the sliding window rate limiting steps in Redis.