Saga pattern for distributed transactions in RabbitMQ - Time & Space Complexity

Time Complexity: Saga pattern for distributed transactions

O(n)

Understanding Time Complexity

We want to understand how the time to complete a saga grows as the number of steps increases.

How does the number of operations change when more services participate in the saga?

Scenario Under Consideration

Analyze the time complexity of the following RabbitMQ saga coordination snippet.

// Pseudocode for saga steps coordination
for each step in sagaSteps:
  sendCommand(step.command)
  waitForReply(step.replyQueue)
  if reply is failure:
    sendCompensateCommands(previousSteps)
    break
end for

This code sends commands for each saga step, waits for replies, and compensates if a failure occurs.

Identify Repeating Operations

Look at what repeats as the saga runs:

• Primary operation: Looping through each saga step to send commands and wait for replies.
• How many times: Once per saga step, sequentially.

How Execution Grows With Input

As the number of saga steps grows, the total time grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	About 10 command sends and waits
100	About 100 command sends and waits
1000	About 1000 command sends and waits

Pattern observation: Doubling the steps roughly doubles the total operations.

Final Time Complexity

Time Complexity: O(n)

This means the time grows linearly with the number of saga steps.

Common Mistake

[X] Wrong: "The saga runs all steps in parallel, so time stays the same no matter how many steps."

[OK] Correct: Each step waits for the previous to finish, so they run one after another, making time grow with steps.

Interview Connect

Understanding how saga steps add up helps you explain system delays and design better distributed workflows.

Self-Check

"What if we changed the saga to run steps in parallel instead of sequentially? How would the time complexity change?"