Key expiry for memory management in Redis - Time & Space Complexity

Time Complexity: Key expiry for memory management

O(1)

Understanding Time Complexity

When Redis removes keys that have expired, it helps manage memory efficiently. We want to understand how the time it takes to check and delete expired keys changes as the number of keys grows.

How does Redis handle key expiry without slowing down as more keys exist?

Scenario Under Consideration

Analyze the time complexity of this Redis key expiry process.

// Redis periodically runs this:
for each key in a small random sample of keys with expiry:
  if key is expired:
    delete key
// Repeat this process every few milliseconds
    

This code shows Redis checking a small random set of keys with expiry and deleting those that are expired, repeating this often to keep memory clean.

Identify Repeating Operations

Look at what repeats in this process.

• Primary operation: Checking a small fixed number of keys for expiry.
• How many times: This check runs repeatedly over time, but each time only a small sample is checked.

How Execution Grows With Input

Even if the total number of keys grows, Redis only checks a small fixed sample each time.

Input Size (n)	Approx. Operations per check
10	5 checks
100	5 checks
1000	5 checks

Pattern observation: The number of operations per check stays the same, no matter how many keys exist.

Final Time Complexity

Time Complexity: O(1)

This means the time to check and delete expired keys does not grow as the number of keys grows; it stays constant.

Common Mistake

[X] Wrong: "Checking all keys for expiry takes longer as more keys are added."

[OK] Correct: Redis does not check all keys at once. It samples a small number repeatedly, keeping the work steady regardless of total keys.

Interview Connect

Understanding how Redis manages key expiry efficiently shows your grasp of practical system design. It highlights how smart sampling keeps performance steady even with lots of data.

Self-Check

"What if Redis checked all keys for expiry every time instead of a small sample? How would the time complexity change?"

Practice

1. What does the EXPIRE command do in Redis?

easy

A. Sets a time limit after which a key will be automatically deleted

B. Immediately deletes a key from the database

C. Shows the remaining time before a key expires

D. Removes the expiration time from a key

Solution

1. Step 1: Understand the purpose of EXPIRE

   The EXPIRE command sets a countdown timer on a key, after which Redis deletes it automatically.

2. Step 2: Differentiate from other commands

   Unlike DEL which deletes immediately, EXPIRE schedules deletion after a set time.

3. Final Answer:

   Sets a time limit after which a key will be automatically deleted -> Option A

4. Quick Check:

   EXPIRE = set auto-delete timer [OK]

Hint: EXPIRE sets timer; key deletes after time [OK]

Common Mistakes:

• Confusing EXPIRE with DEL command
• Thinking EXPIRE shows time left instead of setting it
• Assuming EXPIRE removes expiration instead of adding it

2. Which of the following is the correct syntax to set a key session to expire in 120 seconds?

easy

A. SETEX session 120

B. EXPIRE 120 session

C. TTL session 120

D. EXPIRE session 120

Solution

1. Step 1: Recall EXPIRE command syntax

   The correct syntax is EXPIRE key seconds, so EXPIRE session 120 sets expiry to 120 seconds.

2. Step 2: Check other options

   EXPIRE 120 session reverses arguments, A is incomplete syntax for SETEX, D is invalid usage of TTL.

3. Final Answer:

   EXPIRE session 120 -> Option D

4. Quick Check:

   EXPIRE key seconds = EXPIRE session 120 [OK]

Hint: EXPIRE syntax: EXPIRE key seconds [OK]

Common Mistakes:

• Swapping key and seconds in EXPIRE
• Using TTL to set expiry instead of check
• Confusing SETEX syntax

3. Given the commands:

SET user:1 "Alice"
EXPIRE user:1 10
TTL user:1

What will the TTL user:1 command return immediately after setting expiry?

medium

A. -1

B. Error

C. 10

D. 0

Solution

1. Step 1: Understand TTL after EXPIRE

   After setting EXPIRE to 10 seconds, TTL returns the remaining time in seconds, which is 10 immediately.

2. Step 2: Interpret other options

   -1 means no expiry, 0 means expired, Error is invalid here.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   TTL after EXPIRE = expiry seconds [OK]

Hint: TTL shows seconds left after EXPIRE set [OK]

Common Mistakes:

• Expecting TTL to return -1 immediately
• Thinking TTL returns 0 right after EXPIRE
• Confusing TTL with DEL command

4. You run the command EXPIRE mykey 30 but TTL mykey returns -2. What is the likely problem?

medium

A. The key mykey has no expiry set

B. The key mykey does not exist

C. The EXPIRE command syntax is incorrect

D. The Redis server is down

Solution

1. Step 1: Understand TTL return values

   TTL returns -2 if the key does not exist in Redis.

2. Step 2: Analyze the scenario

   Since TTL returns -2, it means mykey is missing, so EXPIRE had no effect.

3. Final Answer:

   The key mykey does not exist -> Option B

4. Quick Check:

   TTL = -2 means key missing [OK]

Hint: TTL -2 means key missing, not syntax error [OK]

Common Mistakes:

• Assuming -2 means no expiry set
• Thinking EXPIRE syntax is wrong
• Ignoring that key might be deleted

5. You want to keep a Redis key cache:data but remove its expiry to prevent automatic deletion. Which command should you use?

hard

A. PERSIST cache:data

B. EXPIRE cache:data 0

C. DEL cache:data

D. TTL cache:data

Solution

1. Step 1: Identify command to remove expiry

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

2. Step 2: Check other options

   EXPIRE with 0 deletes immediately, DEL deletes key, TTL only checks expiry time.

3. Final Answer:

   PERSIST cache:data -> Option A

4. Quick Check:

   PERSIST removes expiry timer [OK]

Hint: Use PERSIST to cancel expiry, keep key [OK]

Common Mistakes:

• Using EXPIRE 0 which deletes key immediately
• Confusing DEL with removing expiry
• Using TTL expecting it to remove expiry