Journaling: never forget a trade

How an exchange makes sure that anything it has told a client survives a crash, without making every order wait for a slow disk. Covers fsync, write-ahead logs, group commit, torn writes, checksums, segments and deterministic replay, and how Prayog's S8 journal does each.

1. The problem

The matching engine keeps the order books in memory, because memory is fast. But memory is wiped by a crash, a power cut or a deploy. Two promises must still hold:

Nothing acknowledged is ever lost. If a client was told "filled", the fill exists after a restart.
The market comes back exactly as it was. Same resting orders, same queue positions, same next order id.

Saving the whole book after every order would be far too slow. The trick is to save the inputs, cheaply and in order.

2. A business example: the cashier's register tape

A shop cashier doesn't count the drawer after every sale. The register prints every sale onto a paper tape as it happens. If the drawer is stolen, the owner replays the tape from the morning float and knows exactly what should be there.

The tape is append-only: nobody rubs out a line.
The customer gets the receipt after the line is printed on the tape, never before.
If the printer jams mid-line, that half line is obviously garbage and is crossed out; the sale is re-rung.

Prayog's journal is that tape. The drawer is the in-memory order book.

3. Where bytes really go

Call	What it guarantees
`write()`	The OS has the bytes. A process crash is fine; a power cut or kernel panic loses them.
`fsync()`	Data and all metadata (size, timestamps) are on stable storage.
`fdatasync()` = `force(false)`	Data and the metadata needed to read it back (the file size), but not timestamps. Cheaper; what Prayog uses per batch.
fsync of the directory	A newly created or deleted file name is durable. Needed when a new segment file is created.

On macOS, plain fsync may leave data in the drive's own cache; only F_FULLFSYNC forces it out. Production exchanges run on Linux with enterprise SSDs that have power-loss protection, which makes their cache safe.

4. The write-ahead journal

The rule: write the input down durably before anyone sees its effect. Because Prayog's engine is deterministic (no clock reads, no randomness), its state is a pure function of its inputs:

state = setup + command₁ + command₂ + ... + commandₙ

So the input journal is all the database the engine needs. This style is called event sourcing: you never store the current state, you store what happened, and rebuild state by replaying it. Prayog keeps two logs:

Log	Holds	Used for
`input-*.seg`	Record 0: the engine setup. Then every command at its input sequence.	Recovery and replay. The source of truth.
`events-*.seg`	Every event at its event seq.	Determinism checksums; later, Kafka catch-up. Can be rebuilt from the input log.

5. Group commit: one fsync for many orders

If every order waited for its own fsync, throughput would be capped at 1 / fsync-time: with a 1 ms fsync, 1,000 orders a second. Group commit flushes once for a whole batch. The Disruptor hands each handler an endOfBatch flag when it has caught up with the ring, which is exactly when to flush:

Busy market: 500 orders arrive during one fsync. The next batch is those 500, written together, flushed once.
Quiet market: each batch is a single order. It waits for one flush, no more.

Latency adapts to load automatically; nobody has to tune a timer.

fsync time (ms) orders arriving / s

6. Torn writes and checksums

A crash can stop a write at any byte, leaving the last record half on disk: a torn write. Each Prayog record is framed so that a torn one is always detectable:

[length 4][seq 8][payload: SBE message][crc32c 4]

If the length says the record runs past the end of the file, it's torn.
If the bytes are all there but the CRC32C (a checksum over length, seq and payload) doesn't match, it's torn or damaged.

CRC32C is the Castagnoli variant of CRC-32. Modern CPUs compute it in hardware (an SSE4.2 instruction on x86, an equivalent on ARM), and Java has had java.util.zip.CRC32C since Java 9.

Torn tail vs. corruption. Only the last record can legitimately be torn: it was never flushed, so no client was told about it, and cutting it off loses nothing promised. A bad record before the end means flushed data was lost. That's real corruption, and the safe response is to stop and alert a human, not to guess.

7. Crash it

Append orders, flush whenever you like, then pull the plug. Records in the page cache are lost; the record being written when the plug was pulled may be torn. Then recover.

On disk (durable)

In the page cache (not yet durable)

durablebufferedtorn (bad CRC)acknowledged to client

8. Segments and recovery

One endless file is awkward: you can't archive part of it, and recovery would scan from the start. So the journal is split into segments of at most 64 MiB, named by their first sequence number:

input-00000000000000000000.seg   seq 0 .. 1,480,211
input-00000000000001480212.seg   seq 1,480,212 .. now

Each segment starts with a 16-byte header (magic PRYJ, format version, first seq) so a stray file is never mistaken for a journal. On startup:

Scan every segment in order, checking CRCs and that seqs only go up.
Damage in an earlier segment: refuse to start (corruption).
Damage at the end of the last segment: truncate the file to the last good record.
A last segment shorter than its header (crash while creating it): delete it.
Continue appending after the last good record.

Why truncate rather than just skip? If you write a shorter new record over the torn bytes, the leftover tail bytes stay behind it, and a later read can trip over them. Prayog's first test suite missed this; the test now cuts the file at every possible byte and checks that the file really shrinks.

9. Replay and determinism

Replay feeds the input journal, in order, into a fresh engine on one thread. If the engine is deterministic, it must produce the exact same events. Prayog checks it by computing SHA-256 over the replayed events and comparing with the recorded event log. A match proves the engine has no hidden inputs:

no wall-clock reads (time arrives as ClockTick commands);
no unseeded randomness;
no output that depends on hash-map iteration order or thread timing.

In S8, a planted System.nanoTime() in the trade event was caught, and the check named the first differing event (#49). The same property is what will let a standby engine follow the primary by replaying its journal: both compute identical state from identical input.

10. In Prayog

Class	Job
`Journal`	Interface: `append(seq, bytes)`, `flush()`, `lastSeq()`
`FileJournal`	Segment files, 1 MiB write buffer, CRC32C, fdatasync, recovery on open
`JournalReader`	Reads all segments in order through memory-mapped files
`JournalHandler`	Pipeline stage 1: encodes the command and its events with SBE, flushes on `endOfBatch`
`Replay`, `ReplayCheck`	Rebuild a session from the input journal; compare SHA-256; name the first difference
`make replay-check`	CI job: record 51k commands from 5 threads, replay, compare

11. Questions

Why not just use a database?

A database round trip costs far more than an append to a local file, and it sits on the order path, which Prayog's invariants forbid. Databases themselves are built on exactly this technique: PostgreSQL's WAL, Kafka's log segments, and every LSM-tree store start with an append-only, checksummed, fsynced log.

What about losing the whole machine?

A local journal survives crashes and power cuts, not a dead disk. Production venues replicate the journal to a standby (often by sending the sequenced input stream and having the standby replay it) and acknowledge only once a quorum has it. Prayog's single machine is an MVP choice.

Why write through a buffer instead of memory-mapping the file for writes?

Both are common. Buffered writes plus force() keep failure handling simple (an I/O error is an exception, not a crash on a page fault) and make the flush point explicit. The reader does use memory mapping, because reading mapped segments is fast and simple.