System Design Fundamentals
Vote

0% completed

​

Introduction to Bloom Filters

You often need to answer one small question. Have we seen this item before?

The simple way is to keep every item in a hash set and look it up there. That works until the set gets large. Ten million web addresses at about 100 bytes each need roughly a gigabyte of memory. Keeping that on every server is expensive.

A Bloom filter answers the same question in a small, fixed amount of memory. Those ten million items fit in about 12 megabytes. The saving comes from one compromise. The filter is sometimes wrong, and it is wrong in only one direction.

.....

.....

.....

Like the course? Get enrolled and start learning!
kusuma k s

kusuma k s

· 2 years ago

Please add some resources which can explain the Bloom filter concept with an example. Any practical use case example with a structured SQL based example will be ideal.

P

Pankaj Wakchaure

· 2 years ago

Please add more explanation with clear diagrams. Possibly give a detailed example with diagrams.

Nathan Frankel

Nathan Frankel

· 9 months ago

Is this ever relevant for a high level system design interview? I've never heard of this in over 10 years in software engineering. All other topics I have at least heard of at some level. I'm sure this has it's use cases, but questioning if this is a 'system design basic'. In what scenario would one bring this up in a one hour interview context?

Md Nuruzzaman Mithun

Md Nuruzzaman Mithun

· 5 months ago

  • Bloom Filters shouldn't be in the topic of System Design Basic.
  • Need to add some use cases with clear sample examples.
  • Explanation is not quite clear to understand.
A

anmoldeep1509

· 4 months ago

A good example of Bloom filters applications in system design is the use case of username selection. When you select a username which has to be unique in the system. Bloom filters can be used to check if the given username already exists or not. In this use case small number of false positives can be trade-off for the latency.

Piyush Kuhikar

Piyush Kuhikar

· a month ago

Bloom filters are used when you need to quickly test whether an element might be in a set, with a low memory footprint, and when false positives are acceptable but false negatives are not.

Where Bloom filters are used

  • Database/query engines (membership pre-checks): Avoid expensive lookups (e.g., don’t hit a disk/page if it’s definitely not there).
  • Caching / key-set existence checks: Quickly decide whether to check a cache backend.
  • Search systems / inverted index helpers: Prune candidate documents/segments before doing heavier work.
  • Network routing / content discovery: Reduce unnecessary queries (e.g., “maybe you have this item?”).
  • Distributed systems / deduplication pipelines:
Ayush Sur

Ayush Sur

· 4 months ago

Optimal Bit Array Size (m) If you know how many elements n you have and want a specific false positive probability p, the formula is:

m = - n (lnp) / (ln2)^2

As a rule of thumb, for a 1% false positive rate, you need about 9.6 bits per element. Optimal Number of Hash Functions (k) To minimize false positives for a given m and n, the number of hash functions should be:

k = m/n * ln2

Catherine Higgins

Catherine Higgins

· 2 months ago

How are these typically implemented in memory ? And how do we determine the appropriate size to initialize the array ?