4 ms·

Can anyone give some cases of where Bloom filters are used? Has anyone used one in their job?

mbrubeck 11y ago
Web browsers use bloom filters for filtering out CSS rules during selector matching. Here's the implementation of this in Servo (the project I work on): https://github.com/servo/servo/pull/3212 https://github.com/servo/servo/pull/3212 I believe browsers also store their Safe Browsing (anti-malware/phishing) blacklists in bloom filters.
SCHiM 11y ago
I've programmed bloomfilters for my job. A certain product of ours keeps track of certain urls visited. We're talking millions of (unique) urls. We use bloomfilters to quickly check if a url was visited or not. If the bloomfilter search is positive a more expensive search inside a log file begins that gives a conclusive result (since bloomfilters have a (very) small false positive-rate, but we want to be perfectly sure).
- mortehu 11y ago
  > bloomfilters have a (very) small false positive-rate One of the neat things about Bloom filters is that you can choose your own false positive rate, by tuning the number of hashes and the storage size.
  - Freaky 11y ago
    Calculator: http://hur.st/bloomfilter http://hur.st/bloomfilter
gdubya 11y ago
Distributed Hash Table (DHT) networks often use them
miketuritzin 11y ago
The first time I heard of bloom filters was back when I worked at Google a decade ago (on the search indexing team). We used them in MapReduces when doing cross-machine table lookups. The idea was to load the bloom filters into memory on the machines doing the lookups and then to only do the lookup if the bloom filter test passed - this optimization worked because a large fraction of the lookups were for entries not contained in the tables. I can't actually remember what data was being looked up in the tables, though.
gopalv 11y ago
All the time - [1]/[2] When you are going to fetch data from a remote location, you don't want to make a trip in vain. So you end up storing them as a fixed size metadata chunk that lets you guess whether to go fetch it or not. The neat trick is that the bloom filters have no false-negatives - the data might not exist (false positives), but it will never say "no" if it does exist. But unfortunately, it doesn't really support deletion neatly - so it's really useful for scenarios where it's a first point of lookup before overloading a central source-of-truth. The best use case I've seen for it is in Chrome, where the "Safe browsing" list is actually a huge bloom filter, which is used to decide whether to ask Google if this domain is safe. So the list of banned URLs might be in the millions, but the bloom filter is a few megabytes and when it has a false positive, it goes & checks upstream whether it is indeed still banned/problematic. [1] - http://www.slideshare.net/Hadoop_Summit/orc-2015-faster-better-smaller/22 http://www.slideshare.net/Hadoop_Summit/orc-2015-faster-bett... [2] - https://issues.apache.org/jira/browse/HIVE-11306 https://issues.apache.org/jira/browse/HIVE-11306
bcheung 11y ago
They are typically used when you have a lot of items in a list of some kind and you want to know if a particular one is present already without incurring the heavy lookup cost. When you check the Bloom filter it tells you: 1) it might be there or 2) it definitely isn't there. In the case of 2, you don't need to look it up. In case 1, you'll need to do the actual lookup. It is commonly used to filter high volume / frequency requests for something. For example, if you have a list of banned IP addresses, user accounts, etc, you can quickly go through the bloom filter without hitting the database.
bobthecowboy 11y ago
Ceph (the distributed storage platform) uses them for their cache tier to determine if a piece of data is "hot" enough to cache.
colordrops 11y ago
They are used in Cassandra to determine whether or not to make a request to another node for data.
parshimers 11y ago
They are very useful in log structured merge tree (LSM) based storage. HBase uses them, for example. The idea is to have a bloom filter as part of each on-disk component, so that one can look at the bloom filter first- and then only bother with searching the actual component, if there is a match in the filter. That way you can reduce the pain of having to potentially search multiple indices on disk.
Freaky 11y ago
At Newzbin we used them for reducing load on MySQL during Usenet header fetching - each new header would have the Message-ID put through a filtering service to check if it had already been inserted. The service kept an array of 7 filters, rotated daily - the oldest would be cleared and reused for new items, giving us 6-7 days of history. Each individual header was low-value, and a few false positives every week wasn't a big deal - Usenet servers lost a lot more during their normal course of operation.
joeldg 11y ago
spellcheckers use them, any time you see a company with millions of users let you know your email address was already registered, domain name registrars use them -- basically anything with a large search space where you need to know if something is in (or not) the dataset. They are useful all over. I wrote a modified version of bloom filters so the filter files are about 1/3rd the size (but with a slight cpu tradeoff) for a domain name registrar. They are kind of a staple of computer science.
pronoiac 11y ago
I've used them before. I ran a Squid proxy and connected it to the NLANR cache hierarchy[1]; despite the name, it's more of a mesh with siblings. For the best speed, you can use bloom filters (or cache digests, in their terms[2]) to avoid the extra latency of a request of "hey, do you have this URL cached?" from someone who definitely doesn't. [1] http://wiki.squid-cache.org/Features/CacheHierarchy http://wiki.squid-cache.org/Features/CacheHierarchy [2] http://wiki.squid-cache.org/SquidFaq/CacheDigests http://wiki.squid-cache.org/SquidFaq/CacheDigests
simi_ 11y ago
Yes! We use them to check for weak passwords server-side. (Passwords arrive already hashed, we have a large dataset of known bad passwords that we load when the application starts.) https://github.com/lavab/api/search?utf8=%E2%9C%93&q=bf https://github.com/lavab/api/search?utf8=%E2%9C%93&q=bf

Web browsers use bloom filters for filtering out CSS rules during selector matching. Here's the implementation of this in Servo (the project I work on): https://github.com/servo/servo/pull/3212 https://github.com/servo/servo/pull/3212 I believe browsers also store their Safe Browsing (anti-malware/phishing) blacklists in bloom filters.

SCHiM 11y ago

I've programmed bloomfilters for my job. A certain product of ours keeps track of certain urls visited. We're talking millions of (unique) urls. We use bloomfilters to quickly check if a url was visited or not. If the bloomfilter search is positive a more expensive search inside a log file begins that gives a conclusive result (since bloomfilters have a (very) small false positive-rate, but we want to be perfectly sure).

mortehu 11y ago
> bloomfilters have a (very) small false positive-rate One of the neat things about Bloom filters is that you can choose your own false positive rate, by tuning the number of hashes and the storage size.
- Freaky 11y ago
  Calculator: http://hur.st/bloomfilter http://hur.st/bloomfilter

gdubya 11y ago

Distributed Hash Table (DHT) networks often use them

miketuritzin 11y ago

The first time I heard of bloom filters was back when I worked at Google a decade ago (on the search indexing team). We used them in MapReduces when doing cross-machine table lookups. The idea was to load the bloom filters into memory on the machines doing the lookups and then to only do the lookup if the bloom filter test passed - this optimization worked because a large fraction of the lookups were for entries not contained in the tables. I can't actually remember what data was being looked up in the tables, though.

gopalv 11y ago

All the time - [1]/[2] When you are going to fetch data from a remote location, you don't want to make a trip in vain. So you end up storing them as a fixed size metadata chunk that lets you guess whether to go fetch it or not. The neat trick is that the bloom filters have no false-negatives - the data might not exist (false positives), but it will never say "no" if it does exist. But unfortunately, it doesn't really support deletion neatly - so it's really useful for scenarios where it's a first point of lookup before overloading a central source-of-truth. The best use case I've seen for it is in Chrome, where the "Safe browsing" list is actually a huge bloom filter, which is used to decide whether to ask Google if this domain is safe. So the list of banned URLs might be in the millions, but the bloom filter is a few megabytes and when it has a false positive, it goes & checks upstream whether it is indeed still banned/problematic. [1] - http://www.slideshare.net/Hadoop_Summit/orc-2015-faster-better-smaller/22 http://www.slideshare.net/Hadoop_Summit/orc-2015-faster-bett... [2] - https://issues.apache.org/jira/browse/HIVE-11306 https://issues.apache.org/jira/browse/HIVE-11306

bcheung 11y ago

They are typically used when you have a lot of items in a list of some kind and you want to know if a particular one is present already without incurring the heavy lookup cost. When you check the Bloom filter it tells you: 1) it might be there or 2) it definitely isn't there. In the case of 2, you don't need to look it up. In case 1, you'll need to do the actual lookup. It is commonly used to filter high volume / frequency requests for something. For example, if you have a list of banned IP addresses, user accounts, etc, you can quickly go through the bloom filter without hitting the database.

bobthecowboy 11y ago

Ceph (the distributed storage platform) uses them for their cache tier to determine if a piece of data is "hot" enough to cache.

colordrops 11y ago

They are used in Cassandra to determine whether or not to make a request to another node for data.

parshimers 11y ago

They are very useful in log structured merge tree (LSM) based storage. HBase uses them, for example. The idea is to have a bloom filter as part of each on-disk component, so that one can look at the bloom filter first- and then only bother with searching the actual component, if there is a match in the filter. That way you can reduce the pain of having to potentially search multiple indices on disk.

Freaky 11y ago

At Newzbin we used them for reducing load on MySQL during Usenet header fetching - each new header would have the Message-ID put through a filtering service to check if it had already been inserted. The service kept an array of 7 filters, rotated daily - the oldest would be cleared and reused for new items, giving us 6-7 days of history. Each individual header was low-value, and a few false positives every week wasn't a big deal - Usenet servers lost a lot more during their normal course of operation.

joeldg 11y ago

spellcheckers use them, any time you see a company with millions of users let you know your email address was already registered, domain name registrars use them -- basically anything with a large search space where you need to know if something is in (or not) the dataset. They are useful all over. I wrote a modified version of bloom filters so the filter files are about 1/3rd the size (but with a slight cpu tradeoff) for a domain name registrar. They are kind of a staple of computer science.

pronoiac 11y ago

I've used them before. I ran a Squid proxy and connected it to the NLANR cache hierarchy[1]; despite the name, it's more of a mesh with siblings. For the best speed, you can use bloom filters (or cache digests, in their terms[2]) to avoid the extra latency of a request of "hey, do you have this URL cached?" from someone who definitely doesn't. [1] http://wiki.squid-cache.org/Features/CacheHierarchy http://wiki.squid-cache.org/Features/CacheHierarchy [2] http://wiki.squid-cache.org/SquidFaq/CacheDigests http://wiki.squid-cache.org/SquidFaq/CacheDigests

simi_ 11y ago

Yes! We use them to check for weak passwords server-side. (Passwords arrive already hashed, we have a large dataset of known bad passwords that we load when the application starts.) https://github.com/lavab/api/search?utf8=%E2%9C%93&q=bf https://github.com/lavab/api/search?utf8=%E2%9C%93&q=bf