State Machines for Money

Prerequisite: Distributed Systems

Your payment service crashes between debiting the sender and crediting the recipient. When it recovers, the payment record says processing. What does processing mean? Was the debit attempted? Did it succeed? Was the credit queued? You cannot answer these questions because processing is one state covering three distinct operations, and you have no record of which one was in progress when the process died.

The cost of ambiguous payment state is not a retry or a delayed notification. It is money in an unknown position — debited from one account, not yet credited to another, with no machine-readable record of where the flow stopped.

Why Payment States Are Different

A web application’s state machine for an order might look like created → processing → completed → archived. If the application crashes during processing, you retry the operation. The worst case is a delayed email or a duplicate webhook. The blast radius is measured in user experience, not dollars.

A payment state machine operates under harder constraints:

Constraint	Web application	Payment system
Retry safety	Most operations are naturally idempotent or easily made so	A retry that re-executes a debit creates money
Intermediate states	Can be coarse — “processing” covers a lot	Each sub-operation must be individually recoverable
External effects	Mostly internal database writes	Involves banks, card networks, blockchains — external and irreversible
Failure recovery	Retry from the beginning	Must resume from the exact point of failure
Audit requirement	Logs are nice to have	Every state transition must be explainable to a regulator

The difference between pending in a web app and pending in a payment system: in the web app, pending means “we haven’t finished yet.” In the payment system, pending means “money is in flight between two institutions and neither party has confirmed receipt.” These are not the same kind of waiting.

Designing Payment State Machines

A payment state machine must capture enough granularity that any crash at any point leaves the system in a state from which it can deterministically resume. Each state answers two questions: what has already happened (irreversibly), and what should happen next.

                    ┌──────────┐
                    │ initiated│
                    └────┬─────┘
                         │
                    ┌────▼─────┐
              ┌─────│ debiting │─────┐
              │     └──────────┘     │
              │                      │
        ┌─────▼──────┐    ┌─────────▼──────┐
        │debit_failed│    │  debit_settled  │
        └────────────┘    └────────┬────────┘
                                   │
                          ┌────────▼────────┐
                    ┌─────│   crediting     │─────┐
                    │     └─────────────────┘     │
                    │                              │
           ┌───────▼────────┐       ┌─────────────▼──────┐
           │ credit_failed  │       │  credit_settled     │
           └───────┬────────┘       └────────────────────-┘
                   │
           ┌───────▼────────┐
           │  compensating  │
           └───────┬────────┘
                   │
           ┌───────▼────────┐
           │   reversed     │
           └────────────────┘

Each node is a durable state — persisted to the database before any external action begins. If the process crashes during crediting, recovery loads the payment, sees crediting, and knows: the debit succeeded (that is a fact recorded by the debit_settled → crediting transition), and the credit needs to be attempted or retried.

See Executing Money Flows. The handbook covers the three-phase pattern for money movement. The state machine here makes each phase an explicit, recoverable state.

Persisting Transitions, Not Just States

Storing only the current state loses information. A payment in credit_failed tells you the credit failed, but not how many times, when, or why. The state machine must persist transitions as an append-only log.

CREATE TABLE payment_transitions (
  id            BIGSERIAL PRIMARY KEY,
  payment_id    UUID NOT NULL,
  from_state    TEXT NOT NULL,
  to_state      TEXT NOT NULL,
  triggered_by  TEXT NOT NULL,
  metadata      JSONB,
  created_at    TIMESTAMPTZ NOT NULL DEFAULT now()
);

The current state is derived: SELECT to_state FROM payment_transitions WHERE payment_id = $1 ORDER BY id DESC LIMIT 1. The full history is always available. An auditor asking “what happened to this payment?” gets a complete timeline, not a single status field.

The transition log also enables idempotent state advances. Before attempting a transition, check whether it already happened:

SELECT 1 FROM payment_transitions
WHERE payment_id = $1 AND to_state = $2
LIMIT 1;

If the row exists, the transition already occurred — skip the operation. This makes the state advance function safe to call multiple times without duplicating external effects.

Idempotent State Transitions

Every state transition must be safe to retry. The process may crash after completing the external operation (debiting the sender’s bank) but before persisting the transition (debiting → debit_settled). On recovery, the system retries the transition. If the external operation is not idempotent, the retry creates a duplicate debit.

The idempotency boundary depends on the external system:

External system	Idempotency mechanism	Typical key
Card network	Authorization ID from initial auth	auth_id
ACH	Trace number per NACHA file	trace_number
Wire (Fedwire)	Imad/Omad reference	omad
Blockchain	Transaction hash + nonce	tx_hash
Internal ledger	Idempotency key per entry	idempotency_key (UUID)

For internal operations, you control the idempotency key. For external systems, you must use the identifier they provide and handle the case where the external operation succeeded but you never received the confirmation. This is the “unknown” state — the operation may or may not have completed, and you must query the external system to resolve ambiguity before advancing.

attempt_debit(payment):
  if transition_exists(payment, 'debit_settled'):
    return OK  -- already done

  if transition_exists(payment, 'debiting'):
    -- crashed during debit, check external system
    status = query_bank(payment.debit_reference)
    if status == 'completed':
      persist_transition(payment, 'debiting', 'debit_settled')
      return OK
    if status == 'failed':
      persist_transition(payment, 'debiting', 'debit_failed')
      return FAILED
    if status == 'not_found':
      -- external operation never reached the bank, safe to retry
      submit_debit(payment)

  persist_transition(payment, 'initiated', 'debiting')
  submit_debit(payment)

The key insight: the state machine does not assume the outcome of an interrupted operation. It checks.

Compensation Is Not Rollback

When a payment’s credit leg fails after the debit leg succeeded, you cannot undo the debit. The money left the sender’s account. That is a fact recorded by the sender’s bank, reflected in their statement, and potentially reported to regulators. “Rollback” implies erasing the original — you cannot erase a bank transaction.

Compensation creates a new, forward transaction that reverses the economic effect. A debit of $500 followed by a credit of $500 back to the sender. Both transactions appear in the ledger. Both are visible to auditors. The audit trail shows what happened (debit), what went wrong (credit failed), and how it was resolved (compensating credit).

-- Original debit entry
INSERT INTO entries (account_id, amount, type, reference)
VALUES ('sender', -500.00, 'debit', 'pmt_abc123');

-- Compensating entry — new entry, not a deletion
INSERT INTO entries (account_id, amount, type, reference)
VALUES ('sender', 500.00, 'compensation', 'pmt_abc123_comp');

Compensation has its own failure modes. If the compensating credit to the sender fails, you now have money debited from the sender with neither the intended credit to the recipient nor the compensating credit back to the sender completed. The state machine must handle compensation failure as a distinct state (compensation_failed) with its own retry logic and escalation path.

The compensation window matters. A debit reversed within seconds is operationally simple. A debit reversed after end-of-day settlement requires a separate settlement cycle. A debit reversed after the sender’s monthly statement has been issued requires a statement correction. Time increases the cost and complexity of compensation.

Timeouts and the Unknown State

External operations do not always return. A request to a bank API may hang indefinitely. A blockchain transaction may sit in the mempool for hours during gas price spikes. The state machine must handle the case where an operation neither succeeds nor fails within a defined window.

timeout_policy:
  debit_attempt:    30 seconds  → query bank status
  credit_attempt:   30 seconds  → query bank status
  blockchain_tx:    15 minutes  → check mempool, resubmit with higher gas
  compensation:     60 seconds  → escalate to manual review

After timeout, the system enters an investigation state. It queries the external system for the operation’s status. If the external system confirms success or failure, the state machine advances normally. If the external system also does not know (the request was lost in transit), the state machine records status_unknown and routes to manual review.

Automatic retry after timeout is safe only if the operation is idempotent. For non-idempotent external operations where the outcome is genuinely unknown, automated retry risks duplication. The state machine must distinguish between “definitely failed” (safe to retry) and “outcome unknown” (requires investigation).

Timeout scenario	Automated action	Manual escalation trigger
Bank API timeout, status queryable	Query status, advance state	Bank status API also unavailable
Blockchain tx not confirmed	Check mempool, resubmit if expired	Tx confirmed on a reorged fork
Internal service timeout	Retry with same idempotency key	3 consecutive timeouts

State Machine Enforcement

The state machine’s transition rules must be enforced at the database level, not just in application code. Application-level enforcement fails when two instances of the payment processor race on the same payment, or when a bug in a new deployment skips a required state.

A Postgres advisory lock per payment prevents concurrent transitions:

SELECT pg_advisory_xact_lock(hashtext(payment_id::text));

This lock is held for the duration of the transaction and released on commit or rollback. Two processors attempting to advance the same payment serialize on this lock. The second processor re-reads the current state after acquiring the lock and either skips (transition already happened) or proceeds from the updated state.

For additional safety, a CHECK constraint or trigger can enforce valid transitions:

CREATE OR REPLACE FUNCTION validate_transition()
RETURNS TRIGGER AS $$
BEGIN
  IF NOT EXISTS (
    SELECT 1 FROM valid_transitions
    WHERE from_state = (
      SELECT to_state FROM payment_transitions
      WHERE payment_id = NEW.payment_id
      ORDER BY id DESC LIMIT 1
    ) AND to_state = NEW.to_state
  ) THEN
    RAISE EXCEPTION 'Invalid transition to %', NEW.to_state;
  END IF;
  RETURN NEW;
END;
$$ LANGUAGE plpgsql;

This makes illegal state transitions impossible at the storage layer — a payment cannot jump from initiated to credit_settled regardless of what the application code attempts.

Recovery After Crash

When a payment processor starts (or restarts), it must recover in-progress payments. The recovery sweep queries for payments in non-terminal states and resumes each one from its current state.

SELECT DISTINCT ON (payment_id)
  payment_id, to_state
FROM payment_transitions
WHERE to_state NOT IN ('credit_settled', 'reversed', 'failed')
ORDER BY payment_id, id DESC;

Each recovered payment re-enters the state machine at its persisted state. The state handler for each state knows what to do: debiting checks the debit status, crediting checks the credit status, compensating checks the compensation status.

Recovery volume matters. A clean shutdown with in-flight payment draining produces zero recovery candidates. A crash during a traffic spike may produce thousands. The recovery sweep must be rate-limited to avoid overwhelming external systems with thousands of simultaneous status queries. A sweep that fires 5,000 bank API calls in the first second of recovery creates its own outage.

Stripe processes recovery sweeps at a controlled rate of 100–500 payments per second, with exponential backoff when external systems respond with rate limits. The sweep completes within minutes for normal crash recovery and within an hour for large-scale incidents.

Recovery must be idempotent. If the process crashes during recovery, the next recovery sweep must safely re-process all in-progress payments without duplicating any external effects. This is the same idempotency requirement as normal operation — recovery is not a special case, it is the normal case with a different trigger.

Every payment eventually reaches a terminal state. The state machine guarantees this through timeout escalation: if a payment remains in a non-terminal state beyond its maximum lifetime (typically 24–72 hours depending on the rail), it transitions to failed with a compensation sweep for any completed legs. No payment stays in-flight forever.