System Design Cases
Cuckoo filters: probabilistic с deletion
Cuckoo filter (Fan, Andersen, Kaminsky, Mitzenmacher 2014) — probabilistic membership с поддержкой DELETE, в отличие от Bloom. Hash table из buckets с короткими fingerprints (8-12 bits); каждый element имеет 2 candidate bucket; lookup читает 1-2 cache lines (cache-friendly vs Bloom k random reads). Insert при коллизии — partial-key cuckoo eviction до MAX_KICKS. Сравнение vs Bloom: для FPR ≤3% Cuckoo меньше по памяти, поддерживает delete, лучше cache locality, но может FAIL при load >95% и нет dynamic resize. Production: RedisBloom CF.*, Snowflake micro-partition pruning, Apache Kudu, CDN edge cache invalidation, TiKV. Сценарии: insert-happy, insert с kick chain, lookup hit/miss, delete (главное преимущество), сравнение vs Bloom, real production uses.
Cuckoo filters
A cuckoo filter is an approximate membership structure that stores short fingerprints in a bucketized cuckoo hash table. It supports lookup, insertion, and deletion, but every operation has a precise contract.
Two candidate buckets
For key (x), compute fingerprint (f), primary bucket (i_1), and alternate bucket (i_2) derived so that the alternate location can be recovered from a stored fingerprint. Lookup searches both buckets.
- no matching fingerprint means "absent" under the implementation's hash/overflow assumptions;
- a match means "possibly present" and can be a false positive.
The false-positive rate depends on fingerprint width, bucket size, load, and implementation details. Do not quote one universal formula without pinning those parameters.
Insertion and load
Insert into a free slot in either bucket. If both are full, evict a fingerprint and move it to its alternate bucket, repeating up to a bounded kick limit. Insertion can fail near high load. A production design must resize/rebuild, use a stash or exact overflow, or reject without losing the authoritative mutation.
Never acknowledge an authoritative insert solely because the filter insert succeeded. The source of truth owns membership.
Deletion caveat
Deletion is safe for a key known to have been inserted under the filter's multiplicity policy. Deleting an arbitrary key after only an approximate positive can remove an unrelated stored fingerprint that caused the false positive. Duplicate logical inserts also require counts or set semantics outside a bare filter.
Concurrency and versioning
Bucket relocation touches multiple slots. Use the implementation's locking, optimistic version, or single-writer protocol so readers never observe an invalid half-move. Pin hash, fingerprint width, bucket size, and table generation; do not merge raw tables with different parameters.
Diagram scenarios
The animation covers two-bucket lookup, free-slot insertion, bounded relocation, insertion failure, exact-state-backed deletion, and rejection of delete-on-maybe.