Hybrid Storage Engine
A key-value engine in C that keeps values in an append-only log and keys in a B-tree, so rewriting a large value does not churn the index around it.
- Status
- paused
- When
- 2026
- Stack
- c
- Code
- not public yet
What it does
Stores keys and values, and looks them up again. The difference is where the two live: values go to the end of a log file and are never moved; only a small pointer to each value goes into the index.
Why I built it
I kept reading the same argument (B-tree against LSM-tree, read amplification against write amplification) and kept not believing either side, because I had never felt it. Reading about write amplification tells you a large value can be rewritten many times over before it settles. Writing an engine that does it tells you how much that costs and where. Building one was the cheapest way to test the argument myself.
How it works
Two files. Values are appended to a value log and never updated in place; a write is a sequential append plus a pointer. Keys live in a B-tree, and each leaf holds the key and the offset of its value, nothing more. That is the WiscKey idea, with Bitcask’s append-only log underneath it: the index stays small because it carries pointers rather than payloads, so the tree’s pages hold far more keys and the tree stops being rewritten every time a big value changes.
The cost moves somewhere else. A read is now two reads (tree, then log), and the log fills with values nothing points at any more, so it needs a garbage collector that walks it, asks the tree whether each entry is still live, and copies the survivors forward. Most of the design work is in that collector.
What I learned
That the LSM-tree-versus-B-tree question is badly framed. The real axis is whether the index has to move your data when your data changes, and separating the values from the keys is a third answer to that question rather than a point between the two. I also learned how much of RocksDB and LevelDB is compaction policy, which is obvious in hindsight and not obvious from the outside.
Status and what’s next
It works, which is a low bar: it stores and returns keys and values, and it survives a restart. Not benchmarked against anything yet, and the garbage collector is the naive version that holds a lock for far too long. Next: crash-consistency tests before any performance numbers, because I cannot trust speed numbers from an engine that might lose writes.