TTL-based expiry in Redis - Time & Space Complexity

Time Complexity: TTL-based expiry

O(1)

Understanding Time Complexity

We want to understand how the time it takes to expire keys in Redis changes as more keys are set with a time-to-live (TTL).

Specifically, how does Redis handle removing expired keys as the number of keys grows?

Scenario Under Consideration

Analyze the time complexity of this Redis TTL expiry process.

# Set a key with TTL
SET mykey "value"
EXPIRE mykey 60

# Redis periodically checks for expired keys
# It samples a few keys with TTL and deletes expired ones
# This runs in the background automatically
    

This code sets a key with a TTL and Redis automatically removes expired keys by sampling them periodically.

Identify Repeating Operations

Redis does not check every key continuously. Instead, it:

• Primary operation: Samples a small number of keys with TTL to check if they expired.
• How many times: This sampling happens repeatedly but only on a fixed small set each time, not all keys.

How Execution Grows With Input

As the number of keys with TTL grows, Redis still samples only a small fixed number each time.

Input Size (n)	Approx. Operations
10	Checks about 20 keys per cycle
100	Still checks about 20 keys per cycle
1000	Still checks about 20 keys per cycle

Pattern observation: The number of keys checked per cycle stays roughly the same, no matter how many keys have TTL.

Final Time Complexity

Time Complexity: O(1)

This means Redis spends a constant amount of time checking for expired keys, regardless of how many keys have TTL.

Common Mistake

[X] Wrong: "Redis checks every key with TTL every time it runs expiry."

[OK] Correct: Redis only samples a small number of keys each time to keep expiry efficient, not all keys.

Interview Connect

Understanding how Redis handles TTL expiry efficiently shows you can think about how systems manage work as data grows, a useful skill in many database and system design questions.

Self-Check

"What if Redis checked all keys with TTL every time instead of sampling? How would the time complexity change?"