[HN Gopher] Bloom Filters
___________________________________________________________________
Bloom Filters
Author : mfrw
Score : 226 points
Date : 2025-05-02 03:46 UTC (1 days ago)
(HTM) web link (eli.thegreenplace.net)
(TXT) w3m dump (eli.thegreenplace.net)
| noelwelsh wrote:
| Hash functions are kinda magic. Bloom filters are one of the fun
| tricks you can play with them (though Bloom filters themselves
| are quite old at this point; check the literature for various
| alternatives that are better in specific situations.) The field
| of data sketches and streaming algorithms has many others.
| k-Minimum values is a nice example of a set cardinality estimator
| that is very easy to understand.
| f_devd wrote:
| > check the literature for various alternatives that are better
| in specific situations
|
| For direct replacements, see Xor(+)-Filters:
| https://arxiv.org/abs/1912.08258 and the subsequent evolution
| into Binary Fuse Filters: https://arxiv.org/abs/2201.01174
| samuel wrote:
| Interesting, but not quite the same:
|
| _Xor and binary fuse filters require access to the full set
| of keys at construction time. In this sense, they are
| immutable. Alternatives have typically a fixed memory usage
| and a maximal capacity, but they also allow more flexibility
| such as progressive construction (adding keys one by one)._
| virexene wrote:
| I may have missed something when skimming the paper, but it
| sounds like Xor filters are constructed offline and can't be
| modified efficiently afterwards, whereas Bloom filters can be
| inserted into efficiently. So they don't seem to be an exact
| replacement
| f_devd wrote:
| No, you are correct. I misremembered with cuckoofilters.
| sparkie wrote:
| Also quite recent are Ribbon filters:
| https://arxiv.org/abs/2103.02515
|
| But these, and xor/binary-fuse-filters are only direct
| replacements for Bloom filters in some problems. There are
| still problems for which Bloom filters are a better solution.
|
| Bloom filters have the advantage that the filter produced by
| adding two elements, is the same as the bitwise-or of a pair
| of filters made by adding each element separately.
| bloom([x, y]) == bloom([x]) | bloom([y])
|
| Also, the filter produced by bitwise-and, `bloom([x]) &
| bloom([y])`, cannot have any bits set in it which are not
| also set by `bloom([x, y])`. We can assert that
| bloom([x]) & bloom([x, y]) == bloom([x]) bloom([y]) &
| bloom([x, y]) == bloom([y]) (bloom([x]) & bloom([y]))
| | bloom([x, y]) == bloom([x, y])
|
| There are practical applications that this can provide which
| are not satisfied by the "optimized" variants. The bitwise-or
| does set union (or least upper bound), and the bitwise-and
| does a set intersection (or greatest lower bound), though the
| filter produced by `bloom([x, y])` has a higher false
| positive rate than the filter produced by `bloom([x]) &
| bloom([y])`. bloom([x]) | bloom([y])
| == bloom([x, y])
| bloom([x]) bloom([y])
| bloom([x]) & bloom([y])
| f_devd wrote:
| Also based on Ribbon, the BuRR filters:
| https://arxiv.org/pdf/2109.01892 which seem to get very
| close to the theoretical optimum, 0.1%-0.5% overhead
| comparatively
| Snawoot wrote:
| Cuckoo filters are more efficient alternative. The algorithm of
| displacement is also very notable: how we can use random swaps
| to place data in cells optimally.
| londons_explore wrote:
| A whole load of data structures, like bloom filters, are
| 'efficiency tricks'.
|
| For example, "check if we might have Mr Smith's data cached by
| looking in this bloom filter". As Long as the answer is usually
| right, that's good enough.
|
| I do wonder if in the future we'll use a mini online-trained AI
| to achieve the same thing. "Ask the AI if we have MR Smiths data
| cached".
|
| Rather like you might ask an office clerk "Is Mr smith that
| troublesome customer you were dealing with last week? Do you
| still have his file on your desk?"
| nkrisc wrote:
| Why would that be better than a bloom filter (or similar)?
| chupy wrote:
| Because it has AI in it's name /s
| esafak wrote:
| The way that would work is that the LLM would translate that
| sentence into a tool call, which would query a data store that
| does the heavy lifting. Also, there is an ML task called
| "Learning to hash", which is about optimizing the hash for the
| task: https://learning2hash.github.io/
| ozgrakkurt wrote:
| There are actually "learned" bloom filters if anyone is
| interested in machine learning/bloom filter relation. but it is
| not related to chatbots
| hinkley wrote:
| I would imagine a heuristic to keep enough of the filter in L2
| cache to avoid pipeline stalls might be useful. Sort of a
| double bloom, but weighted for common lookups.
| thrance wrote:
| I've known about Bloom Filters for a while now, and I like the
| idea of them, but I've never had a need for them yet.
| speed_spread wrote:
| Good for you. Their main utility is in adtech and surveillance.
| okr wrote:
| Or, in general, all data intensive applications.
| OnlyMortal wrote:
| Such as deduplication.
| bobosha wrote:
| what are some real-world usecases that people use it for?
| gww wrote:
| They are used somewhat commonly in bioinformatics where lookup
| tables can have long keys and many entries [1].
|
| 1.
| https://en.m.wikipedia.org/wiki/Bloom_filters_in_bioinformat...
| leeoniya wrote:
| permission checks (allow/denylists)
| sparkie wrote:
| Using them for whitelists is probably not a great idea
| because they can give false positives. An attacker could
| potentially flood the filter with fake accounts and increase
| the rate of false positives, increasing the chance they're
| granted access.
|
| For blacklists, potentially more suitable, but since it can
| also give false positives, it could deny permission to people
| who should have it. An attacker might also attack this - by
| flooding the filter with accounts that deliberately get
| blacklisted, they could lock out people who should have
| access.
|
| Obviously this is very use-case specific - it's probably not
| the best approach to doing permissions if security is
| paramount.
| withinboredom wrote:
| No, but they can tell you a user is definitely _not_ in an
| allowlist or blocklist. That is useful, especially if it
| can save a database lookup on every check.
| sparkie wrote:
| That may work, but there are potential issues with that
| regarding timing attacks. If an attacker could make many
| attempts to access a resource, they may be able to figure
| out who (probably) has access with a brute-force timing
| test, and narrow down an attack target.
| withinboredom wrote:
| I'm not sure I understand. Generally, an allow-
| list/block-list is for authorized resources? By the time
| you are doing this check, the user is already
| authenticated and this is part of authorization. So, the
| user shouldn't be able to authenticate as arbitrary users
| to do a timing attack. If they can, you have bigger
| problems.
| nsteel wrote:
| https://devblogs.microsoft.com/devops/super-charging-the-git...
| andrewstuart wrote:
| Bloom filters can be extremely fast to tell you if something is
| not in a dataset.
|
| They can give false positives incorrectly indicating an element
| might be in the set when it's not, but never false negatives
|
| Knowing (fast) if something is not in a dataset can be very
| useful.
| withinboredom wrote:
| If you have a whole cluster of machines that have data on them
| and you need to ask: "does this machine probably have or not
| have this data?"; a bloom filter will tell you an answer. It
| can save a ton of time since a bloom filter's answer is
| "probably yes" and "definitely no."
| mfrw wrote:
| I like to think of it as a magical checklist, it helps us to
| quickly check if something _might_ be there, without actually
| looking through everything.
|
| A few non-exhaustive real world use-cases that come to mind:
|
| - Databases: To quickly check if a record might exist before
| doing a costly disk lookup.
|
| - Spell Checkers: To check if a word might be in the
| dictionary.
|
| - Spam Filters: To check if an email sender is on a list of
| known spammers.
|
| - Browser Security: Chrome uses Bloom filters to check if a
| site might be malicious.
|
| - Password Checker: To check if a password is known to be
| leaked.
|
| - Web Caches: To check if a URL or resource is definitely not
| in the cache.
|
| - Distributed Systems: To avoid sending data that another
| system definitely doesn't need.
| hinkley wrote:
| It's big for caches. As your application grows in complexity
| you get dependent lookups. I need the user id to get the
| company id. I need the company id to figure out what features
| the user has access to. And then I need to run a bunch of
| queries to pull data for those feature.
|
| And while using the cache may cut an order of magnitude off
| of the overall time, you've gone from hundreds of
| milliseconds to tens, but with a bloom filter you can figure
| out you have a cache miss faster and start the process of
| fetching the data sooner. The user may not notice the small
| improvement in response time, but by Little's Law your
| cluster size can be smaller for the same traffic.
|
| Web browsers use bloom filters to determine which CSS rules
| apply to which elements. IIRC Chrome removed a perf screen
| for CSS rules because most people were getting results below
| the noise floor for the timing function. The time to load the
| CSS was still relevant (maybe moreso due to the higher setup
| cost of the filters).
| thesz wrote:
| https://news.ycombinator.com/item?id=42486610
|
| Discussion of how Bloom filters made SQLite much faster.
| la_fayette wrote:
| Initially, Bitcoin light wallets were built with bloom filters.
| So a full node would only propagate transactions, which satisfy
| a bloom filter, given by light client to that light client. The
| bloom filter seems not to be privacy preserving, that was one
| reason why this was abondend by some wallets. However, bitcoinj
| and wallets built on top of it, might still use this...
| jeffparsons wrote:
| I recently discovered "compact approximators", which can be seen
| as a generalisation of Bloom filters. Instead of telling you
| "element X is probably in the set", they tell you "a lower bound
| on the value associated with key X".
|
| If there are no collisions, you get the true value. The data
| structure also doesn't "fill up" the way a Bloom filter does --
| the older data just gets probabilistically worse, so in some use
| cases you can keep using the one structure continuously.
|
| My particular use case (which led me to "invent" the structure
| and then discover that of course it's already been described in
| the literature, haha) is implicit cache invalidation. The
| approximator structure(s) store keys like "latest time member X
| was removed from group Y". I can then use that to lazily decide
| which cached values I can still use, instead of doing a
| potentially expensive search to see what I need to invalidate at
| the time the group member was removed.
|
| I'm new to using them, so I keep getting excited about new use
| cases -- much like when I was first introduced to Bloom filters.
| taneq wrote:
| Ooh, this seems like it could be useful for collision avoidance
| (where you need to know a lower bound to your time to impact.)
| abetusk wrote:
| Can you provide a link to a paper or reference?
| thomasmg wrote:
| This is described here: https://en.wikipedia.org/wiki/Bloom_f
| ilter#Compact_approxima...
| nyrikki wrote:
| While there are real use cases for the above, if you are
| looking at bloom filters make sure you check the above works
| for your need.
|
| First-order with least fixed point FO(LFP) == P As P=co-P but
| we think NP!=co-NP, bloom filters often have value for access
| to a small and fast path to co-NP
|
| In that case the collisions don't matter because often
| excluding membership is more valuable than proving membership
| and you have to choose one.
|
| That is why outlook used it to reduce address completion, even
| if a hit requires the expensive call to the server, the set of
| email addresses not in your address book is far larger.
|
| But it is all horses for courses.
|
| If your need does fit in P you have a lot of options, while the
| options for co-NP is far more rarified.
| thomasmg wrote:
| This is a bit similar to count-min sketch, which can be used to
| calculate frequencies in a stream.
|
| Also interesting are "Invertible Bloom Lookup Tables" (IBLT),
| https://arxiv.org/pdf/1101.2245 , which allow to add and remove
| data, and allow to retrieve the remaining data if "little" data
| remains. That means, it can be used for error correction: all
| all the _correct_ data (let's say 1 GB of correct data) into a
| 1 MB IBLT. Let's say a downloader finds that the checksum
| doesn't match: he can download that 1 MB IBLT, and remove the
| data from his (invalid) download. What remains is the delta:
| the error correction data. I know, there are other ways you
| could do error correction, but this is very fast, and quite
| interesting technically.
| nullc wrote:
| IBLT operates over sets though, your downloading example is
| not over a set (the data has a position). You can make it
| work over data with positions by adding a position number to
| every encoding unit, but it's pure overhead. Other codes are
| more efficient.
|
| IBLT is also particularly bandwidth inefficient when the
| amount of correction data is not very large. Ordinary codes
| can recover a missing block (known error location) with just
| the amount of data missing or with twice the amount if the
| location(s) are unknown.
|
| There are codes with quasi-linear performance, though for
| your example application the number of errors are few so it
| shouldn't really matter if the code is cubic in the number of
| errors to decode (which is about the worst any should be).
| thomasmg wrote:
| Yes, I know it is not designed to be a error-correction
| code, and other codes (turbo code, fountain code), are a
| lot more efficient. But I wanted to mention it because it's
| related to the topic.
|
| > You can make it work over data with positions by adding a
| position number
|
| Yes, that's what I did in my experiments. I personally
| found it really simple to implement; I'm not sure how easy
| it is to implement a "real" error correction code.
| nullc wrote:
| Fountain code is decoded by essentially the same
| mechanism, it's called peeling. It's quite fun to
| implement. Though a plain fountain code has similar
| bandwidth inefficiencies... also the implementations that
| exist only correct erasures (though you can turn errors
| into erasures using a checksum/mac).
|
| You can see the fountain code as a very sparse linear
| system that is usually solvable through a fairly simple
| greedy algorithm. You an augment the sparse linear system
| with a dense one like a RS code, which is solved by
| gauss-seidel which is also fun if less braindead simple.
|
| This github user has a whole host of different
| competently implemented very high performance erasure
| codes:
|
| https://github.com/catid/wirehair
| https://github.com/catid/leopard
| https://github.com/catid/fecal
| https://github.com/catid/siamese
|
| As far as direct error codes. There is a competent BCH
| code implementation in the Linux kernel, but it only
| works over small fields so it doesn't support many
| independent blocks/packets.
|
| Then there is https://github.com/bitcoin-core/minisketch
| which I am a coauthor of, which is a set corrector like
| IBLT which achieves perfect communications efficiency (at
| a trade off of cubic decode performance instead of linear
| but with good constant factors). I mention it mostly
| because it contains fast implementations of the relevant
| and tricky number theory algorithms needed for a fast RS
| error correcting code over big fields (any size up to
| 2^64 at least)... but I'm not actually aware of a
| performant large field RS error correcting
| implementation. (IIRC there is a RS error corrector in
| gnuradio but again small field).
|
| (Mostly the small field stuff doesn't work for bigger
| fields because they use a chien search to find the roots
| of a polynomial, which is linear in the field size.
| Minisketch finds roots by factoring in log(|field|) time.
| Root finding is needed in algebraic error codes because
| it's how you find where the errors are. IIRC the linux
| kernel BCH implementation uses factoring like we do but
| is constructed to use a log table to turn multiplications
| into xors.)
| kwillets wrote:
| That's an interesting reference. I came up with what may be a
| simpler case of that -- a structure that estimates the last
| time a key was seen. It's an upper bound, as collisions make
| the time more recent, but never the other way. Instead of a
| semi-order it's a simple ordering, but it may be similar to the
| compact approximator.
|
| Rate limiters apparently use count-min over a fixed time
| interval, which is bursty, but I took the same hash structure
| and came up with "timestamp-min" that allows even pacing (also
| without "fill up"). The one-sided error is also useful for
| checking if a cache entry is too old.
|
| It doesn't fix everything (eg DDOS), but it can prevent any
| single client from over-requesting, or stealing another
| client's requests (collisions can be made as hard as
| necessary).
|
| https://github.com/KWillets/RecencySketch
| andrewstuart wrote:
| Bloom filters - when I eventually learned about them - were
| nothing at all like what I had assumed from the name. And very
| interesting too.
| eimrine wrote:
| "Bloom's filter" that's a more correct name which doesn't let
| to make any assumptions.
|
| "Hashmap" - maybe a less correct name but it lets to make more
| correct assumption.
| celeritascelery wrote:
| The author says that with a 1.2GB bloom filter and 7 hash
| functions lookup is only 30ns. I have to assume this is because
| the cache has loaded all the benchmark values. My guess is that
| the benchmark is only testing a few elements. In real world
| scenarios with a bloom filter this big most of those 7 hash
| lookups will be into cold cache since 1.2 GB is too large. That
| means lookups are much longer than 30ns. Probably still faster
| than going to network or database though.
| returningfory2 wrote:
| This is the benchmark they wrote:
| https://github.com/eliben/code-for-blog/blob/7278526923168d2...
|
| The benchmark alternates between ~1 million different keys to
| check in the filter, explicitly to account for cache effects.
| Tuna-Fish wrote:
| A single lookup is going to take more than 30ns, the reason
| they only see that is that the OoO machinery of their CPU is
| good enough to run those lookups in parallel.
| Tuna-Fish wrote:
| Yes, 30ns means it's in cache. But bloom filters are
| surprisingly fast for the amount of lookups they do, because
| they all happen in parallel and there is a lot of parallelism
| in modern memory subsystems, so that you essentially only pay
| the cost of a single random read for the entire lookup. If
| using 1GB pages, you can still realistically talk about <100ns
| lookups.
| bjornsing wrote:
| > so that you essentially only pay the cost of a single
| random read for the entire lookup
|
| Why would you ever pay more than that for a bloom filter
| lookup? I mean, I don't see how that has anything to do with
| parallelism in memory subsystems. But I may be missing
| something.
| Tuna-Fish wrote:
| A bloom filter needs to multiple loads from different
| memory locations for each single lookup. (7, in the example
| 1.2GB filter.) But unlike, say, with a tree, it knows all
| the addresses after computing the hashes, without having to
| wait for results from the previous loads. So it can start
| all of them in parallel.
| eliben wrote:
| Updated the result to 80ns - thanks for flagging this. This
| grows with the size of the data (because more cache misses),
| and running the benchmark on the full billion takes a while.
|
| [That said, on a hot production bloom filter, much can be
| loaded into caches anyway so it's not an entirely un-realistic
| scenario that some of these are cache hits]
| esafak wrote:
| Available in Redis: https://redis.io/docs/stack/bloom/
| gitroom wrote:
| pretty cool seeing how stuff like this keeps getting new uses - i
| always wanna tinker with these things but never have the right
| problem yet tbh
| ozgrakkurt wrote:
| Would recommend reading rocksdb implementation of bloom filter
| and ribbon filter to anyone wanting learn more about the
| production level implementation side. It is extremely well
| explained in the comments and is the state of the art
| implementation as far as I know.
|
| https://github.com/facebook/rocksdb/blob/main/util/bloom_imp...
|
| https://github.com/facebook/rocksdb/blob/main/util/ribbon_al...
| almostgotcaught wrote:
| These are the kinds of comments that I write when I work really
| hard (and very long) on a PR and I know no one will really dig
| into it (kind of like "well at least I committed the findings
| to posterity").
| econ wrote:
| If you keep at it someone someday will be blown away.
| almostgotcaught wrote:
| Nah ain't no one got time for that - and I don't blame
| anyone either (not like I was read other people's
| comments).
| fooker wrote:
| Here's my use case for it: I want really small filters (say 64
| bits or 128 bits), and use these to represent 50-100 element
| subsets of a ~1000-2000 element set.
|
| I know with a traditional bloom filter this would give me a lot
| of false positives. Is there an alternative that would fare
| better ?
| thomasmg wrote:
| Well, what problem do you want to solve? What you describe is
| not a use case but a possible solution... this smells like an
| xy problem...
| fooker wrote:
| The problem is:
|
| Represent (possibly overlapping, hence trees are tricky)
| subsets of size 50-100 out of a set of size of size
| 1000-2000.
|
| Some amount of false positives is acceptable but not like
| 50%.
| thomasmg wrote:
| So, for this it sounds like you only need one Bloom filter
| (not multiple), and each subset is an _entry_ in the
| filter. The total set size doesn't matter; what matters
| (for the size of the Bloom filter) is the total number of
| entries you put into the Bloom filter, and the false
| positive rate. And then, you can do a membership test (with
| a configurable false positive rate, typical is 1%), to find
| out if an entry is in the set. BTW you can not use Bloom
| filters to store and retrieve entries: for that, you need
| something else (an array, or hash map, or a retrieval data
| structure; Bloom filter can't be used).
| aranw wrote:
| Sam Rose has also written a great article on Bloom Filters and
| has some great animations to help illustrate it too. Definitely
| worth checking out https://samwho.dev/bloom-filters/
| Const-me wrote:
| There's a useful but non-obvious property of these filters.
|
| If you have two Bloom filters which use same set of possible keys
| and same filter setup, you can compute intersection of their
| represented sets with a bitwise AND operation over the bitsets in
| these filters.
|
| If you store bitsets aligned and padded by SIMD vector size (for
| example, an array of __m128i in C++ as opposed to the array of
| uint64 values in the golang example), computing such intersection
| is very efficient on modern computers.
|
| I once used that technique to filter 3D objects from a large set
| using the intersection of 3 range queries, one per coordinate.
| Compute two Bloom filters filled with the objects returned by X
| and Y queries, intersect the filters, then iterate over the
| objects returned by the remaining Z query testing against the
| intersected Bloom filter. Due to probabilistic nature of the
| Bloom filter you still need to test for X and Y queries for the
| objects tested positive by the filter, however with proper setup
| the filter should reject vast majority of them.
| ChuckMcM wrote:
| That's pretty clever. In my 3D experiments I always struggled
| with minimizing the number of objects in the world I had to
| consider for rendering on each frame based on the
| view/fog(range). This seems like it would help with that.
| undefuser wrote:
| Have you tried using Quad Tree?
| ChuckMcM wrote:
| Yes! There was a great Graphics Gems article on
| implementing quad trees. The things that change are the
| sheer number of things you might have in your environment.
| econ wrote:
| From what I understand bloom filters have a hash per item but
| when i invented (hah) them I used a bit array for each property
| where each bit describes an item at the same offset. When
| searching for some properties one can do an AND on those entire
| arrays and eliminate candidates really fast.
| klaussilveira wrote:
| You can even use Bloom Filters for rate limiting with counting
| BF:
|
| https://github.com/FastFilter/fastfilter_cpp/blob/f27873fac4...
| thomasmg wrote:
| Yes, this is the succinct counting blocked Bloom filter I
| wrote. I wanted to write a paper about it. It requires twice
| the space of a blocked Bloom filter (which is about half the
| space of a regular counting Bloom filter). Reads are very fast,
| and updates are okish.
| klaussilveira wrote:
| Well, thank you for that! That library has taught me a lot.
| :)
| redbell wrote:
| Related: https://news.ycombinator.com/item?id=42293832
|
| Also, this -somehow- related _Ask HN_ is a true classic, at least
| for me: https://news.ycombinator.com/item?id=32186203
___________________________________________________________________
(page generated 2025-05-03 23:02 UTC)