Time Complexity: Maxmemory setting
O(1)
0
0
Maxmemory setting in Redis - Time & Space Complexity
Understanding Time Complexity
When Redis reaches its memory limit, it uses the maxmemory setting to decide what to do next.
We want to understand the time complexity of memory management as data size increases.
Scenario Under Consideration
Analyze the time complexity of Redis handling maxmemory eviction with the allkeys-lru policy.
CONFIG SET maxmemory 100mb
CONFIG SET maxmemory-policy allkeys-lru
SET key1 value1
SET key2 value2
...
SET keyN valueN
This code sets a memory limit and an eviction policy that removes least recently used keys when memory is full.
Identify Repeating Operations
Redis samples a small, fixed number of keys to approximate the least recently used key for eviction.
- Primary operation: Sampling and evaluating a fixed number of keys for LRU approximation.
- How many times: A constant number of samples (default 5), independent of total keys.
How Execution Grows With Input
As the number of keys grows, Redis still samples the same fixed number of keys, keeping eviction time constant.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Sample fixed # (e.g., 5) keys |
| 100 | Sample fixed # (e.g., 5) keys |
| 1000 | Sample fixed # (e.g., 5) keys |
Pattern observation: The time to find a key to evict is constant regardless of the number of keys.
Final Time Complexity
Time Complexity: O(1)
This means the time to find a key to evict is constant, independent of the number of keys stored.
Common Mistake
[X] Wrong: "Redis scans all keys linearly to find the LRU key."
[OK] Correct: Redis uses sampling of a fixed small number of keys for approximation, keeping it O(1).
Interview Connect
Understanding how Redis manages memory helps you explain real-world system behavior and performance under load.
Self-Check
"What if we changed the eviction policy from allkeys-lru to noeviction? How would the time complexity change?"