Cache invalidation strategies in Redis - Time & Space Complexity

Time Complexity: Cache invalidation strategies

O(n)

Understanding Time Complexity

When using Redis as a cache, removing or updating old data is important to keep things fresh.

We want to understand how the time to invalidate cache changes as the amount of cached data grows.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands for cache invalidation.

# Invalidate a single cache key
DEL cache:user:123

# Invalidate multiple keys matching a pattern
SCAN 0 MATCH cache:user:* COUNT 100
DEL cache:user:456
DEL cache:user:789
# Repeat SCAN and DEL until all keys are deleted
    

This code deletes either one cache entry or many entries matching a pattern by scanning and deleting keys.

Identify Repeating Operations

Look for repeated actions that take time.

• Primary operation: Scanning keys with SCAN and deleting keys with DEL.
• How many times: SCAN repeats until all matching keys are found; DEL runs once per key to delete.

How Execution Grows With Input

As the number of cached keys grows, the work to find and delete them grows too.

Input Size (n)	Approx. Operations
10 keys	About 10 DEL commands plus a few SCAN calls
100 keys	About 100 DEL commands plus more SCAN calls
1000 keys	About 1000 DEL commands and many SCAN calls

Pattern observation: The number of operations grows roughly in direct proportion to the number of keys to delete.

Final Time Complexity

Time Complexity: O(n)

This means the time to invalidate cache grows linearly with the number of keys you want to remove.

Common Mistake

[X] Wrong: "Deleting keys matching a pattern is instant no matter how many keys there are."

[OK] Correct: Redis must find each key first, which takes more time as keys increase, so deletion time grows with the number of keys.

Interview Connect

Understanding how cache invalidation scales helps you design systems that stay fast and reliable as they grow.

Self-Check

"What if we used Redis key expiration (TTL) instead of manual deletion? How would the time complexity change?"

Practice

1. What is the main purpose of cache invalidation in Redis?

easy

A. To keep cached data fresh and accurate

B. To increase the size of the cache

C. To slow down data retrieval

D. To permanently store data without changes

Solution

1. Step 1: Understand cache invalidation

   Cache invalidation means removing or updating cached data to avoid stale information.

2. Step 2: Identify the main goal

   The goal is to keep the cached data fresh and accurate so users get the latest information.

3. Final Answer:

   To keep cached data fresh and accurate -> Option A

4. Quick Check:

   Cache invalidation = fresh data [OK]

Hint: Cache invalidation means keeping data fresh [OK]

Common Mistakes:

• Thinking cache invalidation increases cache size
• Believing it slows down data retrieval
• Assuming cache data never changes

2. Which Redis command is used to manually delete a cached key for invalidation?

easy

A. EXPIRE

B. GET

C. SETEX

D. DEL

Solution

1. Step 1: Identify commands for cache invalidation

   Manual invalidation requires deleting keys, so the command must remove keys.

2. Step 2: Match command to action

   DEL command deletes keys immediately, while EXPIRE sets a timeout, SETEX sets value with expiration, GET retrieves value.

3. Final Answer:

   DEL -> Option D

4. Quick Check:

   Delete key = DEL command [OK]

Hint: DEL deletes keys instantly for invalidation [OK]

Common Mistakes:

• Confusing EXPIRE with immediate deletion
• Using GET which only reads data
• Thinking SETEX deletes keys

3. Consider this Redis usage:
SET user:1 "Alice" EX 10
What happens after 10 seconds?

medium

A. The key user:1 remains forever

B. The key user:1 is deleted automatically

C. The key user:1 value changes to null

D. The key user:1 expires but stays in memory

Solution

1. Step 1: Understand the EX option in SET

   EX 10 means the key expires after 10 seconds automatically.

2. Step 2: Identify what happens on expiration

   When a key expires, Redis deletes it from memory automatically.

3. Final Answer:

   The key user:1 is deleted automatically -> Option B

4. Quick Check:

   EX sets expiration = auto delete [OK]

Hint: EX sets auto-delete time for keys [OK]

Common Mistakes:

• Thinking key stays forever after expiration
• Believing value changes to null instead of deletion
• Assuming expired keys remain in memory

4. You wrote this Redis command to expire a key:
EXPIRE user:2 0
What is the problem with this command?

medium

A. It sets expiration to zero seconds, effectively deleting the key

B. It deletes the key immediately

C. It sets the key to never expire

D. It causes a syntax error

Solution

1. Step 1: Understand EXPIRE with zero seconds

   EXPIRE key 0 removes any existing expiration timeout (equivalent to PERSIST command).

2. Step 2: Identify the problem

   The intent was to expire the key, but this sets it to never expire instead.

3. Final Answer:

   It sets the key to never expire -> Option C

4. Quick Check:

   EXPIRE 0 = remove expiration [OK]

Hint: EXPIRE 0 removes expiration (never expire) [OK]

Common Mistakes:

• Thinking it deletes the key immediately
• Believing it causes a syntax error
• Assuming zero seconds expires immediately

5. You want to keep cached product data fresh but avoid deleting keys too often. Which strategy best balances speed and data correctness in Redis?

hard

A. Use a long expiration time and rely on manual invalidation when data changes

B. Never expire keys and update them only manually

C. Delete keys immediately after every read

D. Set a short expiration time and manually delete keys on updates

Solution

1. Step 1: Understand trade-offs of expiration and manual deletion

   Short expiration causes frequent reloads; manual deletion alone risks stale data.

2. Step 2: Choose balanced approach

   Long expiration reduces reloads, manual invalidation on updates keeps data correct without overhead.

3. Final Answer:

   Use a long expiration time and rely on manual invalidation when data changes -> Option A

4. Quick Check:

   Balance speed and correctness = long expiry + manual invalidation [OK]

Hint: Long expiry plus manual delete balances freshness and speed [OK]

Common Mistakes:

• Choosing very short expiration causing overhead
• Never expiring keys causing stale data
• Deleting keys after every read causing slow performance