Understanding Bloom Filters, Counting Bloom Filters, and Cuckoo Filters

IO latency is a classic bottleneck in backend systems, so developers often use filters to avoid unnecessary database queries; the article starts with a typical scenario where many requests query non‑existent data, motivating the use of probabilistic filters.

Bloom Filter uses a bitmap and multiple hash functions: when an element is inserted, the corresponding bits are set to 1; a later query checks those bits, and if any are 0 the element is definitely absent, otherwise it may be present, leading to false positives. The filter cannot delete elements because clearing bits may affect other entries.

The Counting Bloom Filter replaces the bitmap with an array of counters, incrementing on insertion and decrementing on deletion, which solves the delete problem but still suffers from false positives.

To overcome Bloom’s shortcomings, the Cuckoo Filter is introduced. It stores only a short fingerprint of each element in a cuckoo‑hash table, allowing true deletions and offering higher space efficiency.

The underlying Cuckoo Hash structure uses two hash functions to map an element to two possible slots in a one‑dimensional array. If both slots are occupied, one existing element is evicted (“cuckoo‑shifting”) and re‑inserted elsewhere, possibly triggering a cascade of evictions. When the table becomes too full, it must be resized.

p1 = hash1(x) % l
p2 = hash2(x) % l

Problems arise when the array is crowded, causing long eviction chains or cycles; to mitigate this, more hash functions (e.g., three or four) and multiple slots per bucket can be used, dramatically improving space utilization and reducing collisions.

In a Cuckoo Filter, each element’s fingerprint fp = fingerprint(x) is stored instead of the full element. Two candidate positions are computed as:

fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp) // XOR

Because the fingerprint is known, the alternate position can be derived from the current position via XOR, ensuring p1 ≠ p2 when hash(fp) != 0 and avoiding self‑eviction loops.

Overall, the article provides a comparative overview of Bloom, Counting Bloom, and Cuckoo filters, explains their core algorithms, highlights their trade‑offs, and suggests practical enhancements for efficient, deletable, and low‑false‑positive filtering in high‑throughput systems.