Time Complexity: Pub/sub vs streams comparison
O(s)
0
0
Pub/sub vs streams comparison in Redis - Performance Comparison
Understanding Time Complexity
When using Redis for messaging, it is important to understand how the time to process messages grows as more messages or subscribers are involved.
We want to see how the cost changes when using Pub/Sub versus Streams as the number of messages or consumers increases.
Scenario Under Consideration
Analyze the time complexity of these Redis commands for message delivery.
# Pub/Sub publish
PUBLISH channel message
# Streams add and read
XADD mystream * message value
XREAD COUNT 10 STREAMS mystream last_id
Pub/Sub sends messages directly to all subscribers. Streams store messages and let consumers read at their own pace.
Identify Repeating Operations
Look at what repeats when messages are sent or read.
- Primary operation: For Pub/Sub, sending message to each subscriber; for Streams, appending message and reading batches.
- How many times: Pub/Sub sends once per subscriber; Streams append once and consumers read independently.
How Execution Grows With Input
Consider how work grows as subscribers or messages increase.
| Input Size (n) | Pub/Sub Operations | Streams Operations |
|---|---|---|
| 10 subscribers | 10 sends per message | 1 append + 10 independent reads |
| 100 subscribers | 100 sends per message | 1 append + 100 independent reads |
| 1000 subscribers | 1000 sends per message | 1 append + 1000 independent reads |
Pub/Sub cost grows directly with number of subscribers per message. Streams cost grows with number of consumers reading messages separately.
Final Time Complexity
Time Complexity: O(s) where s is number of subscribers or consumers.
This means the work to deliver messages grows linearly with how many clients receive or read them.
Common Mistake
[X] Wrong: "Pub/Sub and Streams have the same cost regardless of subscribers."
[OK] Correct: Pub/Sub sends messages to every subscriber immediately, so cost grows with subscribers. Streams store once but each consumer reads separately, so cost depends on consumers reading.
Interview Connect
Understanding how message delivery scales helps you choose the right Redis feature and explain your reasoning clearly in conversations.
Self-Check
What if we batch multiple messages in one XADD call for Streams? How would that affect the time complexity?