4 ms·
This seems a bit like a solution in search of a use case. There are simpler solutions for this particular usecase. Let's take an extreme case: You have 250 mil
by marginalia_nu 5y ago
This seems a bit like a solution in search of a use case. There are simpler solutions for this particular usecase.
Let's take an extreme case: You have 250 million paying customers you want to cache access to. Yeah, that's way more than you probably have, but the point is that you can keep 250 million integers in memory no problem what so ever. It fits in a gigabyte. There are raspberry pis with eight times that amount of RAM.
You can just put the ids in a sorted array and you can check for existence with a binary search without having to deal with false positives. Adding a bunch more is as easy as a merge of sorted lists, and removing items is a great deal easier than doing the same in a floom filter. You're looking at log_2(250 million) = 27 iterations. Cache-wise it's not great but it's faster than a database access by a mile and you don't have to worry about hash functions.
Maybe if you have several billion customers it starts to become a bit much to keep in memory, but that is a weird corner case indeed.
- ak39 5y agoWhy 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)
- marcosdumay 5y agoThis 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).
- marginalia_nu 5y agoI 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.
- hinkley 5y agoAnd 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.
- PragmaticPulp 5y agoObviously 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.
- marginalia_nu 5y agoI'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.
- spenczar5 5y agoI 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.
- marginalia_nu 5y agoThen we're indeed back in the territory of useful use cases, typically characterized by data that is far bigger than the system memory.
- gpderetta 5y ago
- k2xl 5y agoa 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.
- deleted 5y ago[deleted]
- bugzz 5y agoThe 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.
- bqmjjx0kac 5y agoI'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.
- pronoiac 5y ago> 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.
- sethev 5y agoI 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.
- kwillets 5y agoA Bloom filter with 1% FPR would fit in 285 MB and need 7 accesses per key.