Efficient range reservoir sampling from massive sorted key-value datasets. Deterministic, stable, range-friendly, low read amplification. Cython-accelerated hot inner loop (siphash + encoding) with a small Python surface.
Credits: the algorithm was designed by Karen Hambardzumyan (mahnerak) in 2023.
You have a huge sorted-by-integer-key dataset, potentially trillions of items on disk. You want n uniformly-sampled (key, value) pairs from a sub-range [begin, end) without pulling the whole thing. Naive every-Nth sampling is biased. Random shuffling on disk kills range access. You want both: uniformity and efficient range reads.
kh57 gives you:
- deterministic - same keys, same salt, same sample.
- stable - appending new keys outside the queried range does not change which keys inside get sampled.
- range-friendly - scan only what the query needs.
- low read amplification - total reads stay within ~2x of
n.
Each key is hashed with SipHash-2-4 (uniform 64-bit output). The bit_length of that hash becomes the key's "level": level 63 holds roughly half the keys, level 62 a quarter, and so on down. Every item is stored under a compound sort key (level << 57) | key - top 7 bits are the level id, bottom 57 bits are the original key. This preserves original key order within a level, and level order across levels.
To sample from [begin, end): walk levels from sparsest to densest, range_scan each level's slice, take full levels while they fit the quota, reservoir-sample the boundary level for the remainder, stop. Each level is a deterministic uniform subset of the range, so the union is a uniform sample.
pip install kh57Requires Python 3.12+.
from kh57 import kh57, sample, MemBackend
backend = MemBackend()
for key in range(1_000_000):
encoded = kh57(key).to_bytes(8, "big")
backend.put(encoded, str(key).encode())
# 500 uniform samples from the [100_000, 200_000) range
result = sample(backend, 500, begin=100_000, end=200_000)Any sorted-by-bytes key-value store can be a backend - just implement the Backend protocol (get, put, delete, range_scan). MemBackend is the reference in-memory adapter; RocksDB / LMDB adapters can be added out-of-tree.
kh57(key: int) -> int- encode a 57-bit non-negative key into a 64-bit sort key.recover(h: int) -> tuple[int, int]- inverse, returns(level, key).uniform_hash(key: int) -> int- SipHash-2-4 with the default salt.sample(backend, n, begin=None, end=None, *, rng=None) -> list[tuple[int, bytes]].Backend- Protocol.MemBackend- in-memory reference implementation.
make install # create venv + install with dev,test extras
make build # build cython extensions in-place
make test # run tests
make lint # ruff check
make format # ruff format + fix
make wheels # build manylinux wheels via dockerApache-2.0