Time Complexity: Cache invalidation strategies
O(n)
0
0
Cache invalidation strategies in Redis - Time & Space Complexity
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?"