kh57

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.

The problem

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.

How it works

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.

Install

pip install kh57

Requires Python 3.12+.

Usage

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.

Public API

• 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.

Dev

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 docker

License

Apache-2.0