10 ms·
Redis new data structure: the HyperLogLog
- eurleif 13y agoCool. I wonder if bloom filters might be up next?
- lifthrasiir 13y agoThere already exists SETBIT (for adding items), GETBIT (for querying items) and BITOP (for union operation) that can be used to implement bloom filters altogether. HyperLogLog requires multi-bit registers (6 bit long in Redis) which would be inefficient with the current design, so I guess that's why Redis is to include a specialized implementation for that.
- eurleif 13y agoCouldn't HyperLogLog be implemented efficiently using Lua scripting?
- lifthrasiir 13y agoI haven't tried (so have a grain of salt), but I guess it would be certainly slower than the native implementation for various reasons. One reason that Lua does not support an efficient integer type yet (AFAIK 5.3 will support it though) comes to mind.
- dbro 13y agoYes it's possible. I did this a few years ago as a learning project, and the relevant lua scripts can be seen here: https://gist.github.com/dbro/9920666 https://gist.github.com/dbro/9920666. ... 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 sets
- devd 13y agoI guess there are a couple of lua implementations. However, this pushes some logic on to the client side - (generate hash, get number of hashes, set the appropriate bits) which the server should ideally handle. I have experimented adding native bloom filters here - https://github.com/devendralaulkar/redis/tree/bloomfilter https://github.com/devendralaulkar/redis/tree/bloomfilter Basically they reuse the bit operations internally, and set multiple bits in a single command.
- bochi 13y agoThis blog post is a nice survey about other interesting probabilistic data structures: http://highlyscalable.wordpress.com/2012/05/01/probabilistic-structures-web-analytics-data-mining/ http://highlyscalable.wordpress.com/2012/05/01/probabilistic...
- deleted 13y ago[deleted]
- dscrd 13y agoThis is awesome on so many different levels. Check out the implementation: https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c https://github.com/antirez/redis/blob/unstable/src/hyperlogl...
- octo_t 13y agoWith the name, I started reading thinking it was an April fools joke, then I went down the rabbit hole of starting to read the post and every linked paper.
- malanj 13y agoThe idea of inexact computing seems to be gaining a lot of traction over the past few years. The HyperLogLog data structure reminded me of the research at Rice University on inexact processors: http://www.ece.rice.edu/~al4/lingamneni-cf12.pdf http://www.ece.rice.edu/~al4/lingamneni-cf12.pdf There's a lot to gain by being less precise!
- stefantalpalaru 13y agoWe're used to inexact computing from floating point math.
- platz 13y agowell, inexact vs probabilistic do have some differences.
- sitkack 13y agoThe future of computation is probabilistically inexact numbers over an interval. http://en.wikipedia.org/wiki/Interval_arithmetic 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. http://web.media.mit.edu/~bates/Summary_files/BatesTalk.pdf http://web.media.mit.edu/~bates/Summary_files/BatesTalk.pdf
- malanj 13y agoHypothesis: inexact computations will be required to make strong AI work in the medium term. 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.
- sitkack 13y agoTop of the line supercomputers consume ~10 megawatts of power, a human brain uses 20. Different problems yes, but the magnitude is staggering.
- 13y ago
- ris 13y agoOn a related note, the recently released HyperLogLog extension for postgres: https://github.com/aggregateknowledge/postgresql-hll https://github.com/aggregateknowledge/postgresql-hll
- medriscoll 13y agoThe Druid.io folks recently blogged about three additional optimizations to HyperLogLog that compact the registers and can improve query speed: https://groups.google.com/forum/#!searchin/druid-development/hyperloglog/druid-development/q1_R5yD3_DA/Dg6IC-q4L6kJ https://groups.google.com/forum/#!searchin/druid-development...
- e98cuenc 13y agoWe used this datastructure a few months ago to track an approximation to the cardinality of the followers of a set of twitter users, which is handy to calculate the reach of a twitter post. More recently, we used it again to track an approximation to the number of unique images that a user generated in a time period (each image is identified by a different URL). Very handy data structure, and glad to see it land in Redis!
- pointernil 13y agoVery likable naming scheme ;) Kudos for the extraordinary work on redis. cheers
- dexcs 13y agoThe funny fact is that whether it's a april fool or not, i am not able to verify it because it's so well (technical) written :/
- antirez 13y agoNo April fool at all :-) You can build the "unstable" branch and play with it.
- MasterScrat 13y agoThanks for the clarification. It's even more confusing for french speakers as "Philippe Flajolet" really sounds like a made-up name ("Flajolet" means "white beans").
- sbarre 13y agoYeah it would be like seeing a paper written by "Peter Potato" or something like that...
- dhotson 13y agoHyperLogLog counters are one of my favourite things. They're incredibly clever. 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 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-how-to-count-a-billion-distinct-objects-us.html http://highscalability.com/blog/2012/4/5/big-data-counting-h...
- ronaldx 13y agoAveraging the results correctly must be an interesting problem in itself? I believe that standard averages wouldn't necessarily give you the maximum likelihood.
- dhotson 13y agoTo be honest, I'm not an expert at this stuff—merely enthusiastic about it. I could have some details wrong. 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?
- yread 13y agoThe HLL principle seems quite similar to this way of approximating a biased coin with a fair one by counting the 1s in binary http://amakelov.wordpress.com/2013/10/10/arbitrarily-biasing-a-coin-in-2-expected-tosses/ http://amakelov.wordpress.com/2013/10/10/arbitrarily-biasing...
- PanMan 13y agoDoes anybody have a good example of this? E.g. to count unique hits over time without storing each hit?
- nerfhammer 13y agoHere's a cool example of using HLL in javascript to dynamically show set union/intersections for huge sets: http://www.aggregateknowledge.com/science/blog/venn.html http://www.aggregateknowledge.com/science/blog/venn.html
- jimktrains2 13y agoOh man, I started this and native bloom filters a summer ago and never finished it. These are awesome data structures when dealing with really larges sets and you only need a cardinality count or set membership test and not all the members of the set. I can't wait to start using them!
- ronaldx 13y agoIf I've understood correctly, this relates to the German Tank Problem: using statistical analysis to estimate a count. 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?
- antirez 13y agoHello, the use case is that you can count what you usually don't store (for example different IPs connecting every day to your server), or you can count what is usually stored but it is too expensive to count otherwise (Like iterating a database table and counting unique items in a given column). 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.
- nefasti 13y agoA very good post helping explain HyperLogLog : http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/ http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-...
- donretag 13y agoElasticsearch started using HyperLogLog recently for aggregating data. No April Fools there!
- ithkuil 13y agoHow does HyperLogLog compare to Count-Min-Sketch?
- Lanzaa 13y agoOne basic difference between Count-Min Sketches and HyperLogLog is that Count-Min Sketches represent the cardinality of items in multisets while HyperLogLog represent the cardinality of sets. For 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.
- nerfhammer 13y agoIf you made the number of registers (m) extremely large and the register width 1 then a bloom filter and HLL are almost exactly the same (except bloom filters have multiple hashes for the same input and in HLL you only split one hash into two parts). 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_number_of_items_in_a_Bloom_filter 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.
- mitchellh 13y agoThis 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 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. Worked incredibly well. We used it in combination with bloomd: https://github.com/armon/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.
- arielweisberg 13y agoThere are several databases that will do 150k replicated updates a second on a 2 socket server. Heck, 150k multi-statement transactions has been realistic for years. 1 million on a MacBook air no, not yet. Not enough caching, JITing and precompilation to optimize away the overhead of SQL in anything that currently exists. 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.
- AaronFriel 13y agoOh, there are dozens of databases that will do 150k transactions per second. The issue with database throughput for most applications is the storage layer, which is more difficult to fine tune when working with a cloud service. 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.
- eternalban 13y agoNick's blog is a must read for these sort of algorithms. See his original writeup on the HLL here: http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinality-Estimation http://blog.notdot.net/2012/09/Dam-Cool-Algorithms-Cardinali...
- jacinda 13y agoThe top answer about HyperLogLog on stackoverflow links to this awesome visualization: http://www.aggregateknowledge.com/science/blog/hll.html http://www.aggregateknowledge.com/science/blog/hll.html SO Answer: http://stackoverflow.com/a/13074072/307293 http://stackoverflow.com/a/13074072/307293 Full blog post: http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/ http://blog.aggregateknowledge.com/2012/10/25/sketch-of-the-...
- yoyo1999 13y agoI have realized how mediocre I am.
- emmanueloga_ 13y agoI now that projects like http://druid.io http://druid.io use HLL to do timeseries analytics. Can someone explain or link to an explanation about how counting sets cardinality can be used for time series analysis? (Do I need to add I haven't find a satisfactory one myself? :). 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 etc.. 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