Hacker News Reader

The main use case I've always seen is to use bloom filters on the client side to reduce traffic to the server looking things up. As you said, you could cache 250 million integers in a gigabyte - but you don't want to bloat your client side implementation by a gigabyte for every bloom filter you use. Also, many times the items are a lot larger than an integer. For example, storing a list of malicious URLs, a common use case.

I'm so confused by this use case (the traffic-saving one, not the malicious URL classifier). Why not store the "is-paying-customer" bit in a cookie?

What are we using as the user identifier? Where does it come from, if not a cookie?

Also, this client-side bloom filter kind of leaks your user database, supposing it's keyed on email addresses and your adversary has a gigantic list of email addresses, or is patient enough to enumerate them.

> Why not store the "is-paying-customer" bit in a cookie?

You shouldn't trust the client. You probably don't want people to get access to paid features with a relatively easy tweak of cookies.

The client-side filter is more suitable for listing, say, malware URLs, as mostly the response is "no" (go ahead) instead of "maybe", which would require a bit more work (like, network requests) to check if it's blocked or not.

I think you missed the point of the example. Lemire's example isn't "the use-case" for this optimization, it's just a trivial motivating example. The use-case is more like, "assume you're currently using a Bloom filter in an appropriate context, here's a way that might be more efficient".

The point of the post is the optimization technique, not trying to describe when a Bloom filter would be appropriate.

Obviously you don't need bloom filters if lookups are cheap, but you're ignoring all of the cases where lookups aren't cheap.

You can't always put the entire database of everything in memory. Consider cases where the check is done client-side and requires a network request. A bloom filter could allow you to optimize away a network request in some, though not all, cases.

I'm curious if you have a concrete example of a case where lookups aren't cheap and a bloom filter can solve the problem.

In general, bloom filters are mainly useful for the sort of data where lookups are cheap, that is, testing for membership of a set, and that is typically one of the operations a database does really well.

In most cases where you just want to save a network roundtrip, a LRU cache is often a lot easier to get right and is much easier to keep consistent against mutable data.

I use them in astronomical data indexing when doing cross-match searches. That is, “could there be a star or other moving object in within 0.5 arcsec of this point in the sky?” Sky catalogs have many billions of objects but the density per solid angle of the sky is extremely variable, and moving objects also make lookups really complicated. Sky catalogs are big enough that they are not storable in memory, and may be in big Parquet tables on the network, so the full lookup is quite expensive.

Bloom filters are great for this because the backing dataset changes extremely slowly, like a few times a year when a survey publishes a new data release.

Then we're indeed back in the territory of useful use cases, typically characterized by data that is far bigger than the system memory.

Bloom filter generally are much smaller than the data they represent. So if your set fits on disk, the bf might fit in ram; if your data fits in ram, your bf might fit in L3 and so on.

Edit: in particular you might want to use bloom filters fir early rejects, when most of the set ownership queries are expected to fail.

What about https://developers.google.com/safe-browsing?

In the normal case, when a website is not matched by the filter, you save a network request. This is good for both latency and privacy.

Imagine you're making a web browser plugin that blocks ads, or malicious sites. Let's assume the blocklist is a hundred megs (easily fits in ram) and your millions of users need to get the latest data at least hourly in order to keep up with the latest URLs that you want to block.

Rather than distributing the entire blocklist to your userbase, you can instead send a bloom filter + an allowlist of the small handful of sites which have a hash collision with one of the blocked sites.

As a bonus, computing the hashes will have great branch prediction characteristics and you'll have fewer cache misses because the bloom filter is tiny and frequently accessed, so your plugin will not add any perceptible slowdown to the user's experience.

Couldn't you just send deltas if that is the case? Surely the hourly updates wouldn't be hundreds of megabytes? I just tested extracting 5 million URLs from my web crawler and it was like 150 Mb in plain text. That's ignoring how easy it is to create compression schemes for URLs that slash their memory footprint by something like 80%.

Yes, you could do it with deltas instead. The tradeoffs are that it won't be as fast and will cost you a LOT more in bandwidth. (and cost your users more bandwidth as well. They might be on a very slow/limited data plan) Maybe you don't care about bandwidth and would prefer to avoid the complexity and maintenance overhead of adding a bloom filter.

As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently.

As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it.

> As engineers, it's our job to weigh the tradeoffs between different solutions given the resources and constraints of the situation. For the situation I've outlined above, I'd at least strongly consider a bloom filter but it's certainly not the only way to do it.

We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are. Due to the nature of hashing, you won't be able to easily come up with a list of false positives. Finding just one hash collision in a wide hash is computationally stupidly hard.

> As with anything, there are tradeoffs and your requirements can change over time. Maybe the ad networks or malware creators start using new domains every 10 minutes to counter your blocking system so now you have to store more data and disseminate it more frequently.

Domains cost quite a lot of money so that is still pretty unrealistic. Sure you can have CN wildcards, but you can also do wildcard matching.

Actually this whole scenario is unrealistic, since you can just serve ads off a random URL. The way you would create a decent ad filter is to look for characteristics in the script itself (a bit like an antivirus program), not base it off the URL.

> We should also not gloss over that with a bloom filter can't rule out false positives, and it's really not feasible to figure out which they are.

Nothing says a bloom filter has to be the only data structure you use. It's a performance optimization; even if 1% of the time you have to consult a more expensive data structure to confirm your result, it can still save you a lot of computation in the long run.

> Finding just one hash collision in a wide hash is computationally stupidly hard.

But bloom filters don't use wide hashes; the domain of the hash function is the number of bits in the filter.

> Domains cost quite a lot of money so that is still pretty unrealistic.

In the case of malware, the cost of buying domains isn't that relevant, because you can compromise existing domains using automated attacks.

Additionally, this method avoids you having to distribute a list of dubious sites to your users.

Bitcoin light wallet addresses are registered with bloom filters on full nodes.

Why wouldn't "isPayingCustomer" not be part of the Customer object graph immediately after logging in to begin with? (Maybe I didn't understand the use case properly)

This is a very bad example, but the underlying concepts are useful.

It's more realistic if you are storing a set of revoked access keys or altered files on your cache that you subscribe from some channel that is not on your main request - database - response loop.

Normally you won't ever need to store many of those until they reach the expiration time or you update you cache, and you will want a lot of performance for the common case (what the small memory requirements help ensuring).

I think fundamentally bloom filters are mainly useful for astronomical data sizes. If you have a petabyte of data partitioned between several datacenters, and you want to know which shards have entries with certain properties, bloom filers are amazing. A bloom filter that is just a few dozen megabytes can save you an enormous amount of computation in such a scenario.

To cache network requests it really isn't that great. A basic LRU cache typically performs just as good, and is a lot easier to get right.

a good use case is malicious URL detection for browsers. they can look up locally and get a sense whether the url is bad and then double check against webserver.

And you can consistent hash your way out of that problem by having two servers for each customer ID.

But I think the bigger problem is figuring out if John Smith is already in our system, and IDs don’t help here.

A Bloom filter with 1% FPR would fit in 285 MB and need 7 accesses per key.