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?"

Practice

1. What does the Redis command EXPIRE key 60 do?

easy

A. Renames the key to '60'

B. Deletes the key immediately

C. Sets the key to expire and be deleted after 60 seconds

D. Returns the current TTL of the key

Solution

1. Step 1: Understand the EXPIRE command

   The EXPIRE command sets a time-to-live (TTL) in seconds for a key in Redis.

2. Step 2: Apply the command to the example

   Using EXPIRE key 60 means the key will be deleted automatically after 60 seconds.

3. Final Answer:

   Sets the key to expire and be deleted after 60 seconds -> Option C

4. Quick Check:

   EXPIRE sets TTL = expire after time [OK]

Hint: EXPIRE sets countdown in seconds for key deletion [OK]

Common Mistakes:

• Thinking EXPIRE deletes key immediately
• Confusing EXPIRE with TTL command
• Assuming EXPIRE renames the key

2. Which of the following is the correct syntax to check the remaining TTL of a key named session?

easy

A. TTL session

B. EXPIRE session

C. GETTTL session

D. PERSIST session

Solution

1. Step 1: Identify the command to check TTL

   The Redis command to check remaining time-to-live is TTL followed by the key name.

2. Step 2: Match the syntax

   TTL session correctly checks the remaining TTL of the key 'session'. Other options are either invalid or perform different actions.

3. Final Answer:

   TTL session -> Option A

4. Quick Check:

   TTL command returns remaining expiry time [OK]

Hint: Use TTL key to see remaining expiry time in seconds [OK]

Common Mistakes:

• Using EXPIRE to check TTL instead of setting it
• Using PERSIST which removes expiry, not checks it
• Assuming GETTTL is a valid Redis command

3. Consider the following Redis commands executed in order:
SET temp 100
EXPIRE temp 10
TTL temp
What is the expected output of the last command?

medium

A. -1

B. 0

C. Error

D. 10

Solution

1. Step 1: Set key and expiry

   The key 'temp' is set with value '100' and then given a TTL of 10 seconds.

2. Step 2: Check TTL immediately

   Immediately after setting expiry, TTL temp returns the remaining time, which should be close to 10 seconds.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   TTL after EXPIRE shows seconds left [OK]

Hint: TTL right after EXPIRE shows the set seconds [OK]

Common Mistakes:

• Expecting TTL to return -1 (means no expiry)
• Thinking TTL returns 0 immediately after EXPIRE
• Assuming TTL command causes error

4. You run the following commands:
SET user123 "data"
EXPIRE user123 30
PERSIST user123
TTL user123
But the TTL command returns -1. What is the issue?

medium

A. Key user123 does not exist

B. PERSIST removed the expiry, so TTL returns -1

C. TTL command syntax is wrong

D. EXPIRE was not set correctly

Solution

1. Step 1: Understand PERSIST effect

   PERSIST removes the expiry from a key, making it permanent.

2. Step 2: Check TTL after PERSIST

   After PERSIST, TTL returns -1 indicating no expiry is set on the key.

3. Final Answer:

   PERSIST removed the expiry, so TTL returns -1 -> Option B

4. Quick Check:

   PERSIST removes TTL, TTL returns -1 [OK]

Hint: PERSIST removes expiry; TTL then returns -1 [OK]

Common Mistakes:

• Thinking TTL returns error if expiry removed
• Assuming EXPIRE failed without checking
• Confusing TTL -1 with key missing

5. You want to set a key cache_item with a value and ensure it expires exactly after 5 minutes. Which sequence of commands correctly achieves this and verifies the expiry?

hard

A. SET cache_item "value"\nEXPIRE cache_item 300\nTTL cache_item

B. SET cache_item "value"\nTTL cache_item 300\nEXPIRE cache_item

C. EXPIRE cache_item 300\nSET cache_item "value"\nTTL cache_item

D. SET cache_item "value"\nPERSIST cache_item\nTTL cache_item

Solution

1. Step 1: Set the key with value

   Use SET to create the key 'cache_item' with the desired value.

2. Step 2: Set expiry to 300 seconds (5 minutes)

   Use EXPIRE cache_item 300 to set TTL to 5 minutes.

3. Step 3: Verify TTL

   Use TTL cache_item to check remaining time, which should be close to 300 seconds.

4. Final Answer:

   SET cache_item "value"\nEXPIRE cache_item 300\nTTL cache_item -> Option A

5. Quick Check:

   SET then EXPIRE then TTL to verify expiry [OK]

Hint: SET key, then EXPIRE seconds, then TTL to check [OK]

Common Mistakes:

• Using TTL to set expiry (wrong command)
• Setting EXPIRE before SET (key must exist first)
• Using PERSIST which removes expiry