An embeddable LSM-tree storage engine in Rust (zero unsafe) — CRC-framed
write-ahead log with group commit, memtable with atomic freeze/flush,
block-based SSTables with bloom filters and sparse indexes, size-tiered
compaction, crash recovery. Its headline product is not speed but evidence: a
fault-injecting storage layer that simulates power loss at every write and
fsync boundary and shows the engine recovers 330 deterministic crash
points (4 deterministic seeds spanning 3 tear modes × 2 durable modes = 2,640 executions) plus 160
property-based crash schedules with zero acknowledged-write loss — and it is
benchmarked honestly against sled,
publishing the comparisons sled wins.
Storage engines are easy to make fast and hard to make crash-safe. Anyone can
buffer writes and quote a big throughput number; the interesting engineering is
guaranteeing that a put which returned is still there after the power is
cut mid-fsync. So the product of this repository is reproducible evidence, and the design
is harness-first: the fault-injection layer — a deterministic, seeded
page-cache simulator (SimFs) that drops, tears, and bit-flips unsynced bytes
on crash() — was built and reviewed before the engine it judges, and every
component grew up running under it. That is what lets
BUGS_FOUND.md fill organically instead of being decorated after
the fact.
Every number in this README traces to a committed artifact (benchmarks/RESULTS.md or a named test); all were produced on the disclosed build host. Nothing here is hand-tuned or aspirational.
WRITE PATH READ PATH
────────── ─────────
put(k, v) get(k)
│ │
▼ ▼
┌──────────┐ ack per durability mode ┌──────────────────┐
│ WAL │ Always = fsync per commit │ active memtable │
│ CRC- │ GroupCommit = one fsync / batch └────────┬─────────┘
│ framed │ OsBuffered = no durability guarantee miss │
└────┬─────┘ ▼
│ append ┌──────────────────┐
▼ │ frozen memtables │
┌──────────────┐ freeze at size threshold └────────┬─────────┘
│ active │─────────────┐ miss │
│ memtable │ ▼ ▼
│ (BTreeMap) │ ┌──────────────┐ ┌──────────────────────┐
└──────────────┘ │ frozen (Arc) │ flush │ SSTable tiers, │
└──────┬────────┘ ───────► │ newest-first: │
│ │ tier 0 [t][t][t] │
▼ │ tier 1 [ merged ] │
┌──────────────┐ │ ... │
│ SSTable │ └───────────┬───────────┘
│ (tier 0) │ │ per table:
└──────┬────────┘ ┌───────▼────────┐
│ manifest version bump │ bloom filter │ absent? skip
▼ (tmp+fsync+rename+dir-fsync) ├────────────────┤
┌──────────────┐ │ sparse index │ locate block
│ size-tiered │ ≥ fanout tables ├────────────────┤
│ compaction │ merge tier t → t+1 │ 4 KiB block │ in-block scan
└──────────────┘ └────────────────┘
A put is durable (per the configured mode) the instant it returns; the
memtable insert, the size-triggered freeze, the flush to a tier-0 SSTable, and
the manifest version bump all happen behind that contract. A get walks the
active memtable, the frozen memtables, then the SSTable tiers newest-first — the
table's key range and its bloom filter gate each probe, and a sparse index locates
the one 4 KiB block that could hold the key. (scan is correct but takes none of
those shortcuts — see Limitations.) Full walkthrough in
DESIGN_NOTES.md; on-disk byte layouts in FORMAT.md.
accretion-db is a library crate — embed it, no server, no daemon:
use accretion_db::{Db, Options, Durability};
fn main() -> Result<(), accretion_db::DbError> {
// GroupCommit: concurrent writers share one fsync per batch (the headline mode).
let db = Db::open("/tmp/mydb", Options {
durability: Durability::GroupCommit,
..Default::default()
})?;
db.put(b"key", b"value")?; // returns only once durable
assert_eq!(db.get(b"key")?, Some(b"value".to_vec()));
db.delete(b"key")?;
assert_eq!(db.get(b"key")?, None);
// Range scan yields sorted (key, value) pairs, tombstone-aware:
for (k, v) in db.scan(b"a".to_vec()..b"z".to_vec())? {
println!("{:?} => {:?}", k, v);
}
Ok(())
}Run the crash sweep and the benchmarks yourself:
# Headline guarantee: every acked write survives every crash point
# (all 8 crash tests; well under a second on the disclosed host).
cargo test --release --test crash
# Distinct-crash-point count (prints N=330 …):
cargo test --release --test crash reports_crash_point_count -- --nocapture
# Full benchmark matrix (regenerates benchmarks/raw/*, ~30 min):
cargo build --release --features bench-sled --bins
bash scripts/run_matrix.sh
The story starts with the disk. scripts/fsync_probe.rs measures this host's
4 KiB durability calls: fdatasync p50 = 878 µs (what the WAL commit path
pays), with the heavier directory fsync behind rename durability at ~1.97 ms. At
878 µs a bare fsync-per-write engine is capped at ≈ 1,140 durable
writes/sec regardless of engine quality — the disk, not the code, is the
ceiling. Group commit's whole job is to amortize one fdatasync across many
queued writers.
fill-random, 16-byte keys / 100-byte values, closed-loop driver, WAL-commit-bound
regime (64 MiB memtable, so the fill never flushes — this isolates the commit
pipeline). Median of 5 runs:
| mode | c=1 | c=8 | c=64 | write p50 @ c=64 |
|---|---|---|---|---|
Always (fsync per put) |
369 | 348 | 276 | 3.7 ms |
GroupCommit (batched fsync) |
274 | 1,093 | 8,082 | 7.5 ms |
OsBuffered (no durability guarantee) |
60,329 | 38,232 | 34,361 | 17 µs |
Group commit buys a ~29× multiplier (8,082 / 276 at c=64) by trading
same-concurrency p50 latency (3.7 ms → 7.5 ms) for batched fsync amortization —
exactly the throughput-for-latency trade the math predicts. In this no-flush
workload, each Always commit issues one WAL sync_data; its 3.7 ms c=64 p50
also includes append/file-open, locking, and scheduler overhead. The WAL-bound
comparison therefore attributes the difference to one durability barrier per
Always write versus one shared barrier per group, not to three fsyncs. Full
per-cell numbers, commands, and the raw outputs are in
RESULTS.md §3.
Honest full-engine caveat. The ~29× is the commit-pipeline number. Once a
workload crosses flush + compaction boundaries, synchronous compaction under
the write lock (a deliberate simplicity choice — see below) dominates and
collapses GroupCommit to ~623 writes/sec with multi-second stall outliers. That
figure is published side-by-side in RESULTS.md §3b, not hidden: the WAL-bound
number proves the commit-pipeline design; the full-engine number is gated by the
deliberately-simple compaction path.
Point reads (50k keys, c=8, OsBuffered, post-flush so they hit SSTables; warm
page cache — the host has no root to drop caches, disclosed in RESULTS.md §4):
615,188 reads/sec, p50 11.7 µs, p99 21.7 µs. Bloom filter FPR: 0.77 %
measured vs 0.82 % theoretical (10 bits/key, k=7, n=10,000 keys, 100,000
disjoint probes).
The invariant, enforced everywhere: zero acknowledged-write loss. Every
put/delete that returned under a durable mode (Always / GroupCommit)
is present with its exact value after recovery; an in-flight op is either fully
applied or fully absent; there are no phantom keys, acked deletes hold, the
manifest references only checksum-valid files that exist, and the WAL tail
truncates cleanly. Three independent layers test it:
| layer | what it does | count |
|---|---|---|
| Exhaustive deterministic sweep | Run a canonical mixed workload once to count N mutating storage ops; for each i in 1..=N, fresh SimFs, crash after op i (× 4 fixed seeds spanning 3 possible tear modes × 2 durable modes), reopen, verify against the acked-prefix model. |
330 points → 2,640 executions |
| Property-based schedules | proptest generates random op sequences × crash indices × durability modes, shrinking failures to minimal counterexamples; 3 named fixed-seed regressions pin the highest-risk shapes, and each one sweeps every crash point of its own workload × 4 seeds × 2 modes rather than running a single case. | 160 schedules + 3 regression sweeps |
| Real process kill | accretion-crashtest writes to a real RealFs DB in Always, prints each key only once its put returns durable; the parent sends SIGKILL, reopens against real filesystem calls, and confirms every acknowledged key is present with its exact value. The repeated test kills and reopens the same directory three times and, after the last round, re-verifies every key acked in any round — so recovery must hold across successive abrupt deaths. The kernel and page cache remain alive, so this tests abrupt process death, not hardware power loss or torn writes. |
1 single kill + 3 repeated rounds on one directory; ≥8 acked writes required per round; exact-value check; key counts vary with timing |
Modelled: loss of any byte range written but not yet sync_filed; a torn
last unsynced append (dropped, truncated at a random byte boundary, or bit-flipped
inside the unsynced region — drives the CRC path); a volatile
rename/create/delete that reverts to the last sync_dir-durable directory image;
deterministic, seeded replay so a failing schedule reproduces byte-for-byte.
Not modelled (honest boundaries): cross-file sector reordering, sub-byte partial-sector atomicity, or media decay of already-durable data. The engine is only ever permitted to depend on the guarantees this model makes.
See BUGS_FOUND.md for the organic crash-bug journal — including
a tombstone-resurrection bug the BTreeMap-model property test shrank to a
four-op counterexample, a SimFs rename-durability fidelity fix, a group-commit
locking bug the throughput harness surfaced, an out-of-order WAL recovery bug,
and inode-generation/tear-order defects found by independent review. A labelled
positive control deletes one fsync to show the sweep actually catches loss.
sled 0.34 runs behind the same KvBench trait, same driver, same histogram, at
matched durability settings documented in src/bin/accretion-bench/kv.rs.
sled is a mature beta engine with a different (lock-free Bw-tree/log)
architecture; this is context, not a contest — and on this host sled wins
every matched comparison, reported plainly:
| comparison | accretion-db | sled | winner |
|---|---|---|---|
Durable (acc Always vs sled insert+flush), fill-random 3k, c=1 |
364 w/s | 1,070 w/s | sled (2.9×) |
Buffered (acc OsBuffered vs sled no-flush), fill-random 50k, c=1 |
84,937 w/s | 217,719 w/s | sled (2.6×) |
| Buffered point reads, 50k keys, c=8, warm page cache | 615,188 r/s | 3,686,026 r/s | sled (6×) |
Why, honestly: sled's insert+flush() measures 926 µs p50 per write — within
~5 % of this host's 878 µs sync_data p50, i.e. essentially just the one barrier —
while accretion's Always measures 2.73 ms p50: the same single sync_data plus
WAL append/file-open work and engine locking around each write. sled's lock-free
architecture and years of tuning also beat this teaching-scale engine on reads.
accretion-db's
answer to the fsync wall is GroupCommit, which sled has no API for — so it is
reported as accretion's own headline mode against its own Always baseline,
never dressed up as a sled win. Methodology, matched configs, and the full table
are in RESULTS.md §6.
A single logical writer (a mutex on the write path) totally orders every
durable manifest install; readers take an RwLock memtable snapshot plus a
pinned Arc<Version>. A reader holding an old Arc<Version> stays correct while
compaction replaces files underneath it, because a table file is deleted only
once no live Version references it (tracked by Arc strong count). Flush and
compaction run on exactly one path — synchronously, on the writer's thread.
That single-writer, totally-ordered history is why the crash analysis is tractable: the exhaustive sweep and proptest schedules reason about one linear sequence of manifest installs. Moving compaction to a background thread would demand turning the manifest swap into a transactional compare-and-apply and re-establishing the crash invariant against interleaved installs — real work, deliberately deferred. The defense is written up in DESIGN_NOTES.md → Concurrency model.
Stated plainly, each on purpose:
- Synchronous compaction. When a tier crosses its fanout, the triggering write absorbs the full merge latency (the multi-second stalls in RESULTS.md §3b). Bought simple, auditable crash reasoning; background compaction is future work.
- Size-tiered only. Lower write amplification and simpler invariants, at the cost of higher space/read amplification — the honest tiered-vs-leveled tradeoff (DESIGN_NOTES.md). No leveled compaction.
- No transactions, MVCC, or column families. A single-key durable KV store
with range scans; no multi-key atomicity beyond a single
put. - No block cache / compression /
mmap/io_uring. Leans on the OS page cache by design; the point is the crash evidence, not squeezing the I/O path. scandoes not seek the sparse index.getuses the bloom filter and sparse index to touch one 4 KiB block, butscandecodes every block of every table and filters afterwards, so a narrow range costs the same as a full one (RESULTS.md §4). Correct results, unoptimized cost; index-seeking scans are future work.- Single-host, single-process. No network protocol, no multi-writer coordination. All benchmark numbers are single-host; the read numbers are warm-page-cache (no root to drop caches on the build host).
- DESIGN_NOTES.md — the rationale behind every non-obvious choice: write/read path, group-commit math, torn-tail truncation, bloom sizing, tiered-vs-leveled, manifest atomicity, the concurrency model, and the crash evidence.
- FORMAT.md — byte-level on-disk layout of the WAL, SSTable, and manifest.
- BUGS_FOUND.md — the organic crash-bug journal.
- benchmarks/RESULTS.md — host + fsync disclosure, every per-cell command, raw outputs, and the sled comparison.
MIT — see LICENSE. © Ivan Wang
(59074138+iwang-1@users.noreply.github.com).