Uniform samples from a trillion sorted rows.
Pull n uniform samples from any range of a huge sorted key-value store. Deterministic, stable, range-friendly. Total reads stay within 2x of n.
The problem.
You have a sorted-by-key dataset. Billions of rows, maybe trillions. You want a uniform random slice of one range, right now, without loading the whole thing.
Every-Nth sampling is biased. A shuffled index destroys range reads. Loading the range first, then sampling, defeats the point. You want both: uniformity and cheap range access.
Niche. If it is your problem, kh57 is built for exactly that shape.
Four properties, free.
One hash per key, one compound sort key per row, one range walk per sample. Four properties fall out for free.
Deterministic
Same keys, same salt, same sample. Reproduce a report a year later with one line of code.
Stable under growth
Append new keys outside the queried range and the sample inside stays identical. No re-sampling to explain.
Range-friendly
Scan only what the query needs. Ask for 500 samples from a 100k slice, touch on the order of 1000 rows.
Any sorted-KV backend
Implement get, put, delete, range_scan. Done. RocksDB, LMDB, or a dict for tests.
Sample from a range.
Hash keys with kh57, put rows in any sorted-KV backend, then ask for n samples over a range.
Swap MemBackend for a RocksDB or LMDB adapter and the sample call does not change. The compound sort key (level, key) is what makes the range walk cheap.
How it works.
Hash each key with SipHash-2-4. The bit length of the hash is the key's level: half the keys land in level 63, a quarter in 62, and so on. Store each row under a compound sort key of (level, key).
To sample from a range: walk levels sparsest to densest. Take a full level while it fits the quota. Reservoir-sample the boundary level for the remainder. Stop.
Each level is a deterministic uniform subset of the range, so their union is a uniform sample. Read amplification stays within roughly 2x of n.
Algorithm by Karen Hambardzumyan (mahnerak), 2023.
Powers Nu.
kh57 is the sampler under nu.kv's sparse int-keyed Refs. Store a growing collection on any sorted-KV backend, then pull uniform samples from any range with one call.
Like what you see?
The project is young. Star it, join the room, watch what we ship next.