13 — Automated Teller Machine (ATM) System

“Design an ATM. Card in, PIN, pick an amount, take the cash.”

The account was debited and the cash tray jammed. Everything in this chapter exists to make that sentence recoverable.

An ATM is the cleanest object-design problem in the set, for two reasons.

First, it sits on a boundary that cannot be undone. Once a note has left the transport, no try/except puts it back. Software rollback stops at the edge of the motor.

Second, the machine does not own the thing it is spending. The balance lives at the bank; the ATM owns cash. So you have two ledgers, one physical actuator, and a network link that drops.

Three decisions carry the design:

The ask

One line: authenticate a cardholder against a remote bank, then move an exact amount of physical cash from a safe to a human, and make the two ledgers agree afterwards.

Clarifying questions that change the design

Ask these before you draw anything. Each answer removes or adds a whole subsystem.

Four terms in that table, defined once:

• Issuer — the bank that issued the card and holds the account. It is the only party that can move the balance.
• Interchange hop — a request routed through a shared network (Visa, Cirrus, a national switch) because the machine’s operator is not the issuer. The reply is approve or decline and nothing else; the machine never sees a balance.
• Floor limit — the amount below which an offline machine will pay out on its own judgement, betting that the account can cover it.
• Store-and-forward — a local queue of offline-approved transactions, sent to the issuer when the link comes back. It is a second source of truth about money, which is why it doubles the design.

Ask the first one. Offline authorization is the difference between an ATM and a thin terminal. Most interviewers will say online-only, and you have shown you know why that simplifies things.

Actors and use cases

The “Owns” column is the load-bearing one: nobody owns two of these.

The ATM never decrements a balance. A design with account.balance -= amount inside the ATM has misread the problem: the machine is a remote actuator with a local durable log, and the balance is somewhere else behind a network that fails.

Core objects, and why those

The tempting model is one ATM class with methods and an Account field. Three objects have to be lifted out of it before the design can express a jam at all.

Each row below answers one question — what breaks if you fold this object back into ATM?

NotePlanner is a Strategy — an interchangeable algorithm chosen at configuration time — because one amount has several correct answers and choosing between them is an operational decision, not a mathematical one. That argument is Decision 2.

Class diagram

The diagram shows ownership. The thing to look at is the arrowheads out of ATM: filled diamonds (composition) for everything inside the metal box, a plain arrow (association) for the bank.

classDiagram
    class ATM {
        +str atm_id
        +bool in_service
        +withdraw(str, int, Dict) str
        +recover() List~str~
    }
    class Session {
        +State state
        +int pin_tries
        +on(Event) State
    }
    class CashInventory {
        +stock() Dict
        +reserve(NotePlanner, int) Dict
        +replenish(Dict)
    }
    class Cassette {
        +int denomination
        +int count
    }
    class Journal {
        +append(Entry)
        +unsettled() List~Entry~
    }
    class Entry {
        +str txn_id
        +str auth_id
        +int amount
        +Dict plan
        +TxnState state
        +int presented
    }
    class Dispenser {
        +dispense(Dict) int
        +int counted
    }
    class BankGateway {
        <<interface>>
        +hold(str, int) str
        +settle(str, int)
    }
    class NotePlanner {
        <<abstract>>
        +plan(int, Dict) Dict
    }

    ATM "1" *-- "0..1" Session : composition
    ATM "1" *-- "1" CashInventory : composition
    ATM "1" *-- "1" Journal : composition
    ATM "1" *-- "1" Dispenser : composition
    CashInventory "1" *-- "1..4" Cassette : composition
    Journal "1" *-- "0..*" Entry : composition
    ATM "1" --> "1" BankGateway : remote call
    ATM "1" --> "1" NotePlanner : delegates to
    Session "1" --> "1" Card : reads
    NotePlanner <|.. MinNotes
    NotePlanner <|.. BalancedDrain

Every ownership arrow out of ATM is composition: unbolt the machine and the cassettes, the journal file and the dispenser motor go with it. BankGateway is an association because the bank is emphatically not owned by the ATM.

Session is composition at 0..1 because a machine with one card slot has at most one session at a time. That multiplicity is why the interesting race here is not two customers — it is one customer and one servicer.

What this chapter implements, and what it only draws. The runnable code below covers CashInventory, Cassette (as a denomination: count dict entry), Journal, Entry, Dispenser, ATM, a FakeBank standing in for BankGateway, and plan_notes standing in for the MinNotes planner. Session, Card, and BalancedDrain are specified in prose and diagrams only — they are argued for, not coded, because the failure story does not need them to run.

Decision 1 — the session is a state machine, and one region has no exit

A session moves through named states, and the value of drawing them is the region they expose. The picture shows which states exist; the table under it shows what has to be true to move between them and what side effect fires when you do.

stateDiagram-v2
    [*] --> Idle
    Idle --> Authenticating : card inserted
    Authenticating --> Authenticating : wrong PIN, tries < 3
    Authenticating --> RetainingCard : wrong PIN, tries == 3
    Authenticating --> Selecting : PIN ok
    Selecting --> Ejecting : cancel
    Selecting --> Authorizing : withdraw amount
    Authorizing --> Selecting : declined
    Authorizing --> Dispensing : hold placed, intent journalled
    Dispensing --> Settling : notes counted
    Dispensing --> Suspended : jam
    Suspended --> Settling : short dispense recorded
    Settling --> Printing : acknowledged or queued
    Printing --> Ejecting : receipt done
    Ejecting --> Idle : card taken
    Ejecting --> RetainingCard : timeout
    RetainingCard --> Idle : card swallowed

The transition table

This is the artefact to put on the whiteboard. Every row is from state + event + guard -> to state, plus the effect. A guard is a condition that must hold for the transition to fire; if no guard matches, the event is ignored.

Three notes on rows that read strangely:

• amount % 1000 == 0 is in minor units — the smallest indivisible unit of the currency, cents for dollars. 1000 minor units is $10, so the guard says “multiples of ten dollars”. Every amount in this chapter is an integer count of minor units; the reason is below.
• fsync is the system call that forces buffered writes out to the physical disk. Without it the journal entry is in RAM, and RAM does not survive the power cut you wrote the entry for.
• RECOVERY is not a session state. It is a code path that runs at boot, before any card is accepted. That is why it does not appear in the diagram above: no card is in the machine when it runs.

The uncancellable region

The row to say out loud: there is no cancel event on AUTHORIZING, DISPENSING or SETTLING.

From the moment the hold is placed to the moment the settle is written, the cancel button is disabled and the machine is committed. Naming that region is the whole value of drawing the machine. A design that scatters if self.cancelled: return through a withdrawal method has an uncancellable region too — it just cannot say where it begins.

A trace through the bad case

Here is one session hitting a jam, event by event. Follow the state column; the SUSPENDED row is where the machine stops being about this customer.

event                     state after      journal written      cash moved
--------------------------------------------------------------------------
card inserted             AUTHENTICATING   —                    —
PIN entered, correct      SELECTING        —                    —
withdraw 80_00            AUTHORIZING      —                    —
  plan_notes -> {20:4}    AUTHORIZING      —                    —
  hold ok -> auth-1       DISPENSING       INTENT  (fsync)      —
  motor runs, 3 notes     SUSPENDED        SHORT   presented=60_00   $60 out
  settle(auth-1, 60_00)   SETTLING         SETTLED presented=60_00   —
receipt printed           PRINTING         —                    —
card taken                IDLE             —                    —
machine.in_service                                              False

Read the last two columns together. The customer is charged $60, the safe is $60 lighter, and the fourth note is stuck in the transport for the servicer to find. Nobody is out of pocket, and the machine has taken itself out of service so the next customer does not inherit the jam.

Two properties that come free

pin_tries lives on Session, not on Card and not on ATM. Pulling the card destroys the session and resets the local counter; only the issuer’s counter persists across cards and machines. That is correct — the local counter is a UI convenience, the issuer’s counter is the security control.

SUSPENDED is a state of the machine, not of the session. A jam ends this customer’s transaction and every subsequent one, so it has to outlive the object that raised it. In the code below that is the in_service flag on ATM.

Decision 2 — counting out the notes

You have an amount and a set of cassettes. Which notes come out?

Why greedy is wrong here, twice

Greedy takes the largest note that fits and repeats. It is correct for canonical denomination systems — a set where greedy is provably optimal for every amount, which the full US bill set {1, 2, 5, 10, 20, 50, 100} happens to be.

An ATM does not stock the full set. A machine with {$100, $50, $20} cassettes is not canonical, and greedy does not merely use too many notes: it fails to find a combination that exists.

$130 from {100, 50, 20}
greedy    100 -> 30 left; 50 too big; 20 -> 10 left; 20 too big  ->  no plan
exists    50 + 20 + 20 + 20 + 20                                 =  130

The second failure needs no exotic denominations at all, only a cassette running low, which happens on every machine every week:

$80 from 1 x $50 and 4 x $20
greedy    50 -> 30 left; 20 -> 10 left; out of moves             ->  no plan
exists    20 + 20 + 20 + 20                                      =  80

Say both out loud in the interview. The first is about the denomination set; the second is about the inventory. Adding a $10 cassette fixes the first and does nothing for the second.

The planner is a bounded knapsack

Bounded means each denomination can be used at most stock[d] times — the cassette has a finite number of notes. The DP builds one layer per denomination: layer i answers “what is the fewest notes to make each amount, using only the first i denominations?”

The algorithm is the vending machine’s coin bank with the units renamed, and it is worked through there — ch 07, decision 3. Two things are different at an ATM and both matter.

1. The stocked set is deliberately non-canonical, so greedy fails on a full machine and not only on a depleted one.
2. The state space collapses. With step the greatest common divisor of the denominations and the amount, $130 at a $10 step is 13 states rather than 13,000 cents. Every amount and every denomination is a whole multiple of step, so working in units of step loses nothing.

Read the code in three parts: greedy as the foil, the forward DP that fills the layers, and the backward walk that reads a plan out of them.

from __future__ import annotations

import math
from dataclasses import dataclass, replace
from enum import Enum

D20, D50, D100 = 20_00, 50_00, 100_00       # minor units. Never a float


def greedy(amount: int, stock: dict[int, int]) -> dict[int, int] | None:
    """Largest note first. Fast, obvious, and not always correct."""
    plan, left = {}, amount
    for d in sorted(stock, reverse=True):
        n = min(left // d, stock[d])
        if n:
            plan[d] = n
            left -= n * d
    return plan if left == 0 else None


def plan_notes(amount: int, stock: dict[int, int]) -> dict[int, int] | None:
    """Fewest notes for `amount` from bounded `stock`, or None if no
    combination exists. One DP layer per denomination, so denomination `d`
    can be used at most `stock[d]` times."""
    if amount == 0:
        return {}
    step = math.gcd(amount, *stock)
    if step == 0 or amount % step:
        return None
    n, denoms, INF = amount // step, sorted(stock, reverse=True), float("inf")
    layers: list[list[float]] = [[INF] * (n + 1)]
    layers[0][0] = 0.0
    for d in denoms:
        prev, cur = layers[-1], [INF] * (n + 1)
        u, cap = d // step, stock[d]
        for a in range(n + 1):
            if prev[a] == INF:
                continue
            for k in range(cap + 1):
                if a + k * u > n:
                    break
                cur[a + k * u] = min(cur[a + k * u], prev[a] + k)
        layers.append(cur)
    if layers[-1][n] == INF:
        return None
    out, a = {}, n                                    # walk the layers backwards
    for i in range(len(denoms), 0, -1):
        d, u = denoms[i - 1], denoms[i - 1] // step
        for k in range(stock[d] + 1):
            if a - k * u >= 0 and layers[i - 1][a - k * u] + k == layers[i][a]:
                if k:
                    out[d] = k
                a -= k * u
                break
    return out

The layers, filled in by hand

Take plan_notes(130_00, {100: 500, 50: 1000, 20: 4000}). Here step = gcd(13000, 10000, 5000, 2000) = 1000, so n = 13 and the whole table is 14 cells wide instead of 13,001. Each denomination becomes u = d // step units: $100 is 10 units, $50 is 5, $20 is 2.

Each row shows the amounts that are reachable after that denomination has been considered, with the fewest notes needed. Everything not listed is still unreachable.

layers[3][13] = 5, so a plan exists and it uses five notes. Now the backward walk recovers which five. At each layer it asks: how many notes k of this denomination make the arithmetic line up?

a = 13,  layers[3][13] = 5
  $20 (u=2): try k=4 -> layers[2][13 - 8] = layers[2][5] = 1, and 1 + 4 = 5  match
             take 4 twenties, a = 5
a = 5,   layers[2][5] = 1
  $50 (u=5): try k=1 -> layers[1][5 - 5] = layers[1][0] = 0, and 0 + 1 = 1   match
             take 1 fifty, a = 0
a = 0,   layers[1][0] = 0
  $100 (u=10): k=0 -> layers[0][0] = 0, and 0 + 0 = 0                        match
             take 0 hundreds, a = 0

plan = {50: 1, 20: 4}   ->   5000 + 4 * 2000 = 13000  =  $130

Running both planners

The block below is the contract. Compare the greedy line against the plan_notes line in each pair.

STOCKED = {D100: 500, D50: 1000, D20: 4000}
assert greedy(130_00, STOCKED) is None              # a plan exists; greedy misses it
assert plan_notes(130_00, STOCKED) == {D50: 1, D20: 4}

assert greedy(170_00, STOCKED) == {D100: 1, D50: 1, D20: 1}
assert plan_notes(170_00, STOCKED) == {D100: 1, D50: 1, D20: 1}   # agree when greedy works

TIGHT = {D50: 1, D20: 4}
assert greedy(80_00, TIGHT) is None                 # cassette limits, not denominations
assert plan_notes(80_00, TIGHT) == {D20: 4}

assert plan_notes(30_00, {D20: 5}) is None          # genuinely impossible; both agree
assert plan_notes(0, STOCKED) == {}

The 170_00 pair is the one people skip. Greedy is not always wrong — it is wrong unpredictably, which is worse, because the failures land on a customer at 2am and not in your test suite.

Decline before the hold, never after. plan_notes returning None must produce a decline while nothing is reserved and nothing is journalled, which is why withdraw below plans first and holds second. Get that order wrong and every unplannable amount leaves a stray hold on a customer’s account.

Fewest notes is not the only objective

Minimising note count is what a customer asks for and it is not what an operator wants, because it drains one cassette.

Take a machine loaded like this, with $80 the mean withdrawal. The first block is just the load-out — four cassettes and what each is worth.

cassette A   20s      2,000 notes   2,000 * 20     =   40,000
cassette B   20s      2,000 notes   2,000 * 20     =   40,000
cassette C   50s      1,000 notes   1,000 * 50     =   50,000
cassette D   100s       500 notes     500 * 100    =   50,000
total loaded                                          180,000

With {100, 50, 20}, $80 has exactly one representation — four twenties, since 50 + 30 cannot be made. So the note mix is forced, and every withdrawal hits the same two cassettes.

Now run the machine at 200 withdrawals a day and count how long the twenties last.

twenties loaded             2,000 * 2 cassettes    =  4,000 notes
twenties per withdrawal     4
withdrawals per day         200
twenties consumed per day   200 * 4                =  800 notes
days until the 20s run dry  4,000 / 800            =  5
cash dispensed by then      200 * 80 * 5           =  80,000
cash still in the safe      180,000 - 80,000       =  100,000
stranded fraction           100,000 / 180,000      =  0.556

The machine stops serving $80 withdrawals on day 5 with 56% of its cash still locked in the fifties and hundreds.

That is the argument for NotePlanner being a Strategy and not a function. MinNotes is the customer-facing objective. BalancedDrain penalises each cassette by how depleted it is and will hand out 50 + 20 + 10 where a ten cassette exists — five notes’ worth of inconvenience to keep four cassettes alive.

The cost is real, and you should name it: the note mix a customer receives now depends on configuration, so “it gave me six twenties” is a bug report nobody can reproduce without knowing which policy that machine ran.

The race that is actually in the machine

One card slot means one customer at a time, so the concurrent writer is not a second cardholder — it is the servicer at the replenishment door.

CashInventory is read by the planner and written by both the dispenser and the replenishment door. A plan computed against stock that changes before the commit promises notes the machine no longer has. The fix is to make planning and decrementing a single critical section.

Note what reserve does: it takes the planner as a parameter, calls it inside the lock, and decrements in the same breath.

import threading


class CashInventory:
    def __init__(self, cassettes: dict[int, int]):
        self._c, self._lock = dict(cassettes), threading.Lock()

    def stock(self) -> dict[int, int]:
        with self._lock:
            return dict(self._c)

    def reserve(self, planner, amount: int) -> dict[int, int] | None:
        with self._lock:                       # plan and decrement are one step
            plan = planner(amount, dict(self._c))
            if plan is None:
                return None
            for d, k in plan.items():
                self._c[d] -= k
            return plan

    def replenish(self, added: dict[int, int]) -> None:
        with self._lock:
            for d, k in added.items():
                self._c[d] = self._c.get(d, 0) + k

stock() returns a copy, not the live dict, so a caller cannot mutate the inventory by accident or read a half-updated state.

Here is the sequence that matters: two customers wanting $80 from a machine with exactly four twenties, and a servicer between them.

inv = CashInventory({D50: 1, D20: 4})
assert inv.reserve(plan_notes, 80_00) == {D20: 4}
assert inv.stock() == {D50: 1, D20: 0}
assert inv.reserve(plan_notes, 80_00) is None      # second customer, no twenties left
inv.replenish({D20: 4})
assert inv.reserve(plan_notes, 80_00) == {D20: 4}

The second reserve declines before any hold is placed, because the stock is already down to {50: 1, 20: 0} and $80 has no plan there. The lone fifty is still on the books and still spendable — for $50, or $150 once the twenties come back.

reserve decrements at planning time, not at dispensing time. That looks pessimistic until you consider the jam: a jam that presents fewer notes than planned leaves the retracted notes in a reject bin — a locked compartment the machine sweeps un-taken or mis-fed notes into — rather than back in the cassette. The early decrement was right, and the reject bin becomes a term in the reconciliation equation the servicer works through.

Decision 3 — the dispense failure that defines the problem

Debit first, or dispense first? Both are wrong. Worth writing as code, because the loss is a number.

The test harness

Three fakes, and the details in them are the point.

Dispenser simulates a transport that stalls after jam_after notes. counted is the note counter’s reading — a hardware sensor whose value persists in the dispenser’s own memory across a power cut, which is what makes recovery possible at all.

FakeBank offers three operations. hold reserves an amount and returns an auth_id without moving money. settle captures against a hold and is idempotent — replaying the same settle is a no-op rather than a second charge. debit moves money immediately, and exists only to demonstrate the two broken orderings.

from __future__ import annotations   # so `str | None` works on Python 3.9

class Dispenser:
    """`jam_after` notes are presented, then the transport stalls. `counted`
    is the note-counter reading, which survives a power cut."""

    def __init__(self, jam_after: int | None = None):
        self.jam_after, self.counted = jam_after, 0

    def dispense(self, plan: dict[int, int]) -> int:
        self.counted, n = 0, 0
        for d, k in sorted(plan.items(), reverse=True):
            for _ in range(k):
                if self.jam_after is not None and n >= self.jam_after:
                    return self.counted
                self.counted, n = self.counted + d, n + 1
        return self.counted


class FakeBank:
    def __init__(self, balances: dict[str, int]):
        self.balances, self.holds, self._n = dict(balances), {}, 0

    def hold(self, account: str, amount: int) -> str | None:
        if amount > self.balances[account]:
            return None
        self._n += 1
        self.holds[f"auth-{self._n}"] = [account, amount, None]   # captured=None
        return f"auth-{self._n}"

    def settle(self, auth: str, captured: int) -> None:
        acct, _amount, already = self.holds[auth]
        if already is not None:                      # idempotent replay
            assert already == captured, "conflicting settle for one auth"
            return
        self.holds[auth][2] = captured
        self.balances[acct] -= captured

    def debit(self, account: str, amount: int) -> bool:
        if self.balances[account] < amount:
            return False
        self.balances[account] -= amount
        return True

Both naive orderings, priced

Each block below runs one ordering against the same $80 withdrawal. Watch the final balance assertion in each — that is where the money went.

# Ordering A: debit, then dispense. The jam becomes the customer's problem.
bank, disp = FakeBank({"acct": 500_00}), Dispenser(jam_after=3)
bank.debit("acct", 80_00)
presented = disp.dispense({D20: 4})
assert presented == 60_00
assert bank.balances["acct"] == 420_00
assert 80_00 - presented == 20_00        # $20 short, and only a claim gets it back

# Ordering B: dispense, then debit. The decline becomes the bank's problem.
bank2, disp2 = FakeBank({"acct": 50_00}), Dispenser()
presented2 = disp2.dispense({D20: 4})
assert presented2 == 80_00
assert bank2.debit("acct", 80_00) is False
assert bank2.balances["acct"] == 50_00   # $80 walked out; nothing left to reverse

Ordering A loses the customer’s money and turns a mechanical fault into a multi-day dispute. Ordering B loses the bank’s money and is repeatable, which makes it an exploit rather than a bug — a $50 account can withdraw $80 all day.

Neither is fixable by reordering, because the defect is not the order — it is that one non-atomic pair of steps is being asked to behave atomically.

The protocol: bracket the physical action

The real design puts a durable record on each side of the motor.

1. Hold, do not debit. The bank reserves the amount and returns an auth_id. Nothing has moved.
2. Journal the intent, fsync, then actuate. What the machine is about to do is on disk before the motor turns.
3. Actuate. The note counter reports what was actually presented.
4. Journal the outcome with the counted amount.
5. Settle the hold for the amount presented, keyed by auth_id. A short dispense settles short; nothing ever settles more than the hold.

That is the same shape as an outbound charge to a payment provider — a durable intent record, an idempotency key that makes replay safe, and a reconciliation pass that closes whatever the crash left open. It is worked out in full in ch 27, deep dive 3 and is not re-derived here.

The ATM’s own contribution is that the side you cannot undo is a stepper motor rather than a third-party API, and that the arbiter of last resort is a human counting notes.

The journal and the ATM

Four things to look for in the code below.

• TxnState names the four points a transaction can be caught at. Only SETTLED is terminal.
• Journal.append copies the plan dict on the way in (replace(e, plan=dict(e.plan))). A log entry that shares a mutable dict with live code is not a record of what happened.
• Journal.unsettled walks the log backwards and keeps the first entry it sees per txn_id, so the latest state of each transaction wins. It then returns only those whose latest state is not SETTLED.
• withdraw takes a crash_at argument. That is a test hook, not production code: it returns early at a named point to simulate a power cut, so the recovery path can be exercised without pulling a plug.

One structural note. ATM below takes stock as a plain dict rather than holding a CashInventory. That keeps the failure demo to one moving part. In the real machine withdraw would call inventory.reserve(plan_notes, amount) and use the plan it returns — same plan, same lock, one fewer argument.

from __future__ import annotations   # so `str | None` works on Python 3.9

class TxnState(Enum):
    INTENT = "dispense_intent"
    DISPENSED = "dispensed"
    SHORT = "short_dispense"
    SETTLED = "settled"


@dataclass
class Entry:
    txn_id: str
    auth_id: str
    amount: int
    plan: dict[int, int]
    state: TxnState
    presented: int = 0


class Journal:
    """Append-only, fsync before return. On real hardware this is the EJ file
    — the electronic journal, a write-ahead log of every transaction."""

    def __init__(self) -> None:
        self._log: list[Entry] = []

    def append(self, e: Entry) -> None:
        self._log.append(replace(e, plan=dict(e.plan)))

    def unsettled(self) -> list[Entry]:
        seen, out = set(), []
        for e in reversed(self._log):            # latest state per txn wins
            if e.txn_id in seen:
                continue
            seen.add(e.txn_id)
            if e.state is not TxnState.SETTLED:
                out.append(e)
        return out


class ATM:
    def __init__(self, bank: FakeBank, disp: Dispenser, journal: Journal):
        self.bank, self.disp, self.journal = bank, disp, journal
        self.in_service, self._n = True, 0

    def withdraw(self, account: str, amount: int, stock: dict[int, int],
                 crash_at: str | None = None) -> str:
        plan = plan_notes(amount, stock)
        if plan is None:
            return "declined: no note combination"      # decline BEFORE the hold
        auth = self.bank.hold(account, amount)
        if auth is None:
            return "declined: insufficient funds"
        self._n += 1
        txn = f"txn-{self._n}"
        self.journal.append(Entry(txn, auth, amount, plan, TxnState.INTENT))
        if crash_at == "after_intent":
            return "crashed"
        presented = self.disp.dispense(plan)
        state = TxnState.DISPENSED if presented == amount else TxnState.SHORT
        self.journal.append(Entry(txn, auth, amount, plan, state, presented))
        self.in_service = self.in_service and state is TxnState.DISPENSED
        if crash_at == "before_settle":
            return "crashed"
        self.bank.settle(auth, presented)
        self.journal.append(Entry(txn, auth, amount, plan,
                                  TxnState.SETTLED, presented))
        return f"dispensed {presented}"

    def recover(self) -> list[str]:
        """Runs on boot. The journal says what was intended, the note counter
        says what happened, and settle is idempotent, so replay is free."""
        acts = []
        for e in self.journal.unsettled():
            presented = self.disp.counted if e.state is TxnState.INTENT \
                else e.presented
            self.bank.settle(e.auth_id, presented)
            self.journal.append(replace(e, state=TxnState.SETTLED,
                                        presented=presented))
            acts.append(f"{e.txn_id} settled {presented}")
        return acts

in_service is deliberately sticky: self.in_service and state is DISPENSED can only ever go from True to False. One jam takes the machine out of service and nothing in the withdrawal path puts it back. Clearing it is a servicer action.

recover reads self.disp.counted for entries stuck at INTENT, because that is the only evidence of what the motor did before the power went. It is safe here because one card slot means at most one transaction is ever in flight — a machine with concurrent dispensers would need a per-transaction counter reading.

Three crashes, run

Each block below is one failure, from a fresh machine. Read the balance assertion in each: that is the customer’s money after the dust settles.

# 1. The jam: settle what the counter saw, and stop serving.
bank = FakeBank({"acct": 500_00})
atm = ATM(bank, Dispenser(jam_after=3), Journal())
assert atm.withdraw("acct", 80_00, TIGHT) == "dispensed 6000"
assert bank.balances["acct"] == 440_00           # charged 60.00, not 80.00
assert atm.in_service is False

# 2. Power cut between the dispense and the settle: replay closes it.
bank = FakeBank({"acct": 500_00})
atm = ATM(bank, Dispenser(), Journal())
assert atm.withdraw("acct", 80_00, TIGHT, crash_at="before_settle") == "crashed"
assert bank.balances["acct"] == 500_00           # nothing charged yet
assert atm.recover() == ["txn-1 settled 8000"]
assert bank.balances["acct"] == 420_00
assert atm.recover() == []                       # replay is a no-op

Case 1: the customer received $60, so the customer is charged $60. 500_00 - 60_00 = 440_00. The fourth twenty is in the transport, the machine is out of service, and the discrepancy the servicer reconciles is one note.

Case 2: the crash happens after the motor ran and before the settle. On boot, recover finds the DISPENSED entry, settles the 8000 the counter reported, and the balance lands at 420_00. The second recover returns [] because that transaction’s latest journal state is now SETTLED.

# 3. Power cut after the intent, before the motor turned.
bank = FakeBank({"acct": 500_00})
disp = Dispenser()
atm = ATM(bank, disp, Journal())
assert atm.withdraw("acct", 80_00, TIGHT, crash_at="after_intent") == "crashed"
assert disp.counted == 0
assert atm.recover() == ["txn-1 settled 0"]
assert bank.balances["acct"] == 500_00           # hold released, nothing charged

Case 3 is what justifies journalling before the motor turns rather than after. The counter reads 0, so recovery settles 0, which captures nothing and closes the hold. The customer is untouched.

Without the INTENT record, nothing on disk ties auth-1 to this machine: the hold sits open until it ages out, and the safe count at the end of the route has a gap no one can attribute.

Every crash point, and what closes it

This table is the whole protocol read as a failure matrix. “Held” means the funds are reserved but not captured; “captured” means the balance actually moved.

Every row resolves without a human except the jam, which needs one anyway because there are notes stuck in the transport.

Money is an integer count of minor units

80_00 throughout, never 80.0. 80_00 is eight thousand cents; the underscore is Python’s digit separator and is there to make the dollars and cents readable.

The arithmetic for why floats fail — ten additions of a dime not making a dollar — is asserted in ch 09, money, and the ledger consequence is in ch 27, deep dive 2.

The ATM-specific corollary is that denominations are integers too, so the planner above is exact end to end. A float anywhere in it produces a plan whose notes do not sum to the amount requested, which the note counter then reports as a short dispense on a machine that never jammed — a phantom fault that no servicer can find.

Extension scenarios

“Now support deposits”

What does not change: Journal, Entry, recover(), and the settle-what-was-counted rule. A deposit is the same bracketed physical action with the sign flipped, which is the payoff for having named the field presented rather than dispensed.

What changes is a state, not a field. Cash acceptance has an escrow — a holding bay the notes sit in, inside the machine but not yet in the safe. The validator counts and authenticates them there, the customer sees a total and can still refuse, and only on confirm do they drop into the safe.

So the deposit path has a genuine cancel point that the withdrawal path does not, and the machine grows ACCEPTING -> COUNTING -> ESCROW -> {COMMITTING, RETURNING}.

The credit posted to the account is provisional until the servicer’s count agrees, because a note validator is a sensor and sensors are wrong.

CashInventory becoming bidirectional sounds like one new method and is not. The inventory stops being monotone decreasing, so cash-out-per-day no longer bounds the safe’s contents, and the reconciliation equation gains terms for the deposit bin and the reject bin.

“Now add multi-currency”

The planner already takes an arbitrary stock dict and does exact integer arithmetic, so a second currency is a second cassette set and a second call. That part is nearly free.

The expensive part is the type. Bare int amounts must become a Money value object carrying a currency and refusing to add across currencies, and that touches every signature in the chapter — hold, settle, Entry.amount, dispense. Name that cost rather than waving past it; the interviewer is checking whether you know that “add a currency field” is a whole-codebase change.

The genuinely hard part is neither. It is that the FX rate has to be captured in the journal at authorization time and settled at that captured rate. A rate that moves between hold and settle makes the two ledgers disagree by an amount nobody can attribute. The rate is not a parameter of the transaction; it is part of the record of it.

“Now support a daily withdrawal limit across ATMs”

The limit is shared state, and that is the entire difficulty. Every other extension here is local to one machine. This one is not, and no amount of good design inside the ATM helps.

The counter cannot live in the ATM. One card at two machines is a distributed counter with no coordination, and a per-machine counter lets a cardholder take the limit n times at n machines.

It lives at the issuer, and it is checked in the same atomic step as the funds check — which the design already has, because that step is hold. The WHERE clause below does the check and the increment in one statement, so there is no window between reading used and writing it.

LIMIT_SQL = """
UPDATE daily_usage
   SET used = used + :amount
 WHERE card_id = :card AND day = :day
   AND used + :amount <= :limit
"""
# Then: if cursor.rowcount == 0, decline. Read-then-write is the bug -- two
# ATMs both read used = 400_00, both find 100_00 fits under 500_00, both write.

Two subtleties separate answers here:

• The limit is consumed by the settled amount, not the authorized one. A jam that presents $60 of an authorized $80 has to give $20 of allowance back, so the settle path decrements used by the difference. A design that only increments at authorization charges customers for cash they never received — in allowance rather than in dollars, which makes it harder to notice and no less wrong.
• A hold that is never settled must release its slice of the limit, on the same expiry timer that releases the funds hold. Otherwise a machine losing power at the wrong moment costs its customer a day of withdrawals.

The clock that expires those holds is injected, for the reason argued in ch 12: a limit that resets at midnight in some timezone is a rule, and a rule you cannot advance a clock against is a rule you cannot test.

What interviewers probe

Cheat sheet

Previous: ch 12. Next, the same lifecycle discipline applied to a workflow with humans at every step: ch 14.