XTRIM for stream capping in Redis - Time & Space Complexity

Time Complexity: XTRIM for stream capping

O(n)

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?"

Practice

1. What does the Redis XTRIM command do when used with the MAXLEN option?

easy

A. It renames the stream to a new key.

B. It adds new entries to the stream without removing any.

C. It limits the number of entries in a stream by removing the oldest ones.

D. It deletes the entire stream immediately.

Solution

1. Step 1: Understand the purpose of XTRIM with MAXLEN

   The XTRIM command with MAXLEN is used to keep the stream size limited by removing old entries.

2. Step 2: Identify the effect on the stream

   It removes the oldest entries to keep the stream length within the specified maximum.

3. Final Answer:

   It limits the number of entries in a stream by removing the oldest ones. -> Option C

4. Quick Check:

   XTRIM + MAXLEN = Remove oldest entries [OK]

Hint: XTRIM with MAXLEN trims oldest entries to cap stream size [OK]

Common Mistakes:

• Thinking XTRIM adds entries instead of removing
• Confusing XTRIM with deleting the whole stream
• Assuming XTRIM renames the stream

2. Which of the following is the correct syntax to trim a Redis stream named mystream to keep at most 1000 entries approximately?

easy

A. XTRIM mystream MAXLEN ~1000

B. XTRIM mystream MAXLEN=1000

C. XTRIM mystream MAXLEN ~ 1000

D. XTRIM mystream MAXLEN 1000

Solution

1. Step 1: Recall syntax for approximate trimming

   Approximate trimming uses the tilde (~) before the number in the XTRIM command.

2. Step 2: Match correct syntax

   The correct syntax is XTRIM mystream MAXLEN ~1000 with spaces separating arguments.

3. Final Answer:

   XTRIM mystream MAXLEN ~1000 -> Option A

4. Quick Check:

   Approximate trim syntax = MAXLEN ~ number [OK]

Hint: Use tilde (~) with MAXLEN for approximate trimming [OK]

Common Mistakes:

• Omitting the tilde (~) for approximate trimming
• Using equals sign (=) which is invalid syntax
• Not spacing arguments correctly

3. Given the following commands executed sequentially:

XADD mystream * field1 value1
XADD mystream * field2 value2
XADD mystream * field3 value3
XTRIM mystream MAXLEN 2

How many entries will mystream contain after these commands?

medium

A. 2 entries

B. 3 entries

C. 1 entry

D. 0 entries

Solution

1. Step 1: Count entries added before trimming

   Three entries are added to mystream using XADD.

2. Step 2: Apply XTRIM with MAXLEN 2

   The XTRIM command trims the stream to keep only the latest 2 entries, removing the oldest one.

3. Final Answer:

   2 entries -> Option A

4. Quick Check:

   3 added, trimmed to 2 = 2 entries [OK]

Hint: XTRIM MAXLEN keeps newest entries, removes oldest [OK]

Common Mistakes:

• Assuming no trimming happens after XTRIM
• Counting all added entries without trimming
• Thinking XTRIM deletes all entries

4. You run the command XTRIM mystream MAXLEN ~1000 but notice the stream still has over 2000 entries. What is the most likely reason?

medium

A. The command syntax is incorrect and was ignored.

B. The approximate trim (~) allows the stream to exceed the limit temporarily.

C. XTRIM only works on empty streams.

D. The stream key name is case-sensitive and was misspelled.

Solution

1. Step 1: Understand approximate trimming behavior

   Using the tilde (~) means trimming is approximate and may allow the stream to temporarily exceed the limit.

2. Step 2: Eliminate other causes

   Syntax is correct, XTRIM works on non-empty streams, and key name issues would cause errors, not approximate trimming behavior.

3. Final Answer:

   The approximate trim (~) allows the stream to exceed the limit temporarily. -> Option B

4. Quick Check:

   Approximate trim = possible temporary size excess [OK]

Hint: Approximate trim (~) may exceed limit briefly [OK]

Common Mistakes:

• Assuming syntax error caused no trimming
• Thinking XTRIM only works on empty streams
• Ignoring approximate trimming behavior

5. You want to keep a Redis stream events capped at 500 entries but want to improve trimming speed by allowing approximate trimming. Which command should you use?

hard

A. XTRIM events MAXLEN = 500

B. XTRIM events MAXLEN 500

C. XTRIM events MINLEN ~ 500

D. XTRIM events MAXLEN ~500

Solution

1. Step 1: Identify approximate trimming syntax

   Approximate trimming uses the tilde (~) before the number with MAXLEN.

2. Step 2: Choose correct command

   XTRIM events MAXLEN ~500 caps the stream at about 500 entries with faster trimming.

3. Final Answer:

   XTRIM events MAXLEN ~500 -> Option D

4. Quick Check:

   Approximate trim = MAXLEN ~ number [OK]

Hint: Use MAXLEN ~ number for fast approximate trimming [OK]

Common Mistakes:

• Using MINLEN instead of MAXLEN
• Using equals sign (=) which is invalid
• Omitting the tilde (~) for approximate trimming