Time Complexity: XTRIM for stream capping
O(n)
0
0
XTRIM for stream capping in Redis - Time & Space Complexity
Understanding Time Complexity
When using Redis streams, controlling their size is important to keep performance steady.
We want to understand how the time to trim a stream grows as the stream gets bigger.
Scenario Under Consideration
Analyze the time complexity of the following Redis command.
XTRIM mystream MAXLEN 1000
XTRIM mystream MAXLEN ~ 1000
XTRIM mystream MINID 1526985058136-0
XTRIM mystream MINID ~ 1526985058136-0
This code trims a Redis stream to keep it within a certain length or minimum ID, optionally using approximate trimming.
Identify Repeating Operations
Look for repeated work inside the trimming process.
- Primary operation: Removing entries from the stream one by one until the limit is met.
- How many times: Up to the number of entries exceeding the limit, which depends on stream size.
How Execution Grows With Input
As the stream grows larger beyond the limit, more entries need to be removed.
| Input Size (entries over limit) | Approx. Operations (entries removed) |
|---|---|
| 10 | 10 |
| 100 | 100 |
| 1000 | 1000 |
Pattern observation: The work grows linearly with how many entries must be trimmed.
Final Time Complexity
Time Complexity: O(n)
This means the time to trim grows directly with the number of entries removed from the stream.
Common Mistake
[X] Wrong: "XTRIM always runs in constant time no matter the stream size."
[OK] Correct: The command must remove each extra entry, so more entries mean more work and longer time.
Interview Connect
Understanding how trimming scales helps you manage data size and performance in real Redis applications.
Self-Check
"What if we use the approximate (~) flag with XTRIM? How might that affect the time complexity?"