Double-Entry Ledger

Track: Data consistency. 6 stages. Languages: Go, Python, JavaScript, Rust.

Build the kind of ledger that sits behind a bank account or a payment app. Money moves between accounts, never out of nowhere and never into nowhere. Every transfer either fully happens or does not happen at all, even when many transfers land on your ledger at the exact same moment.

Implement New(), CreateAccount(id, currency, opening) to open an account with a starting balance, Post(entries) -> (txID, ok) to move money, Balance(id) -> amount to read an account's current balance, and Transactions(id) -> []txID to list the transfers that touched an account. Amounts are whole numbers (no cents as decimals, just count in the smallest unit, like cents themselves).

A transfer is a list of entries. Each entry names an account and an amount: a negative amount leaves that account, a positive amount arrives in it. For the whole transfer to be allowed, the entries for each currency must add up to exactly zero, so nothing is created or lost. Example: moving 40 from account a to account b is the entry list [{a, -40}, {b, 40}], which adds up to zero. Post must check this and reject the whole transfer, with no change to any account, if it does not add up, or if any entry names an account that was never opened, or if it would take an account below zero where that is not allowed.

Many callers can call Post for the same accounts at the exact same time. Your code must still move money correctly and never go below zero where it is not allowed. For help with the ideas behind this, read the notes. New to code that many callers run at the same time? Read Many callers at once first.

In JavaScript, only one piece of your code runs at a time, so a check and a change with no await between them can never be split. A real Node.js server keeps its data in a database, and that is where the race happens. So in JavaScript, New(db) gets a store from the tester, and you keep all your data in it with await db.get(key) and await db.set(key, value). Every method is async. Values are copied as JSON, like in a real database. While one call waits at an await, other calls run. If post reads a balance, waits, and then writes it back, another post can read the same old balance in between, and one of the two changes is lost. In the stages that send one call at a time, the tester runs two copies of your code that share one db and sends the calls to them in turn, like two servers. Data kept only in a local variable or Map is not seen by the other copy, so it gives wrong answers.

Where it is used

• Stripe tracks the money moving through its system in a ledger built on double-entry bookkeeping. A missing or wrong entry shows up right away as an account that should be zero but is not.
• Square built a ledger service called Books in which every entry must add up to zero, so money cannot appear or vanish without a record.
• TigerBeetle is a database made just for this: every transfer takes money from one account and puts it into another.

Two payments that read the same balance at the same moment can both pass the "is there enough money" check and send the account below zero. That is the race this challenge tests.

Stages

de1: open accounts, move money, check balances (very easy)

Open two accounts and move money between them with one transfer. Check the balances afterward. Example: open account a with 100, open account b with 0. Post [{a, -40}, {b, 40}]. Balance("a") reads 60, Balance("b") reads 40.

The tester will verify: the transfer succeeds, and both balances match, along with the list of transfers that touched each account.

de2: reject a transfer that doesn't add up, or that names an unknown account (easy)

A transfer whose entries don't add up to zero must be rejected, with no change to any balance. The same goes for a transfer naming an account that was never opened: reject the whole thing, don't change the accounts that do exist, and don't create the missing one. Balance of an account that was never opened reads 0. Example: open account a with 100. Post [{a, -30}, {b, 20}]: this adds up to -10, not zero, so it is rejected and Balance("a") still reads 100. Post [{a, -5}, {ghost, 5}], where ghost was never opened: this is also rejected, Balance("a") is unchanged, and Balance("ghost") reads 0.

The tester will verify: both kinds of bad transfer are rejected without touching any balance, a normal transfer right after still works, and Balance of an unknown account reads 0.

de3: keep each currency's money separate (medium)

When accounts use different currencies, each currency must add up to zero on its own. A transfer that nets to zero only by mixing currencies together must be rejected. Example: account a holds USD, account e holds EUR. Post [{a, -20}, {e, 20}]: taken together the numbers cancel out, but USD and EUR are different currencies, so this is rejected. A transfer that only touches USD accounts, or only EUR accounts, and adds up to zero within that currency, still works. After that comes a long run of transfers with 2 to 5 entries each, over 4 USD accounts and 3 EUR accounts, mixed with Balance and Transactions calls. Some transfers add up to zero, some do not, and some add up only by mixing currencies. A transfer may move USD and EUR at the same time. That is allowed when each currency adds up to zero on its own.

The tester will verify: a transfer that adds up to zero only by crossing currencies is rejected, normal same-currency transfers still succeed with the right balances, and every answer in the long run matches our solution exactly.

de4: many transfers at once must not lose or create money (hard)

4 accounts start at 100,000 each, in a ring: account 1 sends to account 2, account 2 sends to account 3, and so on back around to account 1. Each account's own worker sends 100 units to the next account in the ring, 200 times, and all 4 workers run at the same time. Since the same amount flows all the way around the ring, every account should end exactly where it started.

The tester will verify: the total across all 4 accounts stays at 400,000 (nothing created or lost), and every account ends back at exactly 100,000.

de5: many withdrawals at once must never go below zero (hard)

A vault starts with 3,000 units. 150 workers each try to withdraw 30 units from it at the exact same moment. Only as many withdrawals as the vault can actually cover may succeed. Here that is exactly 100 of them (3,000 divided by 30), leaving the vault at 0. The vault must never read below zero, no matter how the workers' calls overlap. A second test follows. It runs 100 rounds (20 in JavaScript), and each round starts a fresh vault with 3,000 units. 8 workers start together, and each one keeps withdrawing 30 units until Post says no. In Go, Python and Rust the workers run on real threads. In JavaScript they are async calls that overlap at every await on the db. Either way, a Post that checks the balance and takes the money in two separate steps, or that uses no lock at all, gets caught here.

The tester will verify: exactly 100 of the 150 withdrawals succeed, the vault ends at exactly 0, and it never goes negative at any point. Every one of the rounds also ends with exactly 100 successful withdrawals and the vault at exactly 0.

de6: make moving money and checking balances fast (hard)

Keep Post and Balance quick even as the number of past transfers grows. Looking back through every past transfer to work out a balance shows up here. Keeping a running balance that you update as you go does not. In JavaScript the db answers at once in this stage, but every call still copies its value, so one list that grows with every transfer gets slow too. Example: if our solution takes 100 ms for a batch of calls, the limit is 150 ms, which is 1.5 times as long. Your solution must also make no more than 2 times as many memory allocations as our solution.

The tester will verify: your code takes at most 1.5 times as long and makes at most 2 times as many memory allocations as our solution, with every answer still correct.

Rules

• Standard library only. No third-party packages.
• Amounts are whole numbers in the smallest unit of the currency.
• A transfer's entries must add up to zero for each currency on its own, or the whole transfer is rejected.
• Apply each transfer in one step that nothing else can interrupt. No caller should ever see a transfer half done, and no update from one caller should be lost because another caller ran at the same time.
• If your code locks more than one account for a single transfer, always lock them in the same order every time, so two transfers can never end up waiting on each other forever.
• Keep Balance quick. Keep a running balance instead of replaying every past transfer on each call.

Read the Double-Entry Ledger notes in the wiki