How to implement Redis using HyperLogLog

1. Overview

Redis added the HyperLogLog data structure in version 2.8.9, which is used for cardinality statistics. The advantage is that when the number of input elements is very large, the space required to calculate the cardinality is relatively small. And generally relatively constant.

In Redis, each HyperLogLog key only costs 12 KB of memory to calculate the cardinality of nearly 2^64 different elements. This is in sharp contrast to the calculation of cardinality, where a collection with more elements consumes more memory. However, because HyperLogLog only calculates the cardinality based on the input elements and does not store the input elements themselves, HyperLogLog cannot return individual elements of the input like a collection.

2. What is the cardinality?

For example, if the data set is {1, 3, 5, 7, 5, 7, 8}, then the cardinality set of this data set is {1, 3, 5 ,7, 8}, the cardinality (non-repeating elements) is 5. Cardinality estimation is to quickly calculate the cardinality within the acceptable error range.

3. Commands

Currently, only three commands, PFADD, PFCOUNT and PFMERGE, are supported by HyperLogLog. Let’s introduce them one by one first.

3.1 PFADD

Earliest available version: 2.8.9. Time complexity: O(1).

The PFADD command can add elements (multiple elements can be specified) to the HyperLogLog data structure and store them in the key specified by the first parameter key. Returns 1 if the cardinality estimate (number of elements evaluated) has changed, otherwise returns 0, i.e. to confirm whether the cardinality estimate has changed after executing the command. If the specified key does not exist, an empty HyperLogLog data structure is created (i.e., a Redis String with the specified string length and encoding). It is also possible to call the command without specifying an element parameter and only specifying the key. If the key exists, do nothing and return 0; if the key does not exist, a new HyperLogLog data node is created and 1 is returned. Essentially it just generates a new HyperLogLog data structure without storing any elements.

(1) Syntax format:

PFADD key element [element ...]

(2) Return value:

Integer type, if at least one element is added, 1 is returned, otherwise 0 is returned.

(3) Example:

127.0.0.1:6379> PFADD hll a b c d e f g
(integer) 1
127.0.0.1:6379> pfcount hll
(integer) 7

3.2 PFCOUNT

Earliest available version: 2.8.9. Time complexity: O(1). For multiple relatively large keys, the time complexity is O(N).

Use the PFCOUNT command to get a HyperLogLog estimated cardinality value (that is, the number of elements). This command returns 0 if the key does not exist, otherwise it returns an estimate of the key's cardinality. For multiple keys, returned is a cardinality estimate for the union of multiple HyperLogLogs, calculated by merging multiple HyperLogLogs into a temporary HyperLogLog. Using a minimal and consistent amount of memory, HyperLogLog can count the number of unique elements of a collection. Each HyperLogLog uses only 12K plus a few bytes of the key itself.

(1) Syntax format:

PFCOUNT key [key ...]

(2) Return value:

Integer, returns the cardinality estimate of the specified HyperLogLog. If there are multiple HyperLogLogs, the union is returned. Cardinality estimate.

(3) Example:

127.0.0.1:6379> PFADD hll foo bar zap
(integer) 1
127.0.0.1:6379> PFADD hll zap zap zap
(integer) 0
127.0.0.1:6379> PFADD hll foo bar
(integer) 0
127.0.0.1:6379> PFCOUNT hll
(integer) 3
127.0.0.1:6379> PFADD some-other-hll 1 2 3
(integer) 1
127.0.0.1:6379> PFCOUNT some-other-hll
(integer) 3
127.0.0.1:6379> PFCOUNT hll some-other-hll
(integer) 6

(4) Limitation:

The results returned by HyperLogLog are not accurate, and the error rate is about 0.81%.

Using this command will change HyperLogLog and use 8 bytes to store the last calculated base. So, technically speaking, PFCOUNT is a write command.

(5) Performance issues

Even though it theoretically takes a long time to process an intensive HyperLogLog, the PFCOUNT command still has high performance when only one key is specified. This is because PFCOUNT caches the base of the last calculation, and this base does not change all the time, because the PFADD command does not update the register in most cases. Therefore, the effect of hundreds of requests per second can be achieved.

When using the PFCOUNT command to process multiple keys, HyperLogLog will be merged. This step is very time-consuming. More importantly, the calculated cardinality of the union cannot be cached. When using multiple keys, the execution of PFCOUNT can take some time (usually on the order of milliseconds), so overuse is not recommended.

It should be noted that the single-key and multi-key execution semantics of this command are different and have different performance. Excessive use of multi-key execution semantics is not recommended.

3.3 PFMERGE

Earliest available version: 2.8.9. Time complexity: O(N), N is the number of HyperLogLogs to be merged.

Multiple HyperLogLogs can be merged into one HyperLogLog through the PFMERGE command. The cardinality estimate of the merged HyperLogLog is calculated by taking the union of all given HyperLogLogs. The calculated result is saved to the specified key.

Syntax format:

PFMERGE destkey sourcekey [sourcekey ...]

Return value:

Return OK.

Example:

127.0.0.1:6379> PFADD hll1 foo bar zap a
(integer) 1
127.0.0.1:6379> PFADD hll2 a b c foo
(integer) 1
127.0.0.1:6379> PFMERGE hll3 hll1 hll2
OK
127.0.0.1:6379> PFCOUNT hll3
(integer) 6

The above is the detailed content of How to implement Redis using HyperLogLog. For more information, please follow other related articles on the PHP Chinese website!