Time Complexity: Key expiry for memory management
O(1)
0
0
Key expiry for memory management in Redis - Time & Space Complexity
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?"