parikshan

System: Payment Ledger

Reading time: ~20 minutes  ·  Prerequisites: Two Pointers, Math, Matrix & Heaps, Arrays & Hashing  ·  Capstone: payment-ledger design problem (parikshan systems track)

The product behind the system

Stripe processes hundreds of billions of dollars a year through a ledger that has been described in their engineering blog and at QCon as double-entry bookkeeping over an event-sourced log. Every credit has a matching debit; every transaction is an immutable event; every account balance is a projection. The ledger is the single source of truth for "did this customer actually pay" and "do we owe this merchant money this morning". A bug in this system is not a bug. It is a regulatory incident and potentially a lawsuit.

Adyen, the Dutch payment processor used by Uber, eBay, and Microsoft, has spoken publicly about its single-tier architecture: every payment, in every currency, in every country, runs through one ledger. The same ledger reconciles against the card networks (Visa, Mastercard) and the banks. The architectural simplicity (one ledger, one truth) is intentional and is the reason Adyen can audit any payment end-to-end in seconds.

Razorpay in India and PayU in emerging markets operate at smaller scale but the same shape. PayPal, Square (Block), and Wise all publish enough engineering material to confirm that the double-entry log + idempotency keys + reconciliation is the universal pattern.

This primer is about how the ledger is structured, why exactly-once payment is mostly a lie (the right framing is "exactly-once with reconciliation"), and how the architect designs a system where a wrong sum is mathematically impossible rather than "unlikely".

What the requirements actually are

Functional requirements:

  • Record every monetary movement as a paired credit and debit. Every transaction touches at least two accounts.
  • Compute current balance for any account in constant time given the latest projection.
  • Allow historical replay: as of timestamp T, what was the balance? This is non-negotiable for audit and dispute resolution.
  • Idempotency: the same Idempotency-Key from a client must produce the same response regardless of how many times the client retries.
  • Reconciliation: nightly (or hourly) match against the upstream network's settlement file. Any discrepancy is alerted.
  • Currency conversion with a known FX rate at the time of transaction, never at reconciliation time.

Non-functional requirements:

  • Throughput: ~10,000 transactions per second peak (Stripe order of magnitude on Black Friday). Latency to commit a payment: ~1 second observable to the merchant, ~100 ms inside the ledger after the network round-trip to the card network.
  • Durability: every transaction must survive multi-region failure. Three or more replicas in two or more regions; sync replication on commit.
  • Consistency: strong consistency within an account; eventual consistency across accounts (a transfer from A to B may briefly show A debited but B not yet credited, but never both un-credited or both credited).
  • Cost ceiling: cost per transaction is dwarfed by the network fees (Visa charges 0.05% or so). Engineering cost optimisation is not the main lever; correctness is.

Above all: a missing or duplicate transaction is a P0 incident. There is no "eventual correctness" for money.

The architect's framing

A payment ledger decomposes into six components. The architect must commit to one principle before drawing the boxes: the log is the source of truth; everything else is a projection that can be rebuilt from the log.

                              +---------------+
   client request --->  idempotency key  ---> |  intake API  |
                              +-------+-------+ checks for dup
                                      |
                                      v
                              +-----------------+
                              |  validator      |  amount > 0, currency valid,
                              |                 |  account exists, kyc passed
                              +--------+--------+
                                       |
                                       v
                              +-----------------+
                              |  ledger writer  |  appends paired entries
                              |  (append-only)  |  to immutable log
                              +--------+--------+
                                       |
                                  fan-out
                          +------------+------------+
                          v            v            v
                +-------------+ +-----------+ +--------------+
                | account     | | analytics | | network      |
                | projection  | | warehouse | | gateway      |
                | (balance)   | |           | | (Visa, ACH)  |
                +------+------+ +-----------+ +------+-------+
                       |                             |
                       v                             v
                +-----------+              +------------------+
                |  reads    |              |  settlement file |
                |  / API    |<-- recon ----| (T+1, T+2)       |
                +-----------+              +------------------+

The single most important architectural decision: double-entry, append-only log. Every transaction is a pair of entries (a debit and a credit) that sum to zero. The log is never updated; corrections are new entries (a "reversal" is a credit of an earlier debit, not a delete). The current balance is SUM(entries) for an account.

Account projections are derived: kept in a fast store (Postgres, Spanner, FoundationDB) as (account_id, balance, last_entry_id). On recovery, the projection is rebuilt by replaying the log from any known checkpoint. The projection is disposable; the log is not.

The trade-offs we will name

1. Double-entry vs single-entry.

  • Choice: double-entry, every transaction touches at least two accounts and the entries sum to zero.
  • Alternative considered: single-entry (only the affected account is touched).
  • Why double-entry wins: it gives you an arithmetic invariant, that the sum of all balances across all accounts must equal zero (or a known sum if there are external accounts representing the bank's float). If this invariant ever fails, you know immediately and exactly which transaction caused it. Single-entry has no such check; a lost write looks identical to a deliberate withdrawal. This is the lesson 700 years of accounting taught the world, and software engineers re-learned it in the 2000s after building several broken systems.
  • When single-entry would win: never, for money. For non-monetary counters (like "feature usage credits" with no refund obligations) you can sometimes get away with single-entry, but the moment refunds, disputes, or settlements enter the picture, you need double-entry.

2. Strong consistency vs eventual consistency.

  • Choice: strong consistency within an account, eventual consistency across accounts.
  • Alternative considered: full strong consistency (every account globally locked during a transfer) or full eventual consistency (everything is eventually correct, with no guarantees per request).
  • Why the hybrid wins: locking globally would limit throughput to a single sequential writer. Eventual everywhere would let you double-spend across two regions for seconds. The hybrid uses per-account sequence numbers: each account is a partition with a sequential log; a transfer between two accounts is a saga (two log appends, the second of which is the inverse if the first fails). Stripe, Adyen, and modern banks all use a saga or two-phase variant.
  • When strong-everywhere wins: small ledgers (a single bank branch, a small fintech) where a single Postgres instance handles the entire throughput. The Postgres serialisable-isolation level is genuinely the simplest correct ledger for under ~1000 TPS.
  • When eventual-everywhere wins: never, for money.

3. Idempotency keys on the client vs on the server.

  • Choice: client provides the key, server enforces it.
  • Alternative considered: server generates a key from request hash.
  • Why client-provided wins: networks are unreliable. A client sends POST /charges and the connection drops before the response. The client retries, with the same key. The server recognises the duplicate and returns the original result. If the server generated the key from the request hash, two clients sending the same charge twice would collide; if the client picks the key, each retry is unambiguous.
  • When server-generated wins: internal APIs between trusted services that already pass a trace ID. The trace ID acts as the key. For external APIs, never trust the client to be unique; mandate the key in the API contract.

4. At-most-once vs at-least-once vs "exactly-once".

  • Choice: at-least-once delivery + idempotency = effectively exactly-once.
  • Alternative considered: pure at-most-once (give up after one try; never duplicate).
  • Why the combination wins: distributed systems cannot guarantee exactly-once at the network level (the Two Generals problem). What you can do is guarantee at-least-once delivery (retry until ack) and de-duplicate at the receiver (idempotency key). The architect's saying: "exactly-once is what at-least-once plus idempotency feels like to the client". Anyone who promises exactly-once at the protocol level is selling something.
  • When at-most-once wins: notifications and metrics, where the cost of a duplicate is annoyance and the cost of a miss is forgettable. For payments, the cost of a duplicate refund is dollars; the cost of a missed retry is a stuck customer.

5. Synchronous reconciliation vs end-of-day reconciliation.

  • Choice: end-of-day (or end-of-hour) reconciliation against the network settlement file.
  • Alternative considered: real-time reconciliation per transaction.
  • Why batch wins: card networks (Visa, Mastercard) send settlement files in batches (T+1, T+2). Real-time reconciliation would mean a per-transaction round trip to the network, which is not how the network operates. The system is designed around the fact that truth from the network arrives late; your ledger is provisional until reconciled.
  • When real-time would win: closed-loop systems (a casino's chip ledger, a transit card system) where the issuer and the acquirer are the same entity and there is no external network.

Where the algorithms from this bank actually appear

Reconciliation is the Two Pointers pattern at industrial scale. You have two sorted streams: your internal ledger and the network's settlement file. You walk both with two pointers and emit "matched", "internal-only", or "network-only" for every record. The merge-sorted-array primer is the literal template; the production version handles 100M records per night and has to be incremental (resumable on failure), but the core loop is identical. A senior engineer who can write merge-sorted-array correctly can write the reconciliation engine; one who cannot, cannot.

Money arithmetic is the lesson the plus-one primer encodes in miniature. Money is integer base-100 (or base-1000) cents, never a float. Adding $0.10 + $0.20 in floating point gives 0.30000000000000004, which is wrong. Stripe, Adyen, and every regulated processor stores money as integers (amount: 30, currency: 'USD' means thirty cents). The plus-one discipline of digit-by-digit arithmetic with explicit carry is the same discipline that makes money math safe.

Idempotency-key storage is a hash-map indexed by (account_id, key) returning the original response. The Arrays & Hashing primer is the foundation; the production version uses Redis with a TTL of 24 hours (the typical retry window) and a Postgres fallback for older keys. The key insight: the stored value is the full response, not just a flag. If the original returned a 404 because the account did not exist, the replay must return the same 404, not re-check the account.

Top-K transaction monitoring (largest pending transactions, accounts with the most failed charges) is the Math, Matrix & Heaps pattern. Fraud-detection pipelines maintain heap-based aggregates over rolling windows; the discipline taught by kth-largest-element and top-k-frequent-elements is the same discipline used by the fraud team to surface anomalies.

Sketch implementation

The append-only ledger write, the heart of the system:

import uuid
from dataclasses import dataclass
from typing import Optional

@dataclass(frozen=True)
class Entry:
    entry_id: str        # uuid
    txn_id: str          # groups paired entries
    account_id: str
    amount_minor: int    # signed, in cents (or 1/1000 for forex)
    currency: str        # ISO 4217
    timestamp: int       # epoch ms
    posted_at: int       # ledger insert time, for audit

def transfer(
    ledger,                      # append-only store, e.g. Postgres + FoundationDB
    idempotency_store,           # KV with 24h TTL
    idempotency_key: str,
    from_account: str,
    to_account: str,
    amount_minor: int,
    currency: str,
) -> dict:
    # 1. Idempotency check (NEVER skipped)
    cached = idempotency_store.get(idempotency_key)
    if cached is not None:
        return cached

    # 2. Validation
    if amount_minor <= 0:
        return _error('amount_must_be_positive', idempotency_store, idempotency_key)
    if from_account == to_account:
        return _error('cannot_transfer_to_self', idempotency_store, idempotency_key)

    # 3. Construct the paired entries
    txn_id = str(uuid.uuid4())
    now = current_time_ms()
    debit  = Entry(str(uuid.uuid4()), txn_id, from_account, -amount_minor, currency, now, now)
    credit = Entry(str(uuid.uuid4()), txn_id, to_account,    amount_minor, currency, now, now)

    # 4. Atomic two-entry append. Both succeed or neither does.
    #    Implementations: a serialisable transaction (Postgres),
    #    a single FoundationDB transaction, or a Spanner read-write txn.
    try:
        with ledger.transaction() as tx:
            tx.balance_check(from_account, currency, -amount_minor)  # raises if insufficient
            tx.append(debit)
            tx.append(credit)
            tx.update_projection(from_account, currency, -amount_minor)
            tx.update_projection(to_account,   currency,  amount_minor)
    except InsufficientFundsError:
        return _error('insufficient_funds', idempotency_store, idempotency_key)

    response = {'txn_id': txn_id, 'status': 'committed'}
    idempotency_store.set(idempotency_key, response, ttl_seconds=24*3600)
    return response

Invariants the code preserves:

  1. The two entries always sum to zero (-amount_minor + amount_minor == 0).
  2. Currency is never mixed at the entry level. Forex is a separate transaction with three entries: debit USD, credit a forex-bridge account in USD, credit EUR; the bridge account holds the spread.
  3. The idempotency cache is written after the ledger append succeeds, but the check happens before. The window where a duplicate could slip through is the gap between the ledger commit and the cache write; the architect closes this with an additional uniqueness constraint on (idempotency_key, txn_id) in the ledger itself.
  4. The balance check and the append are atomic. If they were two separate transactions, a race between two transfers from the same account could leave the balance negative. The serialisable transaction (or equivalent) is non-negotiable.

What the code omits but production needs: per-currency precision (some currencies have 0 decimals, some have 3), high-precision FX rates with timestamped snapshots, accounting categories for double-entry compliance (asset, liability, revenue, expense), regulatory reporting fields (KYC, AML flags, settlement-network identifiers), retry budgets and back-pressure on the upstream, and a write-ahead log for crash recovery.

What breaks at scale

100 transactions / hour: one Postgres database, one schema, manual reconciliation in a spreadsheet. The architect's worry is correctness, not throughput.

1,000 TPS: Postgres still handles this. Serialisable isolation level is non-negotiable. Idempotency keys in a separate Redis. Reconciliation is a nightly batch job in Python.

10,000 TPS (Stripe peak): Postgres is no longer the single point. The ledger is partitioned by account: each account's entries live on a shard determined by hash(account_id). Transfers within a shard are local transactions; cross-shard transfers are sagas (two transactions with a compensating action on failure). FoundationDB and Spanner are the open-source-and-managed answers; Stripe famously runs on a custom layer on top of MongoDB plus a homegrown Raft-based store.

100,000 TPS: cross-region replication is the new bottleneck. The architect designs for regional pinning: an account "lives" in one region, transactions to it are routed to that region, cross-region transfers go through a settlement step at the edge. This is how global banking actually works: your USD account lives in the US, your EUR account lives in Europe, a transfer between them goes through correspondent banking.

1M+ TPS: at this scale you are a payment network yourself (Visa, Mastercard). The ledger is sharded across hundreds of clusters. Reconciliation is continuous (every minute against a stream). Latency budgets are sub-100 ms. The engineering organisation is hundreds of people; the architect's job is to prevent regressions in correctness, not to add features.

Named failure modes:

  • Lost write: a ledger entry committed but the response did not reach the client. The client retries with the same idempotency key; the system returns the same response. If the idempotency cache also failed, a second entry could be created. Mitigation: a unique constraint on (idempotency_key) in the ledger itself; the second append fails the unique check and reports the existing transaction.
  • Reconciliation drift: a transaction shows in the network settlement but not in your ledger. Almost always a bug in your intake or a network re-send. Investigation is manual but tractable because both sides have a transaction ID.
  • Skew on cross-shard transfer: the debit succeeded but the credit failed. The saga compensates by reversing the debit. The system is briefly inconsistent but always recovers. The architect's job: make the saga idempotent on retry and observable (every step logged).
  • Money-creation bug: a bug that lets the sum-of-all-balances drift away from zero. Caught by the daily zero-sum check. If found, every transaction since the last clean checkpoint is replayed against a sanity model.

What an interview / staff-engineer review will ask

Q: How do you guarantee a refund is processed at most once even if the merchant retries six times? A: Idempotency keys on every refund request. The first refund records the transaction and caches the response keyed by (merchant_id, idempotency_key) with a 24-hour TTL. The next five retries hit the cache and return the original response. If the cache is unreachable, the ledger's unique constraint on the key catches duplicates as the row insert fails.

Q: How do you compute the balance for an account with 100M historical entries quickly? A: Never recompute from the log on each read. The projection table holds (account_id, balance, last_entry_id); reads are O(1). The log is the source of truth for rebuilding the projection (replay from the last checkpoint), not for serving balance queries directly. The architect's discipline: projections are derived state, refreshed by a process, not computed on the read path.

Q: How do you handle a foreign-currency transaction? A: Three ledger entries: debit the source currency, credit a forex-bridge account in the source currency, credit the destination currency. The FX rate is snapshot at transaction time and recorded as a separate field. The spread (the difference between mid-market rate and the rate charged to the customer) lands in a forex-revenue account.

Q: What happens if the database goes down mid-write? A: The transaction either committed fully (both entries appended, projections updated) or did not (the database rolled back). The client sees an error and retries with the same idempotency key. The next attempt either finds the cached response (success) or finds no record (the first attempt was rolled back) and proceeds. Partial writes are impossible because the log append and projection updates share the same transaction. This is why serialisable-isolation databases are non-negotiable; eventual-consistency databases (Cassandra, DynamoDB without transactions) are not safe for the primary ledger.

Q: How would you build this on Spanner or FoundationDB versus on Postgres? A: Postgres works to ~5,000 TPS on a single instance and ~50,000 TPS sharded with care. Beyond that, the operational overhead of cross-shard transactions in Postgres becomes painful. Spanner and FoundationDB give you cross-shard serialisable transactions natively; the trade-off is operational lock-in (Spanner is GCP-only) and latency floor (cross-region Spanner writes are ~50-100 ms). The architect's call depends on scale targets and existing platform investment.

In the AI-integrated workspace

Payment ledgers are the highest-risk domain for AI code generation in this catalogue. A bug in a ranker hurts engagement metrics; a bug in a ledger creates or destroys money.

What the architect uses AI for:

  1. Boilerplate API surfaces: request validation, error envelope formatting, OpenAPI specs. AI is a force multiplier here and the worst case is a bad error message.
  2. Test generation: AI is very good at enumerating edge cases for ledger math: zero-amount, negative-amount, currency mismatch, self-transfer, account-does-not-exist. The architect feeds these into the test suite.
  3. Reconciliation parsers: parsing a Visa settlement file (a fixed-width format with quirks) is a tedious task AI handles well, with the architect verifying against the spec.

What the architect audits personally:

  1. The double-entry invariant. Every code path that mutates a ledger must produce paired entries summing to zero. The architect grep-audits for any code that inserts a single entry; that path must be either a bug or an internal accounting move with a clearly-named opposing entry.
  2. The idempotency check ordering. Cache lookup before any ledger mutation; cache write after successful commit; ledger has a unique-key constraint as the last line of defence. AI commonly puts the cache write before the commit, which is a bug.
  3. The transaction isolation level. AI defaults to whatever the framework defaults to (often READ COMMITTED in Postgres). For a ledger, this is wrong. The architect demands SERIALIZABLE and verifies the connection-string sets it.
  4. The money arithmetic. Any line that involves * 0.01, / 100, or float(amount) is a bug. Money is integer minor units, end of story. The architect lints for any float in payment code paths.

What the architect refuses from AI:

  • Any "optimisation" that batches ledger writes without preserving the per-transaction atomic boundary. Batching is fine for analytics; it is forbidden for the primary ledger.
  • Any retry logic without idempotency keys. AI happily writes "retry on failure" loops; without an idempotency key, that is a duplicate-charge generator.
  • Any "currency conversion" using a stale or hardcoded rate. Rates must come from a timestamped feed; AI suggesting RATE = 1.08 for USD/EUR is a regulatory landmine.
  • Any storage of card numbers, CVVs, or full bank details. PCI-DSS scope is non-negotiable. AI may helpfully suggest "store the card number for retry"; the architect refuses. Tokens only, ever.

Variants and adjacent systems

  • Bank core ledger: like a payment ledger but with regulatory reporting, anti-money-laundering hooks, and central-bank settlement integration. Open-source examples are scarce; Mambu and Thought Machine are the SaaS players.
  • Cryptocurrency ledger (Bitcoin, Ethereum): public, append-only, distributed with consensus. The double-entry shape is preserved; the durability model is different.
  • Loyalty-points ledger: same double-entry structure, lower regulatory stakes. Airlines and grocery chains run these at scale; the architecture is a smaller payment ledger.
  • In-game currency ledger: World of Warcraft gold, Roblox Robux, Fortnite V-Bucks. Same shape; the auditor is the platform's anti-cheat team, not the FCA or RBI.
  • Subscription billing system (Recurly, Chargebee): a payment ledger plus a recurring-invoice generator. The billing engine produces transactions that the ledger records.
  • Event-sourced order book (exchanges): the ledger pattern applied to securities trading. NYSE, NASDAQ, NSE, and BSE all run event-sourced order books with per-trade entries; the matching engine sits in front of the ledger.