Redis面试八股文-HyperLogLog类型和实战应用（超大数据量基数统计）

HyperLogLog 是什么？

HyperLogLog 是一种基数估算算法, 并非redis独有。
目的是做基数统计，故不是集合，不会保存元数据，只记录数量而不是数值。
消耗空间极小，支持输入非常大体积的数据量。

具体应用场景

说人话，HyperLogLog能用来干啥？

假设我们手机APP需要统计登录页、注册输入账号密码页、填写基本资料页、填写附加资料页、广告推荐页这五个页面的PV和UV。
PV好办，在Redis中直接放5个key，咱们访问哪个页面一次加一次即可；可是UV不行呐，需要区分不同的用户的访问，同一个用户访问1000次都是加1，需要去重。
假设此时我们的用户量非常大，比如说我们先来它一个小目标的，此时以Redis的Hash数据结构为例，我们将0-100000000的数值作为key，value为空，写入Redis，需要占用7.46GB的内存。
是不是非常的不经济？5个统计就需要37.3GB的内存空间，成本炸裂。

如果此时产品经理告诉你不需要绝对精确，允许一定的误差，那么我们就可以使用HyperLogLog这个数据结构来实现UV统计了。

定义5个key分别存储5个页面的访问估算数据

1
2
3
4
5
6
7

pageKeys := []string{
"RegisterAndLoginPageUVKey",
"RegisterPageUVKey",
"BasicProfilePageUVKey",
"AdditionalProfilePageUVKey",
"RecommendPageUVKey",
}

每个key造一亿个不同的访客ID

使用二维数组每两千个ID一组，通过pfadd写入对应key

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

visitorIDArray := [5][]string{}

for i := 0; i < 500000000; i++ {
indexLevel1 := i % 5
visitorIDArray[indexLevel1] = append(visitorIDArray[indexLevel1], strconv.Itoa(i))
if i%10000 == 0 && i != 0 {
for temp, visitors := range visitorIDArray {
_, err := redisClient.PFAdd(context.Background(), pageKeys[temp], visitors).Result()
if err != nil {
log.Fatalln(err.Error())
}
}
visitorIDArray = [5][]string{}
fmt.Println("offset:", i)
}
}

if len(visitorIDArray[1]) > 0 {
for temp, visitors := range visitorIDArray {
_, err := redisClient.PFAdd(context.Background(), pageKeys[temp], visitors).Result()
if err != nil {
log.Fatalln(err.Error())
}
}
visitorIDArray = [5][]string{}
}

读取数据

通过pfcount计算每个key的估算基数值

1
2
3
4
5
6
7
8

for _, key := range pageKeys {
count, err := redisClient.PFCount(context.Background(), key).Result()
if err != nil {
log.Fatalln(err.Error())
}

fmt.Println(key, ":", count)
}

运行结果：

1
2
3
4
5

RegisterAndLoginPageUVKey : 100528967
RegisterPageUVKey : 100506461
BasicProfilePageUVKey : 100966386
AdditionalProfilePageUVKey : 100068496
RecommendPageUVKey : 100136669

从结果可以看到，每个key的估算值都不是非常准确的100000000，但是误差基本都在1%左右，偶尔高于标准误差0.81%。
但是相比于35GB的内存占用，使用HyperLogLog仅用了60KB内存，而且误差也在可接受范围内，还要啥自行车？

计算多个key的总数

填写基本资料页、填写附加资料页两个key做合并计算：

1
2
3
4
5
6
7
8
9
10
11
12
13

result, err := redisClient.PFMerge(context.Background(), "ProfilePageKey", pageKeys[2], pageKeys[3]).Result()
if err != nil {
log.Fatalln(err.Error())
}

fmt.Println(result)

count, err := redisClient.PFCount(context.Background(), "ProfilePageKey").Result()
if err != nil {
log.Fatalln(err.Error())
}

fmt.Println(count)

运行结果：