Double-Entry Ledger
What it is
Think of the record a bank keeps behind your account. Every time money moves, it moves between two accounts at once: it leaves one and arrives in another, on the same step. Nothing is ever created from nowhere and nothing ever vanishes. In this challenge we call the leaving side of an entry a debit and the arriving side a credit. This is a simplified convention. Real accounting uses these words in a more complex way. You don't need the words to build this: a negative amount leaves an account, a positive amount arrives in it.
A ledger is the record keeper for this. It opens accounts, moves money between them, and always knows each account's current balance and the list of transfers that touched it.
The core idea
A transfer is a list of entries, one per account it touches. For the transfer to be allowed, the entries must add up to exactly zero for each currency. Moving 40 from account a to account b is the entry list {a: -40, b: 40}, which adds up to zero. A transfer that would leave money over or short, for example {a: -40, b: 30}, must be rejected outright, with no change to any account. The same goes for a transfer naming an account that was never opened.
If accounts hold different currencies, each currency must add up to zero on its own. Mixing a USD leg and a EUR leg that happen to cancel out as plain numbers is not good enough: dollars and euros are not the same thing, and a ledger that lets them cancel is really letting money leak from one currency into another.
Example: a transfer, and a rejected one
Open account a with 100 and account b with 0, both in USD. Post {a: -40, b: 40}: it adds up to zero, so it is accepted, and the balances become 60 and 40. Now try to post {a: -30, b: 20}: it adds up to -10, not zero, so it is rejected, and both balances stay exactly where they were. A transfer naming an account that does not exist is rejected the same way, changing nothing, and that unknown account's balance reads 0, not an error and not a surprise new account.
The many-callers-at-once problem
Say a vault holds 90 units, and two withdrawals of 60 each arrive at almost the same instant. If your code reads the balance, decides there is enough, and only then subtracts, both withdrawals can make that same decision before either one has written anything back, and both succeed, taking the vault to -30. This is the same mistake as two people checking a shared bank balance on their phones at the same moment, each seeing enough money, and both spending it.
The fix is to make checking the balance and changing it happen as a single step that nothing else can get in the middle of, usually by holding one lock across the whole transfer. Whichever caller's transfer runs that step first sees the real, current balance, and every other caller waits its turn and sees the updated number.
If you lock more than one account for a single transfer instead of locking the whole ledger at once, always lock the accounts in the same order every time. Two transfers that lock the same two accounts in opposite orders can each end up waiting forever for a lock the other one is holding.
Where you meet this
- Stripe's Ledger is "based on double-entry bookkeeping". Accounts that should end at zero make problems easy to find: "a single missing, late, or incorrect transaction immediately creates a detectable accuracy issue". (Stripe Ledger)
- Square's Books service requires that every journal entry balances to zero, and it never edits an old entry. A fix is a new entry. (Books at Square)
- TigerBeetle is a database for financial transfers. Each transfer has exactly one debit and one credit. (TigerBeetle financial accounting)
When to choose it: you move money, credits, points, or anything else that must never be created or lost by mistake, and you need to explain later where every unit went.
When not to: a simple counter that nobody audits, like page views. One balance column per account is simpler, but it cannot tell you why a balance changed.
Common bugs
- Accepting a transfer whose entries do not add up to zero, or that mix currencies together.
- Applying only some of a transfer's entries instead of rejecting the whole thing.
- Reading a balance, pausing, then writing it back and overwriting another caller's change in between.
- Letting a withdrawal through, even partly, when it would take an account below zero.
- Locking accounts in a different order for different transfers, which can deadlock the whole program.
Check it yourself
After a batch of transfers, add up every account's balance. The total should be exactly the same as before any of them ran, since every transfer moves money around without creating or losing any. If a transfer was rejected, check every account it named still has its old balance.
Keep it fast
Keep a running balance per account, and update it the moment you accept a transfer. Don't work out a balance by replaying every past transfer on each read, that gets slower the longer the ledger runs.
Learn more
This same idea, debits and credits that must balance, is the basis of real double-entry bookkeeping and of how banks and payment processors keep their books honest. "Designing Data-Intensive Applications" covers the concurrency side of this problem: applying a change atomically and locking in a consistent order.