AlgoMaster Logo

Cuckoo Filter

Low Priority17 min readUpdated October 25, 2026
AI Mock Interview

Practice this topic in a realistic system design interview

Premium Video

This video is available to premium subscribers only

Unlock Full Access

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.

1. The Problem

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.

2. The Usual Workarounds

There are a couple of ways to solve this problem.

  • Rebuild the Bloom filter from the database every few hours. This works, but it requires scanning a billion usernames each time, and the filter can become outdated between rebuilds.
  • Use a counting Bloom filter. Instead of storing a single bit at each position, it stores a small counter, which lets us remove an item by decrementing its counters. However, each counter typically uses four bits, making the filter roughly four times larger.

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.

3. What Is a Cuckoo Filter?

Premium Content

This content is for premium members only.