VSTG
VSTG Skips Table Gets
A pure Python, zero dependency bloom filter, built so a check that would otherwise hit your database on every request almost never has to.
The name is also short for vestige, a trace left behind by something that passed through, which is what the underlying bit array actually is.
The problem this solves
Before:
def check_username(request):
username = request.GET["username"]
taken = User.objects.filter(username=username).exists()
return JsonResponse({"available": not taken})
After:
import vstg
def check_username(request):
username = request.GET["username"]
if not vstg.might_contain("usernames", username.encode("utf-8")):
return JsonResponse({"available": True})
taken = User.objects.filter(username=username).exists()
return JsonResponse({"available": not taken})
Every username that was never registered returns without the database being touched. The rare "maybe" still runs the exact same query as before, so correctness never changes, only how often the expensive path is needed.
Install
pip install vstg
No dependencies are ever installed alongside it.
For contributing, clone and install in editable mode instead:
git clone https://github.com/vszlx4/vstg.git
cd vstg
pip install -e '.[dev]'
Usage
from pathlib import Path
import vstg
vstg.init(Path("bloom_state"))
vstg.register("usernames", capacity=10_000_000, error_rate=0.001)
vstg.might_contain("usernames", username.encode("utf-8")) # check
vstg.add("usernames", username.encode("utf-8")) # record
init and register run once, at startup. might_contain and add
run everywhere else, for the life of the process.
Customization
vstg.register(
"usernames",
capacity=10_000_000,
error_rate=0.001,
policy=vstg.PersistPolicy(
checkpoint_interval_seconds=300,
checkpoint_insert_threshold=50_000,
checkpoint_on_shutdown=True,
),
)
vstg.register(
"email_verification_tokens",
capacity=500_000,
error_rate=0.01,
shard_count=8,
)
Every named filter is independent, its own capacity, error rate, and
policy. shard_count, left unset, gives a single checkpoint file. Set
it and a checkpoint only rewrites the shards that actually changed.
Capacity, error rate, and policy are fixed the moment register is
called, for the rest of the process.
The math
A filter is a bit array of length $m$, all bits starting at $0$. Inserting a member sets $k$ of those bits, each position derived by hashing the member. Checking a member reads the same $k$ positions: any bit still $0$ proves the member was never inserted, since insertion only ever sets bits. All $k$ bits set means probably inserted, since an unrelated combination of other members could have set the same positions by coincidence.
Sizing, given an expected item count $n$ (capacity) and a target
false positive probability $p$ (error_rate):
$$ m = -\frac{n \ln p}{(\ln 2)^2} \qquad\qquad k = \frac{m}{n} \ln 2 $$
optimal_size and optimal_hash_count in core.py compute exactly
these two values.
Bit positions, rather than running $k$ separate hash functions, two hashes are computed once and every position derived from them (Kirsch-Mitzenmacher):
$$ i_j = (h_1 + j \cdot h_2) \bmod m, \qquad j = 0, \dots, k-1 $$
Resulting false positive rate, after $n$ insertions into an $m$-bit array with $k$ hash rounds:
$$ p \approx \left(1 - e^{-kn/m}\right)^k $$
The sizing formulas above are exactly this expression solved for the
$m$ and $k$ that minimize it at the requested $n$ and $p$. Exceeding
the configured capacity degrades the real rate past what was
requested, since $n$ in this formula grows while $m$ and $k$ stay
fixed.
Full API
BloomFilter— the bit array,add,might_contain, in memory only.ManagedBloomFilter— aBloomFilterplus automatic checkpointing.ShardedBloomFilter— checkpointing partitioned across shard files.BloomFilterRegistry— the named collectionvstg.registeruses internally.PersistPolicy— checkpoint trigger configuration for all three above.
Contributing
Two space indentation, mypy --strict, no runtime dependencies, a
docstring on every module, class, and function.
git clone https://github.com/vszlx4/vstg.git
cd vstg
pip install -e '.[dev]'
python -m unittest discover -s tests -v
License
MIT, see LICENSE.
Metadata
Release files for vstg 0.1.1
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | Provenance | Actions |
|---|---|---|---|---|
| vstg-0.1.1.tar.gz | 33.1 kB | Without provenance | Details for vstg-0.1.1.tar.gz |
Built distribution (wheel)
| File | Interpreter | ABI | Platform | Actions Reset |
|---|---|---|---|---|
| vstg-0.1.1-py3-none-any.whl | Python 3 | none | any | Details for vstg-0.1.1-py3-none-any.whl |
Total release size: 57.3 kB
Release files / vstg-0.1.1.tar.gz
| Download URL | vstg-0.1.1.tar.gz |
|---|---|
| Size | 33.1 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
3aeeba2ea8c009239e9dd25620bf7e7278277332938f293d1cc24e19dc54f1f2
|
|
BLAKE2b-256 checksum How to use checksums |
2ac16dd7d3dcd4109cc2fb4ce601a3cbdb136631453c49659998b53fc5c548c0
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.2.0 CPython/3.10.8
|
Release files / vstg-0.1.1-py3-none-any.whl
| Download URL | vstg-0.1.1-py3-none-any.whl |
|---|---|
| Size | 24.2 kB |
| Tags | Python 3 |
|
SHA-256 checksum How to use checksums |
cb918aa1af0b49b55642cf3411e8877a3b683c9cf099afdd8bbef9509f59e453
|
|
BLAKE2b-256 checksum How to use checksums |
b86fe724d6b5e80c5892e7345066b48bcff2b426a87f5c540666c86f51d6cd8f
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/6.2.0 CPython/3.10.8
|
Security for vstg 0.1.1
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.
No provenance found
None of the files in this release were uploaded with provenance metadata.
A note on package security
PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.
To learn more about protecting yourself from malicious actors, visit our package security documentation.