Durable · Ordered · Embedded · Zero dependencies
Keystone is a durable, ordered key-value store built on a log-structured merge tree, written from scratch in pure Rust with zero dependencies. You can actually watch it work.
No server. No dependencies. Real crash recovery. It lives inside your program as a library and survives a hard kill, so the data you wrote is still there when you open it again.
A hashmap you serialize to disk is a toy. It loses order, loses data on a crash, and rewrites the whole file on every save. Keystone is an ordered, durable store with a write-ahead log and leveled compaction, embedded with no process to run.
Most stores are a black box. Keystone is a glass box. You can see the memtable fill, flush to L0, compaction merge levels, bloom filters skip tables, tombstones get dropped, and the exact path a Get walks to find an answer.
An AI agent needs local memory that persists, stays sorted for range scans, and does not vanish on restart. A developer needs the same thing without standing up a database. Keystone is one file dependency that does exactly that.
A live, from-scratch model of the LSM tree. Put keys, delete them, flush the memtable, run compaction, and trace what a Get actually does. Everything below runs in your browser with no network calls.
Every panel updates live after each action. Here is what each control does and what to watch for.
The playground above is a teaching model. The real engine ships a keystone binary that operates over a directory: an ordered, durable store you drive with one command.
# every command operates over a --path directory $ keystone --path ./data put user:1 alice ok $ keystone --path ./data put user:2 bob ok $ keystone --path ./data del user:1 ok $ keystone --path ./data get user:1 (nil) $ keystone --path ./data get user:2 bob $ keystone --path ./data scan user: # keys in order, by prefix user:2=bob 1 pairs $ keystone --path ./data verify # read every block, check its CRC ok: 3 tables, 3 entries verified
Five ideas do all the work. Written in plain terms, matched to what you just watched in the playground.
Keystone is a log-structured merge tree. Fresh writes live in memory in a sorted memtable. When it fills, it becomes an immutable sorted file on disk called an SSTable at level 0. Compaction merges those files into larger, deeper levels over time.
Each level holds roughly ten times the data of the one above it. New data is cheap to write at the top and slowly settles downward, so writes stay fast and disk stays tidy.
Every write first appends a record to the write-ahead log, then updates the memtable. The write is only acknowledged after the log record is safe, so a crash can never lose an acknowledged write.
Each write also gets a monotonically increasing sequence number. A newer sequence for the same key always wins. That is how updates and deletes work without ever editing data in place.
A Get checks the memtable first, then L0 from newest table to oldest, then L1, L2 and downward. The very first hit wins, because it holds the newest sequence for that key. The search stops there.
If that first hit is a tombstone, the answer is not found. The key was deleted, and older versions further down are ignored. Trace a Get in the playground to see this exact order.
Without help, a Get might open every SSTable on disk. Each table carries a bloom filter, a tiny probabilistic index that answers one question, could this key be here.
A no means definitely absent, so the table is skipped without a disk read. A maybe means open and check. Bloom filters turn a lookup that could touch many files into one that usually touches only the few that could hold the key.
The write-ahead log is the safety net. On reopen, Keystone replays the log into a fresh memtable, rebuilding exactly the state that existed before the crash. Data already flushed to SSTables is durable on its own.
A crash can leave a half-written trailing record. Keystone detects that torn record by its checksum and discards it, then keeps every complete record before it. Every durable write survives.
Compaction merges overlapping SSTables into the next level. Along the way it drops overwritten versions, keeping only the newest sequence per key, so space is reclaimed.
Tombstones are kept while lower levels might still hold the deleted key. At the bottom level there is nothing below to shadow, so the tombstone and the dead key are dropped entirely. Watch the entry counts fall when you compact into the last level.
Keystone is not a new storage idea. It is the readable, zero-dependency version of the design that powers the production LSM stores, small enough to read end to end.
The production LSM engines: battle-tested, richly configurable, and large. Reading one to learn how an LSM tree actually works means wading through years of optimizations. Keystone is the same core design, a memtable, a WAL, immutable SSTables, leveled compaction, and bloom filters, in a single crate you can read in a sitting.
The usual from-scratch store. It loses key order, loses data on a crash, and rewrites the whole file on every change. Keystone keeps keys sorted for range scans, logs every write before it acknowledges, and appends rather than rewriting.
Most Rust embedded stores pull in large dependency trees. Keystone is standard library only, zero external dependencies, with every on-disk structure checksummed and every length bounds-checked, so corrupt bytes surface as a clean error rather than a wrong answer.
A single crate, standard library only. Open a directory as a library, or drive the same engine from the command line.
Db::open loads the manifest and replays the WAL; put, delete, get, and scan over any range; then flush, compact, verify, and close. Tunable Options for memtable size, block size, bloom bits per key, and sync on write.
keystone --path DIR with put, get, del, scan (all or by prefix), compact, stats, verify, and demo.
A differential fuzz against a BTreeMap oracle, crash-recovery tests including a torn WAL tail, and a corruption sweep that bit-flips and truncates every structure. All run under cargo test.
# build, test, and run the gates cargo build cargo test cargo clippy --all-targets -- -D warnings cargo build --release # scale the differential fuzz against the BTreeMap oracle KEYSTONE_FUZZ_OPS=200000 cargo test --release differential