Counting Bloom Filters and the Price of Supporting Deletion

A Bloom filter cannot forget. Clearing the bits belonging to a removed key also clears bits that survive in other keys, so removal converts a one-sided error into a two-sided one. The obvious repair is to stop storing one bit per position and store a small integer instead: set on insert, decrement on remove, and treat a position as occupied while its counter is positive. That repair is correct in the common case and introduces three separate ways to be wrong, each of which shows up at a different scale.

From bits to counters

The layout is the same array of $m$ positions and the same $k$ probes per key, but each position holds a counter rather than a bit. Insertion increments the $k$ counters a key hashes to; removal decrements them; a lookup tests whether all $k$ are nonzero. With one-byte counters the space is eight times the bit array; with four-bit counters it is four times, which is the variant that made the structure practical for cache-sharing protocols and remains the standard choice.

Four bits is not an arbitrary compromise. It bounds a counter at 15, which is enough for any position that a handful of keys share, and it packs two counters into a byte and sixteen into a 64-bit word. A filter at ten bits per key becomes 40 bits, or five bytes, per key — a million keys occupy 5 MB instead of 1.2 MB. That is the entire price of deletion, and it is why the structure is used only when removal is genuinely required.

The counting variant inherits every property of the bit array. False positives are still one-sided in the absence of bugs, the error still follows $(1 - e^{-kn/m})^k$, and the filter still cannot be resized in place. What changes is the meaning of a position: a bit records “some key hashed here”, a counter records “how many keys hashed here”, and the second quantity is only useful if it is exact.

Saturation, and the residue it leaves

A four-bit counter increments to 15 and then stops. That clamp is deliberate — the alternative, wrapping to zero, would silently erase a position that other keys depend on and produce false negatives immediately. But clamping is not free either. Consider a position that reaches 15 while holding, say, twenty keys. Its true count is 20 and its stored count is 15. Remove five of those keys and the stored count drops to 10, still positive, so nothing is visibly wrong. Remove fifteen more and the stored count reaches zero while five keys remain that still hash there. Their lookups now return negative.

This is the residue failure: saturation is safe only while no key that shares the position is ever removed after the clamp. The probability of reaching 15 rises with the load on the array, so the failure appears late, at exactly the point where the filter is being used hardest. Keeping $m/n$ generously above the design point — more positions per key than the error target alone requires — delays it. The original cache-sharing work chose the counter width and the array size together so that overflow stays rare at the expected number of entries, which is a statement about probability, not a guarantee.

The second failure is the spurious decrement. Removing a key that was never inserted is not a no-op: the removal path decrements $k$ counters belonging to whatever keys happen to share those positions. If a counter drops to zero, every key that still hashes there becomes a false negative. Bloom filters survive this kind of misuse because they have no removal path at all; a counting filter must either trust its caller or verify the key first, and verifying requires the key set it was built to avoid storing.

What the decrement path must refuse

The minimum correct behaviour is to reject a decrement of a zero counter rather than wrapping it. The second is to make removal a mirror of insertion and nothing more: the same $k$ positions, the same order, no conditional logic based on what the lookup returned.

class CountingBloom:
    """One counter per position; real implementations pack two per byte."""

    def __init__(self, m):
        self.m = m
        self.counters = bytearray(m)          # values 0..15

    def add(self, positions):
        for p in positions:
            c = self.counters[p]
            if c < 15:                        # saturate; wrapping would erase other keys
                self.counters[p] = c + 1

    def remove(self, positions):
        for p in positions:
            c = self.counters[p]
            if c == 0:
                raise KeyError('decrement of an empty counter')
            self.counters[p] = c - 1

    def maybe_contains(self, positions):
        return all(self.counters[p] > 0 for p in positions)

The raise is the interesting line. It converts a silent corruption into a loud error, but only for the counter that happens to be at zero. A decrement of a positive counter that belongs entirely to other keys passes unnoticed, and the damage surfaces later as a missing entry. No local check can distinguish the two cases, because the filter does not know which keys contributed to a counter.

The d-left alternative

The alternative construction avoids counters altogether. Instead of one array with $k$ probes, the d-left counting Bloom filter uses $d$ subtables, each divided into buckets of a few slots, and stores a short fingerprint plus a small counter in each slot — a layout close to the cuckoo filter, which also stores fingerprints in buckets but places them by displacement rather than by load. A key is inserted into the least-loaded of its $d$ candidate buckets, which makes the placement deterministic given the current table state. Lookup checks the same $d$ buckets. Removal recomputes the candidate buckets, finds the slot holding the fingerprint, and decrements it — and because insertion always chose the least-loaded bucket, the slot holding a key is known without searching.

Two properties follow. The space is roughly twice a plain Bloom filter at the same error rate rather than four times, because the fingerprint carries most of the discriminating information and the counter needs only enough bits to cover the bucket occupancy. And the false-negative hazard is confined: a removal that finds no matching fingerprint can be rejected outright instead of decrementing someone else’s counter. The cost is a more complex layout — buckets must be located by division, and insertion must compare occupancies — plus the same saturation concern at the bucket level, since a full bucket forces a key into a worse bucket and degrades the placement invariant that removal relies on.

Cache behaviour of the counting variant

Multiplying the array by four has a consequence beyond memory: it moves the filter out of cache. A million-key filter at ten bits per key is about 1.2 MB; the counting version is about 5 MB. On a machine with a 1 MB L2 and an 8 MB L3, the first is a borderline L2 resident and the second is an L3 resident, so each probe becomes a slower access even though the number of probes is unchanged.

There is a second effect. A read-modify-write of a counter is not a read: insertion dirties the cache line, and concurrent insertions to nearby positions contend on the same line. A bit array has the same problem in principle, but setting a bit is idempotent, so two writers racing on the same word both leave it correct. Incrementing is not idempotent, and a lost update is indistinguishable from a key that was never inserted. Sharing a counting filter between threads therefore requires atomic increments or per-thread filters merged later, and the merge is the addition that sketch merging describes — with saturation, not wraparound, at the join.

When the extra space is justified

The structure earns its cost when the live set changes constantly and the filter must track it: a cache admission index, a deduplication window that slides, a per-tenant set that is rebuilt from deltas rather than from scratch. In each case the alternative is periodic reconstruction, and the rebuild cost — a full pass over the live set plus a fresh allocation — can exceed the fourfold space increase.

It does not earn its cost when removal is rare or when the filter can simply be rebuilt cheaply. A read-mostly index over immutable segments should use the plain bit array and drop the segment when it is replaced. A filter whose purpose is to reject most lookups before an expensive operation should also stay a bit array: a false negative there is a correctness bug, and the counting variant is one bug away from producing them.

The remaining question, whether a filter that supports deletion can also be merged across shards, is answered by the counters themselves: two counting filters over the same $m$ and $k$ merge by adding corresponding counters, provided the sum is clamped rather than wrapped. Merging filters built with different $m$ or $k$ is meaningless, and the arithmetic gives no warning when it happens.