Databases, logs and state

What is true: the statement or the balance?

Kofi opens his mobile-money account history: a list of dated operations, and at the top a balance of 90 francs. Both pieces of information are correct, but they are not of the same nature. The balance can be deduced from the list; the list cannot be deduced from the balance. If only "90" were kept, you could neither explain why, nor detect an error, nor find out what happened yesterday. That asymmetry is the idea of the whole workshop.

The words

• An event is a fact that occurred: "credit of 100 to Awa", "transfer of 30 from Awa to Kofi". It has a sequence number.
• The log is the ordered series of events. It is append-only: you add at the end, you never modify or delete past entries.
• The state is the summary at a given moment: the balances, the content of accounts. It is derived from the log.
• The projection (or replay) is the computation that goes from log to state: start from an empty state and apply each event in order. As a formula: state after event k = rule(state after k - 1, event k).

A worked example

Two accounts start at 0 (Awa, Kofi). Here are six events, with the rule "a debit or transfer that would make a balance negative is rejected: no effect, but it stays in the log".

The final state is Awa = 50, Kofi = 90. Consistency check: accepted credits 100 + 50 + 10 = 160, accepted debits 20, 160 - 20 = 140 = 50 + 90. The transfer neither creates nor destroys money: it moves it.

Why keep both?

So you can throw away the state and recompute it, but not the reverse. That is why systems that must account for themselves (banks, ledgers, blockchains) treat the log as the source of truth and the state as a reading convenience.

The opposite approach, which overwrites the value in place ("set the balance to 90"), keeps no trace: an error or a fraud leaves nothing to examine.

What this does not guarantee

• An append-only log is only append-only if the software and the access rights enforce it. Someone who can write to the file can change the past; we will see this in the security exercise.
• The log can contain false events (a credit that should not have happened). Replaying faithfully rebuilds what is written there, not what is true in the world.
• If a bug makes the state drift from the log, the log is authoritative: you replay.

Recap

Log = ordered facts, added at the end. State = derived, rebuildable summary. A rejected event stays in the log. The log's reliability rests on what prevents it from being modified, not on the word "append-only".

Two computers, the same log, two different balances?

Awa and an auditor each receive a copy of the same log. If their final balances differ, one of them made a mistake — or the rules were not the same. For replay to serve as verification, it must be deterministic: same inputs, same output, everywhere and always. That is what lets anyone recompute the state and obtain the same result as everyone else.

The apply rule

Here is the core of a replay, in Python:

def apply(state, event):
    kind, amount = event[0], event[-1]
    if amount <= 0:
        return False          # amounts: strictly positive integers only
    if kind == "CREDIT":
        _, who, amount = event
        state[who] = state.get(who, 0) + amount
        return True
    if kind == "DEBIT":
        _, who, amount = event
        if state.get(who, 0) < amount:
            return False      # rejected: no effect, stays in the log
        state[who] = state[who] - amount
        return True
    if kind == "TRANSFER":
        _, src, dst, amount = event
        if state.get(src, 0) < amount:
            return False
        state[src] = state[src] - amount
        state[dst] = state.get(dst, 0) + amount
        return True
    return False              # unknown kind: rejected

def replay(log):
    state, rejected = {}, 0
    for event in log:
        if not apply(state, event):
            rejected += 1
    return state, rejected

Notice three things. The function looks at nothing but the state and the event. The "rejected" outcome is not an exception: it is a normal consequence of the rules, and must be the same at every replay. And amounts are strictly positive integers (a zero or negative amount, or an unknown event kind, is rejected, otherwise a negative CREDIT would push a balance below zero): the CFA franc has no sub-unit in everyday use, so 5,000 francs are written 5000; for a currency with cents, you likewise store an integer number of the smallest unit. With floating-point numbers, 0.1 + 0.2 equals 0.30000000000000004 in Python: small rounding errors accumulate and can depend on the order of operations.

Order is part of the data

Take two events: A = DEBIT Awa 30 and B = CREDIT Awa 50, with Awa starting at 0.

The same two events give different states depending on the order. A log is therefore a numbered sequence, not a set: order is data, just like the amounts. (Consensus, which you will study later, is precisely how several machines agree on THAT order.)

What makes a replay non-deterministic

• Reading the time or a random number inside the apply rule;
• using floating-point numbers;
• depending on the iteration order of an unordered structure;
• applying a different version of the rules to part of the log: the rules are part of the state's identity. If you change the rejection rule, an old log no longer gives the same balances.

Verifying a state

A rebuilt state can be verified in two ways. First, by recomputing it from the log and comparing. Second, by invariants: properties that must always hold. Here, the sum of balances equals accepted credits minus accepted debits (a transfer does not change it), and no balance is negative. If an invariant is violated after a replay, there is a bug in the rules or an anomaly in the log.

Snapshots: avoiding a full replay

Replaying a million events to read one balance is slow. A snapshot is a copy of the state after event k. To get the current state, start from the snapshot and replay only events k + 1, k + 2, … With a snapshot after 900,000 events in a log of 1,000,000, you replay 100,000 events. A snapshot is a cache: it must always be comparable with a full replay (that is the subject of the independent lab).

What this does not guarantee

Replaying proves that the state is consistent with the log, not that the log is accurate. If an event was falsified before the replay, the replay faithfully rebuilds the lie. Knowing that the log has not been modified needs one more mechanism (security exercise).

Recap

A replay is a function from (state, event) to a new state, with no randomness and no clock; the order of events is part of the data; count in integers; verify by recomputation and invariants; a snapshot avoids replaying everything.

Why not just a file?

You could write the log to a text file. But as soon as several programs read and write, searches must be fast and a crash must not damage anything, you reinvent by hand what a database provides: organised storage, a query language, indexes and guarantees in case of failure. SQLite is a complete database contained in a single file, with no server to install; Python drives it with its sqlite3 module.

Tables, rows, queries

A table is a grid: each row is a record, each column a field. The SQL language describes what you want without saying how to compute it.

CREATE TABLE events (
  id           INTEGER PRIMARY KEY AUTOINCREMENT,
  kind         TEXT    NOT NULL CHECK (kind IN ('CREDIT', 'DEBIT', 'TRANSFER')),
  account      TEXT    NOT NULL,   -- account credited (CREDIT), debited (DEBIT, TRANSFER)
  counterparty TEXT,               -- beneficiary, only for TRANSFER
  amount       INTEGER NOT NULL CHECK (amount > 0)
);

INSERT INTO events (kind, account, amount) VALUES
  ('CREDIT', 'awa',  100),
  ('CREDIT', 'kofi',  50),
  ('DEBIT',  'awa',   30);

SELECT account,
       SUM(CASE kind WHEN 'CREDIT' THEN amount ELSE -amount END) AS balance
FROM events
WHERE kind IN ('CREDIT', 'DEBIT')
GROUP BY account;

Result of the last query: awa | 70 and kofi | 50. That is exactly lesson 2's projection, expressed in SQL: the log is the events table, the balance is a computation over it. The CHECK constraints outright refuse an unknown kind or a zero or negative amount; PRIMARY KEY AUTOINCREMENT gives each row an increasing sequence number. As in lesson 1, a transfer is one event (TRANSFER, with the beneficiary in counterparty); this query does not count it (it would have to debit account and credit counterparty), which is why the state is also kept in a separate table, further down.

Indexes: reusing workshop 102

Finding an account's events with WHERE account = 'awa' without an index forces a scan of the whole table: O(n). An index is an extra structure, maintained by the database, that finds rows in O(log n): in SQLite, tables and indexes are stored in B-trees, the balanced many-children trees mentioned in workshop 102.

CREATE INDEX idx_events_account ON events (account);

The price: every insertion must also update the index, and it takes space. Index what you search often.

Keeping the state next to the log

You can keep, in a second table, an already computed state:

CREATE TABLE balances (
  account TEXT PRIMARY KEY,
  amount  INTEGER NOT NULL CHECK (amount >= 0)
);

The CHECK (amount >= 0) constraint makes the database refuse any operation that would make a balance negative: the offending UPDATE fails, so (lesson 4) the whole transaction is rolled back. It is a second safeguard for the rejection rule. Reading a balance becomes a key access, O(log n) (or O(1) in memory in a dictionary).

A log that refuses modification

You can ask SQLite to forbid modifying and deleting the rows of events:

CREATE TRIGGER events_no_update BEFORE UPDATE ON events
BEGIN
  SELECT RAISE(ABORT, 'events is append-only');
END;

(A similar BEFORE DELETE trigger closes the other door.) This is useful against mistakes and bugs. But someone who controls the file or the administration rights can drop the trigger or rewrite the file: it is not a cryptographic guarantee.

What this does not guarantee

• A database is not "true": it keeps what it was given, mistakes included.
• An index speeds up certain searches and slows down writes; without measurement (workshop 102), you do not know whether it is worth its cost.
• SQL is not magic: the balance query above applies no business rule.

Recap

Table = log; query = projection; index = tree that speeds up search; constraints and triggers = safeguards, not proofs. The ledger's rules are checked at append time or at replay.

The transfer that vanishes

Awa sends 5,000 francs to Kofi. In our ledger that is one event (TRANSFER), but it takes three writes in the database: add the event to the log, take 5,000 off Awa's balance, add 5,000 to Kofi's balance. The program performs the first two… and the battery dies. On restart, Awa has lost 5,000 francs Kofi never received: money has been destroyed. (The other way round, with Kofi's credit written without Awa's debit, it would have been created.) The problem is not a calculation error; it is that writes that were meant to go together got separated.

Atomicity: all or nothing

A transaction groups several operations into a single atomic unit: all are applied, or none. No intermediate result is visible after a crash.

BEGIN;
INSERT INTO events (kind, account, counterparty, amount) VALUES ('TRANSFER', 'awa', 'kofi', 5000);
UPDATE balances SET amount = amount - 5000 WHERE account = 'awa';
UPDATE balances SET amount = amount + 5000 WHERE account = 'kofi';
COMMIT;

Until COMMIT has succeeded, nothing is definitively written; on error, ROLLBACK (or the crash itself) cancels everything. If Awa had only 3,000 francs, the CHECK (amount >= 0) constraint of the balances table would make the first UPDATE fail: the whole transaction would be rolled back, and the refused transfer would be written nowhere, neither in events nor in balances.

The rule is checked inside the transaction

The "no negative balance" rule must be checked at append time, inside the same transaction as the writes. Otherwise two simultaneous requests can read the same balance before either writes, and spend the same money twice. Here is the complete code in Python:

import sqlite3
# isolation_level=None: we write BEGIN / COMMIT / ROLLBACK ourselves
conn = sqlite3.connect("ledger.db", isolation_level=None)

def transfer(conn, src, dst, amount):
    if amount <= 0:
        raise ValueError("invalid amount")
    conn.execute("BEGIN IMMEDIATE")   # write lock taken BEFORE reading the balance
    try:
        row = conn.execute("SELECT amount FROM balances WHERE account = ?", (src,)).fetchone()
        if row is None or row[0] < amount:
            conn.execute("ROLLBACK")
            return False              # refused: nothing is written
        conn.execute("INSERT INTO events (kind, account, counterparty, amount) "
                     "VALUES ('TRANSFER', ?, ?, ?)", (src, dst, amount))
        conn.execute("UPDATE balances SET amount = amount - ? WHERE account = ?", (amount, src))
        cur = conn.execute("UPDATE balances SET amount = amount + ? WHERE account = ?", (amount, dst))
        if cur.rowcount != 1:
            raise ValueError("unknown destination account")   # otherwise the money would vanish
        conn.execute("COMMIT")
        return True
    except Exception:
        conn.execute("ROLLBACK")      # cancels all three writes
        raise

BEGIN IMMEDIATE takes SQLite's write lock before the balance is read: a second simultaneous transfer waits, or fails with a database-locked error, instead of reading the same balance at the same time. This isolation question is one of the letters of ACID, mentioned further down for reference.

Python also offers a shortcut: with the sqlite3 module's default mode (a connection opened without isolation_level=None), a with conn: block commits the transaction if the block ends well and rolls it back if an exception escapes (it does not close the connection).

conn = sqlite3.connect("ledger.db")
with conn:    # commits if the block ends well, rolls back if an exception escapes
    conn.execute("INSERT INTO events (kind, account, counterparty, amount) VALUES ('TRANSFER', 'awa', 'kofi', 5000)")
    conn.execute("UPDATE balances SET amount = amount - 5000 WHERE account = 'awa'")
    conn.execute("UPDATE balances SET amount = amount + 5000 WHERE account = 'kofi'")

This shortcut does not check the balance: the rejection rule still has to be written inside the block.

Durability: what is committed survives

Once COMMIT has answered "success", the data survives a power cut or a program crash. Concretely, with the default settings, SQLite first records in a recovery file enough to undo the transaction (the rollback journal keeps the old content of the modified pages) or redo it (the WAL file, write-ahead log, appends the new content), forces that file to reach the disk (an operation called fsync), and only then announces success. On restart, the database reads that file and brings things back to a state where every transaction is either complete or absent.

What do we find after a crash?

The middle row is atomicity; the last is durability.

The cost of durability

Waiting for the disk to confirm takes time: every durable commit is costly. Grouping many writes into one transaction is therefore often much faster than committing each row separately (check it by measurement, as in workshop 102). SQLite lets you tune this trade-off with PRAGMA synchronous; by lowering it you gain speed but accept that a power cut may lose recent commits; depending on the mode chosen, the database itself may even be damaged. The right settings depend on what a loss costs.

The other letters of ACID

These guarantees are often summed up by the acronym ACID: Atomicity, Consistency, Isolation, Durability. Consistency (the database's rules, such as CHECK, stay true) and isolation (simultaneous transactions do not disturb each other) are mentioned here for reference; they are not part of this workshop.

What this does not guarantee

• Durable does not mean backed up. If the disk dies, the database dies with it. To survive that, you need copies elsewhere.
• Atomicity holds inside one database. If the debit is in your operator's database and the credit in another bank's, no SQLite transaction joins them: coordination protocols are needed, which you will meet with distributed systems.
• An atomic transaction can contain a wrong business rule: it guarantees the result is written in full, not that it is right.
• Durability assumes the hardware honours write requests; some disks lie about that.

Recap

Atomicity: a group of writes is applied entirely or not at all. Durability: a successful commit survives a crash, thanks to a recovery file written before the answer. Neither protects against a destroyed disk, a wrong rule, or a log falsified by someone who controls the database.