book with lmdb-style double-buffering

book-lmdb.md

Book: Append-Only Event Log

File Layout

book.log is a single flat file with three regions:

Offset 0       Offset 4096    Offset 8192
+-----------+  +-----------+  +-------+-------+-------+-----+
| Header A  |  | Header B  |  | Deed  | Deed  | Deed  | ... |
| (32 bytes |  | (32 bytes |  |  #1   |  #2   |  #3   |     |
|  + pad)   |  |  + pad)   |  |       |       |       |     |
+-----------+  +-----------+  +-------+-------+-------+-----+

Each header slot is page-aligned at 4096 bytes. Deeds (events) start at byte 8192 and are appended sequentially. A companion meta.bin file (256 bytes, fixed format) stores ship identity, lifecycle, and fake-network flag separately.

The Header (u3_book_head, 32 bytes)

Field	Size	Purpose
mag_w	4B	Magic 0x424f4f4b ("BOOK")
ver_w	4B	Format version (1)
fir_d	8B	Epoch base -- the event number before the first stored event
las_d	8B	Last committed event number
seq_d	8B	Monotonic sequence counter for double-buffer selection
crc_w	4B	CRC32 of all preceding fields

fir_d is write-once. Events stored in the file are numbered fir_d+1 through las_d. For an epoch starting at event 500, fir_d = 500 and the first deed corresponds to event 501.

Deed Format

Each deed on disk is:

+----------+-------------------+----------+
| len_d    |   buffer_data     |  let_d   |
| (8 bytes)|   (len_d bytes)   | (8 bytes)|
+----------+-------------------+----------+

• len_d: size of the opaque buffer
• buffer_data: the serialized event (opaque bytes, minimum 4)
• let_d: echo of len_d, enabling backward scanning from the end of the file

The deed contains no event number -- the position is implicit. The Nth deed in the file is event fir_d + N.

Double-Buffered Headers

This is the core crash-safety mechanism, borrowed from LMDB's design.

The invariant: At all times, at least one of the two header slots contains a valid, self-consistent snapshot of the log state. A reader can always recover by picking the valid header with the higher seq_d.

Why two slots?

A single header write is not atomic with respect to power loss. If you crash mid-write to a single header, you lose your commit marker. With two slots:

• Slot A and Slot B alternate as the "active" (most recent) header
• You only ever write to the inactive slot
• If that write is interrupted, the active slot still has the previous valid state
• Once the write + fsync() completes, the newly-written slot becomes active (it has a higher seq_d)

In-memory tracking

The u3_book handle caches:

• hed_u: the current valid header contents
• act_w: which slot (0=A, 1=B) is currently active
• las_d: last committed event number (mirrors hed_u.las_d after init)
• off_d: the file offset where the next deed should be appended

Startup: selecting the active header

_book_read_head() reads both slots, validates each (magic, version, CRC via _book_head_okay()), and _book_take_head() selects:

1. If both valid: pick the one with higher seq_d
2. If only one valid: use that one
3. If neither valid: fail

This handles the crash-during-header-write case: the interrupted slot will have a bad CRC and be rejected.

Committing: _book_save_head()

_book_save_head() encapsulates the commit protocol:

1. Increment seq_d
2. Recompute crc_w over the header
3. pwrite() the header to the inactive slot (opposite of act_w)
4. c3_sync() (fsync) -- this single syscall makes both the deed data written earlier and the new header durable atomically
5. Swap act_w in memory

The key insight: deed data is written to the file before the header update. Until the fsync completes and the header is durable, the old header remains authoritative. If a crash occurs after deeds are written but before the header fsync, the old header's las_d still points to the previous last event -- the orphaned deed bytes at the end are harmless garbage that recovery will truncate.

u3_book_save() in Detail

This is the main write path.

Phase 1: Validation

if empty log (fir_d == 0 && las_d == 0):
    first event must equal epo_d + 1    <- epoch boundary check
    set fir_d = epo_d                   <- write-once epoch base
else:
    eve_d must equal las_d + 1          <- contiguity check

Rejects gaps and overlaps. The epoch parameter (epo_d) is only meaningful for the very first save to an empty log.

Phase 2: Batch deed write

The function uses scatter-gather I/O (pwritev) for efficiency. Each deed requires 3 iovec entries: [&siz_u[i], buf, &siz_u[i]] -- note that the same siz_u element serves as both the header and trailer since len_d == let_d.

Because pwritev has an IOV_MAX limit (typically 1024), deeds are chunked into groups of 340 (1020 / 3):

allocate siz_u[len_d]         <- one c3_d per event (serves as both len and let)
allocate iov_u[min(len_d*3, 1020)]

for each event:
    reject if size < 4 bytes
    siz_u[i] = size

for each chunk of up to 340 deeds:
    build 3 iovecs per deed:
        [0] -> &siz_u[i], 8 bytes    (length header)
        [1] -> buffer,    N bytes    (event data)
        [2] -> &siz_u[i], 8 bytes    (length trailer)
    pwritev(fd, iovecs, count*3, offset)
    advance offset

A single pwritev call writes an entire chunk of deeds atomically at the kernel level. For the common case (batch of ~1000 events), this is just 3 syscalls: one pwritev, one pwrite (header), one fsync.

Phase 3: Header commit

new_las_d = eve_d + len_d - 1
hed_u.las_d = new_las_d
_book_save_head(txt_u)          <- increment seq, CRC, write inactive slot, fsync, swap
txt_u->las_d = new_las_d       <- update cached state
txt_u->off_d = now_d            <- advance append cursor

The in-memory las_d and off_d are only updated after the fsync succeeds. If _book_save_head() fails, the caller sees c3n and the cached state hasn't advanced, so a retry would attempt to write the same events again.

Startup Recovery

u3_book_init() handles three cases:

New file (st_size == 0): Parse epoch from directory name, write both header slots identically via _book_make_head(), extend file to 8192 bytes.

Corrupt file (st_size < 8192): Reject.

Existing file: Read headers via _book_read_head(), then run a two-phase recovery:

1. _book_scan_back() (fast path): Read the trailing let_d of the last deed from the end of the file, compute where that deed should start, read it forward to verify len_d == let_d. If valid, trust the header's las_d and set the append offset to the file end. This is O(1) -- a single deed validation.

2. _book_scan_fore() (recovery fallback): If the backward scan fails (truncated write, corruption), scan forward from BOOK_DEED_BASE, validating each deed. Stop at the first invalid one. Truncate the file at that point, update the header via _book_save_head() to reflect the recovered event count. This is O(N) in the number of events but only runs after a detected anomaly.

Read Path

Both u3_book_read() and the walk iterator scan forward from BOOK_DEED_BASE, skipping deeds until reaching the target event. This is O(N) to seek -- acceptable because reads are sequential replays, not random lookups. The skip is cheap: read 8 bytes (len_d), advance by len_d + 16.

Summary of the Durability Guarantee

The system guarantees that after u3_book_save() returns c3y:

1. All deed bytes are on disk
2. The header in the now-active slot reflects las_d covering those deeds
3. The CRC on that header is valid

If a crash occurs at any point:

• Before fsync: Old header is still active, old las_d is authoritative. Written-but-uncommitted deed bytes are ignored or truncated by recovery.
• During header pwrite: The other slot still has the previous valid header. The interrupted slot will have a bad CRC and be skipped.
• After fsync: Committed. Both slots may be valid, but the new one has higher seq_d and wins.

Today's benchmarks on MBP '24 with M4 Pro as of cdbcb1fd8c8ef8826595d02b977fb76e7852786a:

Event batch size histogram:

batch size	count
1	2,128,433
2	407,761
3	234,541
4	89,359
5	41,390
6	21,376
7	10,945
8	5,399
9	5,466

Results:

metric	book	lmdb
events written	99981	99981
save calls	6527	6527
event size	128 bytes	128 bytes
total data	1.22 MB	1.22 MB
total time	26.330 s	27.240 s
write speed	379 evt/s	366 evt/s
throughput	0.05 MB/s	0.04 MB/s
latency	2638.0 µs/evt	2729.1 µs/evt