28 — Design A Digital Wallet

“Design a digital wallet. Users hold balances and send money to each other and to merchants.”

This chapter is about storing and moving money inside a system you fully own — no card network, no outside company in the middle. Owning both sides makes the problem harder, not easier.

Three things you will be able to do by the end:

• explain why a balance is computed rather than stored, and what that computation costs;
• explain why a single popular account is a hard throughput ceiling, and derive the number rather than quote it;
• move money between two machines without the distributed transaction everyone reaches for first, and say why “just use two-phase commit, you own both databases” is the wrong answer — in numbers, not adjectives.

What goes in and what comes out

The input is a transfer request with five fields: a sender account, a receiver account, an amount in whole pennies, a currency, and an idempotency key (a caller-supplied string that marks a retry as the same request rather than a new one).

There are three outputs:

1. a transfer record whose state is one of SENDER_DEBITED, COMPLETED, or COMPENSATED;
2. four immutable bookkeeping rows called ledger entries — two on the sender’s machine, two on the receiver’s;
3. an updated balance that both parties can read.

A balance read is separate: it takes an account id and returns a number plus the position in the log that number was computed at.

Vocabulary, before anything else

Five terms recur on every page. None of them requires opening another chapter, though every one of them has a chapter that derives it.

• Ledger — an append-only list of rows. Rows are added, never edited and never deleted. It is the system’s only record of where money is.
• Minor units — whole pennies. $5.00 is written 500, never 5.00. Binary floating-point cannot represent 0.1 exactly, so money arithmetic on floats silently loses fractions (Deep dive 2 money is never a float demonstrates the loss).
• Double-entry — the rule that every movement of money is recorded as two or more signed lines that add to zero. Money leaving one account is money arriving in another, written once in two halves. So SUM(amount_minor) = 0 holds over the whole ledger at every instant, and any nonzero result names a broken transaction (Deep dive 1 double entry derived derives it, proves what it catches, and prices the check).
• Idempotency — the property that doing something twice leaves the world as it would be after doing it once. The four rules for building it are in 9a the idempotency rules in one place, extended across an external boundary in Deep dive 3 idempotency across a boundary you cannot roll back, and restated for this chapter’s needs in Saga and why compensate is not rollback.
• PSP, or payment service provider — the outside company that talks to card networks on your behalf. It dominates chapter 27, and this chapter deliberately does not have one.

Why this is not chapter 27 again

Chapter 27 put the ledger at the edge of the company, where a card network holds half the state and you cannot see it.

This chapter puts the ledger inside, where you own every byte — and the problem changes shape completely: 10,000 writes per second land on a single merchant’s account row, and a row lock serializes all of them.

A row lock is the database’s way of stopping two transactions from changing the same row at once: the first transaction to touch the row holds it until it commits, and everyone else waits. Serialize means exactly that — the writes happen one after another, never at the same time.

Three numbers are new here, and the table says where each is derived:

1. Framing: what decision, and what breaks

Before any boxes get drawn, one question has to be settled: how is a balance represented? Everything else — the traffic numbers, the interface, the architecture — either feeds that decision or follows from it. And the decision is harder here than in most systems, because a wallet that owns both sides of every transfer has nobody else to blame for a wrong number.

No third party, and why that hurts

There is no third party in this design. The wallet is the bank, so a transfer is two writes you control end to end.

That sounds easier. It is not. Owning both sides removes your last excuse for being eventually consistent — the arrangement where different copies of the data disagree for a while and are guaranteed only to agree in the end.

A user who sees a balance and cannot spend it has been lied to, and there is no payment provider to blame.

The decision: how a balance is represented

There are exactly three candidates.

1. A number in a column, updated in place. Fast, and it cannot be the truth: a money movement has two halves, and if the process dies between them, both rows are individually plausible and no constraint fires — the corruption lives in the relationship between two rows, which the schema does not record (What a single balance column loses walks the failure line by line).
2. A fold over an append-only log of entries. To fold a list is to walk it start to finish carrying a running result — here, adding up every signed entry — so a balance becomes a computation rather than a stored value. Correct, auditable, able to answer questions about any past instant, and unusably slow to read at scale.
3. Both: the log is the truth, and the column holds a memoized copy of the fold — memoized meaning “computed once and saved, so it need not be recomputed” — maintained in the same transaction as the entries it summarizes, with a background job that re-folds the log and compares.

Option 3 is the answer. Everything hard in the rest of the chapter follows from it:

• how often you save a running total (Snapshots derived from a recovery target);
• what happens when one account’s fold is being extended at 10,000/s against a row that sustains 1,333/s (Deep dive 2 the hot account);
• what happens when the two accounts in a transfer live on different machines (Deep dive 3 transfers across shards).

What breaks: the hot account

A hot account is one that takes vastly more traffic than the rest. Not the average account — the average account gets a handful of entries a day and every design here would work for it.

One merchant during a flash sale takes a third of the entire system’s peak write traffic onto a single primary key. Every mechanism that was comfortable at the average becomes a queue at that peak.

Requirements

Three words recur below. A credit here means money arriving in an account and a debit means money leaving it. A hold is money set aside — reserved so it cannot be spent twice — while some pending thing resolves.

Functional

• Hold a per-user, per-currency balance. Credit it, debit it, place and release holds.
• Transfer between two internal accounts atomically from the user’s point of view — meaning the user never observes a state where the money is half-moved.
• Return a balance and a paginated statement.
• Reproduce the balance as of any past instant, from the log alone.

Non-functional. Two shorthands appear in the table.

p99 is the 99th percentile: the latency that 99 requests in 100 come in under. It describes the slow tail rather than the typical case, which is what users actually complain about.

RPO is recovery point objective — how much recently accepted work you are willing to lose when a machine dies. RPO 0 means none, and that single choice forces a second copy of every write before it is acknowledged. Watch what it costs in What one row can actually do; it turns out to set the hardest limit in the chapter.

The third column is the important one: no target here is picked for being round.

Back-of-envelope

Four numbers carry the architecture: transfers per second, entries per second, petabytes of storage, and — the one that decides everything in Deep dive 3 transfers across shards — the fraction of transfers that touch two machines. Each falls out of the business assumptions with a line or two of arithmetic.

Traffic

Assume 1 B transfers/day, $5.00 average — a consumer wallet, so many small payments rather than few large ones. Money is in minor units, so $5.00 is 500.

The 100,000 below is the customary round stand-in for the 86,400 seconds in a day. Rounding up makes the resulting rate slightly conservative and the division doable in your head.

transfers/s, average:     1,000,000,000 / 100,000  =  10,000
transfers/s, peak:        10,000 x 3               =  30,000
value/day, minor units:   1,000,000,000 x 500      =  500,000,000,000

500,000,000,000 minor units is 500 B pennies, which is $5 B/day moving through the system.

Why every transfer is sized at four entries, not two

Two terms first. Each split of the data across machines is a shard, and a transfer whose two accounts live on different shards is cross-shard.

A same-shard transfer writes two entries: debit the sender, credit the receiver. A cross-shard transfer writes four, because the money makes a stop in a holding account on the way:

1. debit the sender (sender’s shard);
2. credit an in-transit account (sender’s shard);
3. debit the in-transit account (receiver’s shard);
4. credit the receiver (receiver’s shard).

Saga and why compensate is not rollback explains why the stop exists. The choice shows almost every transfer is cross-shard, so size on four:

entries/day:              1,000,000,000 x 4        =  4,000,000,000
entries/s at peak:        30,000 x 4               =  120,000

Storage

The entry row is 240 B on disk, derived field by field in ch 27. Same row, a hundred times as many of them:

bytes/day:                4,000,000,000 x 240      =  960,000,000,000
GB over 7 years:          960 x 365 x 7            =  2,452,800
GB with 3 replicas:       2,452,800 x 3            =  7,358,400

Read the middle line carefully: 960,000,000,000 B/day is 960 GB/day, and that GB figure is what gets multiplied by 365 days and 7 years of retention. The third line is the same data held on three machines instead of one.

2.45 PB of ledger, 7.4 PB replicated. Unlike ch 27, this is a storage problem.

The tier split, and the shard count that falls out of it

That much data forces a tier split — keeping recent data on fast, expensive storage and older data on slow, cheap storage.

Statements older than 90 days are something a user deliberately goes and asks for, not something a page load needs. So they can live in columnar object storage: bulk cloud storage holding files laid out column by column rather than row by row, which compresses far better and costs much less per byte.

GB hot, 90 days:          960 x 90                 =  86,400
GB cold:                  2,452,800 - 86,400       =  2,366,400

86 TB hot, 2.37 PB cold. The shard count follows from the hot number alone, because the cold tier is not on these machines at all. Take 4 TB of usable NVMe per node — NVMe being the fast solid-state disk a database primary sits on, and a node being one such machine:

shards for storage:       86,400 / 4,000           =  21.6

So 22 shards would hold the data. Round up to a power of two — 32 shards — because when you eventually need more capacity, doubling the count is the only resharding step (redistributing data across a new number of shards) that moves half the keys instead of nearly all of them (ch 05, Scaling partitioning sharding pooling caching).

Checking the other constraint: is it throughput?

Storage said 22. Now check whether write throughput needs more, because the binding constraint — the resource that runs out first and therefore sets the size — is the one you have to name out loud (ch 02).

A cross-shard transfer is two local write transactions, one per side, so peak transfers double into peak shard transactions:

shard txns/s at peak:     30,000 x 2               =  60,000
per shard:                60,000 / 32              =  1,875

A well-tuned relational primary — the single machine of a shard that accepts writes — running on 32 cores sustains roughly 10,000 small write transactions/s. Divide the cores by the rate and each transaction is getting 3.2 ms of CPU time across those cores, which is a sane budget for a small write.

Utilization below means the fraction of capacity in use, so 0.1875 is 18.75% busy:

CPU-seconds per txn:      32 / 10,000              =  0.0032
utilization per shard:    1,875 / 10,000           =  0.1875
shards for throughput:    60,000 / 10,000          =  6

Storage binds at 22 shards, throughput binds at 6, so storage wins and 32 shards leaves the write path 81% idle (100% − 18.75%) — which is exactly the headroom the hot-account problem is going to consume.

The number that decides section 4

With 32 shards and account pairs chosen roughly at random, put the sender anywhere. The transfer stays on one shard only if the receiver happens to land on that same shard, which is 1 chance in 32. Everything else is cross-shard:

cross-shard fraction:     1 - 1 / 32               =  0.96875

96.9% of transfers touch two shards. That single number decides Deep dive 3 transfers across shards before §4 starts: whatever cross-shard coordination costs, you pay it on the common case, not on an edge case.

API sketch

The interface makes three commitments visible: money is an integer count of pennies, held money is a separate number from available money, and every call that changes something takes an idempotency key.

POST /v1/transfers
Idempotency-Key: 3ab1...             <- canonical hash of the body, ch 23 R1
{ "from": "acc_1", "to": "acc_2", "amount_minor": 500, "currency": "USD" }
201 { "transfer_id": "tr_9", "state": "SENDER_DEBITED" }
409 { "error": "insufficient_funds", "available_minor": 320 }

GET  /v1/accounts/{id}/balance
200 { "available_minor": 12500, "held_minor": 500, "as_of_seq": 88213 }

GET  /v1/accounts/{id}/entries?from=2026-07-01&to=2026-07-31&cursor=...
POST /v1/holds        Idempotency-Key: ...   { "account": "acc_1",
                                               "amount_minor": 2000, "ttl_s": 900 }
DELETE /v1/holds/{id} Idempotency-Key: ...

Three details in that block are doing real work.

The idempotency key is on the hold endpoints too, not only on /transfers. That is rule R4 of the four, “put the key on every call that changes something” (9a the idempotency rules in one place). A retried POST /v1/holds that places the hold twice takes twice the money out of available, and a retried DELETE gives it back twice.

available_minor and held_minor are separate fields because they are separate accounts. A hold is a zero-sum transfer between a user’s available and held sub-accounts — money moved from one pocket to another, the two halves summing to zero — not a boolean flag on a row. That keeps the zero-sum invariant intact (The invariant), and it makes “why is my money gone” answerable from the statement, because the hold is a visible line on it.

as_of_seq is the sequence number the balance was computed at. Each account’s entries are numbered 1, 2, 3, … in commit order, so the sequence number says how far down the log the fold got.

That number is there to make one specific bug visible. A client that reads a balance, then reads it again and sees a lower as_of_seq, has been served by a replica — a copy of the database kept for reads — that is behind the primary. Returning the fold position costs nearly nothing and turns an invisible anomaly into a detectable one.

Data model

Four tables: ledger_entries is the log that is the truth, account_balances is the memoized fold of that log, balance_snapshots holds periodic running totals used only for rebuilds, and transfer_outbox is what makes cross-shard delivery reliable. The two primary keys are the design, not boilerplate.

CREATE TABLE ledger_entries (        -- append only, sharded by account_id
  account_id    BIGINT NOT NULL,
  seq           BIGINT NOT NULL,     -- per-account, gapless, assigned on commit
  transfer_id   UUID   NOT NULL,
  amount_minor  BIGINT NOT NULL CHECK (amount_minor <> 0),
  currency      CHAR(3) NOT NULL,
  created_at    TIMESTAMPTZ NOT NULL,
  prev_hash     BYTEA NOT NULL,      -- see section 5
  PRIMARY KEY (account_id, seq)
);

CREATE TABLE account_balances (      -- the memoized fold, one row PER BUCKET
  account_id    BIGINT NOT NULL,
  bucket        SMALLINT NOT NULL,   -- 0 for cold accounts, 0..15 when hot
  amount_minor  BIGINT NOT NULL,
  last_seq      BIGINT NOT NULL,
  PRIMARY KEY (account_id, bucket)
);

CREATE TABLE balance_snapshots (     -- rebuild and audit only, not the read path
  account_id    BIGINT NOT NULL,
  seq           BIGINT NOT NULL,
  amount_minor  BIGINT NOT NULL,
  PRIMARY KEY (account_id, seq)
);

CREATE TABLE transfer_outbox (       -- written in the SAME txn as step 1
  transfer_id   UUID PRIMARY KEY,
  to_shard      SMALLINT NOT NULL,
  payload       JSONB NOT NULL,
  published_at  TIMESTAMPTZ
);

One design choice in that schema does most of the work: putting account_id first in both primary keys.

PRIMARY KEY (account_id, seq) clusters an account’s entire history contiguously. Clustering means the rows are physically stored in primary-key order, so all of one account’s entries sit next to each other on disk instead of scattered wherever they happened to be written. That is what makes both the statement scan and the fold sequential rather than random, and sequential reads are roughly two orders of magnitude cheaper.

PRIMARY KEY (account_id, bucket) does the same for the buckets of Deep dive 2 the hot account — the several rows a hot account’s balance gets split across. That clustering is what keeps reading a split balance exactly as cheap as reading a single one, and What sharding costs the read path prices it.

One more term from that schema, because it recurs for the rest of the chapter. An outbox is a table you write a to-be-sent message into in the same transaction as the data change that prompted it. Because the message row and the debit commit together, a crash can never leave the debit committed and the message lost. A separate relay process reads the table and publishes what it finds.

High-level architecture

The whole system fits on one page: one write path fanning into 32 shards, plus the background jobs hanging off each shard.

flowchart TD
    C["Wallet client"] --> API["Transfer API<br/>Idempotency-Key required"]
    API --> RT["Router<br/>shard = hash of account_id<br/>32 shards"]
    RT --> S1[("Shard 1<br/>ledger_entries append-only<br/>account_balances by bucket")]
    RT --> SN[("Shard 32")]
    S1 --> OB["Outbox relay<br/>same txn as the debit"]
    OB --> Q["Queue, ch 20<br/>at least once"]
    Q --> W["Saga step 2 worker<br/>idempotent on transfer_id"]
    W --> SN
    W --> DLQ["Dead letter to the human queue of ch 27"]
    S1 --> SNAP["Snapshotter<br/>every 20 M entries"]
    S1 --> ARCH["Archiver<br/>older than 90 days to Parquet"]
    ARCH --> OBJ[("Object storage<br/>2.37 PB cold")]
    S1 --> AUD["Invariant checker<br/>per-shard sum is zero<br/>in-transit residue equals money in flight"]

    style S1 fill:#2d6a4f,color:#fff
    style W fill:#1d3557,color:#fff
    style AUD fill:#bc6c25,color:#fff

The write path, top to bottom

The wallet client is the phone app. It calls the Transfer API, which rejects any mutating request that arrives without an idempotency key.

The router picks a shard by hashing account_id, which spreads accounts evenly over the 32 shards.

Each shard stores two things: ledger_entries append-only, and account_balances by bucket. The log and its memoized fold live in one database on purpose — that is the only way they can be written in a single transaction (The materialized balance is a cache of a fold).

The background jobs

Four jobs hang off every shard, and each one corresponds to a section below.

• Outbox relay — publishes the step-2 messages that were written in the same transaction as the debit, onto a queue that promises at-least-once delivery (ch 20).
• Snapshotter — every 20 M entries, writes down a running total so a rebuild never has to start from the beginning of time (Snapshots derived from a recovery target).
• Archiver — moves entries older than 90 days out to Parquet files in object storage. Parquet is a columnar file format: values are stored grouped by column rather than by row, which compresses far better.
• Invariant checker — verifies two things per shard: that the shard’s entries sum to zero, and that the in-transit residue equals the money genuinely in flight (Saga and why compensate is not rollback).

Downstream of the queue sits the fifth box, the saga step 2 worker. It consumes the relayed messages and is idempotent on transfer_id, so a repeat delivery changes nothing. A saga is a chain of small local transactions standing in for one big distributed one; Saga and why compensate is not rollback builds it. Anything permanently unprocessable goes to a dead-letter store and on to the human queue of Failure modes.

2. Deep dive 1 — balance as a fold

Framing what decision and what breaks committed to option 3 — the log as truth, with a memoized fold beside it — largely on faith. Now earn it: why the log alone is too slow to read, how often to write down a running total, and how you find out when the saved number has quietly gone wrong.

2.1 The fold, and why you cannot do it on read

A balance is not a stored number. It is fold(+, 0, entries) — start from 0 and add every signed entry for that account, in order. That is all “fold” names: an operator (+), a starting value (0), and a list to walk.

That definition is what makes the ledger reproducible. balance(a, T) is the same fold restricted to entries numbered seq <= T, so any past balance is recoverable exactly, and an auditor’s question about last March is a query rather than an archaeology project.

The block below is the definition in ten lines. The part to look at is the snapshot argument: passing (2, 300) means “after entry 2 the balance was 300”, so the fold skips everything up to entry 2 and replays only the tail. Both asserts return the same answer, which is the point — a snapshot changes the work, never the result.

SNAPSHOT_EVERY = 20_000_000        # entries; derived in 2.2 from a 10 s target

def fold(entries, snapshot=None):
    """Balance is a fold over events. A snapshot is (seq, amount) and lets the
    fold start partway through instead of at the beginning of time."""
    start_seq, running = (0, 0) if snapshot is None else snapshot
    for seq, amount in entries:
        if seq > start_seq:
            running += amount
    return running

log = [(1, 500), (2, -200), (3, 750)]
assert fold(log) == 1050

snap = (2, 300)                    # after seq 2 the balance was 300
assert fold(log, snap) == 1050     # 300 + 750: only the tail is replayed

Pricing the fold

Two costs per entry. First, one reference to main memory — one trip out to RAM for a value not already in the processor’s cache, which the standing latency table puts at 100 ns (ch 02). Second, roughly 400 ns to decode the row and add it. The 1,000,000,000 in the second line is nanoseconds in one second:

fold cost per entry, ns:  100 + 400                =  500
fold rate, entries/s:     1,000,000,000 / 500      =  2,000,000

Disk is not the limit. PRIMARY KEY (account_id, seq) makes the read sequential, and a sequential read at 1 GB/s over 240 B rows delivers rows faster than the CPU can consume them:

disk-bound rate, /s:      1,000,000,000 / 240      =  4,166,667

4.2 M/s available from disk against 2 M/s of CPU, so CPU binds and 2 M entries/s is the number to carry for the rest of the chapter.

Applying it to the two extreme accounts

A cold user at 10 entries a day, over the full 7-year retention window:

cold account, entries:    10 x 365 x 7             =  25,550
cold fold, seconds:       25,550 / 2,000,000       =  0.0128

12.8 ms. A cold user’s entire seven-year history folds inside the 10 ms p99 read budget — near enough that for most accounts you would not need a stored balance at all.

Now a large merchant at 100 M entries/year, again over 7 years, which is 700 M entries:

merchant fold, seconds:   700,000,000 / 2,000,000  =  350

350 seconds to answer “what is my balance”. Nearly six minutes.

That is the derivation of why account_balances exists. Not because folding is wrong — it is the correct definition — but because the fold’s cost is proportional to an account’s lifetime activity, and lifetime activity is unbounded.

2.2 Snapshots, derived from a recovery target

How often should you write down a running total? The obvious answer — “every night” — turns out to be wrong at both ends of the account-size range. A snapshot here is one saved pair of (sequence number, balance at that point), which lets a rebuild start partway down the log instead of at the beginning.

If account_balances is lost or found to be wrong, you rebuild it from the log. Rebuild time is what the snapshot interval has to control.

State the target — a balance must be recoverable in 10 s — and multiply by the fold rate from The fold and why you cannot do it on read to get how many entries fit in that budget:

snapshot interval, N:     10 s x 2,000,000 /s      =  20,000,000

So: snapshot every 20 M entries, per account. Note that this is a count of entries, not a clock interval. Convert it to wall clock for the two extreme accounts and you can see why that matters — the merchant takes 10,000 entries/s, the cold user 10 entries/day:

hot merchant, seconds:    20,000,000 / 10,000      =  2,000
hot merchant, minutes:    2,000 / 60               =  33.3
cold user, years:         20,000,000 / 10 / 365    =  5,479

The hot merchant is snapshotted every 33 minutes. The cold user is never snapshotted, and does not need to be — The fold and why you cannot do it on read showed their whole history folds in 12.8 ms.

That five-order-of-magnitude gap is the reason the rule is a count, not a schedule. A nightly scheduled job gets both ends wrong at once: it snapshots 500 M accounts that will never be read, and it still leaves the merchant 8 hours of unsnapshotted log to replay.

What the snapshot table costs

Divide the system’s daily entries by the interval to get snapshots written per day, then multiply by 64 B per snapshot row:

snapshots/day:            4,000,000,000 / 20,000,000  =  200
snapshot bytes/day:       200 x 64                 =  12,800

200 rows and 13 KB a day, system-wide. Say that number out loud in an interview; it pre-empts the “isn’t that a lot of snapshots” question entirely.

2.3 The materialized balance is a cache of a fold

One distinction carries the rest of the design: a saved balance cannot be stale, but it can be wrong, and those need different answers. Materialized means precomputed and stored rather than derived on demand.

account_balances is updated in the same transaction as the entries that change it.

That is the whole cache-invalidation story, and it is why this cache needs no invalidation logic at all. The balance can never be stale, because there is no window of time in which the entries exist and the balance does not — the two either commit together or neither does.

It can still be wrong: a bad migration, a bug in the update code, a corrupted page on disk. Wrong is a different failure from stale, and wrong is what the audit job catches.

What the audit costs

The audit re-folds the log from scratch and compares the result to the stored balance. Price it system-wide in core-seconds — one core-second being one processor core busy for one second. Divide the day’s entries by the fold rate, then spread the work over the shards:

core-seconds/day:         4,000,000,000 / 2,000,000   =  2,000
per shard, seconds:       2,000 / 32               =  62.5

62.5 core-seconds per shard per day. Run it nightly on a replica and it costs nothing anyone will notice.

Pairing it with the zero-sum check

The fold audit catches a balance that disagrees with its log. The zero-sum check catches a movement recorded on one side only. Run both. The technique and the checkpointing argument come from What checking the invariant costs; here it is against this chapter’s volumes, which are a hundred times larger:

entries/day/shard:        4,000,000,000 / 32       =  125,000,000
bytes/day/shard:          125,000,000 x 240        =  30,000,000,000
scan seconds at 1 GB/s:   30 / 1                   =  30

30,000,000,000 B is 30 GB, and 30 GB at 1 GB/s is 30 s per shard. All 32 shards scan in parallel, so the open-partition invariant check is a 30-second job no matter how many shards you add — double the shards and each one has half the data.

Sharding made the correctness check cheaper, not harder. It is the one place in this design where distribution helps instead of hurting.

3. Deep dive 2 — the hot account

A single database row imposes a hard write ceiling, and the flash-sale merchant sails straight through it. The ceiling can be derived from first principles rather than quoted; splitting a balance across several rows gets past it; and the split introduces two concurrency bugs, both invisible unless you test with threads.

3.1 What one row can actually do

The 1,333 writes/s figure the rest of this section attacks is not a hardware fact — it is set by a durability promise, and deriving it shows exactly where the time goes.

A transfer that credits a merchant takes a row lock on that merchant’s balance row and holds it until the transaction commits.

The key idea: the hold time is not the query time. It is everything between acquiring the lock and releasing it at commit. Four things happen in that window.

• An index descent — walking the index from its root down to the row’s location. On a hot row the index pages are already in memory, so this costs 10 us rather than a disk read.
• The row update plus its write-ahead log (WAL) record. The WAL is a sequential log that the database appends every change to before touching the data pages, so a crash can be replayed forward from it. 40 us.
• A group commit fsync. fsync is the system call that forces the operating system to push buffered writes onto the physical disk for real. Group commit means several concurrent transactions share one such call, which is why 200 us is an amortized figure and not the cost of a full disk flush.
• The synchronous replica acknowledgement — one round-trip time (RTT) to a second machine and back, 500 us. This is the RPO 0 promise from the requirements table being paid for.

Add the four:

index descent, cached:      10   us
row update plus WAL:        40   us
group commit fsync:        200   us
sync replica ack, 1 RTT:   500   us
lock hold, us:            10 + 40 + 200 + 500      =  750

Look at where the time goes. The replica acknowledgement is one datacenter round trip and two thirds of the 750 us total. That is not an implementation detail you can tune away — it is the price of RPO 0, and it sits inside the lock because the lock cannot be released before commit.

From lock hold to writes per second

Locked updates to one row are strictly serial: one transaction at a time, each holding the row for 750 us. So one second of wall clock divides into 750 us slots. The 1,000,000 is microseconds in a second:

serial ceiling, /s:       1,000,000 / 750          =  1,333
shortfall factor:         10,000 / 1,333           =  7.5

One row does 1,333 writes/s. The flash-sale merchant needs 10,000. The naive design is 7.5x short — and it does not fail gracefully.

Why “7.5x short” understates it

Lock waiting is a queue. Once demand approaches capacity, waiting time stops growing in proportion to load and starts growing without bound. The ten-thousandth transfer of that second is not 7.5x slower than the first; it is queued behind roughly 7,500 others and its latency has no ceiling at all.

The observable symptom is worse than slow transfers on that account. Every other transfer on that shard slows down too, because each waiter holds a database connection while it waits. Connections come from a fixed-size pool, and once the waiters have taken every connection, work that has nothing to do with the hot account cannot get one either (Scaling partitioning sharding pooling caching).

3.2 Sharded sub-balances

Split the hot account’s balance into K rows, called buckets, whose sum is the true balance. A merchant with 10,000 in the bank might hold 700 in bucket 0, 500 in bucket 1, and so on — no single row is the balance, the sum is.

Credits pick a bucket by hashing the transfer id. So K different rows absorb the writes, and each bucket’s lock is independent of the others.

Choosing K

Divide the demand by what one row sustains:

minimum K:                10,000 / 1,333           =  7.5

K must be at least 8. Take K = 16 for headroom, because you never want a lock queue anywhere near saturation:

per-bucket rate, /s:      10,000 / 16              =  625
utilization:              625 / 1,333              =  0.47

47% utilization per bucket. That is the number that matters more than the raw rate: below roughly half capacity, waiting time grows in proportion to load rather than running away.

K is a power of two for two reasons. The bucket is then hash(transfer_id) & 15, a single bitwise operation. And K can be doubled later while every existing entry keeps a valid bucket assignment.

The two things the code must get right

Two properties have to hold in the block below, and neither is optional.

1. The check and the write happen under one lock set — a lock set being all the locks a single operation holds at once. Otherwise total() returns a number that was true when it was read and is no longer true when the subtraction lands, and the account goes negative.

2. The locks are taken in ascending bucket id. Otherwise two debits that started from different buckets acquire them in opposite orders and deadlock: thread one holds bucket 0 and waits for bucket 15 while thread two holds bucket 15 and waits for bucket 0. Neither can proceed, and because neither can proceed, neither will ever release.

The cure is lock ordering — pick one global order for all locks in advance and require every code path to take them in that order. A deadlock needs a cycle of waiters, and a cycle requires at least one participant to have gone backwards through the order, which the rule forbids.

Reading the block

Read debit() first; it is where everything happens. It takes every bucket lock in ascending order, checks the total rather than one bucket, then pulls money from the other buckets into the chosen one (need = amount - self.buckets[i] is the shortfall to cover) before subtracting. That inner loop is the rebalance, and it is itself zero-sum — every unit it removes from bucket j it adds to bucket i.

Then read the three test sections at the bottom. The first is a plain credit-and-debit sanity check. The second launches two threads whose buckets sit at opposite ends of the range, which is the deadlock case. The third launches 32 threads against a balance that covers only 16 of them, which is the overdraw case. Both threaded cases need real threads to fail — single-threaded, the buggy version passes.

import threading, time

BUCKETS = 16
IO = 0.0002                    # one statement's round trip inside the lock hold

def bucket_for(transfer_id):
    return hash(transfer_id) % BUCKETS

class ShardedBalance:
    """Credits fan out across buckets and never fail. Debits must be checked
    against the TRUE total, which is the sum of every bucket -- and the check
    and the write have to happen under one lock set, or the check is a guess."""

    def __init__(self, n=BUCKETS):
        self.buckets = [0] * n
        self.locks = [threading.Lock() for _ in range(n)]

    def total(self):
        return sum(self.buckets)

    def _acquire(self, order, timeout=1.0):
        """`SELECT ... FOR UPDATE ... ORDER BY bucket`. The order is the whole
        point: a timeout here is a cycle, not congestion."""
        held = []
        for i in order:
            if not self.locks[i].acquire(timeout=timeout):
                for j in reversed(held):
                    self.locks[j].release()
                raise TimeoutError(f"lock cycle waiting for bucket {i}")
            held.append(i)
            time.sleep(IO)
        return held

    def credit(self, transfer_id, amount):
        i = bucket_for(transfer_id)
        with self.locks[i]:                  # one row, so there is no order to get wrong
            time.sleep(IO)
            self.buckets[i] += amount

    def debit(self, transfer_id, amount):
        i = bucket_for(transfer_id)
        held = self._acquire(sorted(range(len(self.buckets))))   # ASCENDING, always
        try:
            if self.total() < amount:        # true under the locks, so still true at write
                raise ValueError("insufficient funds")
            need = amount - self.buckets[i]
            for j, v in enumerate(self.buckets):     # rebalance, itself zero-sum
                if j == i or need <= 0:
                    continue
                move = min(v, need)
                self.buckets[j] -= move
                self.buckets[i] += move
                need -= move
            self.buckets[i] -= amount
        finally:
            for j in reversed(held):
                self.locks[j].release()

acct = ShardedBalance()
for k in range(160):
    acct.credit(f"t{k}", 100)
assert acct.total() == 16000
acct.debit("t0", 15000)
assert acct.total() == 1000

# --- two debits whose chosen buckets are at opposite ends of the range -------
dl = ShardedBalance()
for k in range(64):
    dl.credit(f"c{k}", 100)
low = next(t for t in (f"x{n}" for n in range(10_000)) if bucket_for(t) == 0)
high = next(t for t in (f"x{n}" for n in range(10_000)) if bucket_for(t) == 15)

cycles, guard, gate2 = [], threading.Lock(), threading.Barrier(2)

def rebalancing_debit(tid):
    gate2.wait()
    try:
        dl.debit(tid, 100)
    except TimeoutError as e:
        with guard:
            cycles.append(str(e))

ts = [threading.Thread(target=rebalancing_debit, args=(t,)) for t in (low, high)]
for t in ts:
    t.start()
for t in ts:
    t.join()
assert cycles == [], f"deadlock: {cycles}"

# --- 32 concurrent debits against a balance that covers 16 of them ----------
hot = ShardedBalance()
for k in range(16):
    hot.credit(f"c{k}", 100)
assert hot.total() == 1600

declined, gate = [], threading.Barrier(32)

def spend(n):
    gate.wait()
    try:
        hot.debit(f"d{n}", 100)
    except ValueError:
        with guard:
            declined.append(n)

ts = [threading.Thread(target=spend, args=(n,)) for n in range(32)]
for t in ts:
    t.start()
for t in ts:
    t.join()

assert hot.total() == 0, f"balance ended at {hot.total()}"   # never below zero
assert min(hot.buckets) >= 0
assert len(declined) == 16, f"{32 - len(declined)} debits took 1,600 of funds"

Both threaded assertions fail on the obvious implementation, and they fail differently.

Drop the locks and keep if self.total() < amount as a bare precondition, and the 32-thread run ends at −1,600 on a balance of 1,600. Every thread read a total that covered its 100, and every thread was correct at the moment it read. All 32 then subtracted.

Keep the locks but acquire the chosen bucket first and scan the others afterwards — which is the shape the rebalance loop naturally suggests, since you start from “my” bucket — and the two-thread run deadlocks immediately: one thread holds bucket 15 and waits on 0 while the other holds 0 and waits on 15.

Two objections to answer before moving on.

Locking the whole bucket range on a debit sounds expensive. It is not, for the reason Debits are the hard direction gives: on the account this design exists for, credits are the hot direction and debits are a nightly batch.

The rebalance loop looks like decoration. It is not — it is the only reason a debit against a bucketed account behaves like a debit against a single balance, instead of failing whenever the money happens to sit in a bucket other than the chosen one.

3.3 What sharding costs the read path

Everyone raises the same objection against bucketing: a balance read now touches 16 rows instead of one. The answer turns out to be “almost nothing, because of one line in the schema” — and then there is a cost that is real and cannot be paid with hardware.

Price it. Databases read from disk in fixed-size pages, typically 8 KB, and the page is the unit of I/O — reading one byte of a page costs the same as reading all 8,192. So the real question is not how many rows, it is how many pages those 16 rows span.

A bucket row is small. The addends below are the account_balances columns in schema order — account_id at 8 B, bucket padded to 4 B, amount_minor at 8 B, last_seq at 8 B — plus 36 B of per-row database overhead (the row header the storage engine keeps for visibility and versioning):

bucket row, bytes:        8 + 4 + 8 + 8 + 36       =  64
16 buckets, bytes:        16 x 64                  =  1,024
fraction of an 8 KB page: 1,024 / 8,192            =  0.125

All 16 buckets together are 1 KB — an eighth of one page. Because they are clustered under PRIMARY KEY (account_id, bucket), they sit next to each other, so that eighth of a page is one page and not sixteen.

Now count the reads. A B-tree is the sorted, tree-shaped index a relational database uses to find rows: you walk from the root down to a leaf, the bottom-level page holding the actual data. At realistic table sizes that walk is four page reads (B trees why a lookup is four page reads). One descent lands on the leaf holding all 16 buckets.

The bucketed read therefore costs the same four page reads as the single-row read. That is the answer to the objection, and it holds only because of the clustering choice. A separate balance_buckets table keyed (bucket, account_id) would scatter one account’s buckets across 16 different places in the index, cost 16 descents, and be 16x worse — the objection would be correct.

The cost that is real but small: rows examined

Page reads did not change. Rows the CPU has to look at did. At peak, every transfer’s balance read now examines 16 rows at roughly 200 ns each:

rows read/s at peak:      30,000 x 16              =  480,000
CPU ns/s at 200 ns/row:   480,000 x 200            =  96,000,000
core-fraction:            96,000,000 / 1,000,000,000  =  0.096

96,000,000 ns of CPU work per second of wall clock, against 1,000,000,000 ns that one core provides per second — under 10% of one core across the whole fleet. Negligible, and worth stating so the interviewer knows you checked rather than assumed.

The cost that is real and cannot be paid with hardware: consistency

The 16 rows must all be read as of one instant, or their sum is a number that never existed.

An isolation level is the database setting that decides which concurrency surprises a transaction may observe. The weakest one in common use is READ COMMITTED: you never see uncommitted data, but two reads inside the same transaction may return different answers.

A single SELECT SUM(amount_minor) ... WHERE account_id = ? is one statement, and one statement sees one consistent view of the database. So the plain balance read is safe even at READ COMMITTED.

A read-modify-write across buckets is not safe there. Between your two statements a rebalance can move money out of a bucket you already read and into one you have not read yet, so you count it twice — or move it the other way, and you count it never. Either way you observe a total that never actually existed.

Two ways out: REPEATABLE READ, which promises that re-reading inside a transaction gives the same answer, or an explicit SELECT ... FOR UPDATE that locks the whole bucket range while you work. The full table of which isolation level permits which anomaly is in Transactions acid precisely.

3.4 Debits are the hard direction

Money in and money out are not symmetric problems, and the asymmetry produces its own family of failure modes — among them the deadlock everyone misses, the one on account rows rather than buckets.

Credits split across buckets trivially and debits do not. This asymmetry is the thing to say out loud in an interview.

A credit can go into any bucket. Addition commutes, so the choice does not affect the total, and a credit never fails — there is no precondition to check.

A debit has to answer “are there sufficient funds”, and the funds are spread across 16 rows. Five problems follow, and the table gives each one its fix. Rows 1 to 3 and row 5 are about bucket locks; row 4 is the same idea one level up, about account locks.

The deadlock one level up

The fourth row is the one the ordering rule usually misses, because “ascending bucket id” gets stated about buckets and then quietly assumed to cover everything. It does not.

A same-shard transfer is a single local transaction touching two account rows. The natural way to write it — debit the sender, then credit the receiver — orders the locks by the direction of the transfer. That is the one order guaranteed to collide with a transfer going the other way: A -> B takes A then B, B -> A takes B then A, and both stop forever.

The block below makes it concrete. Two threads hammer acc_1 -> acc_2 and acc_2 -> acc_1 at each other, 20 rounds each. The line to watch is first, second = sorted((src, dst)) — that single sort is all that stands between this design and a permanent stall. The final assertions check both that no thread timed out and that no money was created or destroyed.

import threading, time

BALANCES = {"acc_1": 10_000, "acc_2": 10_000}
ROW_LOCKS = {a: threading.Lock() for a in BALANCES}

def transfer_same_shard(src, dst, amount, timeout=1.0):
    """One shard, so this is a single local transaction -- and a single local
    transaction still deadlocks when two of them lock the same two rows in
    opposite orders. Lock by ascending account_id, never in transfer order."""
    first, second = sorted((src, dst))                 # the guard
    held = []
    try:
        for a in (first, second):
            if not ROW_LOCKS[a].acquire(timeout=timeout):
                raise TimeoutError(f"lock cycle waiting for {a}")
            held.append(a)
            time.sleep(0.0002)
        BALANCES[src] -= amount
        BALANCES[dst] += amount
    finally:
        for a in reversed(held):
            ROW_LOCKS[a].release()

cycles, guard, gate = [], threading.Lock(), threading.Barrier(2)

def hammer(src, dst):
    gate.wait()
    for _ in range(20):
        try:
            transfer_same_shard(src, dst, 100)
        except TimeoutError as e:
            with guard:
                cycles.append(str(e))
            return

ts = [threading.Thread(target=hammer, args=p)
      for p in (("acc_1", "acc_2"), ("acc_2", "acc_1"))]
for t in ts:
    t.start()
for t in ts:
    t.join()

assert cycles == [], f"deadlock: {cycles}"
assert sum(BALANCES.values()) == 20_000

Replace sorted((src, dst)) with src, dst and the two threads deadlock on the first iteration.

The rule is not “order your buckets”. It is “there is exactly one global order in which locks may be taken, and every path takes it” — buckets by id, account rows by account_id, and a shard’s rows before another shard’s if any path ever touches both.

Why the fix works at all: the workload is one-directional

The last table row is the practical answer for the case that motivated this whole section.

A hot merchant is hot in one direction only. It receives 10,000 payments/s and pays out in nightly batches. So credits fan out across 16 buckets, and debits all take bucket 0 — which sees a handful of writes a day, so locking the full range on a debit costs nothing.

Be honest about what that means: the design works because the workload is asymmetric. A design that pretended both directions were hot would need distributed reservations and would be considerably worse.

For an account that genuinely is hot in both directions — an exchange’s settlement account, say — the answer is to stop pretending it is one account. Give it an explicit per-region or per-desk account and reconcile between them with real ledger transfers. The concurrency then shows up in the books, where you can query it, instead of hidden inside a lock.

3.5 Promotion and demotion

Which accounts get buckets, and when? Both thresholds can be derived rather than picked.

Bucketing every account would be a mistake. It multiplies the row count by 16 for the 99.99% of accounts that see fewer than one write per day, and buys them nothing.

So split adaptively, at a threshold derived from the ceiling in What one row can actually do rather than picked by taste:

promote above, writes/s:  1,333 x 0.1              =  133

Promote an account to K = 16 when its one-minute write rate exceeds 133/s. That is 10% of the serial ceiling — early enough that the queue is still well-behaved when the promotion happens, rather than after latency has already run away.

Demote after an hour below 13/s. The gap between promote (133/s) and demote (13/s) is deliberate and has a name: hysteresis. Making the way out different from the way in stops an account whose rate hovers near a single threshold from flapping between the two shapes every minute.

Both transitions are ordinary zero-sum ledger transactions. A split moves the balance out of bucket 0 and into 16 buckets; a merge moves it back. Because they are ordinary transactions, they are subject to the same invariant as everything else — so a bug in the splitter shows up in the The materialized balance is a cache of a fold audit rather than in a customer complaint.

The memory this costs, assuming a generous 1,000 hot accounts each holding 16 rows of 64 B:

hot accounts, bytes:      1,000 x 16 x 64          =  1,024,000

1 MB. The adaptive path is free. The universal path would not have been.

4. Deep dive 3 — transfers across shards

Distributed money movement offers one central trade: one atomic transaction spanning two machines, or availability — and here you cannot have both. The atomic option has a price and a disqualifying failure; the alternative is a chain of local transactions with a holding account in the middle, and it is safe only with three guards.

96.9% of transfers touch two shards, so whatever this costs, it is the common case and not an edge case.

4.1 2PC, and the failure that matters

Two-phase commit has a throughput cost worth pricing precisely — and the cost, bad as it is, turns out not to be the reason to reject it.

Two-phase commit (2PC) is the classic protocol for making two databases commit or abort together.

A coordinator — one process that runs the protocol — asks both shards to PREPARE, which means “get everything ready and promise me you can commit”. If both vote yes, the coordinator records the decision durably and then tells them both to commit.

It gives you real atomicity: the transfer either happens on both shards or on neither, with no observable in-between. The correctness is genuine, and this is not a straw man.

What 2PC costs in throughput

The cost is that the row lock is now held across two extra network phases. Start from the 750 us lock hold derived in What one row can actually do — that is unchanged, it is the local work — and add the coordinator’s own durable log write and the round trip that delivers the commit decision:

local prepare work, us:                              750
coordinator log fsync, us:                           200
commit round trip, us:                               500
lock hold under 2PC, us: 750 + 200 + 500          =  1,450

Feed the longer hold time back through the same division as before, one second of microseconds per 1,450 us slot:

2PC row ceiling, /s:      1,000,000 / 1,450        =  690
throughput lost:          1 - 690 / 1,333          =  0.48

2PC costs 48% of what a single row could do — and it costs it on the exact row this chapter exists to protect. Combine it with the 16 buckets of Sharded sub balances and see whether bucketing rescues it:

2PC with 16 buckets, /s:  16 x 690                 =  11,040
2PC headroom:             11,040 / 10,000          =  1.1

11,040/s against a 10,000/s peak is 10% of headroom, against a target that already assumed a 3x peak multiplier. That is not a margin. It is a coincidence.

The failure mode, which is worse than the throughput

A shard that has voted yes is in the PREPARED state. It has promised it can commit, so it is no longer allowed to abort on its own initiative, and it must keep its locks until the coordinator tells it the outcome.

That is what people mean when they call 2PC a blocking protocol: a participant can be left with no legal move. It cannot commit (it has not been told to), it cannot abort (it promised not to), and it cannot release the locks (either outcome still needs them).

If the coordinator dies after collecting the votes and before the decision is durably recorded, those locks stay held for as long as recovery takes — and if the coordinator’s log is lost, indefinitely, pending a human.

Price a 30-second coordinator outage during the flash sale:

blocked transfers:        10,000 x 30              =  300,000

300,000 held locks on user balance rows. That is 300,000 people who cannot spend their own money, because of a machine they have never heard of.

That sentence is the argument. 2PC does not fail by being slow. It fails by converting one machine’s crash into a system-wide freeze on exactly the accounts that were most active.

4.2 Saga, and why compensate is not rollback

The alternative to 2PC is easy to state and hard to make safe: without three specific guards, it quietly creates or destroys money.

What a saga is

A saga is a sequence of local transactions, each of which commits on its own, with a stored record of intent linking them. Nothing spans two machines; nothing is held open waiting.

If a later step proves impossible, earlier steps are undone by running new transactions that reverse their effect, rather than by aborting anything. That undoing is called compensation, and the difference between compensation and rollback is the end of this subsection.

Concretely, a saga replaces one distributed transaction with two local ones and a durable intent between them:

1. Shard A: debit the sender, credit in_transit@A. Commit. Write the outbox row in the same transaction.
2. Shard B: debit in_transit@B, credit the receiver. Commit, keyed on (transfer_id, step) so a repeated delivery does nothing at all.

Keyed there means an actual uniqueness constraint — a database rule that rejects a second row with the same key — written in the same transaction as the entries (9a the idempotency rules in one place, rule R3). Not a sentence in a design document, and not an if statement in application code that races with itself.

The in-transit account

The in-transit account is what makes this respectable rather than a hack. It is an ordinary account that holds money while it is between owners, so a transfer stalled between its two steps has its money sitting somewhere with a name and a queryable balance.

Each step is independently zero-sum, so the invariant holds on every shard at every instant, including part-way through a saga (The invariant). The money is never nowhere.

The blind spot: zero-sum cannot see a duplicate

That same property is exactly why the invariant cannot be the thing that catches a duplicated step.

A posting is one balanced group of entries written together. A replayed step 2 pays Bob twice, and it does so with two perfectly balanced postings. total() is still 0. shard_total("B") is still 0. Every check this design has stated so far passes, while a stranger’s money is gone.

Double-entry catches asymmetry — a movement recorded on one side only. A duplicate is not asymmetric; it is symmetric, twice (What the invariant catches that a balance column does not).

The block below is the saga in runnable form, and its last five lines are that failure demonstrated rather than asserted.

Read post() first. It has exactly three guards, listed in its own docstring: the posting must be zero-sum, only one posting may exist per (transfer_id, step), and nothing may land on a transfer that has already reached a terminal state.

Then read the assertions below it, which walk four scenarios in order: one clean transfer including a deliberate redelivery, one transfer that stalls after step 1, one compensated transfer whose step 2 arrives late anyway, and finally a duplicate appended by hand — bypassing post() entirely — so you can watch every zero-sum check in this chapter pass while Bob holds 1,000 for a 500 transfer.

import itertools

LEDGER = []       # append-only: (shard, transfer_id, step, posting_id, account, amount)
POSTINGS = {}     # (transfer_id, step) -> posting_id     -- PK, written in the same txn
STATE = {}        # transfer_id -> saga state
TERMINAL = {"COMPLETED", "COMPENSATED"}
POSTING_SEQ = itertools.count(1)

class LateStep(Exception):
    """A step arriving after the saga reached a terminal state."""

def post(shard, transfer_id, step, entries):
    """Three guards, and only the first is the one everybody names.

    1. zero-sum, so a half-written movement has no representation;
    2. one posting per (transfer_id, step) -- delivery is at-least-once, and a
       replayed step pays the receiver twice while every zero-sum check still
       passes. `setdefault` is `INSERT ... ON CONFLICT DO NOTHING` on the
       dedupe row, written in the same transaction as the entries (ch 23 R3);
    3. nothing lands on a transfer that is already terminal, or a compensation
       and a straggling step 2 both apply and the ledger balances at a total
       that includes money nobody sent."""
    if sum(a for _, a in entries) != 0:
        raise ValueError("step does not balance")
    key = (transfer_id, step)
    if key in POSTINGS:                       # a redelivery: benign, and a no-op
        return "duplicate"
    if STATE.get(transfer_id) in TERMINAL:
        raise LateStep(f"{transfer_id} is {STATE[transfer_id]}; refusing {step}")
    posting_id = next(POSTING_SEQ)
    if POSTINGS.setdefault(key, posting_id) != posting_id:
        return "duplicate"                    # lost the race; the PK is the authority
    for account, amount in entries:
        LEDGER.append((shard, transfer_id, step, posting_id, account, amount))
    return "posted"

def complete(transfer_id):
    STATE[transfer_id] = "COMPLETED"

def compensate(shard, transfer_id, entries):
    """The reversing entries and the terminal transition are ONE transaction.
    Once it commits, a straggling step 2 has nowhere to land."""
    result = post(shard, transfer_id, "compensate", entries)
    if result == "posted":
        STATE[transfer_id] = "COMPENSATED"
    return result

def total():
    return sum(a for _, _, _, _, _, a in LEDGER)

def shard_total(shard):
    return sum(a for s, _, _, _, _, a in LEDGER if s == shard)

def account_total(name):
    return sum(a for _, _, _, _, acct, a in LEDGER if acct == name)

def in_flight():
    return account_total("in_transit@A") + account_total("in_transit@B")

def duplicate_postings():
    """The check the zero-sum invariant cannot perform. Duplication is not an
    imbalance, so it is invisible to `total()`; it is visible only as a count
    of distinct postings for one (transfer_id, step)."""
    seen = {}
    for _, tid, step, posting_id, _, _ in LEDGER:
        seen.setdefault((tid, step), set()).add(posting_id)
    return {k: sorted(v) for k, v in seen.items() if len(v) > 1}

# Step 1 on the sender's shard.
post("A", "tr1", "debit_sender", [("alice", -500), ("in_transit@A", 500)])
assert total() == 0                 # holds mid-saga
assert shard_total("A") == 0        # and holds per shard

# Step 2 on the receiver's shard, possibly seconds later.
step2 = [("in_transit@B", -500), ("bob", 500)]
post("B", "tr1", "credit_receiver", step2)

# The outbox is at-least-once, so this WILL happen. It must be a no-op.
assert post("B", "tr1", "credit_receiver", step2) == "duplicate", "step 2 re-applied"
assert account_total("bob") == 500          # paid once
assert duplicate_postings() == {}
complete("tr1")
assert in_flight() == 0

# A second transfer stalls after step 1. The in-transit accounts no longer net
# to zero, and the residue is EXACTLY the money currently in flight.
post("A", "tr2", "debit_sender", [("carol", -200), ("in_transit@A", 200)])
assert in_flight() == 200

# A third is compensated because Eve's account is closed. Then step 2 arrives
# anyway -- the retry that was still in the queue when the operator gave up.
post("A", "tr3", "debit_sender", [("dave", -300), ("in_transit@A", 300)])
compensate("A", "tr3", [("in_transit@A", -300), ("dave", 300)])
assert account_total("dave") == 0

try:
    post("B", "tr3", "credit_receiver", [("in_transit@B", -300), ("eve", 300)])
    raise AssertionError("a compensated transfer accepted its own step 2")
except LateStep:
    pass
assert account_total("eve") == 0            # 300 would have been created here
assert in_flight() == 200                   # still just tr2

# WHY the dedupe cannot be delegated to the invariant: append the duplicate by
# hand and watch every check this chapter has stated so far still pass.
for account, amount in [("in_transit@B", -500), ("bob", 500)]:
    LEDGER.append(("B", "tr1", "credit_receiver", 999, account, amount))
assert total() == 0                         # zero-sum: perfect
assert shard_total("B") == 0                # per shard: perfect
assert account_total("bob") == 1000         # and Bob was paid twice
assert list(duplicate_postings()) == [("tr1", "credit_receiver")]
assert in_flight() == -300                  # residue went negative: money invented

Four things that block is arguing, in the order they matter.

1. The zero-sum invariant is structurally blind to duplication, and the reason is the same reason it works. The invariant holds because the ledger is append-only and every posting balances — so a second copy of a balanced posting preserves it exactly. The property that makes the invariant cheap and total is the property that makes it useless here.

This is not a gap to patch in the invariant. It is a different failure class needing a different check. A design that says “the books balance, so the books are right” has confused the two.

2. So monitor the thing the invariant cannot see. Two checks, and notice that neither of them is a sum over amounts:

• SELECT transfer_id, step, COUNT(DISTINCT posting_id) FROM ledger_entries GROUP BY 1, 2 HAVING COUNT(DISTINCT posting_id) > 1 — the direct one. In steady state it returns zero rows, and one row is a paid-twice incident with the transfer named.
• The in-transit residue must be non-negative, not merely equal to something. The residue is the sum of the in-transit accounts across both shards; in normal operation it is exactly the money currently between steps. A duplicated step 2 debits in_transit@B twice for a credit that arrived once, so the residue goes negative — -300 above. “Residue equals the value of open sagas” is the alert everyone writes; “residue is negative” is the one that catches a duplicate, and it costs nothing extra.

3. A terminal state is a guard, not a label. Compensation and step 2 are two writers racing over one transfer, so the compensation must claim the transfer in the same transaction that posts the reversal.

Without that claim, the straggler lands after the refund. Trace it in the block: Dave gets his 300 back, Eve is credited 300 anyway, total() is 0, every stated check passes — and 300 units of money now exist that nobody sent. The guard is bidirectional: a compensation arriving after COMPLETED is refused by the same line.

4. A repeated delivery of a step already seen is a no-op; a never-seen step arriving after the transfer has finished is an incident. Those are different events and they must produce different outcomes, which is why the dedupe check comes before the terminal-state check in post() and not after.

At-least-once delivery makes redelivery routine. Turning routine redeliveries into exceptions is how a team learns to ignore the exception that mattered.

Monitoring stuck sagas

The in_flight() residue is the monitoring design for transfers that stall. It should equal the value of open sagas recorded in the outbox. A residue that does not decay is a stuck transfer — measured in money rather than in messages, which is the unit an operator can act on.

How step 2 gets triggered, and how long it takes

The trigger is the transactional outbox: the message row committed with the debit in step 1, and the relay publishes whatever it finds in the table.

Delivery is at-least-once — the queue may hand the same message over more than once, and never zero times. That is precisely why step 2 must be idempotent on transfer_id. Ch 20 owns those delivery semantics.

Add up the delay before the receiver sees the money. The relay polls the outbox on an interval, the queue adds a hop, and step 2 is one local commit — the same 750 us lock hold from What one row can actually do, written here in milliseconds:

outbox poll, ms:                                     100
queue hop, ms:                                        50
step 2 commit, ms:                                     0.75
credit visible, ms:       100 + 50 + 0.75          =  150.75

About 150 ms before the receiver sees the money. The commit itself is under 1% of that; the wait is almost entirely the poll interval. Not instant, and the product needs to know that.

Compensating is not rolling back

This is the distinction most candidates blur, and the table makes it concrete. Same event — a transfer that does not complete — down two different paths.

A rollback erases a state that never existed for anyone. A compensation is a new, visible, auditable event that undoes the effect of an old one — and the old effect was real.

If Alice’s balance dropped by 500 for four seconds, a payment she attempted during those four seconds may have been declined. No amount of compensation un-declines it. That is the honest cost of the saga, and you should say it rather than let an interviewer find it.

Two design rules fall out, and they are what keeps that cost rare:

• Order the steps so the step that can fail comes first. The debit can fail on insufficient funds; the credit cannot fail for any business reason. Debiting first means business failures happen before anything is visible, so compensation is only ever needed for infrastructure failures.
• Infrastructure failures are retried, not compensated. Step 2 retries against a live shard until it succeeds. If shard B is down for an hour, the money sits in in_transit for an hour, visibly, and the transfer completes. Compensation is the terminal path only when step 2 is permanently impossible — a closed or frozen receiving account — and that path ends in the human queue of Failure modes.

4.3 The choice

The answer is the saga. Four reasons, strongest first — the order the argument should be made out loud.

1. The blocking window is unacceptable for this workload. 300,000 locked balances from one coordinator crash is a worse failure than any consistency anomaly on this list. Availability of people’s own money is the product.

2. 2PC halves the hot-row ceiling — 1,333/s down to 690/s — and leaves only 10% headroom after bucketing. The saga keeps the full 1,333 per bucket, because every step is a plain local transaction with no extra phases inside the lock:

saga with 16 buckets, /s: 16 x 1,333               =  21,328
saga headroom:            21,328 / 10,000          =  2.13

2.13x headroom against 1.1x. That is the difference between a design with room and a design that happens to fit.

3. At 96.9% cross-shard, 2PC’s cost is not amortized over anything. It is the price of essentially every transfer, not of a rare one.

4. Double-entry removes saga’s usual objection. The standard complaint about sagas is that the intermediate state is anomalous — money in a state the model does not describe. Here it is a named account with a queryable balance and an alertable residue. The invariant never breaks; it just has a leg in in_transit.

What you accept in exchange

Two things, and both are product facts to state rather than bugs to hide:

• reversals are visible on customer statements;
• the receiver’s credit lands about 150 ms after the sender’s debit.

The one case where 2PC would still win is a same-shard transfer, which is 1/32 of traffic — and there it is not 2PC at all, it is a single local transaction. So route both accounts onto the same shard whenever you can (a user and their own sub-accounts, for instance), and that fraction becomes free.

5. Append-only, and why corrections are new entries

Every mechanism so far has appended to the ledger; none has edited it. That is a rule, not a habit: the ledger takes INSERT and nothing else.

UPDATE and DELETE are revoked at the grant level — the database’s own permission system — so nobody holds the privilege, including the application’s own database account. This is enforcement, not a convention discouraged in code review, and the difference matters at 3 a.m.

Three reasons, in descending order of how often each is the one that matters:

1. Time travel is the product. balance(a, T) = SUM(amount_minor) WHERE account_id = a AND seq <= T is exact and cheap only because rows never change. One UPDATE and every historical balance the system ever reported becomes unreproducible — including the ones printed on statements customers already have.
2. A correction carries information. “This entry was wrong and here is the reversal, at this time, by this operator, for this reason” is three facts. Editing the row keeps zero of them.
3. The invariant is only checkable over an immutable log. Yesterday’s checkpointed sum (What checking the invariant costs) is a constant because the past cannot change. Allow updates and every check becomes a full scan of all history.

So a correction is a new zero-sum transaction: it reverses the original and, if needed, posts the right one. It carries corrects: <transfer_id> so the pair is joinable later. The account’s history grows; it never rewrites.

The hash chain

There is one more enforcement level beyond permissions. Chain each entry to the one before it, storing prev_hash = SHA256(prev_hash || row) per shard — each row carries a cryptographic fingerprint computed from the previous row’s fingerprint concatenated with its own contents.

Because every fingerprint depends on the entire history behind it, any silent edit changes every fingerprint after the edited row, and the chain stops verifying from that point on.

That is what tamper-evident means, and note what it does not mean. You cannot prevent a determined operator with disk access from editing a row. You can guarantee the edit is detectable. Publishing the day’s final fingerprint (the head hash) somewhere outside the system makes the break provable to someone who has no reason to trust you.

The cost is one hash over every entry byte. SHA-256 runs at roughly 1 GB/s per core, so divide the peak byte rate by that:

hash bytes/s at peak:     120,000 x 240            =  28,800,000
core-fraction at 1 GB/s:  28,800,000 / 1,000,000,000  =  0.0288

28.8 MB/s of hashing against 1 GB/s of capacity — 2.9% of one core to make the ledger tamper-evident. There is no argument against paying that.

6. Read paths: balance versus statement

Writing money down is half the system. Reading it back splits into two questions — “what is my balance?” and “show me my statement” — which look similar and have nothing in common mechanically: two completely different shapes, one source of truth. In the comparison below, the rows that matter most are “Rows touched” and “Frequency”, because together they explain why one gets optimized and the other does not.

One term used in it: cursor-paginated means results come back a page at a time with an opaque marker meaning “continue from here”, rather than by page number. That is the only correct way to page through a log that is still growing — with page numbers, a new entry arriving between requests shifts every later row and the reader sees a duplicate or a gap.

Size a month of a normal user’s statement, at the 10 entries/day assumed throughout:

entries in a month:       10 x 30                  =  300
bytes:                    300 x 240                =  72,000

72 KB, contiguous on disk thanks to the clustering, read in under a millisecond.

Older months come from Parquet in object storage, partitioned by (month, account_bucket). That read takes seconds — acceptable for something a user explicitly asked for and is watching a spinner for. The column-store layout also makes the archive far smaller than 240 B/row, because currency and account_id compress to nearly nothing once the rows are sorted (Storage what a query actually reads off disk).

The one caching decision

Do not cache the balance in Redis — Redis being the usual in-memory key-value store people reach for.

The reason is not performance. The source is already a four-page read against pages that are almost certainly in the buffer pool, the database’s own in-memory cache of recently used pages. An external cache saves almost nothing.

The reason is that a stale balance is not a slow answer, it is a wrong one. Every cache introduces a window in which the ledger and the cache disagree. In most domains that window is a tolerable trade. In this one it is the bug — it is the “sees a balance and cannot spend it” failure from Framing what decision and what breaks, reintroduced deliberately.

Cache the statement page if you like. Never cache the number the user is about to spend against.

7. Bottlenecks and scaling

Every ceiling derived above, collected in one place — and then the operation that genuinely hurts: changing the number of shards while money is moving. Only the first row is a limit the design has to work around; the rest have comfortable margins.

Resharding

Resharding is the one genuinely painful operation, and it is worth knowing why before you need it.

How much data moves depends entirely on the placement scheme. With plain hash(account_id) mod N, going from 32 to 64 shards changes the modulus, so about half of all keys land somewhere new. With a hash ring — shards and keys both placed on a notional circle, each key owned by the next shard clockwise — adding one shard steals keys from its neighbour alone, about 1/(N+1) of the total, rather than reshuffling everything (ch 05).

Either way, the hard constraint is the same: an account must not move part-way through a transfer. So the procedure is four steps.

1. Freeze new sagas for that account.
2. Drain the in-flight ones. This is measurable rather than guessed — it is the in_transit residue of Saga and why compensate is not rollback, filtered to that account, going to zero.
3. Copy the data and flip the routing entry.
4. Unfreeze.

The drain in step 2 is bounded by the step-2 retry deadline, not by how long the copy takes — so you can predict it before you start.

8. Failure modes

Every way the design breaks, the signal that reveals it, and the response. The middle column deserves the closest attention — three of these failures are invisible to the check most people would reach for.

9. Alternatives rejected

Each row is a design somebody proposes in every review of this system, with the one-line reason it does not survive the numbers above. Knowing why the losers lose is what separates a memorized design from a defended one.

10. Interviewer pushback

These are the six questions this design reliably attracts. The answers are written the way you would say them out loud, and each one shows the number being derived rather than remembered — which is the actual thing being tested.

“You have 16 rows where one would do. Isn’t the read now 16x more expensive?”

No, and the reason is the clustering. All 16 buckets are 1 KB, which is an eighth of an 8 KB page, and the primary key is (account_id, bucket) — so one B-tree descent, four page reads, exactly what the single-row case costs. What actually grows is rows examined: 480,000 a second at peak, about 200 ns each, under a tenth of a core across the fleet. If I had keyed the table (bucket, account_id) instead, the objection would be right and it would be 16 descents. The layout is the whole answer.

“Where does 1,333 writes per second come from? That seems low for modern hardware.”

It is a lock hold time, not a query time. The row lock is held from acquisition to commit, and commit includes a synchronous replica acknowledgement — one datacenter round trip, 500 us, which is two thirds of the 750 us total. The rest is 10 us of index descent, 40 us of update and WAL, and 200 us of amortized group-commit fsync. The hardware is fast; the durability requirement is what serializes. If I relaxed to asynchronous replication I would get maybe 4,000/s and an RPO greater than zero, which for a wallet is not a trade I would make.

“Why not 2PC? You control both shards. It is your own database.”

Owning both sides fixes the enlistment problem, not the blocking one. A participant that has voted yes cannot unilaterally abort, so it holds its locks until the coordinator speaks. At 10,000 transfers a second onto one merchant, a 30-second coordinator outage leaves 300,000 balance rows locked, and those are ordinary users who cannot spend their own money. On top of that, 2PC’s extra round trip and fsync push the lock hold from 750 to 1,450 us, cutting the per-row ceiling to 690/s — and since 96.9% of my transfers are cross-shard, I pay that on essentially every transfer, not on a rare one.

“Compensation leaves a visible reversal on the customer’s statement. Isn’t that a worse user experience than a rollback?”

It is, and I would still take it, because the alternative is not a rollback — the alternative is 2PC’s blocking. What I do instead is make compensation rare by construction: I order the saga so the step that can fail on business grounds, the debit, happens first. After that, step 2 cannot fail for any business reason, so every failure is infrastructure and every infrastructure failure is retried rather than compensated. Money waits visibly in the in-transit account until shard B comes back. Compensation is reserved for permanently impossible credits, like a closed receiving account, and those end in a human queue.

“Your snapshot interval is 20 million entries. Why not every hour?”

Because the recovery time depends on entry count, not on elapsed time, so a time-based rule gets both ends wrong. My fold runs at 2 M entries a second and my target is a 10-second rebuild, which is 20 M entries — that is where the number comes from. For the flash-sale merchant at 10,000 entries a second, 20 M entries is 33 minutes, so an hourly rule would leave twice my recovery budget unsnapshotted. For a normal user at 10 entries a day it would be 5,479 years, so an hourly rule writes millions of snapshots nobody will read. Count-based, the whole system produces 200 snapshots and 13 KB a day.

“How do you know the balances are right, given nothing ever locks the whole system?”

Four independent checks, each catching something the others cannot. Per-transaction zero-sum is enforced at write time, so a half-written movement cannot be persisted. Per-shard, I sum the open partition’s entries against a checkpoint — 30 seconds per shard, all 32 in parallel, every few minutes. Nightly I re-fold the log and compare it to the materialized balances, which is 62.5 core-seconds per shard. And the cross-shard question reduces to one number: the sum of the in-transit accounts must equal the value of open sagas in the outbox. If that residue stops decaying, I have a stuck transfer and I know exactly how much money is in it.

The fourth is the one I would volunteer, because none of the first three can see it: a duplicated saga step. Delivery is at-least-once, so step 2 will be redelivered, and a step applied twice is zero-sum twice — the invariant holds perfectly while the receiver is paid twice. So the dedupe row on (transfer_id, step) is a uniqueness constraint written in the same transaction as the entries, and the monitor is a count of distinct postings per step rather than a sum of amounts. The residue check catches it too, from the other side: a step-2 replay debits in-transit twice for one credit, so the residue goes negative, and “residue is negative” is a cheaper alert than any of the sums.

Assumption ledger

Every number above rests on something assumed. This table separates the assumptions you should simply state and move past from the ones worth asking about, and marks which ones actually change the design if they turn out differently. Load-bearing means the architecture changes if the assumption is wrong; if it is not load-bearing, being wrong only moves a number.

Cheat sheet

Related: 27 — Payment System owns double-entry, money types, and the outside world; 23 — Hotel Reservation owns idempotency keys and the double-booking race; 20 — Distributed Message Queue owns the outbox’s delivery semantics; sql 03 owns isolation levels and the anomaly matrix.