Redis special data type hyperloglog

brief introduction

Redis stay 2.8.9 Version added HyperLogLog structure .

Redis HyperLogLog It's an algorithm for cardinality statistics ,HyperLogLog The advantages of , Enter the number or volume of elements Very, very large , The space needed to calculate the cardinality is always fixed Of 、 And it's very small .

stay Redis Inside , Every HyperLogLog Keys only cost 12 KB Memory , So we can calculate the proximity 2^64 A base of different elements Count . This is the same as calculating the cardinality , The more elements consume memory, the more collections there are .

HyperLogLog Is an algorithm , It provides an imprecise de duplication scheme .

Take a chestnut ： If I want to count the number of web pages UV（ Number of browsing users , Multiple visits by the same user in a day can only be counted as one ）, The traditional solution is to use Set To save the user id, Then count Set To get the number of elements in the page UV. But this scheme can only carry a small amount of

user , Once the number of users increases, it needs to consume a lot of space to store users id. My goal is to count users, not save users , This is a thankless scheme ！ While using Redis Of HyperLogLog At most 12k You can count a large number of users Count , Although it probably has 0.81% Error rate , But for Statistics UV This does not require very accurate data is negligible .

What is the cardinality ?

Like data sets {1, 3, 5, 7, 5, 7, 8}, So the cardinality set of this dataset is {1, 3, 5 ,7, 8}, base ( Don't repeat elements ) by 5.

Cardinality estimation is within the range of acceptable error , Fast base calculation .

Basic commands ：

  test ：

127.0.0.1:6379> pfadd mykey a b c d e f g h i j
(integer) 1
127.0.0.1:6379> pfcount mykey
(integer) 10
127.0.0.1:6379> pfadd mykey2 i j z x c v b n m
(integer) 1
127.0.0.1:6379> pfmerge mykey3 mykey mykey2
OK
127.0.0.1:6379> pfcount mykey3
(integer) 15