6 ms·

What are Bloom filters?

76 points by duck 11y ago

notacoward 11y ago
If Bloom filters look interesting, you should probably also check out cuckoo filters. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf The differences are somewhat subtle, but the use cases overlap a lot.
- jamra 11y ago
  Would it be safe to say that Cuckoo filters are bloom filters with some additional overhead for the ability to add and remove?
  - notacoward 11y ago
    Deletion is the big difference, but even without that I think there can be other significant differences as well. For any given number of items, it can be pretty unclear which one will give better performance (including the cost of false positives) for bounded size, or better space efficiency for bounded performance. Usually you'll need at least an accurate model for both, if not an actual implementation.
bbcbasic 11y ago
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
krat0sprakhar 11y ago
Like everyone else, I too wrote a blog post on Bloom Filters - http://prakhar.me/articles/bloom-filters-for-dummies/ http://prakhar.me/articles/bloom-filters-for-dummies/.
- scrumper 11y ago
  I preferred yours, but I'm not sure what you had for dinner on your last birthday.
  - krat0sprakhar 11y ago
    Haha! What is that supposed to mean? :D
    - Nadya 11y ago
      You didn't include non-important life details when explaining what a bloom-filter is. >I sigh. I’m hungry and the main course has just arrived — venison glazed in honey, served with a sweet potato hash. I learned more about what the author had for dinner on their last birthday than I did about bloom filters in the first paragraphs. So while they prefer your blog - they aren't sure what you had for dinner on your last birthday...
jasode 11y ago
>To understand Bloom filters, you first have to understand hashing. As pedagogy, I think this is the wrong approach. The author already knows Bloom filters and therefore, it seems like the most logical thing to first talk about is hash functions because that's how it's implemented. Unfortunately, that's not how a person brand new to the concept thinks about it. The first thing to talk about is motivations and scenarios and use cases. For that, the first 2 paragraphs of wikipedia article[1] on Bloom filters is fairly straightforward. It explains why it's an interesting technique. Imo, those paragraphs are a better introduction than the author's dive right into "hash functions" immediately after unrelated blurbs of "I put my fork down" and "my wife shakes her head with a rueful smile." [1]https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter
- dustingetz 11y ago
  wow yes, this is an issue with nearly every technical conference talk
  - ionforce 11y ago
    In my experience, more specifically with talks about functional programming techniques. I find them completely impenetrable.
- baddox 11y ago
  I'm fine with explaining the motivation first, but I struggle to see how you can explain bloom filters without eventually getting to hashing. Obviously you don't need to explain any actual real-world hash function, but you need to explain the concept of deterministically mapping X bits to Y bits where X > Y, which is essentially what a hash function does.
  - FellowMarketer 11y ago
    I don't think at the level of the article that it's inappropriate to assume that the reader is at least familiar with the term "hashing", and can wait on the technical details of the particular types of hashing functions needed for bloom filters until the second or third section. I honestly just closed the article when he started in on hashing, because I want to know about bloom filters (which I don't know about), not the basics of hashing (which I learned as an undergrad, and need to know day-to-day as a working programmer).
shostack 11y ago
Anyone happen to have a great Bloom filter tutorial in Ruby geared towards early programmers? I read the article, but am still not grasping the full construct and how it functions. I'm hoping a hands on tutorial might give me a better sense.
bunderbunder 11y ago
I'm beginning to suspect that if I want to really drive a whack of traffic to my blog, I should write a post about how to implement Bloom filters using monads.
- pizza 11y ago
  Go for it.
- ionforce 11y ago
  Try it, see what happens. And then write a Hacker News article about it.
- bshimmin 11y ago
  For maximum impact, you'll need to choose your programming language carefully. I would suggest Elm with a sprinkling of Coq, though I think using either K or MUMPS would earn you a lot of kudos in some quarters.
bru_ 11y ago
Is anybody else irritated with the incredibly tryhard tone in this article? "venison glazed in honey, served with a sweet potato hash"? Seriously??? It's an article about bloom filters for god's sake, not Leveraged Sell Out for the tech industry...
- jathu 11y ago
  Much like most TED talks, this is in line with the common Medium article theme. The article becomes more about ME ME ME, rather than the subject at hand. It's like some Moses syndrome. When it comes to technical articles this starts to become extremely annoying to read blogs/papers as if it was written for BuzzFeed.
- partisan 11y ago
  I couldn't make it through. I was thinking about Bloom filters just earlier today and was actually looking forward to reading about them. I'll try again tomorrow with a different author.
halayli 11y ago
trying too hard. Just go to https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter It's clearer and more informative.

76 points by duck 11y ago

If Bloom filters look interesting, you should probably also check out cuckoo filters. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf The differences are somewhat subtle, but the use cases overlap a lot.

jamra 11y ago
Would it be safe to say that Cuckoo filters are bloom filters with some additional overhead for the ability to add and remove?
- notacoward 11y ago
  Deletion is the big difference, but even without that I think there can be other significant differences as well. For any given number of items, it can be pretty unclear which one will give better performance (including the cost of false positives) for bounded size, or better space efficiency for bounded performance. Usually you'll need at least an accurate model for both, if not an actual implementation.

bbcbasic 11y ago

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

krat0sprakhar 11y ago

Like everyone else, I too wrote a blog post on Bloom Filters - http://prakhar.me/articles/bloom-filters-for-dummies/ http://prakhar.me/articles/bloom-filters-for-dummies/.

scrumper 11y ago
I preferred yours, but I'm not sure what you had for dinner on your last birthday.
- krat0sprakhar 11y ago
  Haha! What is that supposed to mean? :D
  - Nadya 11y ago
    You didn't include non-important life details when explaining what a bloom-filter is. >I sigh. I’m hungry and the main course has just arrived — venison glazed in honey, served with a sweet potato hash. I learned more about what the author had for dinner on their last birthday than I did about bloom filters in the first paragraphs. So while they prefer your blog - they aren't sure what you had for dinner on your last birthday...

jasode 11y ago

>To understand Bloom filters, you first have to understand hashing. As pedagogy, I think this is the wrong approach. The author already knows Bloom filters and therefore, it seems like the most logical thing to first talk about is hash functions because that's how it's implemented. Unfortunately, that's not how a person brand new to the concept thinks about it. The first thing to talk about is motivations and scenarios and use cases. For that, the first 2 paragraphs of wikipedia article[1] on Bloom filters is fairly straightforward. It explains why it's an interesting technique. Imo, those paragraphs are a better introduction than the author's dive right into "hash functions" immediately after unrelated blurbs of "I put my fork down" and "my wife shakes her head with a rueful smile." [1]https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter

dustingetz 11y ago
wow yes, this is an issue with nearly every technical conference talk
- ionforce 11y ago
  In my experience, more specifically with talks about functional programming techniques. I find them completely impenetrable.
baddox 11y ago
I'm fine with explaining the motivation first, but I struggle to see how you can explain bloom filters without eventually getting to hashing. Obviously you don't need to explain any actual real-world hash function, but you need to explain the concept of deterministically mapping X bits to Y bits where X > Y, which is essentially what a hash function does.
- FellowMarketer 11y ago
  I don't think at the level of the article that it's inappropriate to assume that the reader is at least familiar with the term "hashing", and can wait on the technical details of the particular types of hashing functions needed for bloom filters until the second or third section. I honestly just closed the article when he started in on hashing, because I want to know about bloom filters (which I don't know about), not the basics of hashing (which I learned as an undergrad, and need to know day-to-day as a working programmer).

shostack 11y ago

Anyone happen to have a great Bloom filter tutorial in Ruby geared towards early programmers? I read the article, but am still not grasping the full construct and how it functions. I'm hoping a hands on tutorial might give me a better sense.

bunderbunder 11y ago

I'm beginning to suspect that if I want to really drive a whack of traffic to my blog, I should write a post about how to implement Bloom filters using monads.

pizza 11y ago
Go for it.
ionforce 11y ago
Try it, see what happens. And then write a Hacker News article about it.
bshimmin 11y ago
For maximum impact, you'll need to choose your programming language carefully. I would suggest Elm with a sprinkling of Coq, though I think using either K or MUMPS would earn you a lot of kudos in some quarters.

bru_ 11y ago

Is anybody else irritated with the incredibly tryhard tone in this article? "venison glazed in honey, served with a sweet potato hash"? Seriously??? It's an article about bloom filters for god's sake, not Leveraged Sell Out for the tech industry...

jathu 11y ago
Much like most TED talks, this is in line with the common Medium article theme. The article becomes more about ME ME ME, rather than the subject at hand. It's like some Moses syndrome. When it comes to technical articles this starts to become extremely annoying to read blogs/papers as if it was written for BuzzFeed.
partisan 11y ago
I couldn't make it through. I was thinking about Bloom filters just earlier today and was actually looking forward to reading about them. I'll try again tomorrow with a different author.

halayli 11y ago

trying too hard. Just go to https://en.wikipedia.org/wiki/Bloom_filter https://en.wikipedia.org/wiki/Bloom_filter It's clearer and more informative.