Bloomsieve

Stop sending unnecessary membership checks to Redis. Bloomsieve is a fast, persistent, mmap-backed Bloom filter for Python. On its own it is a zero-dependency Bloom filter you can share between processes. In front of RedisBloom it answers "definitely absent" locally, so only the possible positives cross the network, and it keeps the local filters on all your servers in sync through Redis.

                         Application
                              │
                              ▼
                     ┌─────────────────┐
                     │    Bloomsieve   │
                     │   local mmap    │
                     └────────┬────────┘
                              │
                   ┌──────────┴──────────┐
                   │                     │
             definitely absent      possibly present
                   │                     │
                   ▼                     ▼
                 return               RedisBloom
                locally              verification

On a 99%-negative workload this removes ~99% of Redis membership requests (benchmarks).

Contents

• Installation
• Quick start
• Use cases
• Examples
• How it works
• Choosing capacity and error rate
• Benchmarks
• API reference
• Limitations
• Upgrading from 0.2
• Development

Installation

The core filter has no runtime dependencies:

pip install bloomsieve

The RedisBloom integration is an optional extra:

pip install "bloomsieve[redis]"

Redis needs the Bloom filter commands (BF.*) and, for multi-server sync, Redis 6.2 or newer. Redis 8 includes the Bloom commands; for older versions use Redis Stack or the RedisBloom module.

Quick start

from bloomsieve import BloomFilter

bloom = BloomFilter(capacity=1_000_000, error_rate=0.001)

bloom.add("user:123")
"user:123" in bloom  # True  -> possibly present
"user:999" in bloom  # False -> definitely never added

capacity is how many items you expect and error_rate the false-positive probability you accept. A False answer is always correct; a True answer is wrong with probability about error_rate.

Use cases

1. In-memory set membership and de-duplication

add() returns True only for items it has not seen, so one call checks and records an item. This is handy for de-duplicating streams, crawler frontiers or event IDs in a fraction of a set's memory.

from bloomsieve import BloomFilter

seen = BloomFilter(capacity=10_000_000, error_rate=0.001)  # ~17 MiB

for event in stream:
    if seen.add(event.id):  # True -> first time
        process(event)

seen.add_many(ids)  # batch insert, returns how many were new

2. A persistent filter that survives restarts

Pass filepath and the filter lives in a memory-mapped file. Reopening it later (or from another process) restores every bit. The stored configuration wins, so reopening with different arguments can never corrupt it.

from bloomsieve import BloomFilter

with BloomFilter(capacity=1_000_000, error_rate=0.001, filepath="/var/lib/app/seen.bloom") as bloom:
    bloom.add("session:abc")
    bloom.flush()  # durable on disk now (close() also flushes)

# next run
with BloomFilter(capacity=1_000_000, error_rate=0.001, filepath="/var/lib/app/seen.bloom") as bloom:
    "session:abc" in bloom  # True

A damaged file raises BloomFilterFileError instead of silently returning wrong answers.

3. One filter shared by many processes

Several processes (gunicorn workers, multiprocessing pools, cron jobs) can open the same file. Adds from one are immediately visible to all, and writes take an exclusive file lock, so concurrent adds never lose bits. The file lock is POSIX only; on Windows use one writer process per file.

# in every worker process
bloom = BloomFilter(capacity=1_000_000, error_rate=0.001, filepath="/dev/shm/shared.bloom")
bloom.add(f"job:{job_id}")

4. A local pre-filter in front of RedisBloom

BloomFilterService keeps a local mirror of each Redis filter. Negative lookups are answered locally with no network round trip; possible positives are verified in Redis, so answers stay exact for anything RedisBloom would say.

import redis
from bloomsieve import BloomFilterService

svc = BloomFilterService(
    redis_client=redis.Redis(host="redis.internal"),
    capacity=1_000_000,
    error_rate=0.001,
    use_mmap=True,  # enable the local pre-filter
    mmap_dir="/var/lib/bloomsieve",
)

svc.create_filter("active_tokens")  # every server can call this at startup
svc.add("active_tokens", "tok_abc")

svc.exists("active_tokens", "tok_xyz")  # False - answered locally, no network
svc.exists("active_tokens", "tok_abc")  # True  - verified in Redis

5. Many servers, each with its own local filter

Run the same code on every application server; each keeps its mirror on its own disk. Every write, on any server, is also recorded in a small per-filter change log in Redis, and each mirror catches up on that log before it answers "absent". That makes a local "absent" correct for items added on any server, up to a bounded delay:

svc = BloomFilterService(
    redis_client=redis.Redis(host="redis.internal"),
    use_mmap=True,
    mmap_dir="/var/lib/bloomsieve",
    sync_interval=0.5,  # a local "absent" is at most 0.5 s behind other servers (default)
)

Guarantee: exists() only answers False locally if the mirror caught up with Redis less than sync_interval seconds ago. So it can only miss an item added on another server within the last sync_interval seconds. Items added through the same mirror are visible at once. If a mirror cannot catch up (Redis down, filter not replicated), it stops answering negatives and every lookup goes to Redis. sync_interval=0 makes every lookup check Redis first: always exact, but no faster than plain Redis.

How it stays cheap: catching up costs one round trip per sync_interval, not one per lookup. Mirrors take turns compacting the log into a bit snapshot, so the log stays small, and a server that starts later downloads the snapshot plus the recent log instead of every item. Writes cost a little more (one Lua script instead of a plain BF.ADD, about 2× the latency on localhost).

Rules: write through BloomFilterService on every server (with or without use_mmap). Items written to the Redis filter some other way are invisible to mirrors. Don't let Redis evict the bloomsieve:* keys. If no server uses use_mmap, pass replicate=False to skip the change log.

6. Batch writes and lookups

svc.add_many("active_tokens", tokens)  # BF.MADD, one round trip
svc.exists_many("active_tokens", ["a", "b", "c"])  # [True, False, False]

exists_many answers local negatives without Redis and sends the rest in a single BF.MEXISTS round trip.

7. Rebuilding and rotating without downtime

Bloom filters cannot delete items, and their error rate rises past capacity. Rebuild periodically from your source of truth into a temporary filter, then swap it in while the live filter keeps serving reads:

if svc.load_ratio("active_users") > 0.8 and svc.acquire_lock("rebuild:active_users", ttl=300):
    try:
        if svc.rebuild("active_users:next", load_users_from_db(), capacity=2_000_000):
            svc.swap("active_users:next", "active_users")
    finally:
        svc.release_lock("rebuild:active_users")

Only one server runs the rebuild. The others see the new generation on their next sync and load its snapshot.

8. Adopting a Redis filter that already has data

A filter created outside Bloomsieve (or by 0.2) has no change log, so a mirror cannot know what it holds. Lookups stay correct, but every one goes to Redis (a warning is logged once). Rebuild it once from your source of truth to bring it under replication:

svc.rebuild("legacy_filter", all_items)

Examples

Runnable scripts in examples/. The Redis ones need a server (BLOOMSIEVE_REDIS_URL, default redis://localhost:6379/0) and skip cleanly without one.

How it works

• Hashing: one SHA-256 digest per item, expanded to k bit positions with Kirsch-Mitzenmacher double hashing. str items are hashed as UTF-8, so "a" and b"a" are the same item.
• Storage: a 16-byte header (m, k) followed by the bit array, in memory or in a memory-mapped file. New files are created atomically, so concurrent starters never clobber each other.
• Concurrency: writes are serialised by a thread lock plus an flock on the file; lookups are lock-free.
• Replication: each replicated filter has two extra Redis keys: a stream bloomsieve:{<name>}:log with the items written since the last snapshot, and a hash bloomsieve:{<name>}:snap with a generation id and a compacted bit array. Writes go to the log and the filter in one atomic Lua script. Mirrors replay the log, and compact it once it grows. A rebuild starts a new generation, which every mirror detects and reloads. The keys share the filter's Redis Cluster hash slot.
• Trust: the service only answers negatives locally from a mirror that is provably complete and fresh. Its state (generation, log position) is saved in a small <file>.synced marker tied to a random id stored in the mirror file. A restart resumes from where it left off, and a recreated file is never trusted by accident.

Full design, on-disk format, failure modes and consistency model: docs/architecture.md.

Choosing capacity and error rate

Memory is m / 8 bytes, fixed up front:

get_optimal_m_k(capacity, error_rate) returns (m, k) without allocating anything. Going past capacity does not break the filter; its false-positive rate gradually rises, which is the signal to rebuild with a larger capacity.

Benchmarks

benchmarks/benchmark_redis.py, 100 000 items, 100 000 lookups, error_rate=0.001, Redis 8.6 on localhost (so the network is as fast as it gets), Python 3.9, Intel i7-14650HX:

With a simulated 2 ms round trip (benchmark_end_to_end.py, 90% negative), total time drops from 44.8 s to 5.4 s. The further away Redis is, the bigger the win.

Local operations (same machine): lookup of an absent item ~1.4 µs, lookup of a present item ~3.0 µs, add ~3.9 µs (in memory) / ~4.8 µs (file-backed, including the file lock), add_many ~3.4 µs per item. Through the service on localhost Redis: a local negative ~2.1 µs, add ~77 µs with replication (~39 µs without).

Results depend on hardware and network; run the scripts to measure your own environment. Methodology: docs/benchmarks.md.

API reference

BloomFilter(capacity, error_rate, filepath=None)

Items are str or bytes; anything else raises TypeError. Operations on a closed filter raise RuntimeError. A corrupt file raises BloomFilterFileError (a ValueError subclass).

BloomFilterService(redis_client, capacity=1_000_000, error_rate=0.001, expansion=2, use_mmap=False, mmap_dir=None, replicate=True, sync_interval=0.5, max_log_entries=1_000_000)

replicate turns on the change log that keeps mirrors on different servers in sync (it needs a client with the default decode_responses=False). sync_interval bounds how stale a local negative can be. max_log_entries is a safety cap: if the log ever reaches it (no mirror is compacting), replication of that filter switches off and mirrors fall back to Redis until it is rebuilt. Keep it well above write rate × sync_interval.

When Redis is unreachable, writes return False and lookups return a conservative True, both with a logged warning. Bloomsieve logs through the standard logging module (bloomsieve.core, bloomsieve.redis_service).

Limitations

• Bloom filters cannot delete items; refresh with rebuild() + swap().
• Past capacity the false-positive rate rises; it does not fail.
• A local "absent" can miss an item added on another server within the last sync_interval seconds (guarantee).
• Writes must go through BloomFilterService; items added to Redis some other way are invisible to mirrors.
• With replicate=False, every writer must share the mirror file (one host or a shared volume).
• After a machine crash, unflushed mirror writes can be lost; rebuild() after an unclean shutdown.
• Cross-process write locking is POSIX only (Linux, macOS).
• Service locks are advisory (token-checked, but not fenced).
• Python 3.9–3.13.

Upgrading from 0.2

• Files are compatible: the on-disk format and hashing are unchanged.
• Multi-server sync is on by default (replicate=True). In 0.2 a mirror only knew about its own host's writes, and any existing mirror file, or any mirror after a single add, was trusted. That produced wrong "absent" answers. In 0.3, filters from 0.2 start unreplicated: lookups stay correct but go to Redis until you run rebuild(name, items) once. A warning is logged once per filter.
• Writes through the service now run a Lua script (Redis 6.2+), and replicated filters use two extra keys per filter (bloomsieve:{<name>}:log / :snap).
• Mirror files for names containing characters outside [A-Za-z0-9_.-] get a hash suffix, so they start as new (untrusted) files.
• rebuild uses BF.MADD and skips only None items ("" is now added).
• release_lock only releases locks acquired by the same service instance.
• error_rate values needing more than 128 hash functions now raise ValueError.

Full list: CHANGELOG.md.

Development

git clone https://github.com/deepak7448/bloomsieve.git
cd bloomsieve
python -m venv .venv && source .venv/bin/activate
pip install -e ".[dev,redis]"

ruff check . && ruff format --check .
pytest                                                # unit tests, no Redis needed
BLOOMSIEVE_REDIS_URL=redis://localhost:6379/0 pytest  # plus the live Redis suite

Releasing: bump __version__ in src/bloomsieve/__init__.py, update CHANGELOG.md, commit and push, then publish a GitHub release with tag v<version> (e.g. v0.3.0). The Publish to PyPI workflow (.github/workflows/publish.yml) checks the tag against __version__, runs lint and unit tests, builds once, and uploads with Trusted Publishing and signed attestations, so every file shows its provenance on PyPI. A release marked pre-release goes to TestPyPI. Tests run separately in ci.yml on every push and pull request. ./build.sh runs the same checks locally; manual uploads carry no provenance, so publish releases from GitHub.

Issues and pull requests are welcome. Please run the linter and the full test suite (including the live Redis suite if you can) before submitting.

License

MIT. See LICENSE.