Problem RestatementProblem
Design a backend that stores and updates account balances, like a digital wallet or a bank ledger (asked at Capital One). It supports deposit, withdraw, transfer between accounts, and balance/history queries. It must be correct above all: no money created or lost, no overdrafts (unless allowed), no double processing when requests are retried, and a complete history.
RequirementsRequirements
- Deposit, withdraw, transfer (atomic: both sides or neither), get balance, list history.
- No negative balances (overdraft not allowed).
- Idempotent operations (safe client retries).
- Full audit trail, never edited.
- High availability and durability.
1.1 Scale Estimates
- 50M accounts, 5K transactions/sec at peak, and a few hot accounts (merchants) receive many transfers.
Data Model (double-entry)Data model
CREATE TABLE accounts (
account_id BIGINT PRIMARY KEY, owner_id BIGINT, currency CHAR(3),
balance_cents BIGINT NOT NULL CHECK (balance_cents >= 0), -- materialized balance
version BIGINT NOT NULL DEFAULT 0
);
CREATE TABLE transactions (
txn_id UUID PRIMARY KEY, type TEXT, -- deposit, withdraw, transfer
idempotency_key TEXT UNIQUE, status TEXT, created_at TIMESTAMP
);
CREATE TABLE ledger_entries ( -- append-only
entry_id BIGSERIAL PRIMARY KEY, txn_id UUID REFERENCES transactions,
account_id BIGINT, amount_cents BIGINT, -- + credit, - debit
balance_after_cents BIGINT, created_at TIMESTAMP
);- Double-entry: every transaction writes entries that sum to zero. A transfer of $50 from A to B writes −5000 on A and +5000 on B. A deposit debits an external "cash-in" account and credits the user. If the sum isn't zero, it's a bug.
- Append-only entries: history is never edited. Mistakes are fixed with new reversing entries.
- The materialized balance in
accountsmakes reads fast, and it must always equal the sum of that account's entries (verified by reconciliation).
Transfer Flow (in one DB transaction)Flows
- Idempotency: insert the transaction row with the client's
idempotency_key. If it already exists, return the stored result. - Lock both accounts in a fixed order (e.g., lower account_id first) to avoid deadlocks:
SELECT ... FOR UPDATE. - Check
A.balance >= amount. Otherwise mark the transactionfailed: insufficient funds. - Update both balances, insert the two ledger entries, and mark the transaction
completed. - Commit. Everything happens or nothing does.
An alternative without explicit locks: a conditional update, UPDATE accounts SET balance = balance - 50, version = version + 1 WHERE id = A AND balance >= 50. If 0 rows are updated → insufficient funds. The CHECK (balance >= 0) constraint is a final safety net.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
C["Client + Idempotency-Key"] --> API["Ledger API"]
API --> DB[("Accounts + Ledger DB - ACID")]
API --> OUT[("Outbox")]
OUT --> K[("Events - notifications, analytics")]
REC["Nightly reconciliation"] --> DBDeep Dive — The merchant account everyone pays intoDeep dive
Most accounts are quiet. One merchant receives a thousand transfers a second, and every one of them wants to update the same row.
Lock the merchant's row for each transfer
Every transfer takes SELECT ... FOR UPDATE on both accounts and updates the balances.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
T["1,000 transfers/sec to merchant M"] --> LOCK["All lock the same row in M"]
LOCK --> SER["Serialised - each waits for the previous commit"]
SER --> CAP["Throughput capped by one row's commit latency"]
SER --> QUEUE["Transactions queue, hold connections, time out"]Correctness is fine and throughput is not. Every transfer to this merchant is serialised behind one row, so the system's capacity for its most important customer is the slowest thing in the design.
Conditional updates instead of locks
Replace the explicit lock with UPDATE accounts SET balance = balance + :amt WHERE id = :m. No SELECT first, one statement, shorter transaction.
This meaningfully shortens the time the row is held and is worth doing. It does not change the fundamental constraint: the row is still a serialisation point, and at a thousand writes a second the contention simply reappears as lock waits inside the database rather than as application-level retries.
Split the merchant's balance, and batch what cannot overdraft
The key observation is that credits cannot cause an overdraft. A debit has to check a balance; a credit does not. That asymmetry is what makes the hot path splittable:
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
IN["Incoming transfers"] --> PICK["Pick a sub-account - random or by hash"]
PICK --> S1["M sub-account 1"]
PICK --> S2["M sub-account 2"]
PICK --> SN["M sub-account 16"]
S1 --> READ["Balance = sum of sub-accounts"]
S2 --> READ
SN --> READ
IN2["High-volume credits"] --> BATCH["Batch N credits into one ledger write"]
BATCH --> S1
DEBIT["Debits and payouts"] --> CONSOL["Consolidate sub-accounts first, then one checked debit"]- Sub-accounts spread the writes across sixteen rows instead of one, so contention drops by that factor. A balance read sums them — cheap, and it stays exact because the ledger entries are unchanged.
- Batched credits. Because credits are safe to apply in groups, a hundred incoming transfers can become one ledger write plus one balance update, which is an order of magnitude on its own.
- Debits still take the careful path. A payout consolidates the sub-accounts and then performs one checked, locked debit. Overdraft protection is never relaxed; only the safe side is made fast.
The other two hard parts are worth stating alongside it:
- Cross-shard transfers. Accounts sharded by
account_idcannot share one database transaction, so a transfer becomes a saga: debit A with a pending-out entry, credit B, confirm — each step idempotent, driven to completion by the outbox. A failure reverses the debit rather than leaving money in neither account. - Reconciliation every night. Each account's balance must equal the sum of its entries, and all entries across the system must sum to zero. Sub-accounts and batching make the fast path more complex, so the check that proves it is still correct matters more, not less.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Record keeping | Double-entry append-only ledger | Balanced books, audit trail | Only a balance column: no history, hard to audit |
| Balance | Materialized + reconciled | Fast reads, verified | Sum entries on every read: slow |
| Concurrency | Row locks in fixed order (or conditional update) | No overdraft, no deadlocks | No locking: lost updates |
| Retries | Idempotency keys | Exactly-once effect | Hope clients don't retry |
Wrap-UpWrap-up
Use a relational ACID database with an append-only, double-entry ledger (every transaction's entries sum to zero) plus a materialized balance with a non-negative constraint. Perform transfers in one transaction with idempotency keys and locks taken in a fixed order (or conditional updates). Handle hot accounts with sub-accounts or batched credits, shard with idempotent sagas for cross-shard transfers, and reconcile balances against entries every night.