Double-entry ledger

Deep dive

How it works

In: transaction = list of postings (account, signed amount, currency) · Out: appended entries, updated balances, or a rejection · State: append-only journal + cached balance per account · Cost: O(k) for k postings, plus one row lock per touched balance

txn 1  card deposit $100           txn 2  customer pays merchant $30, fee $1
  psp_receivable   (asset)  +10000   customer_wallet  (liab.)  +3000
  customer_wallet  (liab.)  -10000   merchant_wallet  (liab.)  -2900
                                      fee_revenue      (rev.)    -100
  sum = 0                             sum = 0

1. Accounts: id, currency, type (asset, liability, equity, revenue, expense), flags (e.g. must not go negative from the holder's view).
2. Post: validate (≥ 2 postings, non-zero amounts, accounts exist, currency matches, per-currency sum = 0, balance constraints), then append the transaction and update cached balances atomically.
3. Read balance: cached balance (O(1)), or as-of balance = sum of postings up to a time/sequence.
4. Correct: post a reversal (same postings, negated) referencing the original, then post the right transaction.
5. Holds / two-phase: reserve by moving funds to a holds account (or tracking a pending amount), then either post (capture) or void (release).
6. Audit: periodically recompute balances from the journal and check Σ balances = 0 per currency.

Code

use std::collections::HashSet;

pub type AccountId = u32;

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Normal { Debit, Credit } // assets/expenses vs liabilities/equity/revenue

pub struct Account { pub currency: [u8; 3], pub normal: Normal, pub no_overdraft: bool, pub balance: i128 }

#[derive(Clone, Debug)]
pub struct Posting { pub account: AccountId, pub amount: i64 } // > 0 debit, < 0 credit, minor units

#[derive(Clone, Debug)]
pub struct Txn { pub id: u128, pub postings: Vec<Posting>, pub reverses: Option<u64> }

#[derive(Debug, PartialEq, Eq)]
pub enum Error { Duplicate, TooFewPostings, ZeroAmount, UnknownAccount, Unbalanced, Insufficient(AccountId), NotFound }

#[derive(Default)]
pub struct Ledger { pub accounts: Vec<Account>, pub journal: Vec<Txn>, seen: HashSet<u128> }

impl Ledger {
    /// Validates everything first, mutates nothing until all checks pass. Returns the journal sequence.
    pub fn post(&mut self, t: Txn) -> Result<u64, Error> {
        if self.seen.contains(&t.id) { return Err(Error::Duplicate); }        // idempotent by txn id
        if t.postings.len() < 2 { return Err(Error::TooFewPostings); }
        let mut per_cur: Vec<([u8; 3], i128)> = Vec::with_capacity(2);
        let mut delta: Vec<(AccountId, i128)> = Vec::with_capacity(t.postings.len());
        for p in &t.postings {
            if p.amount == 0 { return Err(Error::ZeroAmount); }
            let a = self.accounts.get(p.account as usize).ok_or(Error::UnknownAccount)?;
            match per_cur.iter_mut().find(|(c, _)| *c == a.currency) {
                Some(s) => s.1 += p.amount as i128,
                None => per_cur.push((a.currency, p.amount as i128)),
            }
            match delta.iter_mut().find(|(id, _)| *id == p.account) {    // same account may repeat
                Some(d) => d.1 += p.amount as i128,
                None => delta.push((p.account, p.amount as i128)),
            }
        }
        if per_cur.iter().any(|&(_, s)| s != 0) { return Err(Error::Unbalanced); }
        for &(id, d) in &delta {
            let a = &self.accounts[id as usize];
            let after = a.balance + d;
            let holder_view = if a.normal == Normal::Debit { after } else { -after };
            if a.no_overdraft && holder_view < 0 { return Err(Error::Insufficient(id)); }
        }
        for &(id, d) in &delta { self.accounts[id as usize].balance += d; }
        self.seen.insert(t.id);
        self.journal.push(t);
        Ok(self.journal.len() as u64)                                        // 1-based sequence
    }

    /// Corrections are new transactions; history is never edited.
    pub fn reverse(&mut self, seq: u64, new_id: u128) -> Result<u64, Error> {
        let orig = self.journal.get((seq as usize).wrapping_sub(1)).ok_or(Error::NotFound)?;
        let postings = orig.postings.iter().map(|p| Posting { account: p.account, amount: -p.amount }).collect();
        self.post(Txn { id: new_id, postings, reverses: Some(seq) })
    }

    /// Audit: recompute every balance from the journal; check caches and the zero-sum invariant.
    pub fn verify(&self) -> bool {
        let mut b = vec![0i128; self.accounts.len()];
        for t in &self.journal { for p in &t.postings { b[p.account as usize] += p.amount as i128; } }
        let caches_ok = b.iter().zip(&self.accounts).all(|(x, a)| *x == a.balance);
        let mut per_cur: Vec<([u8; 3], i128)> = Vec::new();
        for a in &self.accounts {
            match per_cur.iter_mut().find(|(c, _)| *c == a.currency) {
                Some(s) => s.1 += a.balance, None => per_cur.push((a.currency, a.balance)),
            }
        }
        caches_ok && per_cur.iter().all(|&(_, s)| s == 0)
    }
}

The same model in SQL (PostgreSQL), with the balance rule enforced at commit:

CREATE TABLE entries (
  txn_id     uuid    NOT NULL,
  entry_no   int     NOT NULL,
  account_id bigint  NOT NULL REFERENCES accounts(id),
  amount     bigint  NOT NULL CHECK (amount <> 0),        -- minor units, debit > 0
  PRIMARY KEY (txn_id, entry_no)
);
CREATE FUNCTION check_balanced() RETURNS trigger LANGUAGE plpgsql AS $$
BEGIN
  IF EXISTS (SELECT 1 FROM entries e JOIN accounts a ON a.id = e.account_id
             WHERE e.txn_id = NEW.txn_id GROUP BY a.currency HAVING sum(e.amount) <> 0) THEN
    RAISE EXCEPTION 'unbalanced transaction %', NEW.txn_id;
  END IF;
  RETURN NULL;
END $$;
CREATE CONSTRAINT TRIGGER balanced AFTER INSERT ON entries
  DEFERRABLE INITIALLY DEFERRED FOR EACH ROW EXECUTE FUNCTION check_balanced();
REVOKE UPDATE, DELETE ON entries FROM app_role;            -- append-only

Complexity and constants

• Post: O(k) for k postings (usually 2-4) plus the balance updates; in SQL, one row insert per posting and one row lock per touched balance.
• Entry size: order of 50-100 bytes per row in SQL with indexes; 128 bytes per transfer in TigerBeetle's fixed layout.
• Throughput limit is the hottest account: every transaction touching a shared fee or settlement account serializes on its balance row.

Efficiency

Cost: the bound is contention on hot account rows plus one fsync per commit; the arithmetic is trivial. A post is O(k) for k postings (usually 2-4), one row insert per posting and one row lock per touched balance in SQL; order of 50-100 bytes per entry in SQL, 128 bytes per transfer in TigerBeetle.

Levers

• Batch commits — many transactions per fsync — TigerBeetle accepts up to 8,189 transfers per request with its default configuration (docs) — any volume.
• Spread hot accounts over N sub-accounts or sum lazily — throughput scales with N instead of one row lock — shared fee or settlement accounts.
• Fixed-size integer records — no parsing, sequential appends — dedicated engines.
• Snapshots — as-of reads scan only postings after the last one — historical balances.
• Lock accounts in ascending id — fewer deadlock retries — multi-account posts.

Naive → standard → state of the art

• Naive: recompute balances by summing all entries · O(entries) per read
• Standard: PostgreSQL with cached balances and a balance-sum check · enough at moderate volume
• State of the art: purpose-built ledger database (TigerBeetle) · batched 128-byte transfers, no row-lock contention model

Implementation notes

• Locking: lock touched balance rows in ascending account id order (SELECT … WHERE account_id = ANY($1) ORDER BY account_id FOR UPDATE) to avoid deadlocks; or use a version column and optimistic concurrency.
• Hot accounts: split a busy house account into N sub-accounts (pick one by hash of txn id), or don't maintain a cached balance for it and sum lazily; the zero-sum check still holds.
• Idempotency: a unique transaction id from the caller (idempotency key) makes retries safe; reject, don't re-apply, duplicates.
• Time: store both the posting time (when recorded) and the effective/value date; as-of queries and statements use the latter.
• Multi-currency: FX is two balanced legs through FX accounts per currency (USD leg: customer → FX pool; EUR leg: FX pool → customer), never one posting mixing currencies.
• Pending (two-phase): either postings to a holds account, or per-account pending_debits/posted_debits fields as in TigerBeetle, with available = posted − pending.
• Snapshots: keep periodic balance snapshots (account, balance, up to sequence) so as-of reads don't scan from the beginning.

Pitfalls

• Updating a balance column without an entry ("adjustments"): the journal no longer explains the balance.
• Deleting or editing entries to fix a mistake: destroys the audit trail; reverse instead.
• Single-entry thinking (one row "user paid 30"): there is no counter-account, so money can silently appear.
• Checking balance sufficiency outside the transaction that posts: two concurrent debits both see enough funds.
• Mixing sign conventions between services (credit-positive here, debit-positive there): reconcile the convention at the API boundary.
• Floats for amounts (money representation).

Variants and alternatives

In production

Banking and payments: TigerBeetle (purpose-built financial database: 128-byte accounts and transfers, u128 amounts, two-phase pending transfers) and the general ledgers of banks and payment companies. Accounting and personal finance: Ledger, Beancount, hledger (plain-text double-entry accounting). Resource accounting and time tracking: TigerBeetle's rate-limiting recipe, hledger timeclock/timedot.

Implementations

Sources

• Martin Fowler, Analysis Patterns: Reusable Object Models, Addison-Wesley, 1996 (accounting patterns). book
• TigerBeetle documentation, Data Modeling and Two-Phase Transfers. data modeling · two-phase · code
• PostgreSQL documentation, CREATE TRIGGER (constraint triggers, DEFERRABLE INITIALLY DEFERRED). docs