Word-Aligned Bloom Filters
lemire.me
Word-Aligned Bloom Filters
1–10 of 82 posts
Re: Word-Aligned Bloom Filters
#2[deleted]
Re: Word-Aligned Bloom Filters
#3This 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.
Re: Word-Aligned Bloom Filters
#4This 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…
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)
Re: Word-Aligned Bloom Filters
#5This 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…
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.
Re: Word-Aligned Bloom Filters
#6This 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…
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).
Re: Word-Aligned Bloom Filters
#7This 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…
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.
Re: Word-Aligned Bloom Filters
#8I 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...
Re: Word-Aligned Bloom Filters
#9[deleted]
Re: Word-Aligned Bloom Filters
#10Earlier quoted context omitted.
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 fo…
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.