XREAD for reading entries in Redis - Time & Space Complexity

Time Complexity: XREAD for reading entries

O(n)

Understanding Time Complexity

When using Redis streams, reading entries efficiently is important for performance.

We want to understand how the time to read entries grows as the number of entries increases.

Scenario Under Consideration

Analyze the time complexity of the following Redis command snippet.

XREAD COUNT 100 STREAMS mystream 0
XREAD COUNT 50 STREAMS mystream 1609459200000-0
XREAD STREAMS mystream $

This code reads entries from a Redis stream named 'mystream' starting from different IDs or the latest entry.

Identify Repeating Operations

Look for repeated work inside the command execution.

• Primary operation: Reading entries one by one from the stream data structure.
• How many times: Up to the COUNT number specified or until no more entries are found.

How Execution Grows With Input

As the number of entries requested (COUNT) grows, the work grows roughly the same.

Input Size (COUNT)	Approx. Operations
10	About 10 entry reads
100	About 100 entry reads
1000	About 1000 entry reads

Pattern observation: The time grows linearly with the number of entries read.

Final Time Complexity

Time Complexity: O(n)

This means reading n entries takes time proportional to n; doubling entries roughly doubles the time.

Common Mistake

[X] Wrong: "XREAD always reads the entire stream quickly regardless of size."

[OK] Correct: The command reads entries one by one up to the count, so larger counts mean more work and more time.

Interview Connect

Understanding how Redis commands scale helps you design efficient data access in real projects and shows you can think about performance clearly.

Self-Check

"What if we change COUNT to a very large number or omit it? How would the time complexity change?"

Practice

1. What does the Redis command XREAD primarily do?

easy

A. Deletes entries from a stream

B. Lists all keys in the Redis database

C. Creates a new stream with initial entries

D. Reads new entries from one or more streams starting at a given ID

Solution

1. Step 1: Understand the purpose of XREAD

   XREAD is designed to read entries from Redis streams, starting at a specified ID.

2. Step 2: Compare with other commands

   Deleting entries is done by XDEL, creating streams is implicit when adding entries, and listing keys is done by KEYS or SCAN.

3. Final Answer:

   Reads new entries from one or more streams starting at a given ID -> Option D

4. Quick Check:

   XREAD reads stream entries = B [OK]

Hint: XREAD always reads entries from streams starting at an ID [OK]

Common Mistakes:

• Confusing XREAD with commands that delete or create streams
• Thinking XREAD lists keys instead of reading stream data

2. Which of the following is the correct syntax to read from a stream named mystream starting from the ID 0-0 using XREAD?

easy

A. XREAD STREAMS mystream 0-0

B. XREAD mystream STREAMS 0-0

C. XREAD STREAMS 0-0 mystream

D. XREAD 0-0 STREAMS mystream

Solution

1. Step 1: Recall XREAD syntax

   The correct syntax is: XREAD STREAMS key [key ...] ID [ID ...]. The keyword STREAMS comes before the stream names and IDs.

2. Step 2: Match the order for one stream

   For one stream, it is: XREAD STREAMS mystream 0-0.

3. Final Answer:

   XREAD STREAMS mystream 0-0 -> Option A

4. Quick Check:

   STREAMS keyword before stream and ID = D [OK]

Hint: Remember: XREAD STREAMS stream_name start_id [OK]

Common Mistakes:

• Placing STREAMS after the stream name
• Swapping stream name and ID order
• Omitting the STREAMS keyword

3. Given the following Redis stream entries in mystream:

1) 1609459200000-0: {"name": "Alice"}
2) 1609459201000-0: {"name": "Bob"}
3) 1609459202000-0: {"name": "Carol"}

What will be the output of the command XREAD COUNT 2 STREAMS mystream 1609459200000-0?

medium

A. [["mystream", [["1609459201000-0", {"name": "Bob"}], ["1609459202000-0", {"name": "Carol"}]]]]

B. [["mystream", [["1609459200000-0", {"name": "Alice"}], ["1609459201000-0", {"name": "Bob"}]]]]

C. [["mystream", [["1609459202000-0", {"name": "Carol"}]]]]

D. Error: Invalid COUNT usage

Solution

1. Step 1: Understand COUNT and starting ID

   Starting at 1609459200000-0 means reading from the first entry. COUNT 2 limits to 2 entries.

2. Step 2: Select the first two entries

   The first two entries are Alice and Bob with IDs 1609459200000-0 and 1609459201000-0.

3. Final Answer:

   [["mystream", [["1609459200000-0", {"name": "Alice"}], ["1609459201000-0", {"name": "Bob"}]]]] -> Option B

4. Quick Check:

   COUNT limits entries read = A [OK]

Hint: COUNT limits number of entries returned [OK]

Common Mistakes:

• Starting from next ID instead of given ID
• Ignoring COUNT and returning all entries
• Misunderstanding the output format

4. You run the command XREAD STREAMS mystream 0-0 COUNT 2 but get an error. Which of the following is the most likely cause?

medium

A. The COUNT argument is placed after the STREAMS keyword

B. The stream name is missing

C. The ID format is incorrect

D. XREAD does not support COUNT option

Solution

1. Step 1: Recall XREAD syntax

   Modifiers like COUNT must precede the STREAMS keyword: XREAD [COUNT count] STREAMS key id ...

2. Step 2: Analyze the given command

   COUNT 2 is placed after STREAMS mystream 0-0, which is invalid and causes a syntax error.

3. Step 3: Rule out other options

   Stream name present, ID 0-0 valid, COUNT supported.

4. Final Answer:

   The COUNT argument is placed after the STREAMS keyword -> Option A

5. Quick Check:

   COUNT after STREAMS = error A [OK]

Hint: COUNT and BLOCK must precede STREAMS [OK]

Common Mistakes:

• Placing COUNT after STREAMS keyword
• Omitting stream name
• Assuming COUNT is unsupported

5. You want to read new entries from two streams, streamA and streamB, starting from IDs 0-0 and 1609459200000-0 respectively, and wait up to 5000 milliseconds if no new entries arrive. Which command correctly achieves this?

hard

A. XREAD STREAMS streamA streamB 0-0 1609459200000-0 COUNT 10 BLOCK 5000

B. XREAD STREAMS streamA streamB 0-0 1609459200000-0 BLOCK 5000 COUNT 10

C. XREAD COUNT 10 BLOCK 5000 STREAMS streamA streamB 0-0 1609459200000-0

D. XREAD BLOCK 5000 STREAMS streamA streamB 0-0 1609459200000-0 COUNT 10

Solution

1. Step 1: Recall correct XREAD order

   XREAD [COUNT count] [BLOCK ms] STREAMS key [key ...] id [id ...]. Modifiers precede STREAMS.

2. Step 2: Match given streams and IDs

   streamA with 0-0, streamB with 1609459200000-0.

3. Step 3: Confirm options placement

   COUNT 10 BLOCK 5000 before STREAMS in XREAD COUNT 10 BLOCK 5000 STREAMS streamA streamB 0-0 1609459200000-0 is correct.

4. Final Answer:

   XREAD COUNT 10 BLOCK 5000 STREAMS streamA streamB 0-0 1609459200000-0 -> Option C

5. Quick Check:

   COUNT/BLOCK before STREAMS = C [OK]

Hint: COUNT and BLOCK before STREAMS keyword [OK]

Common Mistakes:

• Placing COUNT or BLOCK after STREAMS keyword
• Mixing order of streams and IDs
• Omitting BLOCK for waiting