Today I learned about bloom filter. “A space-efficient probabilistic data structure conceived by Burton Howard Bloom” (Wikipedia). But what does it means probabilistic? How much space does it saves? Does it really lightning fast?
Before we talk about bloom filter, let’s talk about why you should be familiar with it. Consider yourself developing a backend that should support many logins at once, or you have to look up if a certain filename exists in some location. Basically any “simple” lookup – you have a huge list of “keys” and you need to check quickly if a specific key is within that HUGE list, or not.
One option, the naive one, is to insert all keys into a list or array and look inside the array. It is trustful and consistent (you have no doubt if you found or haven’t found a match). But it has 2 cons:
1. it can take a lot of time – O(n).
2. it uses a lot of memory.
For small datasets, it is good enough. but if you have millions of records or you have to rapidly check new keys – this is going to be a disaster.
Another option is to use a set or map. These data types solve the lookup time problem. they use hash maps to calculate the location of the key in memory. A fixed algorithm to determine if a key exists or not. However, efficiency comes with a cost – probability. Because calculating the hash of 2 different keys MAY result in the same hash value. most programming languages solved this very very VERY rate collision problem but you should acknowledge it. But we still consume a lot of memory as we need to keep the hash of each key + some metadata
Bloom filter solves both of these issues it is extremely small in size (~1.5MB to store the data of >1GB. over 600 times better). and really efficient – O(1) that is faster than normal hash maps. But it does one thing. and one thing only – tells you if a key is definitely not in the list, or MAY be in the list. This is important because it may (and probably will) lead to false-positive- a case where you think a key exists in your records although it is not.
At this point, I’m encouraging you to go to bloomfilter-tutorial by llimllib on Github. Which explains better than I about bloom filter. As mentioned, since the false positive rate isn’t negligible you’ll probably want to use it where a more precise check is available. That way you can drop most of the unnecessary checks and only review required ones and a small portion of false positives.
Read more:
Wikipedia – https://en.wikipedia.org/wiki/Bloom_filter (especially Examples)
bloom filter calculator – https://hur.st/bloomfilter/
How maps work in Go https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics