Scalable Bloom filters: grow without discarding old members

Last updated: 5 Oct 20269 min read

tutorial

A fixed Bloom filter becomes less selective when insertions exceed its design load. A scalable filter keeps the old generation and creates a new, larger generation once the current one reaches its planned insertion count. Queries check every generation. An inserted key therefore remains queryable after later growth, and a negative answer still means absent under the fixed hash convention. This program doubles each generation's planned capacity and assigns generation I a shrinking error target equal to the total error budget divided by two to the I plus one. The targets form a geometric budget; the usual probability interpretation assumes suitable hash behavior and does not certify a particular deterministic stream. Repeated keys still consume insertion capacity because the filter cannot distinguish a duplicate from a false positive without an exact set.

Operational case

A monitoring service plans initially for four new incident records, then receives fifteen. Rejecting later records would create false negatives. Rebuilding from absent source data would be impossible. The scalable index instead allocates generations sized for four, eight, and sixteen insertions, preserving the first record in its original generation and adding the last to the third. Every query examines all three. An approximate-positive answer can come from any generation and must be verified against authoritative storage before it triggers a user-facing claim. This lesson counts add calls, not distinct IDs; a stream of duplicates can force growth even when its true set remains small.

Working Python program

import hashlib
import math


class ScalableIncidentFilter:
    def __init__(self, first_capacity=4, error_budget=0.04):
        if first_capacity < 1 or not 0 < error_budget < 1:
            raise ValueError("invalid capacity or error budget")
        self.first_capacity = first_capacity
        self.error_budget = error_budget
        self.layers = []
        self._new_layer()

    def _new_layer(self):
        layer_number = len(self.layers)
        capacity = self.first_capacity * (2 ** layer_number)
        layer_budget = self.error_budget / (2 ** (layer_number + 1))
        bit_count = math.ceil(-capacity * math.log(layer_budget) / math.log(2) ** 2)
        hash_count = max(1, round(bit_count / capacity * math.log(2)))
        self.layers.append({"bits": bytearray(bit_count), "capacity": capacity,
                            "insertions": 0, "hash_count": hash_count})

    def _positions(self, incident_id, layer_number):
        layer = self.layers[layer_number]
        encoded = incident_id.encode("utf-8")
        for hash_number in range(layer["hash_count"]):
            digest = hashlib.blake2b(
                encoded + layer_number.to_bytes(4, "big")
                + hash_number.to_bytes(4, "big"), digest_size=8
            ).digest()
            yield int.from_bytes(digest, "big") % len(layer["bits"])

    def add(self, incident_id):
        if self.layers[-1]["insertions"] == self.layers[-1]["capacity"]:
            self._new_layer()
        layer_number = len(self.layers) - 1
        layer = self.layers[-1]
        for position in self._positions(incident_id, layer_number):
            layer["bits"][position] = 1
        layer["insertions"] += 1

    def might_contain(self, incident_id):
        return any(all(self.layers[layer_number]["bits"][position]
                       for position in self._positions(incident_id, layer_number))
                   for layer_number in range(len(self.layers)))


filter_index = ScalableIncidentFilter(first_capacity=4)
for incident_number in range(47, 62):
    filter_index.add(f"incident-{incident_number}")
print("layers=", len(filter_index.layers),
      "first=", filter_index.might_contain("incident-47"),
      "last=", filter_index.might_contain("incident-61"), sep="")

Output

layers=3first=Truelast=True

Time, space, and tradeoff

If L generations exist and generation I uses H-I hash probes, an insertion touches one current generation in O(H-I) time while lookup costs O(sum of H-I across all L). Memory is the sum of all allocated generation bit counts. This Python program uses one byte per conceptual bit, so its actual memory is larger than a packed bit array. A generation is allocated at a capacity boundary, causing a one-time allocation cost. Layer targets add to the specified overall error budget under a probabilistic hash model; independence, truncation, and real key distributions affect observed rates. There is no deletion or space reclamation of earlier generations.

Common Mistakes

Do not query only the newest generation after growth.
Do not treat duplicate insertions as free without an exact duplicate source.
Do not mistake a target probability for a measured guarantee on one stream.
Do not describe a bytearray of bits as a packed-bit implementation.

Connected lessons

Compare its mutation contract with Counting Bloom filters: delete only a known insertion, Blocked Bloom filters: localize probes and watch skew, Cuckoo filters: relocate compact fingerprints safely, then run the membership audit and contract quiz.

data structures

range-query-structures