[HN Gopher] When Bloom filters don't bloom (2020)
___________________________________________________________________
When Bloom filters don't bloom (2020)
Author : tosh
Score : 45 points
Date : 2024-09-10 16:18 UTC (6 hours ago)
(HTM) web link (blog.cloudflare.com)
(TXT) w3m dump (blog.cloudflare.com)
| hinkley wrote:
| > For example, source IPs belonging to a legitimate Italian ISP
| should not arrive in a Brazilian datacenter.
|
| You sure about that?
|
| If the entire network is healthy. Yes, and maybe by two(?)
| transatlantic cables is not the efficient way to serve a page.
| NYC is probably closer to Italy by network topology than is
| Brazil.
|
| But if CF had a data center in Italy and one in Germany, there
| are very valid reasons for Italian traffic to end up in Germany.
| Like a grid failure, flooding. Or fire. So how far you can take
| this and still meet SLAs is a little tricky.
| limit499karma wrote:
| aside: reading that made me wonder just which of Google vs
| Cloudflare knows everything about everyone's web accesses.
| majke wrote:
| Of course it's not that simple. This "IP address pop catchment"
| thing is an area of active research. Even we do weird things,
| like: https://blog.cloudflare.com/cloudflare-servers-dont-own-
| ips-...
| the_gorilla wrote:
| I'm not really convinced by this article. His complaint is that
| bloom filters are too slow for his purpose, and the cause is the
| large memory requirements and random memory accesses causing
| constant cache misses. So, he has 40 million lines and 600 MB of
| data and it takes 12 seconds for his bloom filter to work. I'd
| have to dig into it a lot more but my instincts are telling me
| this is user error because these numbers don't really make sense
| even on older hardware.
| bborud wrote:
| Did you try to repeat the experiment?
| limit499karma wrote:
| > "64 GiB of memory" & "1-error-per-10k" entries.
|
| That's the size of the BF that gives that error rate (per his
| calcs - didn't check). So that definitely busts the cache.
| the_gorilla wrote:
| I didn't say it would fit in the cache.
| majke wrote:
| Random memory access is really slow (compared to CPU speed).
| Therefore it's strictly faster to do exactly one random memory
| fetch (hashtable) than many (bloom filter).
| chuckadams wrote:
| I wonder how the final version with the single hash table stacks
| up against: cat file.txt | perl -ne 'print
| unless $x{$_}++'
| thomasmg wrote:
| The Bloom filter he uses has k=8, that is 8 cache line misses per
| entry. (k=8 is in the command line output). A "blocked Bloom
| fiter" requires only one cache line miss per entry, with a
| slightly worse false positive rate.
|
| With a good implementation it would be roughly 10 times faster,
| eg a SIMD implementation. For example here
| https://github.com/FastFilter/fastfilter_cpp/blob/master/src...
| (there are others)
| majke wrote:
| Thanks for the pointer. The file comment says:
| // This is a block Bloom filter (from Putze et al.'s "Cache-,
| Hash- and Space-Efficient Bloom Filters") with some twists:
| // 1. Each block is a split Bloom filter - see Section 2.1 of
| Broder and Mitzenmacher's // "Network Applications of
| Bloom Filters: A Survey". // 2. The number of bits set
| per Add() is contant in order to take advantage of SIMD
| instructions.
|
| Mentioned papers:
| https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheeffic...
| https://www.eecs.harvard.edu/~michaelm/CS222/bloomsurvey.pdf
___________________________________________________________________
(page generated 2024-09-10 23:01 UTC)