System Design Fundamentals
Vote

0% completed

​

Introduction to Bloom Filters

A web crawler downloads pages from across the internet. Before it downloads a page, it must answer one question: have I already visited this address?

The simple solution is to keep every visited address in a hash set and check each new address against it. This works until the set becomes large. Ten million web addresses, at about 100 bytes each, need about 1 gigabyte of memory. Keeping that much memory on every crawler server is expensive.

A Bloom filter answers the same question with much less memory. Those ten million addresses fit in about 12.5 megabytes

.....

.....

.....

Like the course? Get enrolled and start learning!
Piyush Kuhikar

Piyush Kuhikar

· 3 months 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:
Show 1 reply
Catherine Higgins

Catherine Higgins

· 4 months ago

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

Show 1 reply
Ayush Sur

Ayush Sur

· 6 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

Show 1 reply
A

anmoldeep1509

· 6 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.

Show 1 reply
Md Nuruzzaman Mithun

Md Nuruzzaman Mithun

· 7 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.
Show 1 reply
Nathan Frankel

Nathan Frankel

· a year 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?

Show 1 reply
P

Pankaj Wakchaure

· 2 years ago

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

Show 1 reply
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.

Reading Progress

0%

Vote for new content