4 ms·

How do you use a bloom filter? Because that's never been a limitation in my use cases. The only times I've really needed them is when I needed to know a db row

by lugged 5y ago

How do you use a bloom filter? Because that's never been a limitation in my use cases. The only times I've really needed them is when I needed to know a db row has been updated in this import run. (Can't fit hash in memory, updates happen in batch/async so writes haven't been made yet) I.e. basically using it for dedupe

mungoman2 5y ago
The article mentions using it for indicating which things are in a cache. Not being able to delete entries seems like a severe limitation to effectiveness over time, as false positives increase.
- natch 5y ago
  Use n copies of the filter staggered in time. Start one on first day/hour/some-time-unit, then on next tick of time unit start a new one. The one started on day 2 lacks the entries from day 1. For checking, only use the oldest one. On the nth day, as you are making yet another one, discard the oldest one and the second oldest one becomes the new oldest one. The oldest one always has n time units of data in it.
  - mungoman2 5y ago
    That's clever! You can use this trick to effectively make items expire and be removed after a set time. But it makes the whole thing more complicated with parameters that need tuning, and no longer the simple and powerful things that bloom filters are sold as.
- toast0 5y ago
  If you count false positives, you can recreate your filter when you get a specific count of false positives. If you also count true positives, you can recreate the filter when the ratio between true and false positives hits some number. Still needs tuning though, depends on how costly it is to generate (and transfer, if needed) vs how costly a false positive is.
- thomasmg 5y ago
  If you need the ability to remove entries, then I would consider the counting Bloom filter (which is simpler, but needs more space), and the cuckoo filter. But you do need to be a bit careful as both can overflow if you are unlucky, or if you add too many entries. In which case you would have to re-build them. So better be prepared for this case, or prevent overflowing the filters by using a cascade of filters. Some clever cache implementations internally use special kinds of Bloom filters, e.g. the Caffeine cache (Java) uses TinyLFU, which "builds upon Bloom filter theory" (from the abstract of the paper): https://github.com/ben-manes/caffeine https://github.com/ben-manes/caffeine and https://arxiv.org/pdf/1512.00727.pdf https://arxiv.org/pdf/1512.00727.pdf
- masklinn 5y ago
  Lots of caches don’t need precise invalidation, either because they have a short lifespan (e.g. request-bound) or because the removals are so rare it’s not that expensive to blow the entire cache in the grand scheme of things.

by lugged 5y ago

mungoman2 5y ago

The article mentions using it for indicating which things are in a cache. Not being able to delete entries seems like a severe limitation to effectiveness over time, as false positives increase.

natch 5y ago
Use n copies of the filter staggered in time. Start one on first day/hour/some-time-unit, then on next tick of time unit start a new one. The one started on day 2 lacks the entries from day 1. For checking, only use the oldest one. On the nth day, as you are making yet another one, discard the oldest one and the second oldest one becomes the new oldest one. The oldest one always has n time units of data in it.
- mungoman2 5y ago
  That's clever! You can use this trick to effectively make items expire and be removed after a set time. But it makes the whole thing more complicated with parameters that need tuning, and no longer the simple and powerful things that bloom filters are sold as.
toast0 5y ago
If you count false positives, you can recreate your filter when you get a specific count of false positives. If you also count true positives, you can recreate the filter when the ratio between true and false positives hits some number. Still needs tuning though, depends on how costly it is to generate (and transfer, if needed) vs how costly a false positive is.
thomasmg 5y ago
If you need the ability to remove entries, then I would consider the counting Bloom filter (which is simpler, but needs more space), and the cuckoo filter. But you do need to be a bit careful as both can overflow if you are unlucky, or if you add too many entries. In which case you would have to re-build them. So better be prepared for this case, or prevent overflowing the filters by using a cascade of filters. Some clever cache implementations internally use special kinds of Bloom filters, e.g. the Caffeine cache (Java) uses TinyLFU, which "builds upon Bloom filter theory" (from the abstract of the paper): https://github.com/ben-manes/caffeine https://github.com/ben-manes/caffeine and https://arxiv.org/pdf/1512.00727.pdf https://arxiv.org/pdf/1512.00727.pdf
masklinn 5y ago
Lots of caches don’t need precise invalidation, either because they have a short lifespan (e.g. request-bound) or because the removals are so rare it’s not that expensive to blow the entire cache in the grand scheme of things.