Redis new data structure: the HyperLogLog
antirez.com
antirez.com
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. Worked incredibly well.
We used it in combination with bloomd: https://github.com/armon/bloomd Bloomd is another super high performance data structure server, but this time for bloom filters.
You can read the READMEs to learn why they're better for their specific tasks. Both have been running in production for 2+ years. If you're not going to be using the data structures that much then Redis is a good choice. We personally used these servers alongside Redis for k/v.
This is not to talk down using the right tool for the job, but as soon as you want to do something a little more complicated than count you are right back to reinventing databases. That is basically what you are doing by implementing periodic group commit on top of a database.
With Azure, you have to use one of their very large instances and connect and stripe virtual disks yourself to hit 40k IOs per second, and I think that's just barely possible. With Amazon, you are limited to about 48k IOPS and again, you have to use EBS and provisioned IOPS disks and stripe. Not sure about Google's services.
I can see how you can make your comment without understanding this context and more. But really, I promise you SQL didn't work AT ALL. This is primarily due to the type of data we were putting in there: we needed some aggregates like totals, averages, standard deviation, etc. To get this data, you need to have it inserted first, and we were requesting on the fly in real time at a pretty large rate. This would cause the CPU of the SQL servers to go up pretty hard WHILE also serving hundreds of thousands of insert/update ops/sec. We could've solved this by adding read slaves and all that, but now we're talking expensive CapEx for something we were confident we could fix with some C in a week or two.
Enter: the two servers linked in my parent comment.
We sacrificed durability, accuracy, and some level of safety (if the server crashes before an accumulation period once every X seconds, you lose that data) for raw speed. We calculated out the acceptable tolerances (max % off the real value) and tuned our data structures to that (bloomd and hlld both expose these tunables). We then ran both servers in parallel to our existing SQL solution for a few weeks to verify the numbers were correct. Finally, we switched over.
Like I said, when we built that we were doing maybe 450,000 metrics per second. That was 2 years ago. Now they're doing much much more than that, and both hlld and bloomd are running on a single m3.medium with no persistence (they aggregate then issue a single large UPDATE to SQL) with no issue.
The amortized operating expenses (human labor) cost of developing the servers, along with the thousands saved in server costs, and with the effectively zero ops overhead (they never go down, they're stateless, etc.) has been well worth it.
Hope that makes our decision a little clearer.
Of course writing a specific datastructure will outperform a general solution - that goes without saying. No HA/persistence makes it even easier. And if the datastructure is simple enough, then writing and maintaining the code yourself may pay off.
./redis-benchmark -P 64 -r 100000000 -n 100000000 \
pfadd hll __rand_int__
pfadd hll __rand_int__: 320125.56
./redis-benchmark -P 64 -r 100000000 -n 100000000 \
pfcount hll
pfcount hll: 313309.62
At the same time HLLCOUNT is running in the other benchmark forcing the update of the cached cardinality as often as possible.
Yet we get around 640k ops/sec in a single core, that multiplied for the 4 cores of an Air i7 gets you to 2.4m ops/sec.
EDIT 1: Note that while I'm using random data as argument of PFADD, we are not using N HLLs but a single one, so tis benchmark is surely biased as cache misses are rare. But using multiple keys will not be terrible like losing an order of magnitude, just a reasonable percentage of OPS will go away.
EDIT 2: I had a process running in background consuming a lot of CPU, actually I tried again and reached 900k OPS/sec for core, but read EDIT 1 for more info.
I was not making a comparison. I was showing another potential solution.
That's a comparison, specifically claiming much higher performance.
For people who need SQL and HyperLogLog, we found this extension to work pretty well.
For HyperLogLog, we actually utilize our column based big data store. It is possible, also pretty easily, to create the HyperLogLog algorithm as an SQL query, which we can use to aggregate several useful metrics. This is super useful when you can combine it easily with several other metrics that are not using the HyperLogLog, e.g. making another facts table for your star schema.
Thanks.
So also, you can combine this idea with the idea of bloom filters (another probabilistic data structure) in a really interesting way. The goal is to have a _lot_ of counters in a fixed amount of space.
First part is to encode your HyperLogLog counter in unary. So each counter generally only takes up a few bits.
Quick unary tutorial: in unary you count with a sequence of 1's (followed by 0 to signify the end of the number). 3 is encoded as 1110. 5 is 111110. 7 is 11111110. You get the idea.
So also, we're just estimating cardinality, not an exact count. We're estimating if we've seen 2^n things... not n things. Counting to a billion is going to be: 1 billion ~= 2^30 ~= 31 bits.
So you can store all these counters in a big array of bits (a bitmap) and index into it using a hash function. As you probably guessed, all these unary counters will end up overlapping each other in weird ways.
But! The cool thing is if you use a bloom filter to insert and retrieve multiple counters using different hash functions.. and then average the results. The more of these probabilistic and messed up counters you average .. the better the results get!
It's kind of opposite of the usual programmer "junk in, junk out" problem. In this case, the more junk you combine, the better the results. Pretty neat huh? :)
I don't have links to the papers behind these ideas sorry. I learnt most of this from a presentation by Alex Sharp at PyCon Au. Edit: found link to talk - http://pyvideo.org/video/1621/big-data-with-python
This article explains some of this stuff a bit better: http://highscalability.com/blog/2012/4/5/big-data-counting-h...
I believe that standard averages wouldn't necessarily give you the maximum likelihood.
My intuition says that a straight average should give you fairly good results.. although antirez talks a bit about bias in HyperLogLog counts that he's trying to adjust for.
So maybe an average + some bias correction gives you better results?
The issue is that (e.g.) the arithmetic mean would be very influenced by the stats that gave randomly bad results - the very results you are trying to exclude by doing the test multiple times and taking an average.
From the article:
The standard error of HyperLogLog is 1.04/sqrt(m), where “m” is the number of registers used. Redis uses 16384 registers, so the standard error is 0.81%.
My understanding is that the error is very small because you're averaging over 16,000 registers.
Edit: also, I think you want the mean because it'll give you back a precise/fractional power of 2 that is pretty close to the actual count. The median would give you the nearest integer power of two, which is probably not a good estimate of the real count.
Double edit: looks like there's some research around improving averaging by throwing away outliers: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinali...
The HyperLogLog data structure reminded me of the research at Rice University on inexact processors: http://www.ece.rice.edu/~al4/lingamneni-cf12.pdf
There's a lot to gain by being less precise!
http://en.wikipedia.org/wiki/Interval_arithmetic
We currently have a huge over tolerancing problem. We don't need exact math most of the time.
You can't simulate a brain accurately (and you probably don't need to). Neurons aren't very accurate themselves, and it does the job fine.
With German Tanks, you have limited data available to create an estimate from (a few serial numbers, in the canonical case). But in this case, you deliberately limit the data stored in order to keep it at a manageable level: hash to randomise and then store only summary stats.
Pretty cool. Actually very cool, I really like it.
However, are there any interesting use cases for this? It seems to me that it's not particularly useful until your list is long enough to make search/sort/storage difficult: that's rare even at web-scale, no?
Also since it is so cheap, you start counting even things that could be unreasonable to count otherwise but that may provide useful insight, for example unique users accessing the site for every hour of the day, unique words ever used by a given user in her comments, and so forth.
Very handy data structure, and glad to see it land in Redis!
It's even more confusing for french speakers as "Philippe Flajolet" really sounds like a made-up name ("Flajolet" means "white beans").
Check out the implementation: https://github.com/antirez/redis/blob/unstable/src/hyperlogl...
https://groups.google.com/forum/#!searchin/druid-development...
Naively I think it could be done by factoring in a timestamp on the things to count:
PFADD SOMEHLLVAR "#{timestamp1}#{event1}" "#{timestamp}#{event2}"
PFADD SOMEHLLVAR "#{timestamp2}#{event3}" "#{timestamp}#{event2}"
PFCOUNT "#{timestamp1}#{event1}" # -> 1
PFCOUNT "#{timestamp2}#{event1}" # -> 0
The problem with doing that is that you would need to iterate through each second in a given range to find out the count of specific events... Also, seems like a pretty wasteful way of encoding time <edit> thinking about it is probably not wasteful in the sense the hll size should be the same, but probably sub-optimal some other way
SO Answer: http://stackoverflow.com/a/13074072/307293
Full blog post: http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-...
http://amakelov.wordpress.com/2013/10/10/arbitrarily-biasing...
... but I wouldn't claim that it's done efficiently. From the comments in the code's tests:
# some results based on running speed tests on a lightweight netbook:
# standard error = 0.01, 10kb of registers
# < 1 ms per init()
# < 1 ms per update()
# < 1 ms per count() for single set
# ~30 ms per set for count() of union of setsFor example, Put 3 of the item 'A' (where each 'A' is indistinguishable from another 'A') and similarly 5 of item 'B' into a Count-Min Sketch and a HyperLogLog.
When you query the Count-Min Sketch for 'A', you can probably get back 3. You can also query for 'B' and get back 5.
With you query the HyperLogLog you query how many unique/indistinguishable items are in the set, in this case 2. The HyperLogLog would return a number near 2. You could query the HyperLogLog for whether or not 'A' is in the set, but HyperLogLog are not designed to be accurate for that type of query. It would return true in this case and in general there are no false negatives for set membership queries in the HyperLogLog. I believe it would be less accurate than a Bloom Filter for set membership queries.
You can also use a bloom filter as a cardinality counter assuming it isn't too filled up yet: http://en.wikipedia.org/wiki/Bloom_filter#Approximating_the_...
HLLs are designed to be useful for cardinality counting past the point where a bloom filter would be over capacity. HLL would be useful for set membership but after some threshold the false positive rate will approach 100% at some super-linear rate.