一、hyperloglog
hyperloglog是用来做基数统计的。
其可以非常省内存的去统计各种计数，比如注册ip数、每日访问ip数、页面实时uv（pv肯定字符串就搞定了）、在线用户数等在对准确性不是很重要的应用场景。
hyperloglog的优点是：
在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的，
hyperloglog的缺点:
它是估计基数的算法，所以会有一定误差0.81%。
每个hyperloglog键只需要花费12kb内存，就可以计算接近264个不同元素的基数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。
但是，因为 hyperloglog 只会根据输入元素来计算基数，而不会储存输入元素本身，所以 hyperloglog 不能像集合那样，返回输入的各个元素即无法知道统计的详细内容。
二、基数和估算值
1、基数
基数是集合中不同元素的数量。
比如数据集 {1, 3, 5, 7, 5, 7, 8}， 那么这个数据集的基数集为 {1, 3, 5 ,7, 8}, 基数(不重复元素)为5。
基数估计就是在误差可接受的范围内，快速计算基数。
2、估算值
算法给出的基数并不是精确的，可能会比实际稍微多一些或者稍微少一些，但会控制在合理的范围之内。
三、hperloglog基本命令
redis hyperloglog 的基本命令：
1 pfadd key element [element ...]
添加指定元素到 hyperloglog 中。
2 pfcount key [key ...]
返回给定 hyperloglog 的基数估算值。
3 pfmerge destkey sourcekey [sourcekey ...]
将多个 hyperloglog 合并为一个 hyperloglog
pfadd
将任意数量的元素添加到指定的 hyperloglog 里面。在执行这个命令之后，hyperloglog内部的结构会被更新，并有所反馈，
如果执行完之后hyperloglog内部的基数估算发生了变化，那么就会返回1，否则（认为已经存在）就返回0。
这个命令还有一个比较神器的就是可以只有键，没有值，这样的意思就是只是创建空的键，不放值。
如果这个键存在，不做任何事情，返回0；不存在的话就创建，并返回1。
这个命令的时间复杂度为o(1)，所以就放心用吧~
pfcount
当命令作用于单个键的时候，返回这个键的基数估算值。如果键不存在，则返回0。
当 pfcount 命令作用于多个键时， 返回所有给定 hyperloglog 的并集的近似基数， 这个近似基数是通过将所有给定 hyperloglog 合并至一个临时 hyperloglog 来计算得出的。
这个命令在作用于单个值的时候，时间复杂度为o(1)，并且具有非常低的平均常数时间；在作用于n个值的时候，时间复杂度为o(n)，这个命令的常数复杂度会比较低些。
命令返回的可见集合（observed set）基数并不是精确值， 而是一个带有 0.81% 标准错误（standard error）的近似值。
举个例子， 为了记录一天会执行多少次各不相同的搜索查询， 一个程序可以在每次执行搜索查询时调用一次 pfadd ， 并通过调用 pfcount 命令来获取这个记录的近似结果。
pfmerge
合并（merge）多个hyperloglog为一个hyperloglog。 合并后的 hyperloglog 的基数接近于所有输入 hyperloglog 的可见集合（observed set）的并集。
合并得出的 hyperloglog 会被储存在 destkey 键里面， 如果该键并不存在， 那么命令在执行之前， 会先为该键创建一个空的 hyperloglog 。
这个命令的第一个参数为目标键，剩下的参数为要合并的hyperloglog。命令执行时，如果目标键不存在，则创建后再执行合并。
这个命令的时间复杂度为o(n)，其中n为要合并的hyperloglog的个数。不过这个命令的常数时间复杂度比较高。
redis> pfadd ip:20170626 "192.168.0.10" "192.168.0.20" "192.168.0.30"
(integer) 1
redis> pfadd ip:20170626 "192.168.0.20" "192.168.0.40" "192.168.0.50" # 存在就只加新的
(integer) 1
redis> pfcount ip:20170626 # 元素估计数量没有变化
(integer) 5
redis> pfadd ip:20170626 "192.168.0.20" # 存在就不会增加
(integer) 0
edis> pfmerge ip:20170626 ip:20170627 ip:20170628
ok
redis> pfcount ip:201706
(integer) 5
四、hperloglog 描述
由于hperloglog，这种数据结构在实际应用场景中并不多。因此，这里就不再详细讨论了。
我们看下hperloglog.c文件，对hperloglog的描述
/* the redis hyperloglog implementation is based on the following ideas:
*
* * the use of a 64 bit hash function as proposed in [1], in order to don't
* limited to cardinalities up to 10^9, at the cost of just 1 additional
* bit per register.
* * the use of 16384 6-bit registers for a great level of accuracy, using
* a total of 12k per key.
* * the use of the redis string data type. no new type is introduced.
* * no attempt is made to compress the data structure as in [1]. also the
* algorithm used is the original hyperloglog algorithm as in [2], with
* the only difference that a 64 bit hash function is used, so no correction
* is performed for values near 2^32 as in [1].
*
* [1] heule, nunkesser, hall: hyperloglog in practice: algorithmic
* engineering of a state of the art cardinality estimation algorithm.
*
* [2] p. flajolet, éric fusy, o. gandouet, and f. meunier. hyperloglog: the
* analysis of a near-optimal cardinality estimation algorithm.
*
* redis uses two representations:
*
* 1) a "dense" representation where every entry is represented by
* a 6-bit integer.
* 2) a "sparse" representation using run length compression suitable
* for representing hyperloglogs with many registers set to 0 in
* a memory efficient way.
*
*
* hll header
* ===
*
* both the dense and sparse representation have a 16 byte header as follows:
*
* ------ --- ----- ----------
* | hyll | e | n/u | cardin. |
* ------ --- ----- ----------
*
* the first 4 bytes are a magic string set to the bytes "hyll".
* "e" is one byte encoding, currently set to hll_dense or
* hll_sparse. n/u are three not used bytes.
*
* the "cardin." field is a 64 bit integer stored in little endian format
* with the latest cardinality computed that can be reused if the data
* structure was not modified since the last computation (this is useful
* because there are high probabilities that hlladd operations don't
* modify the actual data structure and hence the approximated cardinality).
*
* when the most significant bit in the most significant byte of the cached
* cardinality is set, it means that the data structure was modified and
* we can't reuse the cached value that must be recomputed.
*
* dense representation
* ===
*
* the dense representation used by redis is the following:
*
* -------- -------- -------- ------// //--
* |11000000|22221111|33333322|55444444 .... |
* -------- -------- -------- ------// //--
*
* the 6 bits counters are encoded one after the other starting from the
* lsb to the msb, and using the next bytes as needed.
*
* sparse representation
* ===
*
* the sparse representation encodes registers using a run length
* encoding composed of three opcodes, two using one byte, and one using
* of two bytes. the opcodes are called zero, xzero and val.
*
* zero opcode is represented as 00xxxxxx. the 6-bit integer represented
* by the six bits 'xxxxxx', plus 1, means that there are n registers set
* to 0. this opcode can represent from 1 to 64 contiguous registers set
* to the value of 0.
*
* xzero opcode is represented by two bytes 01xxxxxx yyyyyyyy. the 14-bit
* integer represented by the bits 'xxxxxx' as most significant bits and
* 'yyyyyyyy' as least significant bits, plus 1, means that there are n
* registers set to 0. this opcode can represent from 0 to 16384 contiguous
* registers set to the value of 0.
*
* val opcode is represented as 1vvvvvxx. it contains a 5-bit integer
* representing the value of a register, and a 2-bit integer representing
* the number of contiguous registers set to that value 'vvvvv'.
* to obtain the value and run length, the integers vvvvv and xx must be
* incremented by one. this opcode can represent values from 1 to 32,
* repeated from 1 to 4 times.
*
* the sparse representation can't represent registers with a value greater
* than 32, however it is very unlikely that we find such a register in an
* hll with a cardinality where the sparse representation is still more
* memory efficient than the dense representation. when this happens the
* hll is converted to the dense representation.
*
* the sparse representation is purely positional. for example a sparse
* representation of an empty hll is just: xzero:16384.
*
* an hll having only 3 non-zero registers at position 1000, 1020, 1021
* respectively set to 2, 3, 3, is represented by the following three
* opcodes:
*
* xzero:1000 (registers 0-999 are set to 0)
* val:2,1 (1 register set to value 2, that is register 1000)
* zero:19 (registers 1001-1019 set to 0)
* val:3,2 (2 registers set to value 3, that is registers 1020,1021)
* xzero:15362 (registers 1022-16383 set to 0)
*
* in the example the sparse representation used just 7 bytes instead
* of 12k in order to represent the hll registers. in general for low
* cardinality there is a big win in terms of space efficiency, traded
* with cpu time since the sparse representation is slower to access:
*
* the following table shows average cardinality vs bytes used, 100
* samples per cardinality (when the set was not representable because
* of registers with too big value, the dense representation size was used
* as a sample).
*
* 100 267
* 200 485
* 300 678
* 400 859
* 500 1033
* 600 1205
* 700 1375
* 800 1544
* 900 1713
* 1000 1882
* 2000 3480
* 3000 4879
* 4000 6089
* 5000 7138
* 6000 8042
* 7000 8823
* 8000 9500
* 9000 10088
* 10000 10591
*
* the dense representation uses 12288 bytes, so there is a big win up to
* a cardinality of ~2000-3000. for bigger cardinalities the constant times
* involved in updating the sparse representation is not justified by the
* memory savings. the exact maximum length of the sparse representation
* when this implementation switches to the dense representation is
* configured via the define server.hll_sparse_max_bytes.
*/