Word-Aligned Bloom Filters • Hacker News Board

Re: Word-Aligned Bloom Filters

#21

Post by marginalia_nu » Sun, Oct 03, 2021, 5:01 PM UTC

spenczar5 wrote: post #14

marginalia_nu wrote: post #11

Earlier quoted context omitted.

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 eas…

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…

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

Re: Word-Aligned Bloom Filters

#22

Post by Gh0stRAT » Sun, Oct 03, 2021, 5:01 PM UTC

marginalia_nu wrote: post #11

PragmaticPulp wrote: post #7

Earlier quoted context omitted.

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 eas…

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.

Re: Word-Aligned Bloom Filters

#23

Post by la_fayette » Sun, Oct 03, 2021, 5:05 PM UTC

marginalia_nu wrote: post #11

PragmaticPulp wrote: post #7

Earlier quoted context omitted.

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 eas…

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

Re: Word-Aligned Bloom Filters

#24

Post by rattlesnakedave » Sun, Oct 03, 2021, 5:11 PM UTC

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

You want to check if an element is probably in a dataset. You want speed, and the possibility of a false positive doesn’t scare you that much.

Say you want to lookup if a username is in a database. That could take a while if you have a really large db of usernames, but you want to tell a user quickly if a name is taken.

So what you can do is make a bloom filter, which is basically just an array of bits of n length. Let’s say 10 for our example.

Then gather some hash functions (h1, h2, and h3).

When someone inputs a username, you run it through the hash functions, and modulo by the number of bits, and get an integer result.

So:

h1(“rattlesnakedave”) % 10 = 3 h2(“rattlesnakedave”) % 10 = 7 h3(“rattlesnakedave”) % 10 = 2

Then you check the bits at position 3,2, and 7 in the array.

If they any of the bits are set to 0, we haven’t seen the username before.

If they’re all set to 1, we have possibly seen the username before.

Let’s say they’re all set to 0, so we probably haven’t seen it. We can present the message that the username is available, and allow registration. During registration, we can do a slower more expensive verification that the username isn’t actually in the dataset.

Now that the username is in the dataset, we can flip the bits on our bloom filter at position 3,2, and 7 to 1. So the next time we lookup that username we can tell quickly that it’s probably taken.

There is no way to delete from the bloom filter. The more values you store relative to its size, the more false positives you get.

Hopefully that makes sense, and is correct.

Re: Word-Aligned Bloom Filters

#25

Post by Taywee » Sun, Oct 03, 2021, 5:14 PM UTC

rattlesnakedave wrote: post #24

lelandfe wrote: post #12

At the risk of finally exposing myself as an impostor, does anyone have a good link for an explanation of bloom filters? I’ve tried, unsuccessfully, to wrap my head around the concept before, and this article seems really interesting!

You want to check if an element is probably in a dataset. You want speed, and the possibility of a false positive doesn’t scare you that much. Say you want to lookup if a username is in a database. That could take a while if you have a really large db of usernames, but you want to tell a user quickly if a name is taken. So what you can do is make a bloom filter, which is basically just an array of bits of n length. L…

Not exactly correct. If all of the bits is 1, then the value is possibly in the set (not "probably", but "possibly", with the likelihood being affected by the sizes of the set and the array).

If any of the bits is zero, the value definitely isn't in the set (also not "probably haven't", but definitely not).

Re: Word-Aligned Bloom Filters

#26

Post by bugzz » Sun, Oct 03, 2021, 5:16 PM UTC

marginalia_nu wrote: post #3

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 amou…

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.

Re: Word-Aligned Bloom Filters

#27

Post by rattlesnakedave » Sun, Oct 03, 2021, 5:20 PM UTC

Taywee wrote: post #25

rattlesnakedave wrote: post #24

Earlier quoted context omitted.

You want to check if an element is probably in a dataset. You want speed, and the possibility of a false positive doesn’t scare you that much. Say you want to lookup if a username is in a database. That could take a while if you have a really large db of usernames, but you want to tell a user quickly if a name is taken. So what you can do is make a bloom filter, which is basically just an array of bits of n length. L…

Not exactly correct. If all of the bits is 1, then the value is possibly in the set (not "probably", but "possibly", with the likelihood being affected by the sizes of the set and the array). If any of the bits is zero, the value definitely isn't in the set (also not "probably haven't", but definitely not).

Good catch! Thank you.

Was trying to keep the initial explanation simple by leaving out the false positives scaling relative to the size of the array and set, and then clarifying at the end.

The second part (any 0 bits it hasn’t been seen) is true, a goof up on my part.

Re: Word-Aligned Bloom Filters

#28

Post by sethev » Sun, Oct 03, 2021, 5:24 PM UTC

marginalia_nu wrote: post #3

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 amou…

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.

Re: Word-Aligned Bloom Filters

#29

Post by marginalia_nu » Sun, Oct 03, 2021, 5:25 PM UTC

Gh0stRAT wrote: post #22

marginalia_nu wrote: post #11

Earlier quoted context omitted.

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 eas…

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…

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%.

Re: Word-Aligned Bloom Filters

#30

Post by blondin » Sun, Oct 03, 2021, 5:28 PM UTC

Rendello wrote: post #8

I find these optimizations fascinating. Anyone familiar with Lemire likely knows about this, but I listened to a podcast episode[1] with him a few days ago and learned about `simdjson`, the tool he authored that parses JSON at 25x the speed of the standard C++ library.[2][3] It's worth looking at if you're into this sort of thing. 1. https://corecursive.com/frontiers-of-performance-with-daniel... 2. https://www.youtu…

yep, great fan of his work here. thanks for sharing that podcast.

that kind of optimization requires you to know your machine architecture quite well. SIMD optimizations aren't new. but it's always amazing to see these performance increases on a single machine!

our CPUs and GPUs are quite amazing. we have decided, as a field, that we can get enough virtual CPUs, GPUs, or RAM on-demand. and that we shouldn't concern ourselves with things happening at that level.

it's actually a situation that saddens me sometimes.