Splitwise

The problem

"Design Splitwise." Friends put shared expenses into a group (a trip, a flat, a dinner), the app shows who owes whom, and when they settle up it suggests who should pay whom. In version 1 no money moves through the app: people pay each other elsewhere.

It reuses the pattern of the Digital Wallet's ledger: every expense writes entries in whole cents that add up to zero. New here: one bill split many ways, edits days later, settling up, adding offline, and several currencies.

The numbers

Say users add 10 million expenses a day. With a day rounded to 100,000 seconds, that's 100 a second, about 500 at busy hours: a light write load. Groups are small: a busy group of 6 people with 500 expenses has at most 3,000 entries, one quick read by group id. The hard part isn't load; it's getting every cent right.

Splitting a bill in whole cents

A $100.00 dinner for Ana, Ben and Cy, split equally, is 10,000 cents ÷ 3 = 3,333 each with 1 cent left over. Pick a rule and use it everywhere: each person gets the whole cents of their share, and leftover cents go one each to members in a fixed order, say the order they joined.

who   share    entry (Ana paid)
Ana   3,334    +6,666
Ben   3,333    −3,333
Cy    3,333    −3,333
sum   10,000   0

Rounding each share to $33.33 leaves the entries a cent off zero; a float can't hold 33.333… exactly, and nobody can pay it. Splits by shares use the same rule (shares of 2, 1 and 1 on $10.00 give 500, 250 and 250 cents), and a split by exact amounts is refused unless they add up to the bill.

Balances from entries: edits are new entries

Store the expenses and their entries, and only ever add rows. A balance is the sum of a person's entries in the group, worked out when the group opens, like "who owes whom" and the settle-up plan. When Ana finds that her $60 grocery receipt really said $90, the edit adds entries that cancel the old split, then the new split's:

entries                      Ana   Ben   Cy
groceries, paid by Ana: $60  +40   −20   −20
edit: cancel the $60 split   −40   +20   +20
edit: the $90 split          +60   −30   −30
balances (sums)              +60   −30   −30

A delete works the same way, so the history shows an expense was added, then removed, and by whom. A stored balance edited on every change drifts the first time a change is applied twice; a sum can always be worked out again.

Settling up: net, then match

After a week's trip, the expenses left these debts among Ana, Ben, Cy and Dee, each owed to whoever paid:

debt        amount
Ben → Ana   $40
Ana → Ben   $10
Cy → Ana    $20
Dee → Ana   $10
Cy → Ben    $10
Dee → Ben   $30
Dee → Cy    $10

Paying each debt is 7 payments moving $130. Canceling each pair's debts first leaves 6 payments and $110, and money still passes through Ben: Dee pays him $30 while he pays Ana $30. Instead, net each person: Ana +$60, Ben +$10, Cy −$20, Dee −$50, adding up to zero. Then the one who owes most pays the one owed most, as much as both allow, until all are at zero:

payment     amount   left after
Dee → Ana   $50      Ana +10, Ben +10, Cy −20
Cy → Ana    $10      Ben +10, Cy −10
Cy → Ben    $10      everyone at 0

Three payments, $70 in all. Every payment brings at least one person to zero and the last brings two, so a group of n never needs more than n − 1 payments. The true minimum can be lower when a few people net to zero among themselves, but finding it means searching subgroups; the greedy match is good enough.

Offline: an id made on the phone

Cy adds "Taxi, $24" on a plane. The phone gives the expense a random id, say e7f3, and keeps it in an outbox until there's signal. If the first send arrives but the answer is lost, the retry carries the same id, and the server, which saves each id once, answers with the saved expense: Idempotency Keys, with the expense's own id as the key. Ids made by the server would turn the retry into $48 of taxis; refusing "the same amount, name and day" would block two real taxis.

Several currencies

In Tokyo, Ben pays ¥12,000 for a dinner for all four. Keep its entries in yen, adding up to zero in yen: Ben +¥9,000, the others −¥3,000 each. Convert only to show a total, at a rate you state: at ¥150 = $1, Ben's ¥9,000 is $60, and with the $30 he owes for groceries his total is +$30.

Converting when the expense is added and storing only dollars forgets what was paid: stored as $80, Cy's share is $20, and a month later at ¥160 = $1 that's ¥3,200, ¥200 more than Ben lent her.

Same pattern as the Digital Wallet's ledger

The ledger carries over: whole cents, entries that add up to zero, rows only added, mistakes fixed with new entries. The wallet kept each balance as a stored copy, since an account collects years of entries; a group's entries are few, so Splitwise works balances out each time.

Summary

• Scope: shared expenses in a group, balances, settling up.
• Data: expenses and entries that add up to zero; edits and deletes are new entries.
• API: every expense sent with an id made on the phone.
• Numbers: about 100 expenses a second; a busy group has about 3,000 entries.
• Splitting: whole cents, leftover cents by a fixed rule.
• Settling up: net each person, then match: at most n − 1 payments.
• Currencies: each entry in its own; convert only to show totals, at a stated rate.