hlld

I've given a talk at Papers We Love about Bloom Filters (http://paperswelove.org/2015/video/armon-dadgar-on-bloom-fil...) for those wanting to learn more. There have been quite a few follow on extensions to standard bloom filters that address some of the shortcomings mentioned here. For example, the cost of having K hash functions can be avoided with some simple math. This is discussed in "Less Hashing, Same Performance" (http://www.eecs.harvard.edu/%7Ekirsch/pubs/bbbf/esa06.pdf). You can also avoid the FPP rate from saturating at 100% using a technique called "Scalable Bloom Filters" (http://gsd.di.uminho.pt/members/cbm/ps/dbloom.pdf). The basic idea is you start with a small BF and layer on progressively larger filters. This also reduces the memory you need to allocate up front without worrying about the FPP rate saturating. As others h

My previous job was at an advertising firm, and we used HyperLogLogs for almost all of our real-time analytics infrastructure. They are incredibly space and time efficient. Each "counter" fits into about a single page of memory, and can count into the trillions with <2% error. We developed an extremely high performance server around it (hlld): https://github.com/armon/hlld. We were typically hitting with with tens of thousands of requests per second across about 50K counters. Although it was benchmarked to >1MM ops a second. Similarly, we also make bloomd, which is an equivalent for using bloom filters, which provide a more set-like abstraction: https://github.com/armon/bloomd

This is nice. At my last job, we developed an extremely high performance HyperLogLog server (hlld). Take a look if you're interested: https://github.com/armon/hlld It processes over a 1MM ops per second on a basic MacBook Air. In production we saw it handle more. We never had to scale it over one server in order to handle millions of distinct metrics. As an ad company, my last company had a ridiculous fanout of metrics for every request. Every ad serve API request (of which we got thousands per second) would fan out to over 150 metrics EACH. So for 1000 requests per second we'd have to modify 150,000 metrics. Raw SQL updates of course fall down with this (even if we tone back their durability). Instead, we opted for accumulated for 10 to 60 seconds in bloomd and hlld and statsite, then aggregating and doing a single bulk SQL update. Worke