当前位置：网站首页>What is redis hyperloglog? The use of these scenes makes me laugh like a dragon

What is redis hyperloglog? The use of these scenes makes me laugh like a dragon

2022-06-21 20:52:00 【InfoQ】

In the business scenario of mobile Internet ,

Large amount of data

, We need to keep this information ： One key Associated with a data set , At the same time, make statistics on this data set .

such as ：

Count one
APP
Daily life of 、 Monthly living number ;

Count how many different accounts visit a page every day （Unique Visitor,UV））;

Count the number of different terms searched by users every day ;

Statistical registration IP Count .

Usually , The number of users and the number of visits we face are huge , such as

One million 、 Tens of millions of users , Or tens of millions of levels 、 Even billion level

Access information for .

today 「 Margo 」 Different data types are used respectively ： The function of counting how many different accounts visit a page every day , Gradually lead out

HyperLogLog

Principle and Java The integration of

Redission

actual combat .

Let's tell you a trick ,Redis The official website can now run online Redis Instructions ：https://redis.io/. Pictured ：

Use Set Realization

A user can only visit a website once a day

, So it's easy to think of passing

Redis Of Set aggregate

To achieve .

For example, wechat ID by 「 Xiao Cai chicken 」 visit 「

Redis Why so soon?

」 In this article , We save this information in Set in .

SADD Redis Why so soon? :uv  Xiao Cai chicken   Xie bage   Xiao Cai chicken 
(integer) 1

「 Xiao Cai chicken 」 Multiple access 「

Redis Why so soon?

」 page ,Set The de duplication function of ensures that the same... Will not be recorded repeatedly 「 WeChat ID」.

adopt

SCARD

command , Statistics 「Redis Why so soon? 」 page UV. Instruction returns the number of elements in a set （ That is, users ID）.

SCARD Redis Why so soon? :uv
(integer) 2

Use Hash Realization

Old and wet , It can also be used Hash Type implementation , Will the user ID As Hash A collection of key, Access to the page is executed HSET The order will value Set to 1.

Even if 「 Xiao Cai chicken 」 Repeat the page , Repeat command , I can only put key be equal to 「 Xiao Cai chicken 」 Of

value

Set to 1.

Last , utilize

HLEN

Command Statistics Hash The number of elements in a set is UV.

as follows ：

HSET Redis Why so soon?   Xiao Cai chicken  1
//  Statistics  UV
HLEN Redis Why so soon?

Use Bitmap Realization

Bitmap The underlying data structure of is String Type of SDS Data structure to hold bit groups ,Redis Put each byte in the array of 8 individual bit Use it , Every bit position Represents the binary state of an element （ No 0 Namely 1）.

Bitmap Provides

GETBIT、SETBIT

operation , By an offset value offset Yes bit Array of offset Positional bit Bit for read and write operations , It should be noted that offset from 0 Start .

Can be Bitmap Think of it as a bit An array of units , Each unit of an array can only store 0 perhaps 1, The subscript of the array is in Bitmap called offset Offset .

For the sake of visualizing , We can understand that buf Each byte of the array is represented by a line , Every line has 8 individual bit position ,8 The two lattices represent each of the 8 individual bit position , As shown in the figure below ：

8 individual bit Form a Byte, therefore Bitmap It saves a lot of storage space .

This is it. Bitmap The advantages of .

How to use Bitmap To count the number of independent user visits to the page ？

Bitmap Provides

SETBIT and BITCOUNT

operation , The former passes through an offset value offset Yes bit Array of offset Positional bit Bit to write , It should be noted that offset from 0 Start .

The latter counts the given bit Array , value = 1 Of bit Number of bits .

Something to pay attention to , We need to take 「 WeChat ID」 Convert to numbers , because

offset

It's a subscript .

Suppose we were to 「 Xiao Cai chicken 」 Convert to code

6

First step , The following instruction means to execute 「 Xiao Cai chicken 」 The code of is 6 and visit 「

Skillfully use Redis The data type realizes 100 million level data statistics

」 This article .

SETBIT  Skillfully use Redis The data type realizes 100 million level data statistics  6 1

The second step , Count page visits , Use

BITCOUNT

Instructions . This instruction is used to count a given bit Array , value = 1 Of bit Number of bits .

BITCOUNT  Skillfully use Redis The data type realizes 100 million level data statistics

HyperLogLog The king plan

Set Is good , If the article is very popular, reach ten million level , One Set Saved the data of tens of millions of users ID, Too many pages and too much memory .
Empathy ,Hash The same is true for data types .
as for Bitmap, It is more suitable for 「
Binary state statistics
」 Usage scenarios of , High precision statistics , Although the memory consumption is higher than
HashMap
Less , However, for a large amount of data, it will still occupy a large amount of memory .
Do how? ？

These are typical 「 Base Statistics 」 Application scenarios , Base Statistics ： Count the number of non repeating elements in a set .

HyperLogLog

The advantage is

The memory it requires does not change with the size of the collection , No matter how many elements the collection contains ,HyperLogLog The memory required to perform calculations is always fixed , And very few

Every

HyperLogLog

At most, it's only a cost 12KB Memory , In standard error

0.81%

Under the premise of , You can calculate 2 Of 64 The cardinality of two elements .

Redis actual combat

HyperLogLog It's too easy to use .

PFADD、PFCOUNT、PFMERGE

Three instructions beat the world .

PFADD

Each user who will visit the page ID Add to

HyperLogLog

in .

PFADD Redis Master slave synchronization principle :uv userID1 userID 2 useID3

PFCOUNT

utilize

PFCOUNT

obtain 「

Redis Master slave synchronization principle

」 The article UV value .

PFCOUNT Redis Master slave synchronization principle :uv

PFMERGE Use scenarios

HyperLogLog`  Except for the top  `PFADD`  and  `PFCOIUNT`  Outside , It also provides  `PFMERGE

grammar

PFMERGE destkey sourcekey [sourcekey ...]

For example, in the website, we have two pages with similar content , The operation said that the data of these two pages should be combined .

One of the pages of UV Traffic also needs to be combined , So at this point

PFMERGE

I can use it , That is to say

The same user visits these two pages only once

As shown below ：Redis、MySQL Two

HyperLogLog

The collection holds two pages of user access data .

PFADD Redis data  user1 user2 user3
PFADD MySQL data  user1 user2 user4
PFMERGE  database  Redis data  MySQL data 
PFCOUNT  database  //  Return value  = 4

Will be multiple HyperLogLog Merge （merge） For one HyperLogLog , After the merger HyperLogLog The cardinality of is close to all inputs HyperLogLog The visible set of （observed set） Union .

user1、user2 All visited Redis and MySQL, It's only one visit .

Redission actual combat

Detailed source code 「 Margo 」 Upload to GitHub 了：https://github.com/MageByte-Zero/springboot-parent-pom.git

pom rely on

<dependency>
 <groupId>org.redisson</groupId>
 <artifactId>redisson-spring-boot-starter</artifactId>
 <version>3.16.7</version>
</dependency>

Add data to Log

//  Add a single element 
public <T> void add(String logName, T item) {
 RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
 hyperLogLog.add(item);
}

//  Add collection data to  HyperLogLog
public <T> void addAll(String logName, List<T> items) {
 RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
 hyperLogLog.addAll(items);
}

Merge

/**
 *  take  otherLogNames  Of  log  Merge into  logName
 *
 * @param logName  At present  log
 * @param otherLogNames  Need to merge to current  log  Other  logs
 * @param <T>
 */
public <T> void merge(String logName, String... otherLogNames) {
 RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
 hyperLogLog.mergeWith(otherLogNames);
}

Statistical base

public <T> long count(String logName) {
 RHyperLogLog<T> hyperLogLog = redissonClient.getHyperLogLog(logName);
 return hyperLogLog.count();
}

unit testing

@Slf4j
@RunWith(SpringRunner.class)
@SpringBootTest(classes = RedissionApplication.class)
public class HyperLogLogTest {

 @Autowired
 private HyperLogLogService hyperLogLogService;

 @Test
 public void testAdd() {
 String logName = &quot; Code byte :Redis Why so soon? :uv&quot;;
 String item = &quot; Xiao Cai chicken &quot;;
 hyperLogLogService.add(logName, item);
 log.info(&quot; Additive elements [{}] To  log [{}]  in .&quot;, item, logName);
 }

 @Test
 public void testCount() {
 String logName = &quot; Code byte :Redis Why so soon? :uv&quot;;
 long count = hyperLogLogService.count(logName);
 log.info(&quot;logName = {} count = {}.&quot;, logName, count);
 }

 @Test
 public void testMerge() {
 ArrayList<String> items = new ArrayList<>();
 items.add(&quot; Xiao Cai chicken &quot;);
 items.add(&quot; Xie bage &quot;);
 items.add(&quot; Chen Xiaobai &quot;);

 String otherLogName = &quot; Code byte :Redis Principle and practice of multithreading model :uv&quot;;
 hyperLogLogService.addAll(otherLogName, items);
 log.info(&quot; add to  {}  Elements to  log [{}]  in .&quot;, items.size(), otherLogName);

 String logName = &quot; Code byte :Redis Why so soon? :uv&quot;;
 hyperLogLogService.merge(logName, otherLogName);
 log.info(&quot; take  {}  Merge into  {}.&quot;, otherLogName, logName);

 long count = hyperLogLogService.count(logName);
 log.info(&quot; After the merger  count = {}.&quot;, count);
 }
}

The basic principle

HyperLogLog It's a probabilistic data structure , It uses a probabilistic algorithm to calculate the approximate cardinality of a set . The origin of its algorithm is Bernoulli process .

Bernoulli process is a coin toss experiment . Toss a normal coin , The landing may be positive , It could be the opposite , The probability of both is

1/2

Bernoulli's process is always tossing coins , Until you land in a frontal position , And record the number of throws

k

for instance , Flip a coin and you'll see the front , here

k

1

; The first toss of a coin is the reverse side , Keep throwing , It wasn't until the third time that the positive , here

k

by 3.

about

n

Sub-bernoulli process , We will get n The number of times a face is thrown

k1, k2 ... kn

, The maximum value here is

k_max

According to a mathematical deduction , We can come to a conclusion ：

2^{k_ max} As a n The estimate of .

That is to say, you can approximately calculate the number of Bernoulli processes you have made based on the maximum number of throws .

therefore HyperLogLog The basic idea is to use the first bit string of numbers in the set 1 The maximum value of the position appears to estimate the overall cardinality , But there is a big error in this method , In order to improve the error situation ,HyperLogLog The concept of bucket average is introduced in this paper , Calculation m The harmonic mean of barrels .

Redis in HyperLogLog It's divided up 2^14 A barrel , That is to say 16384 A barrel . There's one in each bucket 6 bit Array of , As shown in the figure below .

About HyperLogLog It's too complicated , If you want to know, please move ：

https://www.zhihu.com/question/53416615

https://en.wikipedia.org/wiki/HyperLogLog

How to count users' daily and monthly activities - Redis HyperLogLog Detailed explanation

Redis Yes

HyperLogLog

Optimized storage for , When the count is small , Coefficient matrix is used for storage space , It takes up very little space .

Only when the count is large , A sparse matrix can be transformed into a dense matrix only when the space occupied by it exceeds the threshold , Occupy 12KB Space .

Why just 12 KB ah ？

HyperLogLog

What is used in the implementation is

16384

A barrel , That is to say

2^14

, Per barrel

maxbits

need 6 individual

bits

To store , The maximum can mean

maxbits=63

, So the total memory used is

2^14 * 6 / 8 = 12k

byte .

summary

Used separately

Hash

、

Bitmap

、

HyperLogLog

To achieve ：

Hash
： Method is simple , High precision statistics , Use with a small amount of data , For massive data, it will occupy a lot of memory ;

Bitmap
： Bitmap algorithm , Suitable for use 「 Binary statistics scenario 」, Please refer to me for details
This article
, For a large number of different pages, data statistics will still occupy a large amount of memory .

Set
： Use the de duplication feature to realize , One Set Saved the data of tens of millions of users ID, Too many pages and too much memory . stay Redis Inside , Every
HyperLogLog
Keys only cost 12 KB Memory , So we can calculate the proximity
2^64
Cardinality of different elements . because
HyperLogLog
Only the input elements will be used to calculate the cardinality , Instead of storing the input elements themselves , therefore
HyperLogLog
It can't be like a collection , Return the various elements of the input .

HyperLogLog
It's an algorithm , Is not
Redis
alone possess

The purpose is to make cardinality Statistics , Therefore, it is not a set , Metadata will not be saved , Only record the quantity, not the value

Minimal space consumption , Support the input of very large data volume

The core is the cardinality estimation algorithm , It is mainly manifested in the use of memory during calculation and the processing of data merging . There is a certain error in the final value

Redis
Each of them
Hyperloglog
key Occupied 12K Memory used to mark cardinality （ Official documents ）

pfadd
Commands are not assigned at once 12k Memory , But gradually increase the memory allocation as the cardinality increases ; and pfmerge Operation will sourcekey After merging, it is stored in 12k The size of key in , from
hyperloglog
Principle of merge operation （ Two
Hyperloglog
When merging, you need to compare the values of each bucket separately ） It's easy to understand .

Error description ： The result of cardinality estimation is a function with
0.81%
The standard error （standard error） Approximate value . Is an acceptable range

Redis
Yes
HyperLogLog
Optimize your storage , When the count is small , The storage space adopts sparse matrix storage , It takes up very little space , Just as the count grows , When the space occupied by sparse matrix gradually exceeds the threshold, it will be transformed into dense matrix at one time , Will occupy 12k Space