library · how it got fast
the perfect hash.
LSM trees are not supposed to beat B+treesB+treeA sorted tree of pages. Reads walk from the root to a leaf, and pages are changed in place. at reading. Kiban does, because of one thing they have that a B+tree never will: files that never change.
LMDBLMDBA widely used embedded database built on a B+tree and memory-mapped files, known for very fast reads. is the read-speed benchmark for embedded storage. It was also the one engine kiban could not catch. After every optimisation we could find, a cached point read still sat well behind it, and the profile had stopped pointing at anything obvious.
The usual suspects were innocent. Hashing took a fraction of the time. The real cost was somewhere less obvious.
a read begins
An application asks for one record. It is sitting in memory, already cached. Nothing touches the disk. So why does it take any time at all?
memory is the wall
Every stop means following a pointer to somewhere new in memory. We timed it: one uncached memory load costs about 161 ns. Two cost 332 ns. Eight cost 1,317 ns. It is almost perfectly linear, so the cost of a read is how many places it has to visit.
five stops
A sorted file makes the CPU search. Check the Bloom filterBloom filterA compact structure that can say a key is definitely absent, so a read can skip a file., search the index, find the block, search inside it, decode the entry. Each step is sensible. Together they are a long walk for one small record.
a hash, not a search
An SSTSSTSorted string table: an immutable file of sorted keys and values. Once written, it never changes. never changes once written, and that is the opening. If you know every key in advance, you can build a perfect hashMPHFMinimal perfect hash function: maps each of N known keys to its own slot, with no collisions and no empty slots.: every key gets its own slot, with no collisions. The key computes where it lives. Nothing is searched.
reject the impostors
A perfect hash only knows the keys it was built from, so a missing key still lands on some slot. A 16-bit fingerprintfingerprintA few bits of a key's hash, stored beside its slot to reject wrong keys cheaply. beside the slot throws out nearly all of those cheaply.
prove it, then return it
The slot points straight at the record. A full-key compare proves the match, so a hit is never a guess. Three stops, and the value is on its way back.
did it actually work?
An experiment is cheap to believe in, so we tried to kill this one. We built the same data twice and searched one copy with plain binary search. It took 2,851 ns. The hash took 465 ns. The gain was the hash itself, not a side effect of the new layout.
Then it went into the real engine, with snapshots, versions and every safety check. Point reads went from 2.05 µs to 1.15 µs, and throughput from about 480k to 853k reads a second.
Kiban now answers a cached point read 1.3× faster than LMDB in this benchmark. A B+tree cannot make the same move, because its pages change in place and a perfect hash has to be built from a key set that holds still.
what it costs
Nothing here is free, and pretending otherwise would be the fastest way to lose your trust.
- 1.36×slower flushes, because every new file builds its index
- 1.26×slower compaction builds, for the same reason
- +9%more disk, after PH3 cut the index by 61%
- 2×+slower on one 100M read run with a 33 MiB cache, where it halves throughput
That last one is unresolved, and we would rather show it than bury it. It is exactly the kind of thing the next round of work is for.