Practice this topic in a realistic system design interview
Some systems need fast "have we seen this?" checks, but they also need to remove items later.
A Bloom filter is great for fast membership checks, but it can't safely delete items. A cuckoo filter answers the same question, "is this item possibly in the set, or definitely not?", and it also supports deletion.
In this chapter, we'll learn what a cuckoo filter is, how it stores fingerprints and moves them around to make room, how it supports deletion, and when it is a better choice than a Bloom filter.
Suppose you run an application with one billion users, and you use a Bloom filter to check whether a username is already taken. The filter is stored in memory on every application server. If it says a username is definitely not in the set, you can skip the database lookup entirely.
This works well until users start deleting their accounts. When someone deletes their account, their username becomes available again. So we need to remove it from the filter.
But a standard Bloom filter doesn't support deletion. Each username sets several bits, and those bits may also be used by other usernames. If we clear them, the filter could incorrectly report that a username is available when it's actually taken.
So the deleted usernames stay in the filter, and over time, more and more available usernames are reported as "possibly taken," leading to unnecessary database lookups.
There are a couple of ways to solve this problem.
Ideally, we want something that supports deletion, maintains a low false positive rate, and uses about as much memory as a regular Bloom filter.
That's exactly what a cuckoo filter is designed to do.