765,846 Writes/Second Was a Lie: Building a Crash-Safe Key-Value Store With Only Rust's Standard Library

If you've ever written "crash-safe" in a README, you know how cheap those two words are to type. I typed them too, early on, before I understood what I was actually promising.

Here's what took me a while to internalize: a database is either safe when it crashes, or it isn't. There's no "mostly." There's no "worked fine when I tested it." Either the data you told the user was saved is still there when the store reopens, or it's gone, and you lied to them without meaning to.

I built StoneKV for the Zero Dependency Hackathon's Track D — a key-value store, written in Rust, using nothing but the standard library. No third-party crates at all. The brief for Track D was simple to state and hard to satisfy: durability is the whole grade. Not the API. Not the feature list. Just whether it survives being killed mid-operation and comes back correct.

Getting the basic version working — set a key, get a key, delete a key — took a weekend. That part was fun. The part that ate the rest of my time, and taught me the most, was everything that happens when the process gets cut off mid-sentence.

Along the way I ran into three things I didn't expect: a safety check that quietly contradicted itself, a deleted key that could technically come back to life, and a benchmark number that looked incredible and turned out to mean almost nothing.

Why this is harder than it sounds

If you've never built something like this: a key-value store is software that lets you say "save this value under this name" and later "give me back whatever's saved under this name." Sounds trivial.

The hard part isn't storing data while everything's working. The hard part is what happens when your program gets killed — a process crash, forced termination, kill -9, anything that interrupts it halfway through writing something to disk. Did that write happen or not? Can you trust what's on disk afterward? That question is what "crash-safe" actually means, and it's a bigger question than it sounds.

So instead of promising "it's crash-safe" in some vague way, I wrote down one specific, checkable sentence and treated it as the entire spec for the project:

After Store::set() or Store::delete() returns Ok(()), the write has been appended to the write-ahead log and File::sync_all() has completed. On restart, an incomplete final record is detected, the valid prefix is replayed, and the invalid tail is truncated from disk.

I want to be upfront about the scope of that claim, because I think it matters as much as the claim itself: this is a process-crash guarantee. I tested against the process getting killed mid-write, not against sudden power loss or a storage controller lying about what it actually wrote to physical media. sync_all() asks the OS to push data to the filesystem — it doesn't make promises about the hardware underneath that I'm in a position to verify.

Everything below that one sentence — the write-ahead log, the in-memory table, how data gets organized into files, how old files get cleaned up — is the standard design real databases like LevelDB and RocksDB use too. I didn't invent any of it. What took the actual time was finding the cracks in that standard shape: the places where "this should obviously work" turned out to be wrong.

How a write actually gets saved

build the record
      |
      v
append it to the write-ahead log
      |
      v
File::sync_all()
      |
      v
only now, update the in-memory table
      |
      v
occasionally, flush the in-memory table to a permanent file

The rule that makes everything else work: the in-memory copy never gets touched until the write-ahead log entry has been appended and sync_all() has returned. By the time set() tells the caller "done," the fsync has already happened — the durable part occurred before the answer came back, not after.

If the process dies before that answer makes it back to the caller, the caller genuinely doesn't know what happened. But the disk might already have it, and restarting will replay things correctly either way. There's no state where an acknowledged write silently disappears — assuming the implementation is actually correct, which turned out to be a bigger assumption than I expected.

I also hand-wrote the binary format for each record, since I couldn't reach for something like serde:

[op: u8]
[key_len: u32 LE]
[key bytes]
[val_len: u32 LE]
[value bytes]
[crc32: u32 LE]

The checksum covers everything from op through the last value byte — not itself, obviously — and it's checked on every read, not just present for show. It's exactly this detail, the checksum sitting at the end of a record whose length is defined at the start, that led to the first real bug.

The bug where my own rule disagreed with itself

I added a sanity check on the reading side: if a key or value claims to be bigger than 64 megabytes, reject it, on the assumption that a length that big almost certainly means the length field is corrupted, not that someone genuinely has a 64MB key.

if key_len > MAX_FIELD_LEN {
    return Err(StoneError::CorruptRecord {
        reason: format!(
            "declared key length {} exceeds sanity bound {}",
            key_len, MAX_FIELD_LEN
        ),
    });
}

What I didn't notice — and what an outside reviewer caught, not me — is that I'd only put that check on the reading side. I never added the matching check on the writing side.

Which meant, for a while, StoneKV would accept something bigger than 64MB, write it, sync it, tell the caller it succeeded — and then refuse to give it back later, because the same rule that let it in the front door would flag it as corrupted on the way out.

A database that can save your data and then call it corrupted the moment you ask for it back is arguably worse than one that just says "no, that's too big" up front. At least the second one is honest immediately.

The fix was almost embarrassingly simple: enforce the same ceiling on both sides.

pub fn encode(&self) -> Result<Vec<u8>> {
    if self.key.len() > MAX_FIELD_LEN {
        return Err(StoneError::RecordTooLarge {
            field: "key",
            len: self.key.len(),
        });
    }
    // same check applies to the value before it's ever written
}

I added tests that check both directions now — exactly at the limit succeeds, one byte over fails at encode(), not just at decode().

The bigger lesson wasn't about this specific bug. It was about how I was testing my own code. I'd tested "does this reject corrupted data" — it did. I never tested "is the rule that rejects corrupted data the same rule I use when accepting it." Those are two different properties, and I'd only covered one.

A limitation I chose not to hide

The 64MB check only catches wildly implausible corruption — a length field flipped into some absurd multi-gigabyte number. It doesn't catch moderate corruption. If key_len flips from 3 to 1000, and the file happens to run out of bytes before reaching 1000, the decoder produces exactly the same error a genuinely interrupted write would produce.

I didn't fix this, because I don't think it's fixable without changing the file format, and I'd rather say so than pretend otherwise. I wrote a test that locks in the limitation instead of quietly leaving it out:

#[test]
fn moderate_length_corruption_is_still_indistinguishable_from_truncation() {
    // This test documents a real, unresolved limitation, not a fix.
    // It should keep passing exactly as written.
    ...
}

The reason it's structural: the checksum that would tell me "this is corrupted" sits at the end of the record. But if the length field itself is wrong, I don't know how far to read before I can even reach that checksum. I'm stuck trusting a number I have no way to verify yet.

If I rebuilt this from scratch, I'd give every record a small fixed-size header ahead of the payload, with its own independent checksum:

[magic: u32] [version: u8] [key_len: u32] [val_len: u32] [header_crc: u32]
[key bytes] [value bytes] [payload_crc: u32]

That would let recovery verify the lengths themselves before trusting them to slice anything — which is exactly the step the current format skips. Changing the on-disk format at this point felt riskier than it was worth against a codebase that was otherwise stable and well-tested. So instead of a risky rewrite, I did the more honest thing: pin down exactly where the guarantee stops, write a test that proves it, and say so here.

The deleted key that could come back to life

This one looked completely unremarkable at first.

Save a key — it lands in a file on disk, call it generation 1. Delete that key — deletes don't erase anything immediately, they write a "tombstone" marker saying this key is gone, and that tombstone gets its own file, generation 2. Read the key back: the database checks the newest file first, finds the tombstone, and correctly says the key doesn't exist, without even needing generation 1.

Every so often the database runs compaction — merging old files together and discarding anything no longer needed, tombstones included once they have nothing left to shadow. Compacting generations 1 and 2 correctly produces generation 3: a file with nothing in it for that key. That part was right the whole time.

The bug was in what happened right after. Once generation 3 was safely written, the old files needed deleting. I deleted them newest-first, which meant the tombstone (generation 2) got deleted before the original value (generation 1).

If the process crashed in that exact gap — tombstone gone, old value not yet gone — restart would see generation 3 (empty) and generation 1 (still has the value). Reading the key checks generation 3 first, finds nothing, and, following its own normal logic, keeps checking older files instead of stopping. It hits generation 1 and returns the value.

A key that was deleted, and correctly compacted away, comes back. Not because the math was wrong anywhere — it wasn't — but because the order I deleted files in during cleanup wasn't safe against a crash landing in the middle of it.

To be honest about how I found this: I didn't watch it happen live. I found it by tracing through every point a crash could land during compaction and realizing this ordering made the worst case genuinely reachable, not just theoretical. Once I saw the window, I fixed the process and wrote tests to lock the fix in.

This isn't a StoneKV-specific problem — production LSM engines hit the same class of issue and close it the same way. LevelDB durably writes and syncs a version edit in VersionSet::LogAndApply() before it ever removes obsolete files. RocksDB's MANIFEST plays the same role: the durable source of truth for which files are live versus obsolete, checked before anything gets deleted.

I added a small marker file doing the same job:

1. build the new compacted file
2. call sync_all() on the new compacted file
3. write a "compaction in progress" marker and sync_all() it
4. put the new compacted file in its permanent place
5. validate the new file
6. only now, delete the old files it replaced
7. remove the marker

If that marker still exists on restart, that's the signal a compaction got interrupted, and what to do about it depends on what else is on disk:

The idea underneath all five rows is one sentence: never delete old data until its replacement is fully written and validated. I wrote tests for the two scenarios that matter — crashing before the new file exists, and crashing after it exists but before cleanup finishes — to make sure a deleted key can't come back the way it almost did here.

The benchmark number I almost bragged about

I wanted one honest write-throughput number. I got three, and only one of them meant anything.

First run, default temp directory, on my WSL2 setup:

write throughput: 765,846.67 writes per second

That number is fiction, and worth explaining why. On my particular WSL2 setup, /tmp turned out to be mounted as tmpfs — RAM-backed, not disk-backed. I checked this directly instead of assuming it:

$ mount | grep " /tmp "
tmpfs on /tmp type tmpfs (rw,nosuid,nodev,nr_inodes=1048576)

So that first number wasn't measuring the durable-write cost I actually cared about. It was mostly measuring a RAM-backed filesystem.

Second run, pointed at the Windows drive through WSL2's filesystem bridge:

write throughput: 474.78 writes per second

Closer to real, but this path crosses WSL2's bridge between the Linux VM and NTFS, which adds its own overhead unrelated to StoneKV.

Third run, on WSL2's native ext4, confirmed rather than assumed:

$ findmnt -T ~/bench-tmp -o TARGET,SOURCE,FSTYPE,OPTIONS
TARGET SOURCE FSTYPE OPTIONS
/      /dev/sdd ext4 rw,relatime,discard,...

write throughput: 193.61 ops/sec
read throughput: 95,868.79 ops/sec

Same code, same machine, three numbers spanning almost four orders of magnitude. The ext4 number is the cleanest of the three since it avoids both tmpfs and the cross-filesystem bridge — but it's still an environment-specific WSL2 measurement running on a virtual disk (WSL2 backs its Linux filesystem with a virtual ext4 disk, not bare metal), not some universal hardware number. It's the closest I got to what sync_all() actually costs, on this machine, in this environment — not a claim about StoneKV's speed in general.

The roughly 500x gap between the ext4 write and read numbers is consistent with the cost of the durability guarantee becoming visible. Reads never call sync_all() — the newest values can come straight from the memtable, and the OS page cache does a lot of the work for segment reads. Writes pay for a full sync_all() on every acknowledged call, because that's the entire point of the guarantee. I didn't run an experiment isolating sync_all() as the sole cause, but a gap this size lines up with what you'd expect from a synchronous, crash-safe write path.

A number without the environment it was measured in isn't really evidence — it's an optimistic guess with a decimal point attached. That's why the methodology sits right next to the result instead of just the headline number.

What "zero dependencies" actually costs

It's easy to list what you can't use. It's a different thing to feel what each substitution actually costs in hours.

Not using serde meant owning the byte-level format myself — though it's worth being precise about what serde would and wouldn't have given me anyway. serde only defines the Serialize/Deserialize traits, not an actual byte format; getting a real wire representation would still mean pairing it with something like bincode. So the zero-dependency rule didn't remove one library, it removed the whole framing surface — field widths, endianness, where the checksum sits and what it covers — and handed every one of those decisions to me. The encode/decode asymmetry bug is basically what happens when one part of that self-owned surface gets tested and the mirrored part doesn't.

Not using a checksum crate meant writing CRC32 from a known specification and validating it against the canonical IEEE test vector before trusting it with anything. That cost a few extra hours a dependency would have hidden — but I actually know what my checksum covers and what it doesn't.

Not using a temp-file crate meant handling renames and unique paths myself. Worth noting: even a crate like tempfile wouldn't have solved the actual hard problem here — its own docs are explicit that persisting a file doesn't synchronize file contents or the containing directory. What it would have saved is lifecycle convenience, not the crash-safety protocol itself: sync_all() before rename(), a durable marker file, restart recovery checking every intermediate state. That part was always going to be mine to build.

None of this is a complaint. The restriction moved invariants that would normally live inside some mature crate's test suite directly into my own code, where I had to understand and test them myself.

By the numbers

117 tests — 89 unit, 28 integration, 0 failures.

cargo test

Covering checksum corruption, crash-tail recovery, both the obvious and the moderate length-corruption cases above, both interrupted-compaction scenarios, deleted-key resurrection, and concurrent access from multiple threads.

Two clean back-to-back builds on the same machine and toolchain, byte-identical.

cargo clean && cargo build --release && sha256sum target/release/stone

Both builds produced the same file: a7be952baf90dcda665df20f7e8a950530210e01dfd10dcd37a1a556b6c3edce.

14 documented zero-dependency substitutions and hand-built components — covering serialization, CRC32, CLI parsing, error handling, temporary-file handling, unique IDs, and the storage-engine primitives themselves — each with what it replaced, why, and what it cost.

Zero third-party runtime dependencies.

cargo tree -e normal

Prints exactly one line: the project itself.

What I'd do differently next time

Write the guarantee down as one sentence before writing the engine. Everything here exists to keep that sentence true, and having it written down early meant every decision had an obvious test attached: does this preserve the sentence, or quietly weaken it?

Test whether your own safety checks agree with each other, not just whether they exist. The encode/decode bug wasn't a missing check — it was a check that existed in only one of two places that needed to agree, and I'd tested that the check worked without testing that both sides said the same thing.

Something can be logically correct and still unsafe against a crash. The compaction math was never wrong. What was missing was making the file-deletion order safe against being interrupted — a genuinely different property from correctness, and getting one right doesn't get you the other for free.

If a limitation is structural, say so and prove the boundary instead of hiding it. The length-corruption gap isn't something I ran out of time for — it's a property of a length-prefixed format with the checksum at the end. I'd rather write the test that shows exactly where it breaks than pretend a bigger sanity bound solved it.

Never trust a benchmark number until you've named the filesystem underneath it. A folder path tells you nothing about what's actually backing it, and the only way to know is to check directly instead of assuming.

Repo: StoneKV on GitHub — full source, all 117 tests, the decision history. Builds with cargo build --release, no third-party dependency fetch, and Cargo.toml's dependency list stays empty the whole time.

Demo: StoneKV crash-recovery demo — the write-ahead-log and compaction recovery tests, running live.

Built for the Zero Dependency Hackathon, run by Hackathon Raptors.

One more time, since it's the only sentence that actually matters: StoneKV doesn't tell you a write succeeded and hope durability catches up later. sync_all() completes before the caller ever gets the success response. Everything else here is either proof of that sentence, or an honest account of exactly where it stops holding.