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.

Practice

1. What is the main purpose of using a sliding window in rate limiting with Redis?

easy

A. To count actions within a moving time frame for fair limits

B. To store user passwords securely

C. To permanently block users after one action

D. To sort data alphabetically

Solution

1. Step 1: Understand sliding window concept

   Sliding window rate limiting counts actions in a recent time frame that moves forward as time passes.

2. Step 2: Identify purpose in Redis context

   Redis uses sorted sets to track timestamps of actions to enforce limits fairly over time.

3. Final Answer:

   To count actions within a moving time frame for fair limits -> Option A

4. Quick Check:

   Sliding window = moving time frame count [OK]

Hint: Sliding window means counting recent actions, not all time [OK]

Common Mistakes:

• Thinking sliding window blocks permanently
• Confusing with password storage
• Assuming it sorts data alphabetically

2. Which Redis command is essential to add a timestamp to a sorted set for sliding window rate limiting?

easy

A. ZADD

B. GET

C. HSET

D. LPUSH

Solution

1. Step 1: Identify command to add to sorted set

   ZADD adds members with scores (timestamps) to a sorted set in Redis.

2. Step 2: Confirm other commands' purpose

   GET retrieves string values, HSET sets hash fields, LPUSH adds to lists, none add to sorted sets.

3. Final Answer:

   ZADD -> Option A

4. Quick Check:

   ZADD adds to sorted set [OK]

Hint: Use ZADD to add timestamps to sorted sets [OK]

Common Mistakes:

• Using GET which only reads strings
• Confusing HSET (hashes) with sorted sets
• Using LPUSH which is for lists

3. Given this Redis Lua script snippet for sliding window rate limiting:

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

What will be the return value if the current count is equal to the limit?

medium

A. 1

B. nil

C. 0

D. An error

Solution

1. Step 1: Analyze the condition count < limit

   If count is equal to limit, the condition count < limit is false.

2. Step 2: Determine return value when condition is false

   When false, the script returns 0, indicating rate limit reached.

3. Final Answer:

   0 -> Option C

4. Quick Check:

   count == limit returns 0 [OK]

Hint: If count equals limit, return 0 (limit reached) [OK]

Common Mistakes:

• Assuming count == limit returns 1
• Expecting an error instead of 0
• Thinking nil is returned

4. You have this Redis Lua script for sliding window rate limiting:

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

What is the bug in this script?

medium

A. ZREMRANGEBYSCORE is used incorrectly

B. Using <= allows one extra request beyond limit

C. ZADD should use a string member, not number

D. TIME command returns a string, not number

Solution

1. Step 1: Check condition count <= limit

   This condition allows adding a request when count equals limit, exceeding limit by one.

2. Step 2: Verify other commands usage

   ZREMRANGEBYSCORE usage is correct to remove old timestamps; ZADD accepts numbers as members; TIME returns array with string seconds converted to number.

3. Final Answer:

   Using <= allows one extra request beyond limit -> Option B

4. Quick Check:

   count <= limit allows limit+1 requests [OK]

Hint: Use < not <= to enforce strict limit [OK]

Common Mistakes:

• Thinking ZREMRANGEBYSCORE is wrong here
• Believing ZADD can't use numbers as members
• Confusing TIME return type

5. You want to implement a sliding window rate limiter in Redis that allows 100 requests per 60 seconds. Which sequence of Redis commands best enforces this limit efficiently?

hard

A. HSET to store count, GET to read count, INCR to increment count

B. LPUSH to add timestamp, LLEN to count, LTRIM to remove old timestamps

C. SETNX to set a flag, EXPIRE to reset after 60 seconds

D. ZREMRANGEBYSCORE to remove old timestamps, ZCARD to count, ZADD to add current timestamp

Solution

1. Step 1: Understand sliding window enforcement

   Use sorted sets to store timestamps, remove old ones, count current requests, and add new timestamp.

2. Step 2: Evaluate each option's commands

   ZREMRANGEBYSCORE to remove old timestamps, ZCARD to count, ZADD to add current timestamp uses ZREMRANGEBYSCORE, ZCARD, ZADD correctly for sliding window. LPUSH to add timestamp, LLEN to count, LTRIM to remove old timestamps uses lists which are less efficient for range removals. HSET to store count, GET to read count, INCR to increment count uses hashes and counters, not suitable for sliding window. SETNX to set a flag, EXPIRE to reset after 60 seconds uses simple flags, not counting requests.

3. Final Answer:

   ZREMRANGEBYSCORE, ZCARD, ZADD sequence -> Option D

4. Quick Check:

   Sorted sets + remove old + count + add = correct [OK]

Hint: Use sorted sets with ZREMRANGEBYSCORE, ZCARD, ZADD [OK]

Common Mistakes:

• Using lists which are inefficient for sliding windows
• Using counters without timestamps
• Using flags without counting requests