Design a payments ledger

Company: Stripe
Difficulty: Hard

Problem statement

Design the double-entry ledger behind a payments API: money movements must never be lost or applied twice.

Requirements

We are building the double-entry ledger that sits under a payments API (charges, refunds, transfers, payouts), where every money movement is recorded exactly once and every balance can be proven from the record.

Functional requirements

• Accounts for every party and purpose: customer balance, merchant available, merchant pending, platform fees, processor clearing, bank settlement, FX positions.
• Post a transaction as a set of entries whose debits equal credits per currency; reject anything that doesn't balance.
• Every post carries an idempotency key; a retry returns the original result instead of posting twice.
• Read balances (available, pending, held) and paginated entry history per account, including "balance as of time T".
• Holds: reserve funds (authorization), then capture, partially capture, or release them.
• Corrections only by reversing or adjusting transactions; nothing is updated or deleted.
• Daily reconciliation against processor and bank reports, with breaks surfaced for investigation.

Non-functional requirements

• Correctness over everything: no lost, duplicated, or half-applied movement. Strong consistency on the write path.
• Durable on commit: synchronous replication to a second zone before acknowledging (RPO 0).
• Post latency p99 under 50 ms; balance reads p99 under 10 ms.
• 99.99% availability for posting; reconciliation and reporting may lag by minutes.
• Full audit trail kept 7+ years; any balance is reproducible from entries.

Back-of-the-envelope estimation

• 10k payment transactions/s at peak, ~4 entries each → 40k entry rows/s, ~1B entries/day at average load.
• Entry row ≈ 200 bytes with indexes → ~200 GB/day, ~70 TB/year before compression. Hot data (90 days) on the OLTP tier, the rest in columnar cold storage.
• 100M accounts; most are cold, but the top few (platform fee account, processor clearing) see thousands of writes/s each. That skew drives the design.
• Idempotency records: 10k/s × 24 h retention × ~300 B ≈ 260 GB live.

API design

Internal gRPC used by the payments services; nothing here is customer-facing.

PostTransaction(PostRequest) → PostResponse
PostRequest {
  idempotency_key: "chg_8f2a:capture"      // unique per logical movement
  type: "charge.capture"
  effective_at: "2026-10-12T10:04:11Z"
  entries: [
    {account: "acct_proc_clearing:USD", direction: DEBIT,  amount: 10000},
    {account: "acct_merch_42:pending:USD", direction: CREDIT, amount: 9680},
    {account: "acct_platform_fees:USD",    direction: CREDIT, amount: 320}
  ]
  metadata: {charge_id: "ch_123", processor_ref: "psp_abc"}
  expected_versions: {"acct_merch_42:pending:USD": 1841}   // optional, for check-and-set
}
PostResponse { txn_id, status: POSTED | DUPLICATE, posted_at, balances_after[] }

CreateHold(account, amount, currency, idempotency_key, expires_at) → hold_id
CaptureHold(hold_id, amount, idempotency_key) → txn_id   // amount ≤ held
ReleaseHold(hold_id, idempotency_key)
Reverse(txn_id, reason, idempotency_key) → txn_id         // mirrored entries
GetBalance(account, as_of?) → {posted, pending, held, available, version}
ListEntries(account, cursor, limit) → entries[]

Amounts are integers in the currency's minor unit (cents, yen). Errors: UNBALANCED, INSUFFICIENT_FUNDS, VERSION_CONFLICT, IDEMPOTENCY_MISMATCH (same key, different body).

Data model

Primary store: a sharded relational database with serializable or row-locking transactions (Postgres/MySQL on Vitess, or Spanner/CockroachDB). We need multi-row atomic commits, unique constraints, and range scans by account; a key-value store would force us to rebuild all three.

Shard key is account_id. Entries for one account live together, so history scans and balance updates are single-shard. A txn_id → shard list index supports lookups of multi-shard transactions. Every committed transaction also goes to an outbox table, which a CDC pipeline streams to Kafka and on to the warehouse (Parquet/Iceberg) for reporting and reconciliation.

High-level design

Build it one requirement at a time. Each drawing adds to the one before; the shaded boxes are what that step adds.

1) Post a transaction exactly once

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"pay","x":0,"y":140,"width":180,"height":70,"label":{"text":"Payments API"}},
 {"type":"rectangle","id":"ledger","x":260,"y":140,"width":180,"height":70,"label":{"text":"Ledger service"}},
 {"type":"ellipse","id":"idem","x":240,"y":-10,"width":220,"height":90,"label":{"text":"Idempotency\ntable"}},
 {"type":"ellipse","id":"db","x":520,"y":130,"width":200,"height":90,"label":{"text":"Sharded\nledger DB"}},
 {"type":"arrow","id":"pay-ledger","x":180,"y":175,"width":80,"height":0,"start":{"id":"pay"},"end":{"id":"ledger"}},
 {"type":"arrow","id":"ledger-idem","x":350,"y":140,"width":1,"height":-60,"start":{"id":"ledger"},"end":{"id":"idem"}},
 {"type":"arrow","id":"ledger-db","x":440,"y":175,"width":80,"height":0,"start":{"id":"ledger"},"end":{"id":"db"}}
]}

1. Post. The payments service builds the entries and calls PostTransaction with a key derived from its own object (charge_id:capture). The ledger validates that it balances per currency and that the accounts exist.
2. Idempotency. In the same DB transaction, it inserts the key into transactions. A unique violation means the movement already happened: return the stored result with DUPLICATE, or IDEMPOTENCY_MISMATCH if the request hash differs.
3. Apply. Lock the affected balances rows in a fixed order (sorted account_id, to avoid deadlocks), check allow_negative and the available balance, insert entries with balance_after, update balances, write the outbox row, and commit once.

2) Fan out committed transactions

{"type":"excalidraw","elements":[
 {"type":"text","id":"legend","x":0,"y":-70,"text":"Shaded: added in this step","fontSize":16},
 {"type":"rectangle","id":"pay","x":0,"y":140,"width":180,"height":70,"label":{"text":"Payments API"}},
 {"type":"rectangle","id":"ledger","x":260,"y":140,"width":180,"height":70,"label":{"text":"Ledger service"}},
 {"type":"ellipse","id":"idem","x":240,"y":-10,"width":220,"height":90,"label":{"text":"Idempotency\ntable"}},
 {"type":"ellipse","id":"db","x":520,"y":130,"width":200,"height":90,"label":{"text":"Sharded\nledger DB"}},
 {"type":"rectangle","id":"outbox","x":800,"y":140,"width":180,"height":70,"label":{"text":"Outbox and\nCDC"},"backgroundColor":"#d0ebff","fillStyle":"solid"},
 {"type":"rectangle","id":"kafka","x":1060,"y":140,"width":180,"height":70,"label":{"text":"Kafka"},"backgroundColor":"#d0ebff","fillStyle":"solid"},
 {"type":"rectangle","id":"notify","x":1320,"y":140,"width":180,"height":70,"label":{"text":"Notifications\nand webhooks"},"backgroundColor":"#d0ebff","fillStyle":"solid"},
 {"type":"ellipse","id":"wh","x":1050,"y":280,"width":200,"height":80,"label":{"text":"Warehouse"},"backgroundColor":"#d0ebff","fillStyle":"solid"},
 {"type":"arrow","id":"pay-ledger","x":180,"y":175,"width":80,"height":0,"start":{"id":"pay"},"end":{"id":"ledger"}},
 {"type":"arrow","id":"ledger-idem","x":350,"y":140,"width":1,"height":-60,"start":{"id":"ledger"},"end":{"id":"idem"}},
 {"type":"arrow","id":"ledger-db","x":440,"y":175,"width":80,"height":0,"start":{"id":"ledger"},"end":{"id":"db"}},
 {"type":"arrow","id":"db-outbox","x":720,"y":175,"width":80,"height":0,"start":{"id":"db"},"end":{"id":"outbox"}},
 {"type":"arrow","id":"outbox-kafka","x":980,"y":175,"width":80,"height":0,"start":{"id":"outbox"},"end":{"id":"kafka"}},
 {"type":"arrow","id":"kafka-notify","x":1240,"y":175,"width":80,"height":0,"start":{"id":"kafka"},"end":{"id":"notify"}},
 {"type":"arrow","id":"kafka-wh","x":1150,"y":210,"width":1,"height":70,"start":{"id":"kafka"},"end":{"id":"wh"}}
]}

1. Fan out. CDC publishes the committed transaction. Consumers update the read models, fire webhooks, and load the warehouse. They are at-least-once and dedupe on txn_id.

3) Reconcile against the processor and the bank

{"type":"excalidraw","elements":[
 {"type":"text","id":"legend","x":0,"y":-70,"text":"Shaded: added in this step","fontSize":16},
 {"type":"rectangle","id":"pay","x":0,"y":140,"width":180,"height":70,"label":{"text":"Payments API"}},
 {"type":"rectangle","id":"ledger","x":260,"y":140,"width":180,"height":70,"label":{"text":"Ledger service"}},
 {"type":"ellipse","id":"idem","x":240,"y":-10,"width":220,"height":90,"label":{"text":"Idempotency\ntable"}},
 {"type":"ellipse","id":"db","x":520,"y":130,"width":200,"height":90,"label":{"text":"Sharded\nledger DB"}},
 {"type":"rectangle","id":"outbox","x":800,"y":140,"width":180,"height":70,"label":{"text":"Outbox and\nCDC"}},
 {"type":"rectangle","id":"kafka","x":1060,"y":140,"width":180,"height":70,"label":{"text":"Kafka"}},
 {"type":"rectangle","id":"notify","x":1320,"y":140,"width":180,"height":70,"label":{"text":"Notifications\nand webhooks"}},
 {"type":"ellipse","id":"wh","x":1050,"y":280,"width":200,"height":80,"label":{"text":"Warehouse"}},
 {"type":"rectangle","id":"files","x":800,"y":440,"width":180,"height":70,"label":{"text":"Processor and\nbank files"},"backgroundColor":"#d0ebff","fillStyle":"solid"},
 {"type":"rectangle","id":"recon","x":1060,"y":440,"width":180,"height":70,"label":{"text":"Reconciliation\njobs"},"backgroundColor":"#d0ebff","fillStyle":"solid"},
 {"type":"rectangle","id":"breaks","x":1320,"y":440,"width":180,"height":70,"label":{"text":"Breaks queue"},"backgroundColor":"#d0ebff","fillStyle":"solid"},
 {"type":"arrow","id":"pay-ledger","x":180,"y":175,"width":80,"height":0,"start":{"id":"pay"},"end":{"id":"ledger"}},
 {"type":"arrow","id":"ledger-idem","x":350,"y":140,"width":1,"height":-60,"start":{"id":"ledger"},"end":{"id":"idem"}},
 {"type":"arrow","id":"ledger-db","x":440,"y":175,"width":80,"height":0,"start":{"id":"ledger"},"end":{"id":"db"}},
 {"type":"arrow","id":"db-outbox","x":720,"y":175,"width":80,"height":0,"start":{"id":"db"},"end":{"id":"outbox"}},
 {"type":"arrow","id":"outbox-kafka","x":980,"y":175,"width":80,"height":0,"start":{"id":"outbox"},"end":{"id":"kafka"}},
 {"type":"arrow","id":"kafka-notify","x":1240,"y":175,"width":80,"height":0,"start":{"id":"kafka"},"end":{"id":"notify"}},
 {"type":"arrow","id":"kafka-wh","x":1150,"y":210,"width":1,"height":70,"start":{"id":"kafka"},"end":{"id":"wh"}},
 {"type":"arrow","id":"files-recon","x":980,"y":475,"width":80,"height":0,"start":{"id":"files"},"end":{"id":"recon"}},
 {"type":"arrow","id":"wh-recon","x":1150,"y":360,"width":1,"height":80,"start":{"id":"wh"},"end":{"id":"recon"}},
 {"type":"arrow","id":"recon-breaks","x":1240,"y":475,"width":80,"height":0,"start":{"id":"recon"},"end":{"id":"breaks"}}
]}

1. Reconcile. Nightly and intraday jobs match processor settlement files and bank statements against clearing-account entries and file the mismatches as breaks.

Final design

The hold expiry sweeper releases expired holds through the same ledger API.

{"type":"excalidraw","elements":[
 {"type":"rectangle","id":"pay","x":0,"y":140,"width":180,"height":70,"label":{"text":"Payments API"}},
 {"type":"rectangle","id":"ledger","x":260,"y":140,"width":180,"height":70,"label":{"text":"Ledger service"}},
 {"type":"ellipse","id":"idem","x":240,"y":-10,"width":220,"height":90,"label":{"text":"Idempotency\ntable"}},
 {"type":"ellipse","id":"db","x":520,"y":130,"width":200,"height":90,"label":{"text":"Sharded\nledger DB"}},
 {"type":"rectangle","id":"outbox","x":800,"y":140,"width":180,"height":70,"label":{"text":"Outbox and\nCDC"}},
 {"type":"rectangle","id":"kafka","x":1060,"y":140,"width":180,"height":70,"label":{"text":"Kafka"}},
 {"type":"rectangle","id":"notify","x":1320,"y":140,"width":180,"height":70,"label":{"text":"Notifications\nand webhooks"}},
 {"type":"ellipse","id":"wh","x":1050,"y":280,"width":200,"height":80,"label":{"text":"Warehouse"}},
 {"type":"rectangle","id":"files","x":800,"y":440,"width":180,"height":70,"label":{"text":"Processor and\nbank files"}},
 {"type":"rectangle","id":"recon","x":1060,"y":440,"width":180,"height":70,"label":{"text":"Reconciliation\njobs"}},
 {"type":"rectangle","id":"breaks","x":1320,"y":440,"width":180,"height":70,"label":{"text":"Breaks queue"}},
 {"type":"rectangle","id":"sweep","x":260,"y":300,"width":180,"height":70,"label":{"text":"Hold expiry\nsweeper"}},
 {"type":"arrow","id":"pay-ledger","x":180,"y":175,"width":80,"height":0,"start":{"id":"pay"},"end":{"id":"ledger"}},
 {"type":"arrow","id":"ledger-idem","x":350,"y":140,"width":1,"height":-60,"start":{"id":"ledger"},"end":{"id":"idem"}},
 {"type":"arrow","id":"ledger-db","x":440,"y":175,"width":80,"height":0,"start":{"id":"ledger"},"end":{"id":"db"}},
 {"type":"arrow","id":"db-outbox","x":720,"y":175,"width":80,"height":0,"start":{"id":"db"},"end":{"id":"outbox"}},
 {"type":"arrow","id":"outbox-kafka","x":980,"y":175,"width":80,"height":0,"start":{"id":"outbox"},"end":{"id":"kafka"}},
 {"type":"arrow","id":"kafka-notify","x":1240,"y":175,"width":80,"height":0,"start":{"id":"kafka"},"end":{"id":"notify"}},
 {"type":"arrow","id":"kafka-wh","x":1150,"y":210,"width":1,"height":70,"start":{"id":"kafka"},"end":{"id":"wh"}},
 {"type":"arrow","id":"files-recon","x":980,"y":475,"width":80,"height":0,"start":{"id":"files"},"end":{"id":"recon"}},
 {"type":"arrow","id":"wh-recon","x":1150,"y":360,"width":1,"height":80,"start":{"id":"wh"},"end":{"id":"recon"}},
 {"type":"arrow","id":"recon-breaks","x":1240,"y":475,"width":80,"height":0,"start":{"id":"recon"},"end":{"id":"breaks"}},
 {"type":"arrow","id":"sweep-ledger","x":350,"y":300,"width":1,"height":-90,"start":{"id":"sweep"},"end":{"id":"ledger"}}
]}

Deep dives

Double entry and correctness invariants. Every transaction has at least two entries, and for each currency the debits equal the credits. The service enforces this, and a database check enforces it again: a deferred constraint, or a post-commit verifier on the outbox that pages on any failure. A charge of $100 with a 3.2% fee is debit processor clearing 10000 / credit merchant pending 9680 / credit platform fees 320. When the processor settles, debit bank cash and credit processor clearing; a clearing account that isn't back to zero after settlement is exactly the signal reconciliation looks for. The global invariant is that the sum over all accounts in each currency is 0, and a job checks it every hour from the per-shard sums.

Idempotency end to end. Keys have to be stable at every hop. The client sends Idempotency-Key to the public API. The payments service stores it on the charge and derives deterministic ledger keys per step (ch_123:auth, ch_123:capture, ch_123:refund:re_9). The ledger's unique constraint commits in the same transaction as the entries, so there is no window where the entries exist but the key does not. Calls to the external processor reuse the same derived key, so a timeout followed by a retry never charges twice. Unknown outcomes (a timeout after sending) go to a pending state, and a resolver asks the processor for the status before posting anything. The ledger never guesses.

Balances: derived vs materialized.

Pick the materialized row plus balance_after. Entries remain the source of truth, and an hourly verifier recomputes snapshot + Σ entries since and compares it to the row. A mismatch blocks the account and pages someone. Balances are split into posted, pending (authorized, not settled), and held. Available = posted − held, and only available can be spent.

Hot accounts. The platform fee account and processor clearing take a write from nearly every charge, and a single locked row tops out around 1–2k updates/s. Fixes, in order of preference: (a) sub-accounts: split platform_fees into 64 shards picked by hash of txn_id, with the logical balance as their sum, which is fine for an account that only receives credits and never needs a spend check; (b) batching: entries land on the hot account asynchronously, and a worker nets them every 100 ms into one entry per batch, with each charge recording a pending-sweep entry; (c) for accounts that do need an overdraft check, such as merchant payouts, keep a single row but group the work: a per-account queue in the ledger service serializes requests and commits 50 at a time in one transaction. Never drop the balance check to win throughput on accounts that can go negative.

Holds, multi-currency, and multi-shard transactions. CreateHold increments held and writes a hold row but posts no entries. CaptureHold posts the real entries and drops held by the captured amount; any remainder is released. A sweeper releases expired holds (card auths typically lapse after 7 days) through the same idempotent API. Each account has one currency. FX is two legs through FX position accounts: debit customer EUR 9200 → credit FX position EUR 9200; debit FX position USD 10000 → credit merchant USD 10000. The rate and quote ID are stored on the transaction, and the FX position balances become the treasury's exposure. When the accounts of one transaction land on different shards, use the database's distributed transaction (Spanner/CockroachDB). On a sharded MySQL, run a saga through a per-shard suspense account: post the debit side and a suspense credit on shard A, then the matching entries on shard B, each step under its own idempotency key. The suspense account must net to zero, and a monitor alerts on anything older than 5 minutes.

Reconciliation, audit, and corrections. Three loops. (1) Internal: the hourly zero-sum check, plus balance rows matched against entry sums. (2) Processor: the T+1 settlement file is matched on processor_ref and amount to clearing entries, with classes for matched, missing in the ledger, missing at the processor, and amount mismatch. Fee differences are auto-posted to a variance account if under a threshold; anything else goes to a human queue. (3) Bank: statement lines (BAI2/camt.053) are matched against bank cash entries and expected payouts. Corrections are always new transactions. Reverse posts mirrored entries linked by reverses_txn_id, and an adjustment posts the delta. The original is never edited, so the books as they stood at any past time can still be reproduced. The tables are append-only through grants (the app role has no UPDATE or DELETE on entries or transactions). Each daily batch can also be hash-chained, with its digest stored in WORM storage as tamper evidence.

Trade-offs

• A relational store with strong transactions costs write throughput and makes sharding harder than a log-structured KV store would, but it gives atomic multi-entry commits and unique keys for free. For money, that trade is worth it.
• Materialized balances give O(1) reads and real-time overdraft checks, but they create hot rows and a second copy that can drift. The verifier is the price of the speed.
• Sub-accounts and batching remove hot spots but make "the" balance of those accounts eventually consistent within seconds. That is only acceptable for accounts that need no spend check.
• Saga with suspense accounts avoids distributed transactions, but money sits visibly in suspense for milliseconds to minutes, and stuck sagas need a repair process.
• Synchronous cross-zone replication adds ~2–5 ms per commit and lowers availability during a zone failure. Losing an acknowledged entry is unacceptable, so we pay it.
• Reversals instead of edits keep a perfect audit trail but double the row count for errors and make the history noisier to read.
• Integer minor units avoid float errors but need care with currencies that have 0 or 3 decimal places and with FX rounding. Rounding remainders go to an explicit rounding account.

Interviewer expectations

Mid-level (L4)

• Models accounts, transactions, and entries with debits = credits, and stores integer minor units.
• Uses an idempotency key with a unique constraint, committed with the entries.
• Keeps entries immutable and corrects with reversals.

Senior (L5)

• Separates posted, pending, and held balances, and walks a charge through auth → capture → settle → payout with real entries.
• Picks materialized balances with a verifier; locks accounts in a fixed order; explains the hot-account limit and at least one fix.
• Carries idempotency through to the external processor and handles unknown outcomes without guessing.
• Describes reconciliation against settlement files and what a clearing account that won't return to zero means.

Staff (L6+)

• Shards by account and has a clear answer for cross-shard transactions (distributed transactions vs saga with suspense accounts) and its failure modes.
• Separates hot-account strategies by whether the account needs a spend check.
• Treats FX as two-leg postings with position accounts and explicit rounding.
• Covers operations: zero-sum and drift monitors, tamper-evident audit, cold storage for 7-year retention, and a break-resolution workflow with owners and SLAs.