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
1 maintainer
Metadata
1 maintainer
Release files for kh57 0.1.4
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| kh57-0.1.4.tar.gz | 20.3 kB | Details |
Built distributions (wheels)
Total release size: 7.7 MB
Release files / kh57-0.1.4.tar.gz
| Download URL | kh57-0.1.4.tar.gz |
|---|---|
| Size | 20.3 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
84524ff7d86802bcbe6f32517644d554f7f190204fecaa338fb5f70c8844090e
|
|
BLAKE2b-256 checksum How to use checksums |
b69826f1a3b90a172b9617e46e662d03a7958037a700c4f34c49290280d338d9
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp314-cp314-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl
| Download URL | kh57-0.1.4-cp314-cp314-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl |
|---|---|
| Size | 1.2 MB |
| Tags | CPython 3.14 Linux glibc 2.17+ x86-64 Linux glibc 2.28+ x86-64 |
|
SHA-256 checksum How to use checksums |
7953865f4337d7907590fcc5321a74a4183f7474e15662589cd9c85c01c44e22
|
|
BLAKE2b-256 checksum How to use checksums |
cb2a85816fba6e438a1101a1681af218c19496c351fc4c41874f34679adddca7
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp314-cp314-macosx_11_0_arm64.whl
| Download URL | kh57-0.1.4-cp314-cp314-macosx_11_0_arm64.whl |
|---|---|
| Size | 190.6 kB |
| Tags | CPython 3.14 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
46d95a2562919e7b3a12961659352bc53d55fe8d575055e62772b275a5c41105
|
|
BLAKE2b-256 checksum How to use checksums |
15a2924ae89c7a7e2f5fb111e99eabfca42865df690544c62427564dbe98839a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp314-cp314-macosx_10_15_x86_64.whl
| Download URL | kh57-0.1.4-cp314-cp314-macosx_10_15_x86_64.whl |
|---|---|
| Size | 192.9 kB |
| Tags | CPython 3.14 macOS 10.15+ x86-64 |
|
SHA-256 checksum How to use checksums |
d1d161b54c253cb83a4e75068eb31a46bc2e753a7e492666b772afe5f2a58da7
|
|
BLAKE2b-256 checksum How to use checksums |
cb7cac53d8709938de3b8a56deb7af123739043f50e5ce2e7dc2d3723613ffdb
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp313-cp313-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl
| Download URL | kh57-0.1.4-cp313-cp313-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl |
|---|---|
| Size | 1.2 MB |
| Tags | CPython 3.13 Linux glibc 2.17+ x86-64 Linux glibc 2.28+ x86-64 |
|
SHA-256 checksum How to use checksums |
f0d6a0ca1577dbd2bb3381cf9e84275edb989ff71e8063c4b5ed997a17277da3
|
|
BLAKE2b-256 checksum How to use checksums |
1f1804a3549a96f6b7586d66637f0f8624c080a238b08ef55aaa80e251ea0d4d
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp313-cp313-macosx_11_0_arm64.whl
| Download URL | kh57-0.1.4-cp313-cp313-macosx_11_0_arm64.whl |
|---|---|
| Size | 188.9 kB |
| Tags | CPython 3.13 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
c6dcc560d754fc0461473b710d596dc5264ca57af97c967b8578d22aa142568e
|
|
BLAKE2b-256 checksum How to use checksums |
1364f84287a1d83aa4492f05978cd7a2fabfe8c7ecf45756c7c5841ebe687645
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp313-cp313-macosx_10_14_x86_64.whl
| Download URL | kh57-0.1.4-cp313-cp313-macosx_10_14_x86_64.whl |
|---|---|
| Size | 192.3 kB |
| Tags | CPython 3.13 macOS 10.14+ x86-64 |
|
SHA-256 checksum How to use checksums |
58b83e1f45e9e49bc49997cacfed972e60f8cfcb705151b81762fb16bd9ce50b
|
|
BLAKE2b-256 checksum How to use checksums |
fdaa4a965b6b6e338fc895b8f2b5edfb7e8faea4f341011d81e26fc16e4147a2
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl
| Download URL | kh57-0.1.4-cp312-cp312-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl |
|---|---|
| Size | 1.2 MB |
| Tags | CPython 3.12 Linux glibc 2.17+ x86-64 Linux glibc 2.28+ x86-64 |
|
SHA-256 checksum How to use checksums |
f15e5829a2136c2fb52b6629eeac4b3a205fb7a054171bf3bbefe7d3121479cf
|
|
BLAKE2b-256 checksum How to use checksums |
4f243975eacb57eb86913f0fd6b38282ebce728fd56d4334d9a883256d9efb71
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp312-cp312-macosx_11_0_arm64.whl
| Download URL | kh57-0.1.4-cp312-cp312-macosx_11_0_arm64.whl |
|---|---|
| Size | 190.8 kB |
| Tags | CPython 3.12 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
d8886fcc7a7d519a63e038a7fbcb60cf6a4967ec9ab5ff163f4da73b8c540e61
|
|
BLAKE2b-256 checksum How to use checksums |
f72ffbb78e995335306d775b6a0239b8a066856125aed5a66058425ecbb93866
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp312-cp312-macosx_10_14_x86_64.whl
| Download URL | kh57-0.1.4-cp312-cp312-macosx_10_14_x86_64.whl |
|---|---|
| Size | 194.2 kB |
| Tags | CPython 3.12 macOS 10.14+ x86-64 |
|
SHA-256 checksum How to use checksums |
3f612479b616bfa6f6bce953b745a5b4cb954e3d83c8710ae43ebd427314f045
|
|
BLAKE2b-256 checksum How to use checksums |
04fa0e6ae2ca76b2c5ff020fd0a2ffffea369704d46e0dad2918822ef498125a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp311-cp311-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl
| Download URL | kh57-0.1.4-cp311-cp311-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl |
|---|---|
| Size | 1.2 MB |
| Tags | CPython 3.11 Linux glibc 2.17+ x86-64 Linux glibc 2.28+ x86-64 |
|
SHA-256 checksum How to use checksums |
8ccea7d059016e7733c64c953f7bef68c3c8cf590d0277cc64a0232f7f5cb500
|
|
BLAKE2b-256 checksum How to use checksums |
4ab175649a695bb1f014fa74bbced0e0d8fc5d7f48f56afd6665b371f111852a
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp311-cp311-macosx_11_0_arm64.whl
| Download URL | kh57-0.1.4-cp311-cp311-macosx_11_0_arm64.whl |
|---|---|
| Size | 189.0 kB |
| Tags | CPython 3.11 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
b5e6ba5b687a198a2ac06a23fecc62cec6f644c23fdea76dfe214cf03c5397aa
|
|
BLAKE2b-256 checksum How to use checksums |
47f3cf0659e060b2a02a967c038ef339c5a642581d00131acc92c071010174e3
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp311-cp311-macosx_10_14_x86_64.whl
| Download URL | kh57-0.1.4-cp311-cp311-macosx_10_14_x86_64.whl |
|---|---|
| Size | 190.8 kB |
| Tags | CPython 3.11 macOS 10.14+ x86-64 |
|
SHA-256 checksum How to use checksums |
df5a57ed82927d8ac7561849e7dfb9b1520e502ab82018faffc197fd61fda6fb
|
|
BLAKE2b-256 checksum How to use checksums |
b8302d8fe76a88acc63fc26694c464b1e4e31739d3888fe44b0fb6d035f5e603
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp310-cp310-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl
| Download URL | kh57-0.1.4-cp310-cp310-manylinux2014_x86_64.manylinux_2_17_x86_64.manylinux_2_28_x86_64.whl |
|---|---|
| Size | 1.1 MB |
| Tags | CPython 3.10 Linux glibc 2.17+ x86-64 Linux glibc 2.28+ x86-64 |
|
SHA-256 checksum How to use checksums |
04ea18caff3bc29722628756c105f6d07bdb908a088e356f1957b0940af66a65
|
|
BLAKE2b-256 checksum How to use checksums |
451abe12361977ad96a39765268510c9c290008de3283e5ba4dbe31cb01e048c
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp310-cp310-macosx_11_0_arm64.whl
| Download URL | kh57-0.1.4-cp310-cp310-macosx_11_0_arm64.whl |
|---|---|
| Size | 189.4 kB |
| Tags | CPython 3.10 macOS 11.0+ ARM64 |
|
SHA-256 checksum How to use checksums |
cb8a9cf6dac5b241481abd04dd8590ed51448be638af9aa98565f4151caf7a7c
|
|
BLAKE2b-256 checksum How to use checksums |
7e53a040f719d42a944ebe14c084df6d1893ecfcc8c2ff9a8b7ea391d4b8a959
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency logRelease files / kh57-0.1.4-cp310-cp310-macosx_10_14_x86_64.whl
| Download URL | kh57-0.1.4-cp310-cp310-macosx_10_14_x86_64.whl |
|---|---|
| Size | 191.2 kB |
| Tags | CPython 3.10 macOS 10.14+ x86-64 |
|
SHA-256 checksum How to use checksums |
411835687c3a1b8283735ceb2964b60c7542ade4e3468f441e2912202054a4d7
|
|
BLAKE2b-256 checksum How to use checksums |
4ecbc30971e1cb5b830f8ec5344b8f15a922e815d9a9d2ae94319b7d8bb65b4f
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
Yes |
| Uploaded via |
twine/7.0.0 CPython/3.13.14
|
Provenance
Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.
PyPI Publish Attestation
PyPI verified that this artifact, at this checksum, originated from the publisher listed below.
Signed by GitHub Actions, verified by PyPI on Aug 6, 2026.
Transparency log
