Topic: How the checkpoint sequence number flows between the main data store and the WAL to ensure truncate is safe

Date: 2026-05-29

Time: 06:24

Checkpoint Sequence Number Flow: WAL ↔ Data Store

What the WAL Provides

The WAL in write-ahead-log/wal.py exposes two key methods that form a coordination protocol:

1. checkpoint() (line 170) — Increments the internal seqnum, writes an OP_CHECKPOINT record to the log, force-syncs to disk, and returns the checkpoint's sequence number. This return value is the handoff point — it tells the caller "everything up to this number is now marked as checkpointed."

2. truncate(uptoseq) (line ~180) — Accepts a sequence number and physically removes all records with seqnum <= upto_seq. It flushes and fsyncs the current file before scanning, then rewrites each .wal file keeping only records above the cutoff. Files that become empty are deleted entirely.

The intended protocol is:

Data Store                          WAL
    |                                |
    |-- flush state to disk -------->|
    |-- wal.checkpoint() ----------->|  writes OP_CHECKPOINT, returns seq=N
    |<---- seq N --------------------|
    |                                |
    |  (store records N as its       |
    |   last-durable checkpoint)     |
    |                                |
    |-- wal.truncate(N) ------------>|  deletes all records where seq ≤ N
    |                                |

The sequence number is the contract between the two: the data store promises "I have durably applied everything up to N," and the WAL promises "I will only discard records ≤ N."

How the Sequence Number Makes Truncation Safe

The monotonic counter (seqnum, initialized at line 73 and recovered via recoverseq_num() at line 84) guarantees a total ordering. The safety argument is:

• Every mutation gets a unique, increasing seqnum via append() (line 139) or appendbatch() (line 148).
• checkpoint() gets a seq_num after all preceding mutations — so if checkpoint returns N, mutations 1..N-1 are guaranteed to precede it in the log.
• truncate(N) only removes records ≤ N. Any mutations appended after the checkpoint have seq_num > N and are preserved.
• On crash recovery, recoverseqnum() (line 84) scans all WAL files to find the highest surviving seqnum, so the counter never goes backward.

The test at write-ahead-log/test_wal.py:63-70 demonstrates this directly:

wal.append("PUT", "a", "1")   # seq 1
wal.append("PUT", "b", "2")   # seq 2
wal.append("PUT", "c", "3")   # seq 3
wal.truncate(2)                # discard seq ≤ 2
records = wal.replay()
assert len(records) == 1       # only seq 3 survives
assert records[0].key == "c"

What's Missing from the Observations

The observations are insufficient to show the full flow. Specifically:

• No data store class was found — the grep for class.*Store|class.*Database|class.*Engine returned zero matches. We can't see who calls checkpoint() and feeds its return value to truncate().
• The LSM tree call at log-structured-merge-tree/lsm.py:314 uses self.wal.truncate() with no argument, which doesn't match the WAL's truncate(upto_seq) signature. This suggests the LSM either wraps a different WAL implementation or tracks the checkpoint seq internally and passes it differently.
• No code shows the "store durably, then checkpoint, then truncate" three-step sequence in a single caller. The WAL provides the primitives, but the coordination logic that ties them together isn't visible in these observations.

To fully answer the question, you'd need to read the LSM tree's flush/compaction code and whatever storage engine consumes this WAL module.