http://www.tutorialspoint.com/redis/redis_hyperloglog.htm
PFCOUNT tutorials
PFADD key element [element ...]
PFCOUNT key [key ...]
PFMERGE destkey sourcekey [sourcekey ...]
PFADD hll1 foo bar zap a
PFADD hll2 a b c foo
PFMERGE hll3 hll1 hll2
https://redislabs.com/blog/how-to-use-redis-at-least-x1000-more-efficiently
HyperLogLog allows you to estimate the cardinality of a set or, put differently, get an approximate count of unique items.
HLL let you do that using a fixed amount of memory and constant complexity.
HLL’s count has a standard error of up to 0.81%.
Assume you want to keep track of how many unique users are using your app throughout the day, hour by hour. Before HyperLogLog, one simple way that you could do that in Redis was by storing the IDs of your users (e.g. their emails) in an hourly set, so for each request you'd do something like:
SADD users:<date>:<hour> <email>
This way, the result of SCARD for any such set would be the number of unique users for that hour.
《流浪地球》，火了！
火到什么程度呢？火到了全宇宙都知道地球发明出了行星发动机。纷纷发来贺电。天量贺电.
天到什么程度呢？10^21 （1000000000000000000000）这个量级。这也是宇宙中所有星星的估算数量。
地球联合政府代表大刘找到你，要求查出天亮贺电里有多少Unique的星星。你能得到的是每个贺电源星星的坐标: 比如这一段学天文的同学熟悉的字串：RA 3h 4m 38.05s Dec 1° 51' 49.0''
如果用传统的办法，那么自然要用到的空间复杂度为O(N * K) K为星星的identity的平均长度。这个空间复杂度是超出地球上所有存储媒体的大小的。所以是无法实现的。
有一种概率数据结构：Hyperloglog。拥有这样的特质：虽然不是特别精确，有+- 0.81%的标准误差。但是运算快，内存小O（1）。是不是很神奇？
为了理解这个神奇的算法。我们来想想一个简化的例子。给你一些32以下的随机、均匀分布的数（允许重复），求总共多少distinct数。只允许你用一个int variable。
从0-31的随机数，并且按照从左数连续零的长度分组，则会得到：
如果你仅仅记录你看到的从左数连续最长的零的数目，那么你就可以估算出一个比较准确的估计值。
比如你见过从左数连续零最长为：2，那么你可以推断出你至少见过00100 00101 00110 00111之一。因为这些数在均匀分布的整个基数空间的概率为4/32 = 1/8 （即1/2^（2+1））。
虽然你也可能见过从左数连续零最长为1，从左数连续零最长为0 的数，但是那些数出现的概率为 1/4 1/2。比不上 1/8. 所以你可以大胆粗糙估计：你应该见过8个左右的distinct的数。
可以想见，这是一个相当粗糙的估计。但是如果基数越大，那么这个估计应该越准确。
Redis（和多个开源项目甚至包括Presto）实现HyperLogLog的时候，用到了几大神器和设计
MurmurHash是个设计极其简单（Multiply, Shift and XOR）但是功能非常强大的哈希算法。给定任意长度bytes，能够产生even distribution的64位（8bytes）。
这样把hash的前几位作为bucket id，把后面的若干位，求从左边数连续的0的长度。如果大于则放入bucket中。这样bucket里就存放了最长见过的连续0的长度。
为了理解桶在hyperloglog里的应用，看下图的上半部分的例子，用4个桶。
Redis实现的时候，其buckets数为（m=2^14=16384)。任何key通过MurmurHash产生一个64位的hash。hash的前14位用于表征去哪个bucket。后面的50bit，最长也就50. 因此每个bucket只需要6个bit，来表征不超过2^6=64的数。这样下来我们看看：16384 * 6 = 98304 bits = 12288 (12K Bytes)。对于不超过2^64个基数空间。则O（1）空间就可以解决统计distinct的问题。
如果碰巧第一次就得到hash 00000 怎么办？Harmonic Mean的巧妙之处在于接近所有观测者（buckets）里最短的从左数最长的连续0。把bucket里0的概率相加。那么碰巧的连续长0的概率（很小的一个值）通过和其它概率相加就被边缘化了。比如在图中的例子里最后得到的是buckets的概率分别是：2^-3，2^-2，2^-2，2^-4. 相加以后2^-3和2^-4会因为2^-2而被边缘化。注意Redis源码里用的是histogram。这里就不认真琢磨了。想来面试中不会考这深的地方。真正写正式码的时候还是要琢磨一下的。
照Redis的官方介绍，其错误空间为standard error of 0.81%. 也就是说，如果放入1000000个distinct值，则Redis count的结果会在[1000000 - 8100, 1000000 + 8100]区间之内。即99.19%-100.81%之间。
因为O(1)空间复杂度，所以Redis还提供了两套桶合并的功能。如果你有两个统计（在Redis里有两个Keys。那么Redis里有两套12K的桶。）合并的时候无非就是每个bucket取max。不细数了。
更多的Redis HyperLogLog的实现请参照 https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L1013
好了，上面我们从面试角度浅显低了解了一下HyperLogLog的原理。现在我们回到地球联合政府的海量计算的差事上吧。
10^21 （1000000000000000000000）这么多个要处理的消息。我们假设网络不是问题。大不了大家都去天文台旁边建数据中心好了。硬盘也不是瓶颈。
能交货吗？还能更快吗？
更多参考链接：
http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
https://sites.google.com/site/murmurhash/
Redis HyperLogLog is a algorithm that use randomization in order to provide an approximation of the number of unique elements in a set using just a constant, and small, amount of memory.
HyperLogLog provides a very good approximation of the cardinality of a set even using a very small amount of memory around 12 kbytes per key with a standard error of 0.81% and there is no limit to the number of items you can count, unless you approach 264 items.
PFADD tutorials "redis"PFCOUNT tutorials
PFADD key element [element ...]
PFCOUNT key [key ...]
PFMERGE destkey sourcekey [sourcekey ...]
PFADD hll1 foo bar zap a
PFADD hll2 a b c foo
PFMERGE hll3 hll1 hll2
https://redislabs.com/blog/how-to-use-redis-at-least-x1000-more-efficiently
HyperLogLog allows you to estimate the cardinality of a set or, put differently, get an approximate count of unique items.
HLL let you do that using a fixed amount of memory and constant complexity.
HLL’s count has a standard error of up to 0.81%.
Assume you want to keep track of how many unique users are using your app throughout the day, hour by hour. Before HyperLogLog, one simple way that you could do that in Redis was by storing the IDs of your users (e.g. their emails) in an hourly set, so for each request you'd do something like:
SADD users:<date>:<hour> <email>
This way, the result of SCARD for any such set would be the number of unique users for that hour.
When using HLL we'd count the users with:
PFADD users:<date>:<hour> <email>
And use PFCOUNT to obtain the hourly count. But what if you wanted (and you usually do) to have aggregates for different time periods, like 3h, 6h, 12h and 24h? With the SADD/SCARD approach, you'll either need to dedicate a few more counter sets for each resolution or execute on-demand/periodic SUNIONs, costing RAM and CPU. You could, as shown above, gain considerably by using HLL but there's actually another big saving with it. Since HLLs can be merged very efficiently, you don't need to save a counter for each of time resolution and justPFMERGE the relevant counters to get the sums.
全宇宙发来天量贺电 简介高级概率数据结构HyperLogLog《流浪地球》，火了！
火到什么程度呢？火到了全宇宙都知道地球发明出了行星发动机。纷纷发来贺电。天量贺电.
天到什么程度呢？10^21 （1000000000000000000000）这个量级。这也是宇宙中所有星星的估算数量。
地球联合政府代表大刘找到你，要求查出天亮贺电里有多少Unique的星星。你能得到的是每个贺电源星星的坐标: 比如这一段学天文的同学熟悉的字串：RA 3h 4m 38.05s Dec 1° 51' 49.0''
如果用传统的办法，那么自然要用到的空间复杂度为O(N * K) K为星星的identity的平均长度。这个空间复杂度是超出地球上所有存储媒体的大小的。所以是无法实现的。
有一种概率数据结构：Hyperloglog。拥有这样的特质：虽然不是特别精确，有+- 0.81%的标准误差。但是运算快，内存小O（1）。是不是很神奇？
为了理解这个神奇的算法。我们来想想一个简化的例子。给你一些32以下的随机、均匀分布的数（允许重复），求总共多少distinct数。只允许你用一个int variable。
从0-31的随机数，并且按照从左数连续零的长度分组，则会得到：
[Bash shell] 纯文本查看 复制代码
从左数连续5个零，共一个：00000从左数连续4个零，共一个：00001从左数连续3个零，共两个：00010 00011从左数连续2个零，共四个：00100 00101 00110 00111从左数连续1个零，共八个：01000 01001 01010 01011 01100 01101 01110 01111从左数连续没有零，共十六个：10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111 |
如果你仅仅记录你看到的从左数连续最长的零的数目，那么你就可以估算出一个比较准确的估计值。
比如你见过从左数连续零最长为：2，那么你可以推断出你至少见过00100 00101 00110 00111之一。因为这些数在均匀分布的整个基数空间的概率为4/32 = 1/8 （即1/2^（2+1））。
虽然你也可能见过从左数连续零最长为1，从左数连续零最长为0 的数，但是那些数出现的概率为 1/4 1/2。比不上 1/8. 所以你可以大胆粗糙估计：你应该见过8个左右的distinct的数。
可以想见，这是一个相当粗糙的估计。但是如果基数越大，那么这个估计应该越准确。
Redis（和多个开源项目甚至包括Presto）实现HyperLogLog的时候，用到了几大神器和设计
- 为了对于任意给定的String key产生随机、均匀分布的数，用到了MurmurHash
- 为了消除误差，用到了16384个桶，实现了O(1)空间复杂度
- 为了消除桶和桶之间的极端数，在估算Cardinality的时候用到了Harmonic Mean
MurmurHash是个设计极其简单（Multiply, Shift and XOR）但是功能非常强大的哈希算法。给定任意长度bytes，能够产生even distribution的64位（8bytes）。
这样把hash的前几位作为bucket id，把后面的若干位，求从左边数连续的0的长度。如果大于则放入bucket中。这样bucket里就存放了最长见过的连续0的长度。
为了理解桶在hyperloglog里的应用，看下图的上半部分的例子，用4个桶。
Redis实现的时候，其buckets数为（m=2^14=16384)。任何key通过MurmurHash产生一个64位的hash。hash的前14位用于表征去哪个bucket。后面的50bit，最长也就50. 因此每个bucket只需要6个bit，来表征不超过2^6=64的数。这样下来我们看看：16384 * 6 = 98304 bits = 12288 (12K Bytes)。对于不超过2^64个基数空间。则O（1）空间就可以解决统计distinct的问题。
如果碰巧第一次就得到hash 00000 怎么办？Harmonic Mean的巧妙之处在于接近所有观测者（buckets）里最短的从左数最长的连续0。把bucket里0的概率相加。那么碰巧的连续长0的概率（很小的一个值）通过和其它概率相加就被边缘化了。比如在图中的例子里最后得到的是buckets的概率分别是：2^-3，2^-2，2^-2，2^-4. 相加以后2^-3和2^-4会因为2^-2而被边缘化。注意Redis源码里用的是histogram。这里就不认真琢磨了。想来面试中不会考这深的地方。真正写正式码的时候还是要琢磨一下的。
照Redis的官方介绍，其错误空间为standard error of 0.81%. 也就是说，如果放入1000000个distinct值，则Redis count的结果会在[1000000 - 8100, 1000000 + 8100]区间之内。即99.19%-100.81%之间。
因为O(1)空间复杂度，所以Redis还提供了两套桶合并的功能。如果你有两个统计（在Redis里有两个Keys。那么Redis里有两套12K的桶。）合并的时候无非就是每个bucket取max。不细数了。
更多的Redis HyperLogLog的实现请参照 https://github.com/antirez/redis/blob/unstable/src/hyperloglog.c#L1013
好了，上面我们从面试角度浅显低了解了一下HyperLogLog的原理。现在我们回到地球联合政府的海量计算的差事上吧。
10^21 （1000000000000000000000）这么多个要处理的消息。我们假设网络不是问题。大不了大家都去天文台旁边建数据中心好了。硬盘也不是瓶颈。
- 我们考虑把外星人的消息shard到多台机器上去。shard的基数定位redis能够承受的基数：2^64 = 18446744073709550000
- 全世界有多少台电脑？查了下发现去年有259390000 PCs卖出去。这是PC不是什么特别好的机器。但这也是分布计算的魅力之所在。
- 有259390000个shard，每个shard能承受2^64。这样总体能够承受4.78E+27个distinct数，远远大于10^21。所以从基数空间这点上看是可行的。
- 下面再来考虑运算速度，多长时间出活？
- 一个Redis process的hyperloglog的运算量估计为：30000 qps。这不是什么特别好的机器。
- 考虑到哪怕一个不是那么好的机器也应该有若干核：4
- 那么我们估计一个PC的运算量在：4*30000 = 120000
- 全球所有的PC的运算量：259390000 * 120000 = 31126800000000
- 每天24小时，3600秒每小时。所以每天的运算量在：2689355520000000000
- 每年365天，每年全球的运算量在：981614764800000000000 即：9.81E+20
- 和10^21很接近了。一年时间。
能交货吗？还能更快吗？
更多参考链接：
http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
https://sites.google.com/site/murmurhash/
