A brief analysis of HyperLogLog for Redis data type learning

This article will take you to understand the HyperLogLog in the Redis data type, which is usually used to count the number of unique elements in a collection. I hope it will be helpful to you!

Today is Friday, you are happily fishing, and the product manager sends you a requirements document via email. The demand is probably: the company needs to count the website's daily visitor IPs, and this statistics is a long-term behavior, ranging from a few months to a few years.

After reading the requirements, you will feel that this is so easy. You can easily implement this function using the collection type of Redis: generate a collection type key every day, use SADD to store the daily visitor IP, and use the SCARD command to easily Get the number of visitor IPs per day.

You quickly finished typing the code and passed the test, and the function was online. After going online and running for a period of time, you will find that the server where Redis is located starts to alarm. The reason is that the memory usage of some keys is too large. You took a look and found that these keys are all set keys that store visitor IPs. Only then did you pat your head, knowing that you had dug a big hole for yourself.

Assume that storing an IP address in IPv4 format requires up to 15 bytes and that the website has up to 1 million visitors per day. These set keys will use 0.45 GB of memory per month and 5.4 GB of memory per year. This is only an estimate of the IPv4 format. If the IPv6 format will occupy more memory. Although the time complexity of SADD and SCARD is O(1), their memory consumption is unacceptable.

You browsed the official website of Redis and found that Redis also provides a data type HyperLogLog, which can not only meet the needs of the product but also occupy less memory. [Related recommendations: Redis Video Tutorial]

HyperLogLog Algorithm

HyperLogLog is a probabilistic algorithm created specifically for calculating the cardinality of a set. The approximate cardinality of a given set can be calculated.

The approximate cardinality is not the actual cardinality of the set. It may be a little smaller or larger than the actual cardinality, but the error between the estimated cardinality and the actual cardinality will be within a reasonable range. For those who do not require Very accurate statistics can be achieved using the HyperLogLog algorithm.

The advantage of HyperLogLog is that the memory required for calculating the approximate cardinality does not change due to the size of the set. No matter how many elements the set contains, the memory required for HyperLogLog to calculate is always fixed, and are very few.

Each HyperLogLog type of Redis only needs to use 12KB of memory space to count nearly: 2⁶⁴ elements, and the standard error of the algorithm is only 0.81%.

If you use the HyperLogLog type to implement the above functions, if there are 1 million visitors per day, it will only occupy 360KB of memory in one month.

PFADD

The PFADD command can be used to count one or more given set elements.

PFADD key element [element...]

Depending on whether the given element has been counted, the PFADD command may return 0 or 1:

• If all the given elements have been counted, the PFADD command will return 0, indicating that the approximate cardinality calculated by HyperLogLog has not changed.
• The PFADD command will return 1 if the approximate cardinality calculated by HyperLogLog changes due to the presence of at least one element in a given element that has not been previously counted.

For example:

redis> PFADD letters a b c -- 第一次添加
(integer) 1
redis> PFADD letters a     -- 第二次添加
(integer) 0

It is also possible if you only specify the key without specifying the element when calling this command. If the key exists, no operation will be performed. If it does not exist, A data structure will be created (returns 1).

PFCOUNT

The PFCOUNT command can be used to obtain the approximate cardinality calculated by HyperLogLog for the collection. If the given key does not exist, 0 will be returned.

PFCOUNT key [key...]

For example:

redis> PFCOUNT letters
(integer) 3

When multiple HyperLogLogs are passed to PFCOUNT, the PFCOUNT command will first The union of all HyperLogLogs is then returned and the approximate cardinality is returned.

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFCOUNT letters1 letters2
(integer) 5

PFMERGE

The PFMERGE command can perform a union calculation on multiple HyperLogLogs, and then save the calculated union HyperLogLog to the specified key.

PFMERGE destKey sourceKey [sourceKey...]

If the specified key already exists, the PFMERGE command will overwrite the existing key.

redis> PFADD letters1 a b c
(integer) 1
redis> PFADD letters2 c d e
(integer) 1
redis> PFMERGE res letters1 letters2
OK
redis> PFCOUNT res
(integer) 5

You can see that the PFMERGE and PFCOUNT commands are very similar. In fact, the PFCOUNT command performs the following operations when calculating the approximate base of multiple HyperLogLogs:

• Internally called The PFMERGE command calculates the union of all given HyperLogLogs and stores the union into a temporary HyperLogLog.

• Execute the PFCOUNT command on the temporary HyperLogLog to get its approximate cardinality.

• Delete the temporary HyperLogLog.

• Return the resulting approximate base.

When the program needs to call the PFCOUNT command on multiple HyperLogLogs, and this call may be repeated multiple times, you can consider replacing this call with the corresponding PFMERGE command call: by combining the The calculation results are stored in the specified HyperLogLog instead of recalculating the union every time, and the program can minimize unnecessary union calculations.

Business Scenario

HyperLogLog’s features are very suitable for: counting (monthly, annual statistics), deduplication (spam SMS detection) and other scenarios.

For more programming-related knowledge, please visit: Introduction to Programming! !

The above is the detailed content of A brief analysis of HyperLogLog for Redis data type learning. For more information, please follow other related articles on the PHP Chinese website!