Zero dependencies, pure Python

A bloom filter that keeps most lookups from ever happening.

vstg checks membership in constant memory before the expensive query runs. Nothing else gets installed alongside it.

$ pip install vstg View on GitHub
vstg in action, add words and watch the bits fill 0 / 48 bits set
Every check below answers either certainly absent or maybe present. A bloom filter never confirms membership outright, that trade-off is what keeps it fast. Click a bit or a word at any time to see just its own connections.
Add a word to see which bit numbers it set.
SHA-256 stand-in for blake2b, m=48, k=4, fills up as bits saturate · current false positive rate 0%

The database call you didn't need

Most availability and dedup checks ask a database a question whose answer is almost always no. A bloom filter answers most of those questions itself.

BeforePython 3.10+, Django-style, illustrative example
def check_username(request):
  username = request.GET["username"]
  taken = User.objects.filter(
    username=username
  ).exists()
  return JsonResponse({"available": not taken})
AfterPython 3.10+, Django-style, illustrative example
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. A genuine hit still runs the same query as before, so correctness never changes, only how often the expensive path runs.

How it works

A fixed-size bit array, two hash rounds, and a formula that picks the size for you.

1

Start with a bit array of zeros

Its length is fixed the moment the filter is created. Nothing about the array grows afterward, no matter how many members go in.

2

Inserting sets k bits

Each member is hashed twice, and every one of its k positions is derived from those two digests instead of running k separate hash functions.

3

Checking reads the same k bits

Any bit still zero proves the member was never inserted. All k bits set means probably inserted, since other members could have set the same combination by coincidence.

4

Capacity and error rate pick the size

You supply how many members you expect and how many false positives you can tolerate. optimal_size and optimal_hash_count do the rest.

Bit array size
Hash rounds
Bit position j, from two digests
Resulting false positive rate

Full API

Five composable pieces, plus a module-level convenience layer for the common case where you just want a name and two functions.

BloomFilter

capacity: int error_rate: float
  • add(member: bytes) -> None
  • might_contain(member: bytes) -> bool
  • member in filter, via __contains__
  • .size, .hash_count, .bits
# in memory only, every other class here wraps one of these
f = BloomFilter(capacity=100_000, error_rate=0.001)
f.add(b"user:42")
f.might_contain(b"user:42")  # True

ShardedBloomFilter

shard_count: int dirty tracking
  • ShardedBloomFilter.open(dir, shard_count, ...)
  • .dirty_shard_count
  • .checkpoint() writes only dirty shards
# checkpoint rewrites only the shards that changed
sf = ShardedBloomFilter.open(
  path, shard_count=16,
  capacity=10_000_000, error_rate=0.001,
  policy=policy,
)

ManagedBloomFilter

A BloomFilter bound to a destination path and a checkpoint policy, so time or insert count trigger a save on their own.

  • ManagedBloomFilter.open(path, ...), resumes from disk
  • .checkpoint(), .close()
  • context manager, closes on with exit

BloomFilterRegistry

Several named filters under one base directory, each with its own capacity, error rate, and policy.

  • register(name, capacity, error_rate, ...)
  • get(name), might_contain(name, m)
  • checkpoint_all(), close_all()

PersistPolicy

Checkpoint on an interval, on an insert threshold, on shutdown, or any combination. A dataclass, nothing hidden.

  • checkpoint_interval_seconds
  • checkpoint_insert_threshold
  • checkpoint_on_shutdown, defaults to True

Module level

  • vstg.init(directory), once per process
  • vstg.register(name, capacity, error_rate)
  • vstg.might_contain(name, m), vstg.add(name, m)
# configure once at startup, call from anywhere after that
vstg.init(Path("state"))
vstg.register("usernames", 10_000_000, 0.001)
vstg.might_contain("usernames", member)

Measured, not guessed

202 benchmark records, run on an Apple M2. The figures below are all one configuration from that suite: 100 million items, sized for a 0.01% false positive rate.

228.5MiB
RAM required
100M items, 0.01% error rate
13
hash rounds per operation
k, derived from capacity and error rate
3.57µs
estimated lookup / insert
same cost either direction
0.256s
estimated full checkpoint
single-file, OS page cache warm

See the full benchmark results and capacity planner →