Metadata-Version: 2.4
Name: kh57
Version: 0.1.2
Summary: Efficient range reservoir sampling from massive sorted key-value datasets.
Author-email: Gor Arakelyan <gorarkln@gmail.com>
Maintainer-email: Gor Arakelyan <gorarkln@gmail.com>
License-Expression: Apache-2.0
Project-URL: Homepage, https://github.com/nustackdev/kh57
Project-URL: Repository, https://github.com/nustackdev/kh57
Project-URL: Issues, https://github.com/nustackdev/kh57/issues
Project-URL: PyPI, https://pypi.org/project/kh57/
Keywords: sampling,reservoir-sampling,range-sampling,key-value,kv,siphash,cython,deterministic,sorted
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Developers
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Programming Language :: Python :: 3.14
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Topic :: Scientific/Engineering
Requires-Python: >=3.12
Description-Content-Type: text/markdown
License-File: LICENSE
Provides-Extra: dev
Requires-Dist: ruff>=0.1.0; extra == "dev"
Requires-Dist: pre-commit>=3.0.0; extra == "dev"
Requires-Dist: mypy>=1.0.0; extra == "dev"
Requires-Dist: cython>=3.0; extra == "dev"
Requires-Dist: setuptools>=68.0; extra == "dev"
Provides-Extra: test
Requires-Dist: pytest>=7.0.0; extra == "test"
Requires-Dist: pytest-cov>=4.0.0; extra == "test"
Requires-Dist: pytest-xdist>=3.0.0; extra == "test"
Requires-Dist: pytest-timeout>=2.1.0; extra == "test"
Requires-Dist: pytest-benchmark>=4.0.0; extra == "test"
Requires-Dist: hypothesis>=6.0.0; extra == "test"
Provides-Extra: all
Requires-Dist: kh57[dev,test]; extra == "all"
Dynamic: license-file

# 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

```bash
pip install kh57
```

Requires Python 3.12+.

## Usage

```python
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

```bash
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
