Bloom Filters

A small, fast filter that answers 'definitely not here' or 'maybe here', used to skip disk reads, database lookups and network calls for items that do not exist.

Overview

A Bloom filter is a compact summary of a set. You can add items to it and ask whether an item is in it, and it answers in one of two ways: definitely not, which is always right, or maybe, which is usually right. It never stores the items themselves, so it takes a few bits per item no matter how large the items are.

Burton Bloom described it in 1970. Its value in system design is as a cheap first check in front of something expensive. If most lookups are for things that are not there, the filter turns most of those lookups into a memory check instead of a disk read, a database query or a network call.

The cost is a small, tunable chance of a wrong 'maybe'. A wrong 'maybe' only means one wasted lookup, which is why the trade is usually a good one.

What you will be able to do

  • Explain how a Bloom filter answers, and why it can be wrong only one way.
  • Size a filter from the number of items and the error rate you can accept.
  • Place one in a design: in front of disk files, a database or a remote service.
  • Handle deletes and growth with counting, cuckoo or stacked filters.
  • Say when a Bloom filter is the wrong tool.

Key concepts

  • Bit array and k hashes
  • No false negatives
  • False positive rate
  • Sizing: bits per item
  • LSM read path
  • Lookups for missing keys
  • Counting and cuckoo filters
  • Scalable filters
  • Union by OR

Interview questions

  • How does a Bloom filter work, and why can it have false positives but not false negatives?
  • Size a Bloom filter for 100 million items at a 1% false positive rate.
  • Where do databases use Bloom filters, and what do they save?
  • Attackers are requesting random product IDs that do not exist, and every request reaches the database. What do you do?
  • Why can you not delete from a Bloom filter, and what do you use instead?
  • Bloom filter, hash set or cuckoo filter: how do you choose?
  • How do you combine filters built on different machines?

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio