Implementing the Saga Pattern for Distributed Transactions

Distributed systems often involve multiple independent services that need to coordinate to complete a single business transaction. Ensuring atomicity across these services is challenging. The Saga pattern offers a way to manage data consistency across microservices without relying on a distributed ACID transaction. This challenge will have you implement a basic Saga orchestrator to handle a sequence of operations and their compensation actions.

Problem Description

Your task is to implement a Saga pattern orchestrator in Python. A Saga is a sequence of local transactions. Each local transaction updates data within a single service and publishes a message or event to trigger the next local transaction in the saga. If a local transaction fails, the Saga executes a set of compensating transactions to undo the changes made by preceding local transactions.

You will need to create a SagaOrchestrator class that can:

1. Register Steps: Allow users to register a sequence of steps. Each step should consist of a forward action (the operation to perform) and a compensation action (the operation to undo the forward action).
2. Execute Saga: Run the registered steps sequentially. If all steps succeed, the saga completes successfully.
3. Handle Failures: If any step fails, the orchestrator must execute the compensation actions for all successfully completed preceding steps in reverse order.
4. Manage State: Keep track of which steps have been successfully executed and which have failed.

Key Requirements:

• The SagaOrchestrator should have a method like add_step(forward_action, compensation_action, step_name).
• The forward_action and compensation_action should be callable functions.
• The orchestrator should have a method like run(initial_data) to start the saga.
• The run method should return a boolean indicating success or failure.
• If a forward_action raises an exception, the saga should be considered failed, and compensation should be triggered.
• Compensation should only be triggered for steps that successfully completed their forward action.
• The initial_data should be passed to the first forward_action and the result of each step should be passed as input to the next forward_action.
• Compensation actions should also receive data relevant to the failed step, potentially the data that was passed to its corresponding forward action.

Expected Behavior:

• If all forward actions succeed, the saga completes successfully.
• If any forward action fails, the saga fails, and all previously completed forward actions are compensated in reverse order.

Edge Cases to Consider:

• A saga with no steps.
• A step failing immediately.
• A step failing after several preceding steps have already succeeded.
• A compensation action itself failing (for simplicity in this challenge, assume compensation actions succeed or are handled externally by retries, but be mindful of the concept).

Examples

Example 1: Successful Saga

Imagine a simple order placement saga:

1. Reserve Inventory: Deduct items from stock.
2. Process Payment: Charge the customer.
3. Create Order: Generate an order record.

Input: initial_data = {"item_id": "A123", "quantity": 2, "user_id": "user1"}

Steps:
    - Step 1: reserve_inventory (forward), release_inventory (compensation)
    - Step 2: process_payment (forward), refund_payment (compensation)
    - Step 3: create_order (forward), cancel_order (compensation)

Expected Output:

True (indicating successful completion)

Explanation:

All three forward actions (reserve_inventory, process_payment, create_order) execute successfully. No compensation is needed.

Example 2: Saga Failure and Compensation

Imagine the same order placement saga, but payment processing fails:

1. Reserve Inventory: Deduct items from stock. (SUCCESS)
2. Process Payment: Charge the customer. (FAILS)
3. Create Order: Generate an order record. (NEVER REACHED)

Input: initial_data = {"item_id": "B456", "quantity": 1, "user_id": "user2"}

Steps:
    - Step 1: reserve_inventory (forward), release_inventory (compensation)
    - Step 2: process_payment (forward), refund_payment (compensation)
    - Step 3: create_order (forward), cancel_order (compensation)

Assume process_payment raises an exception.

Expected Output:

False (indicating failure)

Explanation:

• reserve_inventory succeeds.
• process_payment fails.
• The saga orchestrator detects the failure.
• It then executes the compensation for reserve_inventory (i.e., release_inventory) in reverse order of completion.
• create_order is never executed.

Example 3: Failure after Multiple Steps

Consider a slightly longer saga:

1. Step A: Create User Profile.
2. Step B: Send Welcome Email.
3. Step C: Initialize User Preferences. (FAILS)
4. Step D: Grant Initial Permissions. (NEVER REACHED)

Input: initial_data = {"username": "testuser", "email": "test@example.com"}

Steps:
    - Step A: create_profile (forward), delete_profile (compensation)
    - Step B: send_welcome_email (forward), resend_welcome_email (compensation) - simplified compensation
    - Step C: init_preferences (forward), reset_preferences (compensation)
    - Step D: grant_permissions (forward), revoke_permissions (compensation)

Assume init_preferences raises an exception.

Expected Output:

False (indicating failure)

Explanation:

• create_profile succeeds.
• send_welcome_email succeeds.
• init_preferences fails.
• The orchestrator triggers compensation:
  • First, it compensates send_welcome_email (using resend_welcome_email - this highlights that compensation might not be a direct undo but a corrective action).
  • Then, it compensates create_profile (using delete_profile).
• grant_permissions is never executed.

Constraints

• The SagaOrchestrator should be implemented as a single class.
• The forward and compensation actions will be represented by Python functions.
• The maximum number of steps in a saga is 100.
• The input data passed between steps will be a dictionary.
• The solution should be efficient enough to handle up to 100 steps within a reasonable execution time (e.g., < 1 second for a purely in-memory simulation).

Notes

• This challenge focuses on the orchestration logic. You can simulate success and failure by having your placeholder functions either return a value or raise an exception.
• Consider how you will pass data between steps and how compensation actions will receive appropriate context.
• Think about how to manage the state of completed steps.
• For simplicity, assume that if a compensation action fails, it will raise an exception, and this exception will be handled by the orchestrator (though full error recovery for compensation failures is beyond the scope of this basic implementation).
• The concept of idempotency is crucial for Sagas, especially for compensation actions, but is not a primary focus of this specific challenge implementation.