Distributed Transactions

Wikipedia · Two-phase commit

Two-phase commit (2PC) ensures all-or-nothing across multiple nodes. Phase 1: coordinator asks participants to prepare (vote yes/no). Phase 2: if all vote yes, coordinator commits; otherwise aborts. The weakness: if the coordinator crashes after prepare, participants are stuck waiting. Sagas offer an alternative: execute steps with compensating actions for rollback.

Two-phase commit

Scheme

; Two-phase commit simulation.
; Phase 1: coordinator asks, participants vote.
; Phase 2: if all yes, commit. Otherwise abort.

(define (two-phase-commit votes)
  (display "Phase 1: collecting votes") (newline)
  (let loop ((v votes) (i 1))
    (if (null? v) #t
        (begin
          (display "  Participant ") (display i) (display ": ")
          (display (if (car v) "YES" "NO")) (newline)
          (loop (cdr v) (+ i 1)))))

  (display "Phase 2: ")
  (let ((all-yes (let loop ((v votes))
                   (if (null? v) #t
                       (and (car v) (loop (cdr v)))))))
    (if all-yes
        (display "COMMIT")
        (display "ABORT"))
    (newline)))

(display "--- All agree ---") (newline)
(two-phase-commit (list #t #t #t))
(newline)
(display "--- One votes no ---") (newline)
(two-phase-commit (list #t #f #t))

The blocking problem

If the coordinator crashes after sending prepare but before sending commit/abort, participants that voted yes are blocked. They cannot commit (the coordinator might abort) or abort (the coordinator might commit). They must wait. This is why 2PC is called a blocking protocol. Three-phase commit (3PC) adds a pre-commit phase to reduce blocking, but is more complex and still not partition-tolerant.

Saga pattern

A saga splits a distributed transaction into a sequence of local transactions. Each step has a compensating transaction that undoes its effects. If step 3 fails, run compensations for steps 2 and 1 in reverse. No coordinator lock. No blocking. The tradeoff: intermediate states are visible (no isolation).

Scheme

; Saga pattern: forward steps + compensating actions.
; If a step fails, run compensations in reverse.

(define steps (list "reserve hotel" "book flight" "charge card"))
(define compensations (list "cancel hotel" "cancel flight" "refund card"))

(define (run-saga steps compensations fail-at)
  (let loop ((s steps) (c compensations) (i 1) (done (list)))
    (if (null? s)
        (begin (display "Saga completed successfully") (newline))
        (if (= i fail-at)
            (begin
              (display "Step ") (display i) (display " FAILED: ")
              (display (car s)) (newline)
              (display "Running compensations:") (newline)
              (let undo ((d (reverse done)))
                (if (null? d) #t
                    (begin
                      (display "  ") (display (car d)) (newline)
                      (undo (cdr d))))))
            (begin
              (display "Step ") (display i) (display ": ")
              (display (car s)) (newline)
              (loop (cdr s) (cdr c) (+ i 1)
                    (cons (car c) done)))))))

(display "--- Success ---") (newline)
(run-saga steps compensations 99)
(newline)
(display "--- Fail at step 3 ---") (newline)
(run-saga steps compensations 3)

; Saga pattern: forward steps + compensating actions.
; If a step fails, run compensations in reverse.

(define steps (list "reserve hotel" "book flight" "charge card"))
(define compensations (list "cancel hotel" "cancel flight" "refund card"))

(define (run-saga steps compensations fail-at)
  (let loop ((s steps) (c compensations) (i 1) (done (list)))
    (if (null? s)
        (begin (display "Saga completed successfully") (newline))
        (if (= i fail-at)
            (begin
              (display "Step ") (display i) (display " FAILED: ")
              (display (car s)) (newline)
              (display "Running compensations:") (newline)
              (let undo ((d (reverse done)))
                (if (null? d) #t
                    (begin
                      (display "  ") (display (car d)) (newline)
                      (undo (cdr d))))))
            (begin
              (display "Step ") (display i) (display ": ")
              (display (car s)) (newline)
              (loop (cdr s) (cdr c) (+ i 1)
                    (cons (car c) done)))))))

(display "--- Success ---") (newline)
(run-saga steps compensations 99)
(newline)
(display "--- Fail at step 3 ---") (newline)
(run-saga steps compensations 3)

Neighbors

Cross-references

🌐 Ch.4 Consensus — 2PC is a degenerate case where the coordinator is the single proposer

← CAP Theorem by june.kim Gossip Protocols →