# redis数据结构之hperloglog-ag真人游戏

hyperloglog是用来做基数统计的。

hyperloglog的优点是：

hyperloglog的缺点:

1、基数

2、估算值

redis hyperloglog 的基本命令：

1 pfadd key element [element ...]

2 pfcount key [key ...]

3 pfmerge destkey sourcekey [sourcekey ...]

pfcount

pfmerge

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

/* 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].

*

*     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.

*

*

* ===

*

* 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.

*/