Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bloom filters are good for search that does not scale

notpeerreviewed.com

Post reply on HN
Print view View original

21–30 of 43 posts

Re: Bloom filters are good for search that does not scale

#21

Post by hinkley »

UltraSane wrote: post #18
susam wrote: post #5

When I worked at RSA over a decade ago, we developed Bloom filter-based indexing to speed up querying on a proprietary database that was specialised for storing petabytes of network events and packet data. I implemented the core Bloom filter-based indexer based on MurmurHash2 functions and I was quite proud of the work I did back then. The resulting improvement in query performance looked impressive to our customers.…

Splunk uses bloom filters to make searching for rare events fast. Rare events are usually the most interesting.

I’ve only used Splunk with one set of devs and maybe we were doing it wrong, but it didn’t feel fast to me.

Several of us were working hard to move everything into Prometheus that made any sense to be in Prometheus instead of Splunk.

Notably any time we had a production issue that it was unclear which team was responsible, Splunk became the bottleneck because we started exceeding quotas immediately.

Re: Bloom filters are good for search that does not scale

#22

Post by hijinks »

philipkglass wrote: post #19
hijinks wrote: post #12

is there a better way then bloom filters to handle needle in the haystack type searches where the haystack might be terabytes of data and you only want a few lines?

There are a lot of "better than Bloom" filters that work similarly in some aspects. I have used Cuckoo [1] and Ribbon [2] filters for Bloom-type applications. If you have an application where you do a lot of one kind of searching, it may also be worth implementing a specialized variant of a data structure. I needed a Cuckoo-type filter on the JVM but only for 64 bit integers and I was able to make a smaller, faster c…

thanks.. i'll read up into these.. always amazes me that companies like datadog somehow made log search quick

Re: Bloom filters are good for search that does not scale

#23

Post by hinkley »

6510 wrote: post #9
susam wrote: post #5

When I worked at RSA over a decade ago, we developed Bloom filter-based indexing to speed up querying on a proprietary database that was specialised for storing petabytes of network events and packet data. I implemented the core Bloom filter-based indexer based on MurmurHash2 functions and I was quite proud of the work I did back then. The resulting improvement in query performance looked impressive to our customers.…

I'm not an expert at all, I learn they exist after making something similar to search a few thousand blog posts. Rather than one hash per file I made a file for each 2 letter combinations like aa.raw, ab.raw, etc where each bit in the file represents a record. (bit 0 is file 0 etc) you could ofc do 3 or 4 letters too. A query is split into 2 letter combinations. 1st + 2nd, 2nd + 3rd, etc the files are loaded, do a bi…

I had a problem where we needed to compare large data sets between machines for keys that existed in both, and the bandwidth cost just wasn’t mathing for the median result set size. I was trying to figure out how to send a fingerprint from machine A to B, then have machine B send the hits back. Or how many round trips I could do based on set size to minimize bandwidth + latency. I ended up with a calculus problem nobody could help me solve because of an n^5 term.

My boss was generally pretty good with obscure data structures but neither of us had encountered Bloom filters. This was about three years after Google published their paper on how they were using Bloom filters, but that company would be bankrupt before I figured it out.

Re: Bloom filters are good for search that does not scale

#24

Post by taeric »

I will forever think of Bloom filters as "bouncer filters." Could go with concierge filter. Basically, it is the equivalent of every movie where the detective is asking the front desk various attributes of who they are looking for.

It is not hard to see how you could start asking the front desk to track every obscure attribute and to expect to fall over for various reasons.

Re: Bloom filters are good for search that does not scale

#25

Post by hinkley »

philipkglass wrote: post #19
hijinks wrote: post #12

is there a better way then bloom filters to handle needle in the haystack type searches where the haystack might be terabytes of data and you only want a few lines?

There are a lot of "better than Bloom" filters that work similarly in some aspects. I have used Cuckoo [1] and Ribbon [2] filters for Bloom-type applications. If you have an application where you do a lot of one kind of searching, it may also be worth implementing a specialized variant of a data structure. I needed a Cuckoo-type filter on the JVM but only for 64 bit integers and I was able to make a smaller, faster c…

I wonder how often in the wild people are tuning for a 1% false positive rate versus a much lower one, like .1%. You do quickly reach data set sizes where even 1% introduces some strain on resources or responsiveness.

Cuckoo claims 70% of the size of bloom for the same error rate, and the space is logarithmic to the error rate. Looks like about 6.6 bits per record versus 9.56 bits for bloom at 1%. But at .5% error rate a cuckoo is 7.6 bpr. In fact you can get to about a .13% error rate for a cuckoo only a hair larger than the equivalent bloom filter (n^9.567 = 758.5)

Re: Bloom filters are good for search that does not scale

#26

Post by hinkley »

pi_22by7 wrote: post #14

The key insight about bloom filters lacking synergy is excellent. The ~7K document crossover point makes sense because inverted indexes amortize dictionary storage across all documents while bloom filters must encode it linearly per document

But doesn’t that depend on the cardinality of the indexes versus the document count? I’ve seen systems with a stupid number of tag values.

Re: Bloom filters are good for search that does not scale

#27

Post by UltraSane »

hinkley wrote: post #21
UltraSane wrote: post #18

Earlier quoted context omitted.

Splunk uses bloom filters to make searching for rare events fast. Rare events are usually the most interesting.

I’ve only used Splunk with one set of devs and maybe we were doing it wrong, but it didn’t feel fast to me. Several of us were working hard to move everything into Prometheus that made any sense to be in Prometheus instead of Splunk. Notably any time we had a production issue that it was unclear which team was responsible, Splunk became the bottleneck because we started exceeding quotas immediately.

Splunk is one of the best software I've ever used but it HAS to be used with very fast storage to be effective. I've only used it on enterprise grade storage arrays and servers with lots of RAM for caches. On modern PCIe 5.0 NVMe drives it is stupid fast.

I'm not sure what you mean by exceed quotas because Splunk is normally licensed on GB ingested per day. This can lead to bitter fights between teams over how this is allocated.

The good thing about this license model is that you can use as much hardware as you want for no extra license cost.

Re: Bloom filters are good for search that does not scale

#28

Post by hinkley »

UltraSane wrote: post #27
hinkley wrote: post #21

Earlier quoted context omitted.

I’ve only used Splunk with one set of devs and maybe we were doing it wrong, but it didn’t feel fast to me. Several of us were working hard to move everything into Prometheus that made any sense to be in Prometheus instead of Splunk. Notably any time we had a production issue that it was unclear which team was responsible, Splunk became the bottleneck because we started exceeding quotas immediately.

Splunk is one of the best software I've ever used but it HAS to be used with very fast storage to be effective. I've only used it on enterprise grade storage arrays and servers with lots of RAM for caches. On modern PCIe 5.0 NVMe drives it is stupid fast. I'm not sure what you mean by exceed quotas because Splunk is normally licensed on GB ingested per day. This can lead to bitter fights between teams over how this i…

> used with very fast storage

That’s sounds like self hosting. Which is not the only product they offer. But you still have hardware that can only run so many queries at once and then starts queuing any additional request, yeah? Once you have a dozen people on a call it went to shit. Only occasionally ran into problems like this with graphite. But you need a lot of people looking at a very large dashboard to start feeling refresh delays.

Re: Bloom filters are good for search that does not scale

#30

Post by hinkley »

adamzwasserman wrote: post #13

The "no sharing between filters" insight clicked for me on a different problem. I needed to filter items by tags. Bloom filter per item seemed clever - quick membership checks. But with thousands of items sharing dozens of tags, each filter re-encodes the same vocabulary. Pure waste. Switched to an inverted index (tag → item list) with bloom filters per chunk of the index. Now the tag vocabulary is shared, and bloom…

Why do these “inverted indexes” just look like indexes to me? Too much time with databases perhaps?
Post reply on HN