Invariants and all-or-nothing updates: keeping data consistent
Name the rules your data must always obey, enforce them in one place, validate everything before changing anything, keep history append-only, and test invariants with random operations.
Bugs that lose money or stock are rarely clever. Usually one operation changed half of what it should have, or a rule was checked in one place and forgotten in another. Invariants are the cure.
Name the invariants
Write them down, in the design note and as a comment on the class:
Ledger: every balance >= -overdraft_limit of its account
sum of all balances == sum of all deposits - withdrawals
Inventory: every count >= 0
Order book: best bid < best ask (otherwise they would have traded)
LRU cache: index and recency list contain exactly the same keys; size <= capacityIf you can't state the rules, you can't check that the code keeps them.
Enforce them in one place
Make the data private and let only a few operations change it (see classes that protect an invariant). Then every invariant has a short list of functions that could break it, and each of those is where you check it.
Validate everything, then change everything
An operation that fails halfway is worse than one that fails at the start. Structure every change in two phases:
transfer(from, to, amount):
# 1. check - nothing has changed yet
if amount <= 0: return InvalidAmount
if from or to doesn't exist: return UnknownAccount
if from.balance - amount < -from.limit: return InsufficientFunds
# 2. apply - nothing below can fail
from.balance -= amount
to.balance += amount
log.append(Transfer(from, to, amount))The same applies to batches: an order with five lines either ships all five or none. Check all five first, then apply. That's what "atomic" means in a ticket: all or nothing, never a partial result. If phase 2 can fail (allocation, I/O), prepare the new state on the side and swap it in at the end, so a failure leaves the old state untouched; see keeping state consistent.
Append-only history and reversals
Don't fix a mistake by editing or deleting a past transaction: add a new one that reverses it.
#41 Deposit +100.00
#42 Reversal -100.00 (reverses #41: entered twice)The balance is right, the history explains why, and anything derived from the log (statements, audits, replicas) stays correct. Mark the original as reversed so it can't be reversed twice. This is also why databases and key-value stores write an append-only log first.
Test invariants, not just examples
Example tests check the cases you thought of. To find the ones you didn't, generate random operations and check the invariants after each one:
repeat 10,000 times with a fixed random seed:
pick a random operation and random arguments (including invalid ones)
apply it
assert all invariants holdUse a fixed seed so a failure can be reproduced, and print the seed and step when it fails. This property-based testing is how order books, databases and file systems are tested. Try it in an order book for Tickmark Exchange.
Questions and answers
- What is an invariant in programming?
- A condition that must be true whenever no operation is in progress: 'a balance never goes below its overdraft limit', 'the best bid is below the best ask', 'every key in the index points into the list'. Every operation must start and end with it true.
- What is property-based testing?
- Instead of checking specific examples, you generate many random sequences of operations and check after each one that the invariants still hold. It finds the odd combinations hand-written tests miss.
Practise it in a project
These projects put this guide to work, with tickets, tests and code review.
Coinbridge Credit Union
Account ledger for Coinbridge
Build the ledger behind Coinbridge's accounts: deposits, withdrawals, all-or-nothing transfers, reversals and statements with running balances.
- invariants
- atomic operations
- audit trails
- result codes
Pantry & Co.
Stock counts for Pantry & Co.
Track stock as goods arrive and leave Pantry's warehouse, and tell the buyers what to reorder.
- classes
- invariants
- std::map
- input validation
Tickmark Exchange
An order book for Tickmark Exchange
Build the heart of an exchange: a limit order book with price-time priority, partial fills and O(1) cancels, then market orders, immediate-or-cancel and order amendments.
- ordered maps
- iterator stability
- invariants
- property-based testing
Vaultline
A durable key-value store for Vaultline
Build Vaultline's embedded key-value store: an append-only log that survives crashes, checksums that catch corruption, and compaction that rewrites the log atomically.
- append-only logs
- crash recovery
- checksums
- atomic file replacement
Read next
- State machines in practice: transition tables, guards and event logs
Model order statuses, CSV quoting and regex matching as state machines: one transition table, guards for business rules, event logs you can replay, and NFAs that track several states.