System Design - (Day 4)

Bloom Filters - Hashing

Example 1: Let’s say you are creating an account in the facebook.com, and you have entered your name, (Ex: Manoj), it returned a message as “Username is already taken”, and you tried your name with your birth year, unfortunately it again returns “Username is already taken”, have you ever wondered how fast that response gonna be coming to you, they have millions of users in the facebook,
1. They can use Linear Search, it would take soo soo much time that you could have created you account in tinder and started started chatting with some stranger, just kidding😂. it’ll take O(n) (worst case).
2. They can use binary Search, ya it can store names alphabetically and get you the message, but that’s not the optimised approach.
Here it comes the super power which is Hashing with Bloom filters,
This will gives you the super power of getting the data faster than your blink.

Example 2:Suppose you’re searching for a user named “Sneha” on Facebook in your browser. After you’ve looked her up three to five times in a row, the browser can cache her profile locally—so subsequent visits load almost instantly without making another API request to Facebook’s servers. Under the hood, you might implement this using an in-memory cache (or even the browser’s localStorage/ sessionStorage) combined with a Bloom filter:

• Hash functions map each profile ID to one or more bit positions in a fixed-size bit array.

• Before issuing an API call, you first query the Bloom filter to see if “Sneha”’s profile is likely cached.

• A cache hit means you can fetch the profile from local storage; a cache miss triggers the API call and updates both the cache and the Bloom filter’s bit array.