What a returned write guarantees
A crash-safe, append-only key-value store in C++20.
Fig. 1, one record, little-endian
13 B header
crc324 B
type1 B
klen4 B
vlen4 B
keyvariable
valuevariable
045913
checksummed, [4, end)
Durability costs 624×
284,629 ops/s
None
Always
None
624×
456 ops/sAlways
| Mode | When put() returns | Worst-case loss | ops/s | µs/op |
|---|---|---|---|---|
| None | In the page cache | All not yet flushed by the OS | 284,629 | 3.51 |
| Batched | Flushed every 128 appends | Fewer than 128 records | 34,387 | 29.08 |
| Always | Flushed to media (F_FULLFSYNC on macOS) | Nothing acknowledged | 456 | 2,195.27 |
Apple M2, APFS, 20,000 records, 128 B values. Batched does 75 writes per Always write; one run. Six-figure “durable” writes on a laptop measure the drive’s cache.
Recovery
- 01
Replay from offset 0
Each record is checked for structure and checksum.
- 02
Stop at the first bad record
What follows is a torn tail from a crash mid-append.
- 03
Truncate to the last good offset
A partial write surfaces as absence, never as garbage.
- 04
Verify on every read
The index says where a record is, not that its bytes are still good.
Killed mid-append
A process crash, not a power cut: SIGKILL leaves the page cache intact, so this checks ordering and recovery, not media durability. Torn tails are tested by truncating the log mid-record.
The writer prints an index after every put() that returns, then dies by SIGKILL. The verifier checks every acknowledged write.
One more recovered than acknowledged is correct: it landed before the acknowledgement printed.
$ ./tools/crashtest.sh 5 build
crash test: 5 rounds, SIGKILL mid-append
round 1: PASS acked=248 present=248 missing=0 wrong=0 recovered=249 truncated=0
round 2: PASS acked=344 present=344 missing=0 wrong=0 recovered=345 truncated=0
round 3: PASS acked=339 present=339 missing=0 wrong=0 recovered=340 truncated=0
round 4: PASS acked=261 present=261 missing=0 wrong=0 recovered=262 truncated=0
round 5: PASS acked=211 present=211 missing=0 wrong=0 recovered=212 truncated=0
all rounds passed: no acknowledged write was lostScope
- Single node, single writer, no locking.
- The index lives in memory; recovery replays the whole log. A hint file is next.
- Compaction is stop-the-world, then
rename(2)and an fsync of the directory. - A bad record mid-log is treated as a torn tail: everything after it is dropped.
Build
40 assertions, including a torn tail and a flipped bit. ASan and UBSan run in CI on Linux.
cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build -j4
./build/test_store
./tools/crashtest.sh 10 build
./build/bench 20000 128 128