LLD 案例：ATM 取款机

ATM 这道题看起来简单：插卡、输密码、取钱。面试官真正想看的是两件事：一是你能不能把“当前处于哪个阶段”建模清楚，二是钱这件事上你有没有一致性意识——账户扣了款，钞票却没吐出来，这是绝对不能接受的。

需求澄清

功能需求

1. 插卡后输入 PIN；连续 3 次输错，吞卡并结束会话。
2. 认证后可以查余额、取款，存款作为可选项。
3. 取款金额必须能用钞箱里现有的面额凑出来（比如 100、50、20 元）；单笔和单日限额由银行判断。
4. 出钞后退卡，结束会话。

非功能需求

• 扣款和出钞要么都成功，要么都不发生：出钞失败必须冲正。
• 和银行之间的网络会超时、会重试，同一笔取款不能被扣两次。

明确不做：银行账户系统本身（当作外部服务 BankService）、硬件驱动、凭条打印的细节。

核心类

classDiagram
  accTitle: ATM 类图：状态、会话、钞箱与银行接口
  class Atm {
    -AtmState state
    -Session session
    +insertCard(Card card)
    +enterPin(String pin)
    +withdraw(int amount)
    +eject()
  }
  class AtmState {
    <<interface>>
    +insertCard(Atm atm, Card card)
    +enterPin(Atm atm, String pin)
    +withdraw(Atm atm, int amount)
    +eject(Atm atm)
  }
  class Session {
    -Card card
  }
  class CashDispenser {
    -Map counts
    +plan(int amount) Optional
    +dispense(Map notes)
  }
  class BankService {
    <<interface>>
    +verifyPin(Card card, String pin) PinResult
    +debit(Card card, int amount, String txId)
    +reverse(String txId)
  }
  Atm --> AtmState : current
  Atm --> Session
  Atm *-- CashDispenser
  Atm ..> BankService : calls
  AtmState <|.. IdleState
  AtmState <|.. CardInsertedState
  AtmState <|.. AuthenticatedState

用到的设计模式

• 状态模式：同一个按键在不同阶段含义不同。没插卡时按“取款”应该无效，输完 PIN 前也不行。如果在 Atm 的每个方法里写 if (state == ...)，阶段一多，判断会散落在所有方法里。状态模式把“这个阶段允许做什么、做完去哪个阶段”集中到一个类里，加一个“维护中”状态只需要新增一个类。
• 门面：外部（按键面板、读卡器）只和 Atm 打交道，不直接碰状态类和银行接口。
• 依赖注入：BankService 是接口，测试时换成假的实现，可以模拟拒付、超时。

核心代码

状态接口给每个操作一个默认实现“当前不允许”，具体状态只覆盖自己支持的操作：

interface AtmState {
    default void insertCard(Atm atm, Card card) { throw new IllegalStateException("Not now"); }
    default void enterPin(Atm atm, String pin)  { throw new IllegalStateException("Not now"); }
    default void withdraw(Atm atm, int amount)  { throw new IllegalStateException("Not now"); }
    default void eject(Atm atm)                 { atm.endSession(); }   // back to IdleState
}

class IdleState implements AtmState {
    public void insertCard(Atm atm, Card card) {
        atm.startSession(card);
        atm.setState(new CardInsertedState());
    }
    public void eject(Atm atm) { }                                      // no card to return
}

class CardInsertedState implements AtmState {
    public void enterPin(Atm atm, String pin) {
        switch (atm.bank().verifyPin(atm.session().card(), pin)) {      // the bank counts wrong PINs per card
            case OK -> atm.setState(new AuthenticatedState());
            case LOCKED -> atm.retainCard();                            // 3rd wrong PIN in a row: keeps the card, back to idle
            case WRONG -> { }                                           // stays here for another try
        }
    }
}

class AuthenticatedState implements AtmState {
    public void withdraw(Atm atm, int amount) {
        Map<Integer, Integer> notes = atm.dispenser().plan(amount)
            .orElseThrow(() -> new IllegalArgumentException("This amount cannot be paid out"));
        String txId = atm.newTransactionId();
        atm.bank().debit(atm.session().card(), amount, txId);           // throws when declined
        try {
            atm.dispenser().dispense(notes);
        } catch (HardwareException e) {
            atm.bank().reverse(txId);                                   // same id, so a retry is harmless
            throw e;
        }
    }
}

连续输错的次数由银行按卡记，不放在 Session 上。会话在退卡时结束，计数放在会话里的话，输错两次就退卡重插，计数清零，可以无限次猜 PIN。

注意取款的顺序：先算出钞方案，再扣款，最后出钞。先确认钞箱凑得出这个金额，可以避免“扣了款才发现凑不出”的冲正。扣款带上交易号 txId，出钞失败时用同一个交易号冲正。

出钞：贪心不一定对

最直觉的做法是贪心：每次拿能拿的最大面额。可是 100/50/20 这组面额本身就不适合贪心：用户取 60，贪心先拿 50，剩下的 10 凑不出来，于是失败，其实 3 张 20 正好够；取 80 也一样（4 张 20）。钞箱里每种面额的张数还是有限的，比如 100 元的取空了，贪心失败的情况会更多。

面额只有三四种，每次取款金额也有上限，所以直接做一个小搜索就行：

class CashDispenser {
    // denomination -> notes left, largest denomination first
    private final TreeMap<Integer, Integer> left = new TreeMap<>(Comparator.reverseOrder());
    private final CashHardware hardware;

    CashDispenser(CashHardware hardware) { this.hardware = hardware; }

    synchronized Optional<Map<Integer, Integer>> plan(int amount) {
        List<Integer> denoms = new ArrayList<>(left.keySet());
        Map<Integer, Integer> pick = new HashMap<>();
        return search(denoms, 0, amount, pick) ? Optional.of(pick) : Optional.empty();
    }

    // Try many large notes first, then fewer: the first hit uses few notes.
    private boolean search(List<Integer> denoms, int i, int rest, Map<Integer, Integer> pick) {
        if (rest == 0) return true;
        if (i == denoms.size()) return false;
        int d = denoms.get(i);
        for (int k = Math.min(rest / d, left.get(d)); k >= 0; k--) {
            pick.put(d, k);
            if (search(denoms, i + 1, rest - k * d, pick)) return true;
        }
        pick.remove(d);
        return false;
    }

    synchronized void dispense(Map<Integer, Integer> notes) {
        hardware.eject(notes);                                // throws HardwareException on a jam
        notes.forEach((d, k) -> left.merge(d, -k, Integer::sum));
    }
}

搜索时先尝试多用大面额，所以找到的第一个解张数通常很少。不保证一定最少，不过这里只要“凑得出、张数不离谱”就够了。

一致性：超时怎么办

最难的情况不是被拒，而是扣款请求超时：ATM 不知道银行到底扣没扣。这时候：

• 不能出钞，因为可能根本没扣成功；
• 也不能换一个新交易号重新扣款，因为第一笔可能已经成功了，会扣两次；
• 正确做法是用同一个交易号发冲正（或先查询这笔交易的状态）。银行侧按交易号做幂等：没扣过就什么也不做，扣过就退回。

ATM 本地还应该把每一步写进日志（交易号、金额、阶段），断电重启后能知道哪笔交易停在了中间，交给对账流程处理。

扩展讨论

• 存款：新增 DepositState，存入的现金先进暂存区，用户确认后才入账，取消就原样退回。
• 多币种：钞箱的键从面额变成（币种，面额）。
• 维护模式：运维开门补钞时进入 MaintenanceState，拒绝所有用户操作。
• 钞箱余量告警：观察者模式，某个面额低于阈值时通知运维。
• 并发：一台 ATM 同一时刻只服务一个人，本地不需要复杂的锁；真正的并发冲突（同一个账户在两台 ATM 上同时取款）由银行侧保证。