Chapter 14: Distributed Transactions

1. The Problem: ACID Across Multiple Nodes

Why Distributed Transactions Are Hard

Single-node transactions rely on ACID guarantees enforced by the database. When operations span multiple nodes, services, or databases, these guarantees break down.

Failure Modes in Distributed Transactions

Motivating Example: E-Commerce Order

Placing an order requires coordinating multiple operations across services:

Order Placement Transaction:
1. Inventory Service: Reserve product (decrement stock)
2. Payment Service: Charge customer's card
3. Order Service: Create order record
4. Shipping Service: Create shipping request
5. Notification Service: Send confirmation email

What happens if:
- Step 2 fails? (Must unreserve inventory)
- Step 3 fails? (Must refund payment AND unreserve)
- Network partitions after step 2? (Money charged, but order not created)

The Dual-Write Problem

The classic anti-pattern that necessitates distributed transactions:

// Anti-pattern: Two separate writes
database.insert(order);          // Write 1
messageQueue.publish(order);     // Write 2

// What if:
// - DB insert succeeds, but message publish fails?
// - Message publish succeeds, but DB insert fails?
// - Process crashes between the two operations?

// Result: Inconsistency between DB and downstream consumers

CAP Theorem Implications

2. Two-Phase Commit (2PC)

Overview

2PC is a blocking, synchronous protocol that ensures all participants either commit or abort. It uses a coordinator to orchestrate a two-phase process.

Protocol Steps

Success Case: All Participants Commit

Failure Case: One Participant Votes NO

The Blocking Problem

2PC's critical flaw: if the coordinator crashes after participants vote YES but before sending COMMIT, participants are stuck holding locks indefinitely.

State Transitions

Implementation Details

class TwoPhaseCommitCoordinator {
  function beginTransaction(participants) {
    txnId = generateId();
    log.write("BEGIN", txnId);

    // Phase 1: PREPARE
    votes = [];
    for (participant in participants) {
      vote = participant.prepare(txnId);
      votes.push(vote);

      if (vote == NO || timeout) {
        // Early abort
        decision = ABORT;
        break;
      }
    }

    // Make decision (write to durable log FIRST)
    if (all votes == YES) {
      decision = COMMIT;
    } else {
      decision = ABORT;
    }
    log.write(decision, txnId);  // CRITICAL: durable before sending

    // Phase 2: COMMIT or ABORT
    for (participant in participants) {
      participant.finalize(txnId, decision);
    }

    // Wait for acks (optional, fire-and-forget also works)
    waitForAcks(participants, txnId);
    log.write("END", txnId);

    return decision;
  }
}

class TwoPhaseCommitParticipant {
  function prepare(txnId) {
    // Try to acquire locks and validate constraints
    if (!canCommit(txnId)) {
      return NO;
    }

    // Write tentative changes to redo log (durable)
    log.write("PREPARED", txnId, changes);

    // Hold locks until COMMIT or ABORT received
    locks.hold(txnId);

    return YES;  // Promise to commit if asked
  }

  function finalize(txnId, decision) {
    if (decision == COMMIT) {
      // Apply changes from redo log
      applyChanges(txnId);
      log.write("COMMITTED", txnId);
    } else {
      // Discard redo log
      rollback(txnId);
      log.write("ABORTED", txnId);
    }

    // Release locks
    locks.release(txnId);

    return ACK;
  }

  function recover(txnId) {
    // On restart, check log
    state = log.read(txnId);

    if (state == PREPARED) {
      // Still waiting for coordinator decision
      // Must contact coordinator or wait
      decision = askCoordinator(txnId);
      finalize(txnId, decision);
    }
  }
}

Recovery and Coordinator Failover

Performance Characteristics

Real-World Usage

When to Use 2PC

• Strong consistency is non-negotiable (financial transactions)
• Participants are co-located (same data center, low latency)
• Transaction volume is low (not a high-throughput system)
• Participants support XA or similar protocol
• Acceptable to block during coordinator failure (e.g., batch jobs)

When to Avoid 2PC

• Microservices across multiple data centers (network latency kills performance)
• High-throughput systems (lock duration bottleneck)
• Need high availability during failures (coordinator SPOF)
• Participants don't all support 2PC
• Can tolerate eventual consistency (use Saga instead)

3. Three-Phase Commit (3PC)

Overview

3PC attempts to solve 2PC's blocking problem by adding a third phase: pre-commit. This allows participants to make progress even if the coordinator crashes, under certain assumptions.

The Three Phases

Success Case

Non-Blocking on Coordinator Failure

Key improvement: if coordinator crashes after PRE-COMMIT, participants know the decision was commit and can proceed.

State Transitions

The Network Partition Problem

3PC's Achilles heel: it assumes a synchronous network with bounded delays. Network partitions break this assumption.

Comparison: 2PC vs 3PC

Why 3PC is Rarely Used

• Higher Latency: 50% more round trips than 2PC
• Network Partition Vulnerability: Can lead to split-brain inconsistency
• Synchronous Network Assumption: Real networks are asynchronous
• Timeout Complexity: Choosing correct timeout values is hard
• No Significant Benefit: In practice, coordinator crashes are rare enough that 2PC blocking is acceptable, or eventual consistency (Saga) is better

Theoretical Interest vs. Practical Reality

Conclusion: 3PC is a textbook protocol that demonstrates the difficulty of achieving non-blocking distributed consensus. In practice, systems use 2PC for strong consistency (accepting blocking) or move to eventual consistency patterns (Saga, TCC) that embrace asynchrony.

4. Saga Pattern

Overview

Saga is an eventual consistency pattern that breaks a distributed transaction into a sequence of local transactions, each with a compensating transaction to undo it if needed. No distributed locks, no blocking.

Two Flavors: Choreography vs. Orchestration

Choreography: Event-Driven Saga

Each service publishes events, and other services react by executing their local transaction and publishing the next event.

Choreography: Failure and Compensation

Orchestration: Centralized Saga Coordinator

A dedicated orchestrator service controls the flow, calling each participant and handling failures.

Orchestration: Failure and Rollback

Compensating Transactions

Compensating transactions are NOT rollbacks - they are forward-correcting operations that semantically undo the effect.

Saga State Machine

Implementation: Orchestrator Pseudocode

class SagaOrchestrator {
  function executeSaga(sagaDefinition, input) {
    sagaId = generateId();
    state = initializeState(sagaId, input);

    try {
      // Execute forward steps
      for (step in sagaDefinition.steps) {
        result = executeStep(step, state);

        if (result.failed) {
          throw new SagaFailure(step, result.error);
        }

        // Save state after each step (for recovery)
        state = updateState(sagaId, step, result);
      }

      // All steps succeeded
      markCompleted(sagaId);
      return state;

    } catch (error) {
      // Saga failed - execute compensating transactions
      compensate(sagaId, state, error);
      throw error;
    }
  }

  function compensate(sagaId, state, originalError) {
    completedSteps = state.getCompletedSteps();

    // Execute compensations in REVERSE order
    for (step in reverse(completedSteps)) {
      try {
        compensatingTxn = step.getCompensation();
        compensatingTxn.execute(state);

        state = updateState(sagaId, "compensated_" + step.name, null);

      } catch (compensationError) {
        // Compensation failed - log and retry
        log.error("Compensation failed for step " + step.name, compensationError);
        retryCompensation(sagaId, step, state);
      }
    }

    markFailed(sagaId, originalError);
  }

  function recover(sagaId) {
    // On restart, load state from durable storage
    state = loadState(sagaId);

    if (state.status == "IN_PROGRESS") {
      // Resume saga from last completed step
      resumeSaga(sagaId, state);
    } else if (state.status == "COMPENSATING") {
      // Resume compensation
      resumeCompensation(sagaId, state);
    }
  }
}

Saga Execution Guarantees (SEC)

Real-World Example: Order Placement Saga

Saga Orchestration Tools

When to Use Saga

• Distributed transactions across microservices
• Can tolerate eventual consistency (not immediate consistency)
• Each step can be compensated (or manual intervention is acceptable)
• Need high availability and throughput (no blocking)
• Long-running transactions (minutes to hours)

When to Avoid Saga

• Strong consistency required (use 2PC or single database)
• Steps cannot be compensated (e.g., physical actions)
• Isolation is critical (intermediate states must not be visible)
• Simple use case (overhead not justified)

Complete Saga Example: E-Commerce Order (All 5 Steps + All Compensations)

This end-to-end example demonstrates a complete order placement saga, including the exact sequence of forward transactions and compensating transactions when a step fails.

Forward Transactions (Success Path)

Failure Scenario: Shipping Service Down at Step 4

Problem: After successfully charging the customer's card (step 3), the shipping service API is down. The saga must compensate by refunding the payment, releasing inventory, and canceling the order.

Compensating Transactions (Executed in Reverse Order)

Key Saga Rules

Saga Flow: Success and Failure Paths

Alternative: Success Path

Handling Compensation Failures: Retry and DLQ

What if a compensation fails? Example: Payment service refunds the card successfully, but Inventory service is down and cannot release the reservation.

Compensation Retry Logic:
1. Attempt releaseReservation(RES-456)
2. If fails: Retry after 1s (exponential backoff: 1s, 2s, 4s, 8s, ...)
3. After 10 retries (or 5 minutes elapsed): Move to Dead Letter Queue
4. Alert operations team: "Saga ORD-123 compensation stuck: inventory reservation RES-456 not released"
5. Human intervention: Manually release reservation or wait for Inventory service recovery and retry

Idempotency Example: Refund Payment

Saga orchestrator might call refundPayment(PAY-789) multiple times due to retries or crashes. The payment service must ensure idempotency:

function refundPayment(payment_id, reason) {
  // Check if refund already exists (idempotency)
  existing_refund = db.query("SELECT * FROM refunds WHERE payment_id = ?", payment_id);
  if (existing_refund) {
    return existing_refund; // Already refunded, return existing refund
  }

  // First time - execute refund
  refund_id = stripe.refund(payment_id, reason);
  db.insert("INSERT INTO refunds (refund_id, payment_id, reason, created_at) VALUES (?, ?, ?, NOW())", refund_id, payment_id, reason);

  return { refund_id: refund_id, status: "success" };
}

Result: Calling refundPayment(PAY-789) 10 times results in exactly 1 refund, not 10 refunds.

Real-World Production Details

5. TCC Pattern (Try-Confirm-Cancel)

Overview

TCC is a three-phase distributed transaction pattern that reserves resources upfront (Try), then either commits (Confirm) or releases (Cancel) them. It's a middle ground between 2PC and Saga.

The Three Phases

TCC Flow: Success Case

TCC Flow: Failure Case (Cancel)

How TCC Differs from Saga

TCC Implementation: Inventory Service Example

class InventoryService {
  // Try: Reserve stock
  function tryReserve(productId, quantity, txnId) {
    // Check if enough stock available
    available = db.query("SELECT quantity FROM inventory WHERE product_id = ?", productId);

    if (available < quantity) {
      return { success: false, error: "Insufficient stock" };
    }

    // Create reservation record (tentative hold)
    reservation = {
      id: generateId(),
      txnId: txnId,
      productId: productId,
      quantity: quantity,
      status: "RESERVED",
      expiresAt: now() + 10minutes  // Timeout for Try phase
    };

    db.insert("reservations", reservation);

    // Decrement available inventory (but don't commit sale yet)
    db.update("inventory SET reserved = reserved + ? WHERE product_id = ?", quantity, productId);

    return { success: true, reservationId: reservation.id };
  }

  // Confirm: Commit the reservation
  function confirm(txnId) {
    reservation = db.query("SELECT * FROM reservations WHERE txn_id = ?", txnId);

    if (!reservation) {
      // Already confirmed or cancelled - idempotent
      return { success: true };
    }

    // Move from reserved to sold
    db.update("inventory SET sold = sold + ?, reserved = reserved - ? WHERE product_id = ?",
              reservation.quantity, reservation.quantity, reservation.productId);

    // Delete reservation record
    db.delete("reservations WHERE txn_id = ?", txnId);

    return { success: true };
  }

  // Cancel: Release the reservation
  function cancel(txnId) {
    reservation = db.query("SELECT * FROM reservations WHERE txn_id = ?", txnId);

    if (!reservation) {
      // Already cancelled - idempotent
      return { success: true };
    }

    // Release reserved inventory
    db.update("inventory SET reserved = reserved - ? WHERE product_id = ?",
              reservation.quantity, reservation.productId);

    // Delete reservation record
    db.delete("reservations WHERE txn_id = ?", txnId);

    return { success: true };
  }

  // Background job: Clean up expired reservations
  function cleanupExpiredReservations() {
    expired = db.query("SELECT * FROM reservations WHERE expires_at < ?", now());

    for (reservation in expired) {
      cancel(reservation.txnId);
    }
  }
}

TCC Coordinator

class TCCCoordinator {
  function executeTransaction(participants, txnId) {
    tryResults = [];

    try {
      // Phase 1: TRY on all participants
      for (participant in participants) {
        result = participant.try(txnId);

        if (!result.success) {
          throw new TryFailure(participant, result.error);
        }

        tryResults.push({ participant, result });
      }

      // All Try succeeded - log COMMIT decision
      log.write("TCC_COMMIT", txnId);

      // Phase 2: CONFIRM on all participants
      for (entry in tryResults) {
        entry.participant.confirm(txnId);
      }

      log.write("TCC_COMPLETED", txnId);
      return { success: true };

    } catch (error) {
      // Try phase failed - log CANCEL decision
      log.write("TCC_CANCEL", txnId, error);

      // Phase 3: CANCEL on all participants (including ones that succeeded)
      for (entry in tryResults) {
        try {
          entry.participant.cancel(txnId);
        } catch (cancelError) {
          // Cancel must succeed - retry
          retryCancel(entry.participant, txnId);
        }
      }

      log.write("TCC_CANCELLED", txnId);
      return { success: false, error };
    }
  }

  function recover(txnId) {
    state = log.read(txnId);

    if (state == "TCC_COMMIT") {
      // Coordinator decided COMMIT - resume Confirm phase
      resumeConfirm(txnId);
    } else if (state == "TCC_CANCEL") {
      // Coordinator decided CANCEL - resume Cancel phase
      resumeCancel(txnId);
    }
  }
}

Idempotency Requirements

All TCC operations (Try, Confirm, Cancel) MUST be idempotent because the coordinator may retry them.

TCC State Diagram

Real-World Use Cases

Advantages of TCC

• Better Isolation: Reserved resources not visible to other transactions
• Predictable: If Try succeeds, Confirm will succeed (no surprises)
• Shorter Inconsistency Window: Faster than Saga's eventual consistency
• No Rollback Complexity: Cancel is simpler than Saga compensation

Disadvantages of TCC

• High Complexity: Every service must implement 3 operations (Try, Confirm, Cancel)
• Resource Locking: Reservations hold resources (availability impact)
• Timeout Management: Must handle expired Try phase reservations
• Extra Round Trip: Try phase adds latency
• Idempotency Required: All operations must be idempotent (implementation burden)

When to Use TCC

• Financial transactions where isolation matters (e.g., prevent double-spending)
• Inventory management with strict availability guarantees
• Resource allocation systems (cloud, tickets, reservations)
• Need better isolation than Saga but can't afford 2PC blocking

When to Avoid TCC

• Services don't naturally support reservations (implementation burden too high)
• Long-running transactions (holding reservations for hours is costly)
• Isolation not critical (Saga is simpler)
• Need true ACID guarantees (use 2PC or single database)

9. Comparison Matrix

Overview Table: All Patterns

Failure Handling Comparison

Use Case Fit

Decision Tree

Performance Characteristics

Implementation Complexity

10. Real-World Patterns

Uber: Trip Lifecycle with Saga

Architecture

Trip Request Saga (Orchestrated with Cadence)

Why Cadence?

• Durable Execution: Workflow state persisted, survives failures
• Automatic Retries: Failed steps retry with exponential backoff
• Timeout Management: Each activity has timeout, workflow can compensate
• Versioning: Can deploy new workflow versions without breaking in-flight trips
• Observability: Full visibility into workflow execution (Cadence UI)

Stripe: Payment Idempotency and Webhooks

Architecture

Idempotency Key Flow

POST https://api.stripe.com/v1/charges
Headers:
  Authorization: Bearer sk_test_...
  Idempotency-Key: 7f3d9c8b-4e2a-4c9f-8e1a-5b6d7c8e9f0a
Body:
  amount=1000
  currency=usd
  source=tok_visa
  description=Order #12345

// Stripe's handling:
1. Check if Idempotency-Key exists in `idempotency_keys` table
2. If exists and status=completed → return cached response
3. If exists and status=processing → return 409 Conflict
4. If new → process payment, cache result with key
5. Return response

// Client can safely retry on network failure
// Same Idempotency-Key = same result (no double charge)

Webhook Delivery (Outbox Pattern)

{
  "id": "evt_1J3Q4R2eZvKYlo2C0X5Y6Z7A",  // Event ID for deduplication
  "type": "charge.succeeded",
  "created": 1625097600,
  "data": {
    "object": {
      "id": "ch_1J3Q4R2eZvKYlo2C0X5Y6Z7A",
      "amount": 1000,
      "currency": "usd",
      "status": "succeeded"
    }
  }
}

// Merchant's webhook handler (idempotent):
function handleWebhook(event) {
  // Check if already processed
  exists = db.query("SELECT 1 FROM processed_stripe_events WHERE event_id = ?", event.id);
  if (exists) {
    return { status: 200, message: "Already processed" };
  }

  // Process event
  db.beginTransaction();
  updateOrder(event.data.object.id);
  db.insert("processed_stripe_events", { event_id: event.id });
  db.commit();

  return { status: 200 };
}

DoorDash: Order Fulfillment Saga

Architecture

Order Placement Saga

Temporal Workflow Code (Simplified)

@WorkflowMethod
public void fulfillOrder(Order order) {
  try {
    // Step 1: Pre-authorize payment
    PaymentResult preAuth = activities.preAuthorizePayment(order.paymentMethod, order.total);
    workflow.sleep(Duration.ofSeconds(1)); // Wait for auth to settle

    // Step 2: Submit to restaurant
    RestaurantResult restaurant = activities.submitToRestaurant(order.restaurantId, order.items);

    // Step 3: Assign Dasher (with timeout)
    DasherResult dasher = activities.assignDasher(
      order.restaurantLocation,
      order.deliveryLocation,
      Duration.ofMinutes(10)
    );

    // Step 4: Capture payment
    activities.capturePayment(preAuth.authId);

    // Step 5: Send notifications
    activities.sendNotification(order.customerId, "Order confirmed!");
    activities.sendNotification(dasher.dasherId, "New delivery!");

    // Mark workflow complete
    activities.completeOrder(order.id);

  } catch (Exception e) {
    // Compensate in reverse order
    compensate(order, e);
  }
}

private void compensate(Order order, Exception originalError) {
  try {
    // Cancel in reverse order
    activities.cancelDasherAssignment(order.id);
    activities.cancelRestaurantOrder(order.id);
    activities.cancelPaymentAuth(order.id);
    activities.sendNotification(order.customerId, "Order cancelled: " + originalError.getMessage());
    activities.markOrderFailed(order.id, originalError);

  } catch (Exception compensationError) {
    // Log and alert - manual intervention needed
    log.error("Compensation failed for order " + order.id, compensationError);
    alertOncall("Compensation failure", order.id, compensationError);
  }
}

Why Temporal?

• Long-Running Workflows: Dasher assignment can take 10+ minutes
• Automatic Retries: Activity failures retry automatically
• Durable Timers: workflow.sleep() survives process restarts
• Versioning: Can change workflow logic without breaking in-flight orders
• Visibility: Temporal UI shows all in-flight orders, stuck workflows

Netflix: Event Sourcing for User Activity

Architecture

Event Sourcing Pattern

All state changes are stored as immutable events. Current state is derived by replaying events.

Guarantees

• Immutable Event Log: Events never deleted (Kafka retention = forever for critical topics)
• Ordering Per User: Kafka partition key = userId (all user events in order)
• Replay Capability: Can rebuild any view by replaying events
• Schema Evolution: Use Avro with schema registry (backward/forward compatible)
• Idempotent Consumers: All consumers handle duplicate events (event ID deduplication)

11. When to Avoid Distributed Transactions

Alternative: Eventual Consistency

Many problems that seem to require distributed transactions can be solved with eventual consistency and domain modeling.

Example: Bank Transfer

Alternative: Single Database

If possible, keep related data in the same database. Use microservices when needed, but don't split data unnecessarily.

When to Keep Data Together

• Strong consistency required: Financial transactions, inventory management
• Frequent joins: Queries span multiple entities (splitting causes N+1 problem)
• Low scale: Single DB can handle load (splitting adds complexity without benefit)
• ACID guarantees: Need rollback, foreign keys, constraints

Alternative: Accepting Inconsistency

Some business domains naturally tolerate inconsistency. Document and communicate these trade-offs.

Examples of Acceptable Inconsistency

Alternative: Reconciliation Jobs

Instead of preventing inconsistency, detect and fix it after the fact.

Reconciliation Pattern

// Run nightly to detect and fix inconsistencies
function reconcileOrders() {
  // Find orders that are PAID but not SHIPPED after 24 hours
  stuckOrders = db.query(`
    SELECT o.id, o.status, p.status as payment_status, s.status as shipping_status
    FROM orders o
    JOIN payments p ON o.id = p.order_id
    LEFT JOIN shipments s ON o.id = s.order_id
    WHERE o.status = 'PAID'
      AND (s.status IS NULL OR s.status = 'PENDING')
      AND o.created_at < NOW() - INTERVAL 24 HOUR
  `);

  for (order in stuckOrders) {
    if (order.payment_status == 'COMPLETED' && order.shipping_status == NULL) {
      // Payment succeeded but shipment never created - create it now
      log.warn("Reconciliation: Creating missing shipment for order", order.id);
      shippingService.createShipment(order.id);

    } else if (order.payment_status == 'FAILED' && order.shipping_status != NULL) {
      // Payment failed but shipment exists - cancel shipment
      log.warn("Reconciliation: Canceling shipment for failed payment", order.id);
      shippingService.cancelShipment(order.id);
      orderService.updateStatus(order.id, 'CANCELLED');
    }
  }
}

Reconciliation Use Cases

• Financial Systems: Daily balance reconciliation (sum of transactions = account balance)
• Inventory: Physical count vs. system count (adjust discrepancies)
• Distributed Caches: Compare cache vs. DB, invalidate stale entries
• Multi-Region: Compare data across regions, flag differences

Alternative: CQRS (Command Query Responsibility Segregation)

Separate write model (commands) from read model (queries). Accept that read model is eventually consistent.

Decision Framework: Do I Need Distributed Transactions?

Anti-Patterns to Avoid

The KISS Principle

Keep It Simple, Stupid. Distributed transactions add immense complexity. Avoid them if possible.