3 ms·
When Bloom filters don't bloom (2020)
- hinkley 2y ago> 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 2y agoaside: reading that made me wonder just which of Google vs Cloudflare knows everything about everyone's web accesses.
- majke 2y agoOf 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-anymore/ https://blog.cloudflare.com/cloudflare-servers-dont-own-ips-...
- JackSlateur 2y agoYes, it is sure The important word is "should" : italian people should not arrive in a brazilian datacenter Indeed, sometimes they still get there. But in itself, greeting italian in brazil is enough to conclude something is going on. One should not conclude, however, that said traffic should be deleted.
- the_gorilla 2y agoI'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 2y agoDid you try to repeat the experiment?
- limit499karma 2y ago> "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 2y agoI didn't say it would fit in the cache.
- limit499karma 2y agoCorrect. You mentioned your instincts.
- majke 2y agoRandom 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 2y agoI wonder how the final version with the single hash table stacks up against: cat file.txt | perl -ne 'print unless $x{$_}++'
- thomasmg 2y agoThe 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/bloom/simd-block.h https://github.com/FastFilter/fastfilter_cpp/blob/master/src... (there are others)
- majke 2y agoThanks 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/cacheefficientbloomfilters-jea.pdf https://www.cs.amherst.edu/~ccmcgeoch/cs34/papers/cacheeffic... https://www.eecs.harvard.edu/~michaelm/CS222/bloomsurvey.pdf https://www.eecs.harvard.edu/~michaelm/CS222/bloomsurvey.pdf
- limit499karma 2y agoThat's the L1. Blocked -- segmented would have been a better name imo -- approach still depends on the blocks to be resident in L2/LLC. OP's problem is that most of the blocks' pages (not cache-line) are not resident in LLC. I wonder about an op-buffer approach. ~: buffer the BF ops to aggregate ops on a specific address ranges. Say first buffer n ops for the filter, sort by the (relevant) hash bits, and then apply m ops for a specific page, and so on. And optimizing that, it may be possible to only process the op-buffer partially, i.e. add ops until the buffer is full, gather the ops that map to a page-segment (4k), and if the rest of the buffer is still all over the place continue buffering, and rinse and repeat. [p.s.] OP's task at hand is an off-line matter whereas general BF approaches assume an on-line use case. By adopting an off-line approach, I should think there remain many opportunities for optimizing the runtime.
- 2y ago