Time Complexity: SNS and SQS integration pattern (fan-out)
O(n)
0
0
SNS and SQS integration pattern (fan-out) in AWS - Time & Space Complexity
Understanding Time Complexity
When using SNS to send messages to multiple SQS queues, it's important to understand how the number of queues affects the work done.
We want to know how the number of API calls grows as we add more queues to the fan-out.
Scenario Under Consideration
Analyze the time complexity of sending a message from SNS to multiple SQS queues.
# Create SNS topic
aws sns create-topic --name MyTopic
# Create multiple SQS queues
aws sqs create-queue --queue-name Queue1
aws sqs create-queue --queue-name Queue2
# ... more queues
# Subscribe each SQS queue to the SNS topic
aws sns subscribe --topic-arn arn:aws:sns:region:account-id:MyTopic --protocol sqs --notification-endpoint arn:aws:sqs:region:account-id:Queue1
aws sns subscribe --topic-arn arn:aws:sns:region:account-id:MyTopic --protocol sqs --notification-endpoint arn:aws:sqs:region:account-id:Queue2
# Publish a message to SNS topic
aws sns publish --topic-arn arn:aws:sns:region:account-id:MyTopic --message "Hello"
This sequence sets up SNS to send one message to many SQS queues, creating a fan-out pattern.
Identify Repeating Operations
Look at what happens repeatedly when a message is published.
- Primary operation: SNS delivers the message to each subscribed SQS queue.
- How many times: Once per subscribed queue.
How Execution Grows With Input
As you add more queues, SNS sends the message to each one separately.
| Input Size (n) | Approx. Api Calls/Operations |
|---|---|
| 10 | 10 message deliveries |
| 100 | 100 message deliveries |
| 1000 | 1000 message deliveries |
Pattern observation: The number of message deliveries grows directly with the number of queues.
Final Time Complexity
Time Complexity: O(n)
This means the work grows linearly as you add more queues to the fan-out.
Common Mistake
[X] Wrong: "Publishing one message to SNS sends it once, no matter how many queues are subscribed."
[OK] Correct: SNS sends a separate copy of the message to each subscribed queue, so the total work increases with the number of queues.
Interview Connect
Understanding how message fan-out scales helps you design systems that handle growing workloads smoothly.
Self-Check
"What if we replaced SQS queues with HTTP endpoints subscribed to SNS? How would the time complexity change?"