Bloom Filter Variants, in depth: counting, partitioned, scalable, stable, rotating and invertible Bloom filters with code, sizing math and failure modes

Four limits, four variants

A useful habit: before picking a variant, write down which guarantee you can afford to lose. If the answer is "none, and I need deletes", a cuckoo filter usually beats a counting Bloom filter on space. If you need to merge or resize on disk, look at the quotient filter.

Counting Bloom filters: deletes

Replace every bit with a small counter. Insert increments the k counters, delete decrements them, and a query asks whether all k are non-zero. The false positive rate is the same as a bit filter with the same m and k, because a counter is non-zero exactly when the bit would have been set. This is the variant Fan, Cao, Almeida and Broder used in the Summary Cache work on sharing web proxy caches, where cached objects come and go.

How wide must the counters be? With the optimal k, Fan et al. bound the probability that any counter reaches i by m(e ln 2 / i)ⁱ. For i = 16, (e ln 2 / 16) is about 0.118, and 0.118¹⁶ is about 1.4 × 10^-15, so even a filter with a billion counters overflows a 4-bit counter with probability around one in a million. That bound assumes distinct keys; duplicate inserts of the same key are what really overflow counters, so make insert idempotent or saturate.

import hashlib

class CountingBloom:
    def __init__(self, m, k):
        self.m, self.k = m, k
        self.c = bytearray(m)              # one byte per counter for clarity;
                                           # pack two 4-bit counters per byte in production
    def _idx(self, key: bytes):
        d = hashlib.blake2b(key, digest_size=16).digest()
        h1 = int.from_bytes(d[:8], "little")
        h2 = int.from_bytes(d[8:], "little") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, key):
        for i in self._idx(key):
            if self.c[i] < 15:             # saturate: a stuck counter is safe
                self.c[i] += 1

    def remove(self, key):
        idx = self._idx(key)
        if not all(self.c[i] for i in idx):
            raise KeyError("not present; refusing to corrupt other keys")
        for i in idx:
            if self.c[i] < 15:             # never decrement a saturated counter
                self.c[i] -= 1

    def __contains__(self, key):
        return all(self.c[i] for i in self._idx(key))

Two rules make deletion safe. First, a saturated counter must never be decremented: you no longer know its true value, and decrementing it could create a false negative. Second, never delete a key that was not inserted. The filter cannot detect this reliably (a false positive passes the check above), and a wrong delete decrements counters that belong to other keys, so a later query for one of them says "definitely absent" when it is present. Only delete keys whose membership you know from an authoritative source.

Scalable Bloom filters: unknown n

A classic filter sized for n keys degrades smoothly past n until it is useless. When n is unknown, the scalable Bloom filter of Almeida, Baquero, Preguiça and Hutchison chains filters: when the current slice reaches its capacity, it is frozen and a new, larger slice is added. Inserts go to the newest slice; a query checks all slices.

The trick is in the error budget. The overall false positive rate is at most the sum of the slices' rates. If slice i is given rate P₀rⁱ with a tightening ratio r below 1, the sum is a geometric series bounded by P₀/(1 − r). To hit a target P, set P₀ = P(1 − r). Capacity grows by a factor s per slice; the paper suggests s of 2 or 4 and r between 0.8 and 0.9. Each new slice needs about log₂(1/r) more hash functions than the one before, which is 0.15 for r = 0.9.

import math

class ScalableBloom:
    def __init__(self, initial_capacity=1_000_000, target_fpr=0.01, s=2, r=0.9):
        self.cap0, self.s, self.r = initial_capacity, s, r
        self.p0 = target_fpr * (1 - r)
        self.slices = []                   # list of (bloom, capacity)
        self._grow()

    def _grow(self):
        i = len(self.slices)
        cap = self.cap0 * self.s ** i
        p = self.p0 * self.r ** i
        k = math.ceil(math.log2(1 / p))
        m = math.ceil(cap * k / math.log(2))    # m/n = k/ln2 at the optimum
        self.slices.append([PartitionedBloom(m, k), cap, 0])   # described below

    def add(self, key):
        if key in self:                    # avoid double-counting capacity
            return
        sl = self.slices[-1]
        if sl[2] >= sl[1]:
            self._grow()
            sl = self.slices[-1]
        sl[0].add(key)
        sl[2] += 1

    def __contains__(self, key):
        # newest first: recent keys are often the hot ones
        return any(key in b for b, _, _ in reversed(self.slices))

Each slice is a partitioned Bloom filter: its m bits are split into k regions of m/k bits and hash i sets one bit in region i. The false positive rate is approximately the same as the unpartitioned filter, every key sets exactly k distinct bits, and the fill ratio of each region is easy to reason about, which is why the scalable design uses it. The membership check in add deserves a note: it keeps the count honest for repeated keys, at the price that a false positive silently skips a genuinely new key. That is harmless for deduplication and wrong if you later need the exact count.

Worked example: sizing a scalable chain

Suppose a crawler must remember seen URLs, expects about a million but might see ten million, and can tolerate 1 percent false positives. With r = 0.9, P₀ = 0.001. The bits per key at rate p are k/ln 2 with k = ⌈log₂(1/p)⌉.

At 10 million keys the chain has four slices, 29.6 MB in total, with slice 3 three-eighths full. The measured false positive rate is about the sum of the full slices, 0.10 + 0.09 + 0.081 ≈ 0.27 percent, because a partly filled slice contributes almost nothing. That is far inside the 1 percent bound, which is conservative by design. Compare a single classic filter sized for exactly 10 million keys at 1 percent: 9.6 bits per key, 12 MB, one probe set per query. The scalable chain cost about 2.5 times the memory and four probe sets for the privilege of not knowing n. If you can rebuild offline when a filter fills, rebuilding is cheaper; scalable filters earn their keep when the filter must stay online and growth is unpredictable.

Stable and rotating filters: forgetting

Stream deduplication usually cares about recent duplicates: was this click seen in the last hour? A classic filter fills up and eventually says yes to everything. Two designs fix that by forgetting.

The stable Bloom filter of Deng and Rafiei uses small counters. Each insert first decrements P randomly chosen counters by one, then sets the key's k counters to the maximum value. Old keys fade as random decrements wear their counters down, and the fraction of zero counters converges to a stable value, so the false positive rate stops growing. The price is false negatives: a recent key whose counter was decremented to zero is reported unseen. That is a real change of contract, and any consumer that assumed "no means no" must be checked.

The simpler and more common production answer is rotation: keep a current and a previous classic filter, insert into the current one, query both, and every window swap them and clear the new current. Every key is remembered for at least one window and at most two, with no randomised forgetting to explain.

class RotatingBloom:
    def __init__(self, make_filter, window_s, clock):
        self.make, self.window, self.clock = make_filter, window_s, clock
        self.cur, self.prev = make_filter(), make_filter()
        self.started = clock()

    def _maybe_rotate(self):
        if self.clock() - self.started >= self.window:
            self.prev, self.cur = self.cur, self.make()
            self.started = self.clock()

    def seen_or_add(self, key) -> bool:
        self._maybe_rotate()
        hit = key in self.cur or key in self.prev
        if not hit:
            self.cur.add(key)
        return hit

Size each generation for the keys of one window, not of two, because only one generation receives inserts. The false positive rate of a query is roughly the sum of both generations' rates.

Invertible Bloom lookup tables: listing and diffing

A classic filter cannot tell you which keys it holds. An invertible Bloom lookup table (Goodrich and Mitzenmacher) can, as long as it holds few enough. Each cell keeps a count, the XOR of all keys hashed into it and the XOR of a checksum of those keys. A cell with count 1 and a matching checksum is "pure": its key sum is a single key. Decoding repeatedly finds a pure cell, reads the key, removes it from its other k − 1 cells and continues. This peeling succeeds with high probability when the number of entries is below a threshold; for k = 3 that is about 0.81 entries per cell, so in practice allocate around 1.5 cells per expected entry.

Its best use is set reconciliation, described by Eppstein, Goodrich, Uyeda and Varghese as a difference digest. Replica A builds a table of its keys and sends it. B subtracts its own keys cell by cell. Keys present on both sides cancel, whatever the set sizes, so the table only needs to be big enough for the difference. Peeling then returns keys only A has (count +1) and only B has (count −1).

import hashlib

def _h(key: int, salt: int) -> int:
    d = hashlib.blake2b(key.to_bytes(8, "little"), digest_size=8,
                        salt=salt.to_bytes(16, "little")).digest()
    return int.from_bytes(d, "little")

class IBLT:
    def __init__(self, cells, k=3):
        self.n, self.k = cells, k
        self.count = [0] * cells
        self.keysum = [0] * cells
        self.chksum = [0] * cells

    def _cells(self, key):
        per = self.n // self.k             # partitioned: one cell per region
        return [i * per + _h(key, i) % per for i in range(self.k)]

    def _update(self, key, delta):
        chk = _h(key, 99)
        for i in self._cells(key):
            self.count[i] += delta
            self.keysum[i] ^= key
            self.chksum[i] ^= chk

    def insert(self, key): self._update(key, +1)

    def subtract(self, other):
        for i in range(self.n):
            self.count[i] -= other.count[i]
            self.keysum[i] ^= other.keysum[i]
            self.chksum[i] ^= other.chksum[i]

    def decode(self):
        only_a, only_b = set(), set()
        stack = list(range(self.n))
        while stack:
            i = stack.pop()
            if self.count[i] in (1, -1) and self.chksum[i] == _h(self.keysum[i], 99):
                key, sign = self.keysum[i], self.count[i]
                (only_a if sign == 1 else only_b).add(key)
                self._update(key, -sign)
                stack.extend(self._cells(key))
        ok = not any(self.count) and not any(self.keysum)
        return ok, only_a, only_b          # ok=False: table too small, retry larger

Worked example: two replicas each hold about a million 64-bit keys and differ by roughly 100. A 150-cell table with 4-byte counts and two 8-byte sums is 3 KB; shipping the smaller replica's key list would be 8 MB. You need an estimate of the difference before sizing the table; the difference digest paper pairs the table with a strata estimator (a stack of small tables over hash-prefix strata) for this. When decoding fails, the ok flag says so; double the table and retry rather than trusting a partial result.

Failure modes

• Deleting from a classic filter. Clearing bits for one key erases others. Any delete path needs counters, a cuckoo filter or a rebuild.
• Wrong deletes in counting filters. Removing a key that was never inserted, or removing twice, creates false negatives that look like data loss. Delete only with authoritative knowledge, and never decrement a saturated counter.
• Unbounded scalable chains. A misconfigured producer that inserts random keys grows the chain forever, and every query probes every slice. Cap the slice count and alert on growth.
• Assuming no false negatives after adopting decay. Stable Bloom filters lose keys by design; callers that skip work on "absent" must tolerate it.
• Trusting a failed IBLT decode. A partial peel returns a plausible subset of the difference. Always check that the table is empty after peeling.
• Hash inconsistency across processes. Filters shipped between services or persisted to disk need the same hash function, seed and layout version on both sides. Python's built-in hash() is salted per process and must never be used.

What to do next

1. Write down which classic limitation you are hitting: delete, growth, ageing or listing.
2. If it is deletion, prototype a cuckoo filter first and fall back to counting Bloom only when you need its merge or arithmetic properties.
3. If n is unknown, compare a scalable chain with rebuild-on-threshold using the table above and your real growth curve; cap the chain length.
4. For stream deduplication, start with two rotating generations sized for one window, and document the forgetting window to consumers.
5. For replica repair, prototype an IBLT with a difference estimate, check decode success on a replay of real divergence, and retry larger on failure.
6. Pin hash functions and seeds in a versioned serialisation format, and test measured false positive rate against the formula on held-out keys.